Многоугольник задан своими вершинами расположенными в порядке их следования, каким образом можно определить направление обхода вершин при построении многоугольника (по часовой или против часовой стрелки)?

Если многоугольник выпуклый, то посчитать векторное (косое, Cross Product) произведение для пары векторов, образованных тремя последовательными точками. Знак его укажет на направление обхода

может быть и невыпуклым

MBo, а можешь подробнее?

SparF 



Добавлено @ 10:19 
harper, 
>может быть и невыпуклым 

От центра одного из отрезков направить влево (по его ходу) перпендикулярно отрезку луч, посчитать количество пересечений со сторонами. Четность этого количества (надо не забыть правильно учитывать возможные попадания точно в углы и совпадения луча со сторонами) будет свидетельствовать о направлении обхода (Это использование одного из алгоритмов PointInPolygon)

MBo, а ссылки на более подробное описание есть?

MBo, понял) спасибо)))

О, еще один способ вспомнил ;)
Посчитать ориентированную площадь (в примере - удвоенная считается) и посмотреть ее знак



Это сообщение отредактировал(а) MBo - 8.10.2006, 11:30

MBo, это для невыпуклого многоугольника подходит? 

MBo, а как подсчитать площадь для произвольного многоугольника?

я в свое время делал через статистическое моделирование:
"стрелял" с равномерным распределением  по площади прямоугольника, который описывает этот произвольный многоугольник, и считал сколько попал/не попал в произвольный.
есть ли что-нть более быстрое?

PS кому надо - могу исходник выложить

Это сообщение отредактировал(а) SparF - 8.10.2006, 12:02

harper, 
>это для невыпуклого многоугольника подходит?  

Да

Добавлено @ 12:08 
SparF, 
>а как подсчитать площадь для произвольного многоугольника?
Код я привел,  для получения площади нужно модуль результата пополам разделить, вычисления в вещественную арифметику при необходимости перевести. 

Работает и с невыпуклыми.

MBo,
а можешь картинку дать какие площади он считает на произвольном многоугольнике при помощи

если это, конечно, можно нарисовать
или ссылочку где это выводится
буду оч благодарен - просто понять для себя хочу (запоминать просто так бесполезно)

SparF, 
Математически - алгоритм следует из формулы Грина (связь между  интегралом по контуру и заключенной в нем площадью), но это, наверно, слишком сложно.
http://mathworld.wolfram.com/GreensTheorem.html

Каждая величина в скобках - удвоенная площадь треугольника, составленного из двух последовательных точек и начала координат. 
Модуль векторного произведения есть произведение длин исходных векторов на синус угла между ними 
Если взять на коорд. плоскости 3 точки A B C, то площадь треугольника ABC есть сумма ориентированных площадей треугольников OAB, OBC, OCA. Общие фрагменты вычтутся.



Это сообщение отредактировал(а) MBo - 8.10.2006, 13:52

MBo,
Пасибо)) просто не представляешь насколько это полезная для меня инфа =)

Это сообщение отредактировал(а) SparF - 8.10.2006, 14:25