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

Контур выпуклый. Берем произвольно три последовательные точки (главное, чтобы не на одной прямой), смотрим, в право или влево уклоняется третья от вектора, заданного от первой ко второй.
Подробно, пусть это три точки
A1=(x1,y1) , 
A2=(x2,y2) , 
A3=(x3,y3) , 
Тогда прямая, проходящая ч/з A1 и A2: (x-x1)(y2-y1)=(x2-x1)(y-y1).
Пусть x1<x2, тогда если точка A3 справа от вектора A1A2, то она ниже прямой 
и следовательно (x3-x1)(y2-y1)>(x2-x1)(y3-y1) , следовательно направление всего контура по часовой, 
если x1<x2 и (x3-x1)(y2-y1)<(x2-x1)(y3-y1) , то против часовой,
x1>x2 и (x3-x1)(y2-y1)<(x2-x1)(y3-y1) по часовой,
x1>x2 и (x3-x1)(y2-y1)>(x2-x1)(y3-y1) против часовой.
Т.к. контур выпуклый, то достаточно рассмотреть только три точки.

P.S. И отдельный случай, если x1=x2.
Тогда если y1<y2 и x3>x1 -- по часовой,
y1<y2 и x3<x1 -- против часовой,
y1>y2 и x3>x1 -- против часовой,
y1>y2 и x3<x1 -- по часовой.


Это сообщение отредактировал(а) Artemios - 15.4.2007, 00:39

для невыпуклого можно посмотреть, на на какой угол изменяется направление вектора при переходе от n к (n+1)-му и сложить эти углы
получится +360 или -360 та и определить
ещё можно покрутить в сторону формулы Грина - с помощью неё можно определить "ориентированную площадь", знак которой и даёт ответ...

Не совсем понял твою мысль.

Насчет формулы Грина - разве она не только для выпуклых многоугольников?

P.P.S.
Для произвольного контура, не обязательно выпуклого, можно поступить и таким образом.
Пусть даны последовательные точки A(i)=(x(i),y(i)), где 1<=i<=n.
Определим числа s(i) = ( x(i+1) - x(i) ) * ( y(i) + y(i+1) ) / 2  при i<n,
s(n) = ( x(1) - x(n) ) * ( y(n) + y(1) ) / 2 .
Считаем сумму всех s(i) : S = sum s(i) , 1<=i<=n .
Если S>0 , то направление по часовой стрелке,
если S<0 , то против.

Добавлено @ 01:42
это и есть "ориентированная площадь"

Добавлено @ 01:45
Кстати, это:

говорит о том, что контур именно выпуклый по определению.

Это сообщение отредактировал(а) Artemios - 15.4.2007, 01:48

первую или вторую?
если вторую, то Artemios как раз её и описал

Нет, это не так. Нарисуй любой контур по точкам и проставь стрелки.

Поначалу - первую. Уже разобрался. Углы считать будет сложнее чем по формуле ориентированной площади.

Это сообщение отредактировал(а) S.A.G. - 15.4.2007, 12:35

да, второй способ лучше, арксинусов не надо будет считать, да и площадь на всякий случай имеется
первый я так, "до кучи" 

Artemios, получаеться что любой контур имеет направление? Мой контур имеет направление которое зависит от направления движения мыши при вводе точек - от начальной точки к конечной.  Будет ли совпадать это направление с определенным по формуле Грина?

Это сообщение отредактировал(а) S.A.G. - 15.4.2007, 14:01

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

Кстати а если S = 0 или такой вариант невозможен?

Это сообщение отредактировал(а) S.A.G. - 15.4.2007, 14:56

Многоугольник называется выпуклым, если для любого ребра весь многоугольник лежит только по одну сторону от ребра (в одной полуплоскости). Независимо от того, направленные ребра или просто отрезки.


Если без самопересечений, то невозможен.

Не говорит. Такое можно сказать как о выпуклых так и о не выпуклых многоугольниках. 

???
Пусть направление по часовой (аналогично и для "против часовой"). Все точки, расположенные слева от каждого вектора лежат вне контура.
Следовательно, весь контур (за исключением данного вектора) лежит справа от этого вектора.
Определение выпуклости многоугольника (еще школьное, кажись):

поэтому

все-же нельзя сказать.

Ну нарисуй контур невыпуклый и убедись что это не всегда так.

Именно  При невыпуклом -- действительно не всегда так  Точнее, если многоугольник не выпуклый, то как минимум для двух ребер (а следовательно и векторов) не выполнено условие: