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

[Nova-nova]

Невыпуклый многоугольник задается координатами вершин при его обходе по часовой или против часовой стрелки. Контур многоугольника не имеет самопересечений. Определить направление обхода.

[mihiv]

Рассмотрим вектор $\vec a=-y\vec i,\operatorname{rot} \vec a=\vec k$, ясно, что поток $\operatorname{rot}\vec a $ через часть плоскости, ограниченную контуром, положителен (равен площади многоугольника). С другой стороны этот поток равен циркуляции вектора $\vec a$ по контуру многоугольника. Если знаки вычисленных циркуляции и потока совпадают, то обход идет против часовой стрелки, иначе по - часовой стрелке.

[мат-ламер]

Для начала найдём хотя-бы одну точку, принадлежащую многоугольнику. Например, из середины любой стороны многоугольника востановить перпендикуляр в ней. Тогда, в одну сторону от середины (в окрестности её) будут точки из многоугольника, а в другую сторону нет. Затем просуммируем углы, под которыми видны стороны многоугольника из этой точки.

[Null]

Обычно считают ориентированную площадь этого многоугольника.

[mihiv]

По-моему можно еще так:(предполагаем, что многоугольник в плоскости $xoy$). Выберем вершину с наименьшей абсциссой, пусть это будет $A_k$, составим векторное произведение $\vec A_{k,k+1}\times \vec A_{k,k+1}$, если проекция в.п. на ось $z$ больше 0, то обход против часовой стрелки, если меньше 0, то по часовой стрелке.

[Nova-nova]

А такой вариант возможен: находим сумму Sin углов между векторами и в зависимости от знака это будет обход по часовой или против часовой стрелки?

-- 14.02.2013, 13:57 --

Null в сообщении #683532 писал(а):

Обычно считают ориентированную площадь этого многоугольника.

Хорошая идея

-- 14.02.2013, 13:59 --

Всем большое спасибо Очень помогли!

[mihiv]

mihiv в сообщении #683760 писал(а):

составим векторное произведение $\vec A_{k,k+1}\times \vec A_{k,k+1}$

Вкралась ошибка, должно быть: $\vec A_{k,k+1}\times \vec A_{k,k-1}$, где вектор $\vec A_{k,k-1}$ проведен из вершины $A_k$ в вершину $A_{k-1}$.

[Nova-nova]

mihiv в сообщении #683897 писал(а):

mihiv в сообщении #683760 писал(а):

составим векторное произведение $\vec A_{k,k+1}\times \vec A_{k,k+1}$

Вкралась ошибка, должно быть: $\vec A_{k,k+1}\times \vec A_{k,k-1}$, где вектор $\vec A_{k,k-1}$ проведен из вершины $A_k$ в вершину $A_{k-1}$.

Да спасибо этот момент выяснен

[snake32]

Подскажите, обязательно ли суммировать векторные произведения для всех вершин полигона?
Например, для треугольника где k изменяется [1..3], то есть будет 3 векторных произведения, но, на сколько знаю, в этом случае достаточно одного.
Можно ли говорить о том что для НЕ выпуклого полигона состоящего из N вершин достаточно N-2 векторных произведений?

[slavav]

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

В зависимости от вида вашей формулы для суммирования, этот трюк можно провернуть даже для треугольника.

-- 20.07.2016, 18:32 --

mihiv в сообщении #683897 писал(а):

mihiv в сообщении #683760 писал(а):

составим векторное произведение $\vec A_{k,k+1}\times \vec A_{k,k+1}$

Вкралась ошибка, должно быть: $\vec A_{k,k+1}\times \vec A_{k,k-1}$, где вектор $\vec A_{k,k-1}$ проведен из вершины $A_k$ в вершину $A_{k-1}$.

Это неверная формула. Для треугольника вы получите результат в три раза (или в шесть раз) больше реального. Для квадрата ваша формула выдаст в два или четыре раза больше.

Я для запоминания формулы площади ввожу понятие "удвоенная площадь стороны": $A_k\times A_{k+1}$. Это удвоенная ориентированная площадь треугольника построенного на вершинах $A_k$, $A_{k+1}$ и начале координат. Площадь многоугольника есть сумма площадей его сторон.