определение направления обхода контура

[tae1980]

Сабжевый вопрос не совсем топичен, но реализацию алгоритма планируется в Excel, а значит он имеет отношение к этой программе.

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

Может кто знает как это реализовывается. Должно быть что-то простое, а мне на ум лезут только сверх сложные расчеты.

[EducatedFool]

А что сложного?

Перебираете в цикле координаты вершин, и вычисляете угол между 2 векторами - текущей стороной контура, и следующей.

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

Если знак величины угла изменяется - обход осуществляется не в порядке расположения вершин (или контур не является выпуклым).

Нашел кое-что по теме: http://faqs.org.ru/forum/viewtopic.php?t=11754

[alexBlack]

Еще можно вычислить площадь
http://programmersforum.ru/showthrea...621#post206621
и по ее знаку определить направление

[tae1980]

Сообщение от EducatedFool

А что сложного?
Перебираете в цикле координаты вершин, и вычисляете угол между 2 векторами - текущей стороной контура, и следующей.
Если в течении всего цикла величины углов меньше нуля, значит, обход осуществляется по часовой стрелке, в случае же углов больше 0 - против часовой стрелки.
Если знак величины угла изменяется - обход осуществляется не в порядке расположения вершин (или контур не является выпуклым).

Работа на компьютере с углами всегда затруднительна, так как это не "родная" его система. Я всегда стараюсь избегать тригонометрических функций, ибо мало что работает более тормозно и более не предсказуемо. На разных машинах, одна и та же формула может давать разные значения. Как показала практика в 98% можно обойтись без них, а решения будут более простые.

Сообщение от EducatedFool

Нашел кое-что по теме: http://faqs.org.ru/forum/viewtopic.php?t=11754

Спасибо! Прочитал, к сожалению это только "рабочий" материал.

Я пока склоняюсь к варианту определения по четвертям.
1. Находим точку с минимальным значением по X. Это позволит избавиться от 2 нижних четвертей.
2. Находим Dy предыдущей и последующей точек.
3. Находим Dy/2 середину. Ось X.
4. If y(пред)<y(посл) then
if y(посл)>Dy then обход по часовой
Else Обход против часовой.
Else
if y(пред)>Dy then обход по часовой
Else Обход против часовой.
5. Если Dy=0 тоже самое для оси X.

Что мне не нравиться: слишком много разных проверок. Возможно стоит вернуться к проверке по всем четырем четвертям, тогда можно будет за основу брать любую точку. Ну конечно нужно еще все раз проверить, может я еще чего не учел.

[tae1980]

Но нутром чую есть более простое решение.....

[EducatedFool]

Но нутром чую есть более простое решение.....

Вы и так сильно упрощаете задачу...
В общем случае (при невыпуклом контуре) требуются более сложные алгоритмы.

Ну а если для определения направления Вы не считаете нужным анализировать все координаты, то можно сделать даже так:

1) Находим самую верхнюю, самую нижнюю, а также самую правую и самую левую точки.
2) Анализируем индексы найденных точек: к примеру, если индекс самой правой меньше индекса самой нижней, значит, обход осуществляется по часовой стрелке.

[tae1980]

Сообщение от EducatedFool

Вы и так сильно упрощаете задачу...
В общем случае (при невыпуклом контуре) требуются более сложные алгоритмы.

Условия выкпуклости нет оговорено, так что контур может быть любой конфигурации, более того он 100% будет сложной конфигурации, где будут все виды поверхностей которые только есть, с любым количеством точек.

Сообщение от EducatedFool

Ну а если для определения направления Вы не считаете нужным анализировать все координаты,

Я уверен что нет необходимости для решения данной задачи лишний раз прогонять цикл или пару по всем точкам. Один цикл будет обязательно при вводе информации (в данном случае из текстового файла).

Сообщение от EducatedFool

то можно сделать даже так:
1) Находим самую верхнюю, самую нижнюю, а также самую правую и самую левую точки.
2) Анализируем индексы найденных точек: к примеру, если индекс самой правой меньше индекса самой нижней, значит, обход осуществляется по часовой стрелке.

Уже 30 минут сижу тупо глядя на нарисованный и номерами точек по краям.... Как раз эта идея... Пытаюсь придумать случае, когда возможны сбои. Пока не нашел.... Реализую - погоняю на практике.

[tae1980]

Сообщение от alexBlack

Еще можно вычислить площадь
http://programmersforum.ru/showthrea...621#post206621
и по ее знаку определить направление

Уж больно это расточительно по 2-3 раза считать площадь одного участка....
Вот моя функция для подсчета площади. ИМХО поудобнее, в ней заложена возможность проверки корректности переданных координат, но не реализована:

'' *** Площадь ***
'Функция расчета площади земельного участка аналитическим способ.

'На входе:
'Точки            - Массив координат (X,Y) поворотных точек земельного участка, БЕЗ имен точек (2 колонки).
'                   Excel передает их (для двух столбцов) в виде: X1 Y1 X2 Y2 X3 Y3 ... Xn Yn

'Переменные:
'Размер           - Размер переданого массива, общее количество элементов.
'P1, P2           - Удвоенная площади, расчитанная по X и Y.
'n                - Переменная цикла.

Function Площадь(Точки)
    размер = Точки.Count
    p1 = 0: P2 = 0
    p1 = p1 + ((Точки.Cells(размер - 1) - Точки.Cells(3)) * Точки.Cells(2))
    P2 = P2 + ((Точки.Cells(4) - Точки.Cells(размер)) * Точки.Cells(1))
    For n = 3 To (размер - 2) Step 2
        p1 = p1 + ((Точки.Cells(n - 2) - Точки.Cells(n + 2)) * Точки.Cells(n + 1))
        P2 = P2 + ((Точки.Cells(n + 3) - Точки.Cells(n - 1)) * Точки.Cells(n))
    Next n
    p1 = p1 + ((Точки.Cells(размер - 3) - Точки.Cells(1)) * Точки.Cells(размер))
    P2 = P2 + ((Точки.Cells(2) - Точки.Cells(размер - 2)) * Точки.Cells(размер - 1))
   
    Площадь = p1 / 2
End Function

[alexBlack]

Почему два-три раза ?

Вообще-то я предложил это как метод определения направления обхода.
Одновременно получаем и площадь.
Пример для контура в виде цифры 2 (площадь 14).

function getOpr(P1, P2, P3:TPoint):integer;
begin
   result := P1.x*P2.Y*1 +
             P1.Y*P3.X*1 +
             P2.X*P3.Y*1 -
             P3.X*P2.Y*1 -
             P2.X*P1.Y*1 -
             P3.Y*P1.X*1;
end;

const P:array [1..12] of TPoint =  
      ((X:1; Y:6),                 // S = 14
       (X:5; Y:6),
       (X:5; Y:3),
       (X:2; Y:3),
       (X:2; Y:2),
       (X:5; Y:2),
       (X:5; Y:1),
       (X:1; Y:1),
       (X:1; Y:4),
       (X:4; Y:4),
       (X:4; Y:5),
       (X:1; Y:5)
      );

var S, i, N:integer;
begin
   S := 0;
   for i := Low(P) to High(P) do begin
     N := i+1;
     if N > High(P) then N := Low(P);
     S := S + getOpr( Point(0, 0), P[i], P[N] );
   end;
   writeln(S); // -28 по часовой

   S := 0;
   for i := High(P) downto Low(P) do begin
     N := i-1;
     if N < Low(P) then N := High(P);
     S := S + getOpr( Point(0, 0), P[i], P[N] );
   end;
   writeln(S); // 28 против часовой

   readln;
end.

[tae1980]

Сообщение от alexBlack

Почему два-три раза ?

А сколько у тебя в пример? :))

Сообщение от alexBlack

Вообще-то я предложил это как метод определения направления обхода.

Нельзя этого делать. Получение отрицательной площади - ОШИБКА, черных дыр у нас пока нет. Использование ОШИБОЧНЫХ данных в работе обязательно приводит к появлению ошибок в других местах. А применение такого топорного исправление ошибка как "умножение результата на -1", как минимум указывает на халатность исполнителя и отсутствие стиля программирования, а как максимум на проф не пригодность. И как программиста и как геодезиста.
Весь мой более десятилетний опыт работы говорит - Так работать нельзя.

Сообщение от alexBlack

Одновременно получаем и площадь.

Это две разные операции, совмещать подобное ни в коем случае нельзя. Я позволяю себе подобное только при "накидном монтаже" решения задачи.

Сообщение от alexBlack

Пример для контура в виде цифры 2 (площадь 14).

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

Сообщение от alexBlack

function getOpr(P1, P2, P3:TPoint):integer;
begin
   result := P1.x*P2.Y*1 +
             P1.Y*P3.X*1 +
             P2.X*P3.Y*1 -
             P3.X*P2.Y*1 -
             P2.X*P1.Y*1 -
             P3.Y*P1.X*1;
end;

const P:array [1..12] of TPoint =  
      ((X:1; Y:6),                 // S = 14
       (X:5; Y:6),
       (X:5; Y:3),
       (X:2; Y:3),
       (X:2; Y:2),
       (X:5; Y:2),
       (X:5; Y:1),
       (X:1; Y:1),
       (X:1; Y:4),
       (X:4; Y:4),
       (X:4; Y:5),
       (X:1; Y:5)
      );

var S, i, N:integer;
begin
   S := 0;
   for i := Low(P) to High(P) do begin
     N := i+1;
     if N > High(P) then N := Low(P);
     S := S + getOpr( Point(0, 0), P[i], P[N] );
   end;
   writeln(S); // -28 по часовой

   S := 0;
   for i := High(P) downto Low(P) do begin
     N := i-1;
     if N < Low(P) then N := High(P);
     S := S + getOpr( Point(0, 0), P[i], P[N] );
   end;
   writeln(S); // 28 против часовой

   readln;
end.

Позволю себе ряд комментариев:
1. Наличие отдельной процедуры, задача не такая уж сложная задача.
2. Наличие двух циклов. Ей богу не понял зачем... если только для примера.
3. На мой взгляд сложная конструкция: функция, проверки, сложное условие цикла... Короче раздолье для появления ошибки.
4. Отсутствие комментариев. Есть простое правило, которое мало кто соблюдает: если есть переменная, она должна быть прокомментирована.