Помогите с расчетом координат.

← →
Ssergy (2002-11-07 18:32) [0]

Мастера, помогите пожалуйста.
Есть замкнутый контур, заданный точкам.
Необходимо получит контур, находящийся внутри данного, на расстоянии k от каждой из сторон. (т.е надо получить пропорционально уменьшеный контур внутри данного).
Хоть какие - либо идеи please.
Заранее спасибо.

← →
Ketmar (2002-11-07 19:31) [1]

элементарно, Ватсон. %-) уменьшить размер исходного контура на необходимую величину.

Satanas Nobiscum! 07-Nov-XXXVII A.S.

← →
Ssergy (2002-11-07 20:23) [2]

Если уменьшать координаты контура на необходимую величину, новый контур не будет находиться внутри заданного, он смститься, а необходимо, что-бы он находился внутри.

← →
ZrenBy (2002-11-07 20:30) [3]

Выбираешь систему координат.
Берешь точку (x1,y1)
находишь два вектора из нее к соседним точкам
определяешь вектор-биссектрису к расчетной точке
находишь длину этого вектора, так чтобы расчетная точка
была на заданном удалении
Определяешь координаты расчетной точки.

Фу. кажется так, только формулы надо вывести.

← →
LestatRE (2002-11-07 21:24) [4]

Example
__________
/\ /\
/ \ / \
/ \ / \
/ \ / \
/________\/________\
\ /\ /
\ / \ /
\ / \ /
\ / \ /
\/________\/

Пересечение прямых внутри фигуры вызывает центральную точку.
Если отмерить точки на этих прямых, равноудаленные внутрь
от границ многоугольника и соединить их между собой прямыми, то получится необходимый результат : фигура, меньшая исходной на значение величины k. Однако действует этот способ не везде. В остальном, я думаю, можно разобраться .

← →
Ssergy (2002-11-07 23:25) [5]

ZrenBy пожалуйста, если можно поподробнее.
По моему в точке x1,y1 метод работать не будет, т.к вектор- бисектриса буде напралена вне контура.
/------
/ |
\ |
\ |
\ |
(x1,y1). |
/ |
/ |
/_______|
\-------/

← →
Alex44 (2002-11-08 01:59) [6]

Esli contur ne vypuklyj, ne ochen" ponyatno, chto est" "vnutri".

1 2
__________
\ /
\ /
\ /
\ /
\/
/\
/__\
3 4

Esli eto resheno (skazhem, contur orientirovan), to ostal"noe elementarno: kazhdaya pryamaya sdvigaetsya po perpendiculyaru na nuzhnoe rasstoyanie (sm. freshman calculus), a potom vershiny nahodyatsya, kak tochki peresecheniya sosednih reber (linejnaya algebra).

← →
Ketmar (2002-11-08 09:45) [7]

господа, вы что, с дубов попадали? я же уже ответил!
>Если уменьшать координаты контура на необходимую величину, новый контур не будет находиться внутри заданного, он сместится, а необходимо, что-бы он находился внутри.
вы чего, совсем думать не желаете? а принять за начало координат центр вашего первичного контура моральные принципы не позволяют? начало координат есмь штука неприкосновенная, да?
единственно, мой ответ подразумевал, что "контур" - это "полигон". причем неважно, какой: convex или concave. чем отличается полигон от фигуры Alex"а44, надеюсь, все знают.

Satanas Nobiscum! 08-Nov-XXXVII A.S.

← →
Ssergy (2002-11-08 09:58) [8]

А как найти центр совершенно произвольного контура???

← →
Ketmar (2002-11-08 11:23) [9]

извиняюсь. с дуба упал я. мой метод работает только для convex polygons. %-( недодумал.
вношу поправку: если полигон есть concave, то нужно его побить на кучу convex"ов, потом для каждого применить мой алгоритм (немного усложненный), потом все нарисовать (естественно, не рисуя ребра-"разбиватели").
под "центром" я, естественно, имел в виду центр масс.
более подробно описывать лень...

Satanas Nobiscum! 08-Nov-XXXVII A.S.

← →
AlexT1000 (2002-11-08 11:56) [10]

берешь выкачиваешь G32 http://g32.org там среди работы с полигонами есть функция Grow . и будет тебе счастье.

← →
Alex44 (2002-11-08 19:59) [11]

> Ketmar
Chestno govorya, mne, kak mathematicu, ochen" lyubopytno, chto takoe polygon (esli on not convex). Prosto, ya schitayu sebya professionalom (v mathematice, ne v programmirovanii), i nedavno ya prisutstvoval na zasedanii redcollegii nekogo Francusskogo analiga nashego Quant"a, gde neskol"ko nehilyh (poverte) mathematicov pytalis" opredelit", chto takoe polygon...

← →
Ketmar (2002-11-08 20:41) [12]

2Alex44:
в данном случае ПОЛИГОН - это скорее программерский термин, нежели математический. %-) полигон - это контур, в котором ребра не имеют пересечений.

Satanas Nobiscum! 08-Nov-XXXVII A.S.

← →
Alex45 (2002-11-10 14:21) [13]

Sserg, метод с биссектрисой - весьма дельно предложен. Ведь бывает же и биссектриса тупого угла, не так ли :).

Alex44, не надо умничать, пожалуйста, Вы не единственный математик здесь. Естественно, имелся в виду контур без самопересечений (выпуклость, кстати, это нечто другое), и метод, предложенный уважаемым ZrenBy эффективнее (не надо находить прямые, а затем их точки пересечения. Сразу - вершины нового контура!).
PS Я бы, на Вашем месте, не спешил называть себя профессионалом в математике. Кстати, Вы что заканчивали?

← →
Song (2002-11-10 18:47) [14]

А может просто InflateRect()?

← →
Alex44 (2002-11-10 19:45) [15]

To Alex45

Ya smotryu, tut uzhe pereshli na lichnosti. Kstati, ya zakanchival LGU i aspiranturu v LOMI.

> Есть замкнутый контур, заданный точкам.

Tem samym, lyuboj algorithm dolzhen by snachala opredelit" (po tochkam), chto contour ne imeet samoperesechenij, a potom ego orientirovat", chtoby otlichit" vnuttrennost" ot vneshnosti. (Zadazha reshabel"naya, no tozhe ne s naletu.)

V smysle skorosti, ya ne uveren, chto vychislenie dlin bissectriss na osnove predvaritel"no vychislennyh uglov bystree, chem reshenie linejnyh system.

← →
Alex45 (2002-11-11 07:27) [16]

Alex44, найти направляющий вектор биссектрисы по двум направляющим углов - элементарно (это школа!). А уж затем привести его длину к необходимой - это, простите, вовсе теорема Пифагора.
Теперь сравним.
Ваш метод (В):
1. Найти перпендикуляр. Далее параллельный перенос ребра контура по этому вектору.

Метод ZrenBy (Z):
1. Найти вектор биссектрисы, затем привести его к нужной длине.

(В):
2. Решить N систем лин. ур-ий, где N - кол-во рёбер, тем самым получив точки нового контура.

(Z, В):
3. Соединить получивиеся точки. Ч. и т.д.

И никаких систем...

Что по вашему проще?
К тому же, я думаю, не надо говорить о том, что векторный метод предпочтительнее, нежели координатный. У нас при поступлении за задачу решённую координатным методом снимали баллы, за слабую способность к производству мысли...

С уважением, Колобов.

← →
Fenik (2002-12-01 10:57) [17]

Попробовал написать процедуру по методу Alex44. Получилось отчасти. Проц-а работает только для приведённого случая. Для многих других случаев работает неверно. Может кто-нибудь попробует доделать (я тоже попытаюсь - задача интересная и полезная).

unit Unit1; interface uses Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Math; type TForm1 = class(TForm) procedure FormPaint(Sender: TObject); end; var Form1: TForm1; implementation {$R *.DFM} {function Len(L: TLine): Integer; begin Result := Round(Sqrt(Sqr(L.P2.x - L.P1.x) + Sqr(L.P2.y - L.P1.y))); end; } type TPoints = array of TPoint; TLine = record P1, P2: TPoint; end; function Inside(const P: TPoints; Size: Integer): TPoints; function GetCrossLine(const A, B: TLine; var Cross: TPoint): Boolean; const Epsilon = 1e-8; // выставлять в зависимости от точности Double var dx1, dy1, dx2, dy2, D: Integer; P2: Double; begin Result := False; dx1 := A.P2.X - A.P1.X; dy1 := A.P2.Y - A.P1.Y; dx2 := B.P2.X - B.P1.X; dy2 := B.P2.Y - B.P1.Y; D := dy1*dx2 - dy2*dx1; if Abs(D) < Epsilon then Exit; P2 := (dy1*(A.P1.X - B.P1.X) - dx1*(A.P1.Y - B.P1.Y))/D; Cross.X := Round(B.P1.X + dx2*P2); Cross.Y := Round(B.P1.Y + dy2*P2); Result := True; end; function GetParallelLine(const Line: TLine; i: Integer): TLine; var ASin, ACos: Extended; begin SinCos(ArcTan2(Line.P2.X - Line.P1.X, Line.P2.Y - Line.P1.Y)+Pi/2*i, ASin, ACos); with Result do begin P1.X := Round(Line.P1.X + Size*ACos); P1.Y := Round(Line.P1.Y + Size*ASin); P2.X := Round(Line.P2.X + Size*ACos); P2.Y := Round(Line.P2.Y + Size*ASin); end; end; var i, l: Integer; L1, L2, L3: TLine; begin l := High(P); if l < 2 then Exit; SetLength(Result, L + 1); L1.P1 := P[0]; L1.P2 := P[l]; L1 := GetParallelLine(L1, 1); L3 := L1; for i := 0 to l-1 do begin L2.P1 := P[i]; L2.P2 := P[i + 1]; L2 := GetParallelLine(L2, 1); GetCrossLine(L2, L3, Result[i]); L3 := L2; end; GetCrossLine(L1, L3, Result[l]); end; procedure TForm1.FormPaint(Sender: TObject); var P: TPoints; begin SetLength(P, 3); P[0] := Point(200, 100); P[1] := Point(300, 300); P[2] := Point(100, 200); with Canvas do begin Brush.Style := bsClear; Pen.Color := clRed; Pen.Width := 2; Polygon(P); Pen.Color := clBlue; Polygon(Inside(P, 30)); end; end; end.

← →
Alex45 (2002-12-03 06:50) [18]

А конкретнее? Для каких не работает?

← →
Alex45 (2002-12-03 08:10) [19]

А если вот так?

← →
Alex45 (2002-12-03 08:18) [20]

for i:=2 to Counter do
begin
Vect1[1]:=Points[i+1,1]-Points[i,1]; //x-coordinate
Vect1[2]:=Points[i+1,2]-Points[i,2]; //y-coordinate
length1:=sqrt(sqr(Vect1[1])+sqr(Vect1[2])); //length of Vect1

Vect2[1]:=Points[i-1,1]-Points[i,1]; //x-coordinate
Vect2[2]:=Points[i-1,2]-Points[i,2]; //y-coordinate
length2:=sqrt(sqr(Vect2[1])+sqr(Vect2[2])); // length of Vect2

Vect1[1]:=Vect1[1]/length1;//Norm Vect1
Vect1[2]:=Vect1[2]/length1;
Vect2[1]:=Vect2[1]/length2;//Norm Vect2
Vect2[2]:=Vect2[2]/length2;

ResultVect[1]:=Vect1[1]+Vect2[1]; // Compute bisector
ResultVect[2]:=Vect1[2]+Vect2[2];
ResultVectLength:=sqrt(sqr(ResultVect[1])+sqr(ResultVect[2]));

if (Vect1[1]*Vect2[2]-Vect1[2]*Vect2[1])<0 then IsObtuse:=true else IsObtuse:=false;
if IsObtuse then //if angle is obtuse then change result vector orientation
begin
ResultVect[1]:=-ResultVect[1];
ResultVect[2]:=-ResultVect[2];
end;

k:=StrToFloat(Edit1.Text); //
OutlinePoints[i,1]:=Points[i,1]+round(ResultVect[1]*k/ResultVectLength);
OutlinePoints[i,2]:=Points[i,2]+round(ResultVect[2]*k/ResultVectLength);

end;

k - длина, на которую нужно сместить результирующий контур

Points - массив с координатами точек исходного контура. Предполагается, что точки задаются по часовой стрелке.

OutlinePoints - массив с координатами нового контура.

Counter=N+1, где N - число точек начального контура, т.е. N+1-ая точка является одновременно и 1-ой. Это сделано для того, чтобы все координаты просчитывать в цикле.

← →
Fenik (2002-12-07 20:37) [21]

2 Alex45
>>А конкретнее? Для каких не работает?
Попробуй в моём примере задать побольше точек и поменять координаты...

Твой код не правильно работает. И вообще что за странное задание точек через массив [1..2]. Попробуй сам его проверить.
...Тут не только математика. Тут нужен энтузиазм программиста.

← →
Alex45 (2002-12-09 06:41) [22]

2 Fenik.

Конкретно, пожалуйста, в каком случае работает неверно метод предложенный ZrenBy?

Массив точек задан в связи с тем, что TPoint(или его аналог) существует далеко не во всех ЯП :) Следовательно, человеку, не имеющему понятие об этом, сложно будет реализовать алгоритм.
А в общем, ты совершенно прав.

В том, что в здесь нужен энтузиазм - согласен. Но задача ЧИСТО математическая...

Жду здоровой критики.

← →
Fenik (2002-12-13 21:09) [23]

Задача:
Необходимо получит контур, находящийся внутри данного, на расстоянии k от каждой из сторон. (т.е надо получить пропорционально уменьшеный контур внутри данного).

Метод ZrenBy:
Выбираешь систему координат.
Берешь точку (x1,y1)
находишь два вектора из нее к соседним точкам
определяешь вектор-биссектрису к расчетной точке
находишь длину этого вектора, так чтобы расчетная точка
была на заданном удалении
Определяешь координаты расчетной точки.

Конечно, метод ZrenBy хорош (рациональнее метода Alex44), единичный вектор-биссектрису можно найти из суммы единичных вектров (между которыми биссектриса). Но из каждого угла по биссектрисе нельзя откладывать одно и то же расстояние, т.к. все углы могут быть разные и стороны нового многоугольника (если брать одно расстояние) окажутся не параллельными сторонам исходного. Первая проблема: какое откладывать расстояние по биссектрисе? Вторая проблема: в какую сторону откладывать? Если многоугольник выпуклый, то понятно где внутренняя часть, а если нет, то некоторые внутренние углы будут тупыми и получится так, что вектор-биссектриса будет направлен наружу. И, в конце концов, нужно определить имеет ли многоугольник самопересечения: если да, то или выйти из процедуры, или преобразовать массив точек в многоугольник без самопересечений.!?.

← →
Alex45 (2002-12-15 07:41) [24]

Внутренность определяется по знаку векторного произведения. В моём коде стоит эта проверка. Условимся, что точки задаются ПО ЧАСОВОЙ стрелке и ВНУТРЕННЕЙ частью считаем то, что остаётся справа от контура при данном направлении обхода.
Насчёт того, что полученный контур не будет пропорционально уменьшенной копией заданного - согласен. Не додумал.
Предлагаю вариант, являющийся обобщением.
По заданным опорным точкам интерполируем (напр., кубическим сплайном), таким образом получая граничную кривую контура. Далее высчитываем нормаль в каждой точке получившейся кривой (уравнение кривой => касательная => нормаль), и, приводя её к нужной длине, на выходе имеем точки нового контура. Метод "в лоб". Вопрос о самопересечении - открыт.

← →
msts (2002-12-15 10:47) [25]

Ну че, решили задачу?
Если нет то по памяти могу сказать -
решается в два этапа:
1 найти центр многоугольника (не помню как называется)
В школе помнится был !учебник! по геометрии за !несколько! классов вот гдето в промежутке 70%-80% был раздел - как вписать заданный многоугольник в окружность, соот-но с формулами, по ним и находим эти координаты (центр окружности - центр многоугольника). Для любителей векторов переносим систему координат в этот центр.
2 перебираем все координаты многоугольника и смещаем их на указанную длину в направлении к центру (где то выше указано как)
и все вроде

← →
Alex45 (2002-12-15 11:37) [26]

Просто класс!
Видимо у нас были разные школьные курсы по геометрии.
Здравый смысл - отдыхает. Попробуйте вписать ПРОИЗВОЛЬНЫЙ многоугольник в окружность. Интересно было бы взглянуть на Ваши формулы.
Вы, наверное, в курсе, что окружность определяется по 3 точкам единственным образом. Поясню: количество окружностей, которые можно получить по N точкам контура (3<=N<бескон-ть), равно, как Вы, безусловно, догадываетесь N. Какой из N центров Вы предпочитаете?
А если контур с самопересечениями? В результате - полный бардак.

← →
zavdim (2002-12-16 07:19) [27]

>
> Ssergy (07.11.02 18:32)
> Мастера, помогите пожалуйста.
> Есть замкнутый контур, заданный точкам.
> Необходимо получит контур, находящийся внутри данного, на
> расстоянии k от каждой из сторон. (т.е надо получить пропорционально
> уменьшеный контур внутри данного).
> Хоть какие - либо идеи please.
> Заранее спасибо.

Пропорционально уменьшенный и на одинаковом расстоянии - противоречие.
Возмите картину с рамкой определенной толщины - внутренность рамки не является подобной внешности. Вы уж определитесь чего надо.
Этот вопрос обсуждался на http://algolist.manual.ru/forum/viewtopic.php?t=33
я там Dmitriy.

← →
zavdim (2002-12-16 07:37) [28]

Если же просто ужать и всунуть. То в любой афинной системе координат делите координаты на что надо и потом делаете параллельный перенос. Вопрос о праллельном решите сами.
Но вот что вы при этом получите? Как например с 8-ой, или еще чего. В общем советую прочитать приведенную ссылку. Потом подумать, хотя обычно с этого начинают. Далее более четко оформить вопрос.

Помогите с расчетом координат. Найти похожие ветки