Войти
ПрограммированиеФорум2D графика и изометрия

Определить направление обхода вершин.

#0
20:55, 19 окт. 2014

Дан массив 2D векторов с координатами вершин полигона, полигон может быть невыпуклым, но без самопересечений, вершины в массив занесены, естественно, последовательно.
Вопрос - как определить, по часовой стрелке, или против занесены вершины в массив?
Способ "в лоб" я представляю - посчитать сумму углов справа (или слева), углы можно находить по теореме косинусов. Может есть вариант проще?

#1
22:07, 19 окт. 2014

Стандартная задача: "Собака на привязи" =)

#2
22:10, 19 окт. 2014

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

#3
23:14, 19 окт. 2014

Mikle
Я у себя вот так делаю:
  Находим номер и координаты вершины сверху слева.
  Находим по её номеру координаты предыдущей и следующей вершины в списке вершин.
  Дальше для этих трех координат вызываем вот эту функцию(если верёнт true, то значит обходим вершины по часовой стрелке):

bool isRight(const vec2d&prev,const vec2d&o,const vec2d&next){return (next-o).Rot(prev-o).y>0;}

Сделал demo для функции isRight.
Небольшое пояснение:
direction of traversal | Определить направление обхода вершин.
Скачать: DemoDirectionOfTraversal

Сделано на QapLite

#4
23:25, 19 окт. 2014

Adler
То есть даже не три крайние вершины, а одна с соседями. Логично.

#5
0:42, 20 окт. 2014

Mikle
если бы полигон был выпуклым, то достаточно было бы посчитать векторное произведение любых двух последовательных рёбер. так как такого условия нет, придётся искать сумму всех углов со знаком.

#6
1:43, 20 окт. 2014

Mikle
Я тупой, или ответ - вчистую знак ориентированной площади многоугольника?
Определение (англ.)
e-maxx (рус.)
AlgoList (рус.)
("или" - не исключающее).

Правка: добавил ссылку на algolist.
#7
10:03, 20 окт. 2014

На алголисте есть и про конкейвы.
http://algolist.manual.ru/maths/geom/polygon/orient.php

#8
11:14, 20 окт. 2014

Suslik
Векторное произведение двух последовательных рёбер можно использовать даже тогда, когда полигон невыпуклый. Для этого достаточно взять рёбра у крайней вершины, например взять самую левую из всех верхних.
FordPerfect
Почитал про ориентированную площадь, думаю, что мой метод проще.

#9
17:09, 20 окт. 2014

Mikle
> Почитал про ориентированную площадь, думаю, что мой метод проще.
Ориентированная площадь устойчивей.
Если в результате ошибок округления появятся небольшие самопересечения, то локальные алгоритмы могут заглючить, а площадь все прожует.

#10
18:08, 20 окт. 2014

}:+()___ [Smile]

Mikle
> Почитал про ориентированную площадь, думаю, что мой метод проще.
Ориентированная площадь устойчивей.
Если в результате ошибок округления появятся небольшие самопересечения, то локальные алгоритмы могут заглючить, а площадь все прожует.

Другой пример - дублирующиеся точки. Например "самая левая из всех верхних" указана 4 раза подряд. Ориентированная площадь - прожуёт.
Насчёт проще - дело вкуса, но мне хотелось бы увидеть код, который будет проще этого:
double signed_area(const std::vector<vec2d> &v)
{
    double S=0.0;
    for(int i=0,n=v.size();i<n;++i)
        S+=v[i].x*(v[(i+1)%n].y-v[(i+n-1)%n].y);
    return S/2.0;
}

// Return value:
// +1 == counterclockwise
//  0 == degenerate
// -1 == clockwise
int orientation(const std::vector<vec2d> &v)
{
    double S=signed_area(v);
    return int(0.0<S)-int(S<0.0);
}
Он работает для n<3, кстати.
Скорость низкая (2 взятия остатка на итерацию), так что если задача определения направления вдруг является performance-critical - то можно код переписать длиннее, но без модулей.

ryzed
Статья на algolist'е несколько мутная. Вот это утверждение:

Ориентация будет "по часовой стрелке", если площадь положительна.

не совпадает с общепринятым определением.
Вообще педантично вместо "против часовой стрелки" говорить "ориентация, согласованная с ориентацией базиса".
#11
18:10, 20 окт. 2014

Дублирующиеся точки и самопересечения у меня всё равно детектируются заранее, так что от них проблем не будет.

ПрограммированиеФорум2D графика и изометрия

Тема в архиве.