2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

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

 
 
 
 Re: Определить направление обхода
Сообщение13.02.2013, 20:15 
Обычно считают ориентированную площадь этого многоугольника.

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

 
 
 
 Re: Определить направление обхода
Сообщение14.02.2013, 12:48 
А такой вариант возможен: находим сумму Sin углов между векторами и в зависимости от знака это будет обход по часовой или против часовой стрелки?

-- 14.02.2013, 13:57 --

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

Хорошая идея :-)

-- 14.02.2013, 13:59 --

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

 
 
 
 Re: Определить направление обхода
Сообщение14.02.2013, 17:27 
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}$.

 
 
 
 Re: Определить направление обхода
Сообщение14.02.2013, 22:27 
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}$.

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

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

 
 
 
 Re: Определить направление обхода
Сообщение20.07.2016, 18:10 
Можно привести пару многоугольников отличающихся только одной вершиной, имеющих разную ориентацию и таких что если удалить из суммы два слагаемых, то получите числа одного знака.

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

-- 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}$ и начале координат. Площадь многоугольника есть сумма площадей его сторон.

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group