Как определить, входит диагональ в вогнутый многоугольник или выходит из него?
Диагональ (диагональ-это отрезок, соединяющий несмежные вершины) вогнутого (невыпуклого) многоугольника может полностью входить или выходить из многоугольника (или может пересекаться с ребрами многоугольника). Как определить, находится ли он полностью в полигоне?(метод без теста точка-в-полигоне ).
5 ответов:
Если диагональ имеет хотя бы одно пересечение с ребрами, она частично входит и частично выходит из многоугольника, однако, если диагональ не пересекается с ними, есть только два состояния: она полностью входит или полностью выходит из многоугольника.
Чтобы определить, находится ли он внутри или вне полигона:
Предположим, что вершины многоугольника отсортированы против часовой стрелки. Рассмотрим одну из конечных точек диагонали, лежащую на вершине с именем P[i] (другая конечная точка - p [j]). Затем составьте три вектора, первые точки которых p[i]:
V1 : p[i+1] - p[i]
V2 : p[i-1] - p[i]
V3 : p[j] - p[i]
Диагональ полностью находится в многоугольнике тогда и только тогда, когда V3 находится между V1 и V2, когда мы движемся против часовой стрелки от V1 к V2.
Alt текст http://www.freeimagehosting.net/uploads/1b97107f4a.jpg
Как определить, находится ли V3 между V1 и V2, когда мы идем от V1 к V2 против часовой стрелки? идти к здесь .
Я написал программу, использующую этот метод, и она работает эффективно .
Как определить, находится ли он полностью в многоугольнике?
Если вы хотите определить, никогда ли диагональ не покидает границу многоугольника, просто определите, пересекает ли она какие-либо линии между двумя соседними вершинами.
Если это так, то он частично входит и частично выходит из полигона.
Если нет, то он либо полностью в полигоне, либо полностью вне его. Отсюда простейший способ-использовать точку-в-многоугольнике на любая точка на диагонали, но если вы не хотите этого делать, Используйте алгоритм намотки.
Я полагаю, что ответ Джона упускает важный случай: когда диагональ полностью выходит за пределы многоугольника с самого начала. Представьте, что в диагональ моста "" две башни своей "U" в форме многоугольника.
Я должен был решить эту проблему несколько лет назад, поэтому, пожалуйста, простите, если мои воспоминания немного запятнаны.
Способ, которым я решил это, состоял в выполнении тестов пересечения линий диагонали против каждого ребра в многоугольнике. Тогда у вас есть два возможных случая: вы либо был хотя бы один перекресток, или у вас не было перекрестков. Если вы получаете какие-либо пересечения, диагональ не находится внутри многоугольника.
Если вы не получаете никаких пересечений, вам нужно определить, находится ли диагональ полностью внутри или полностью вне многоугольника. Предположим, что диагональ соединяет p[i] с p[j], что i
Как только вы это сделаете, угол 2D диагонали будет положительным, если диагональ находится вне полигона, или отрицательным, если она находится внутри полигона.
Что касается проверки пересечений между сегментами линий (что является первым шагом, который вам, вероятно, придется сделать), я нашел объяснения на SoftSurfer полезными. Вы должны были бы проверить пересечение между диагональю и любым из ребер многоугольника. Если вы используете MATLAB, вы должны быть в состоянии найти эффективный способ проверить пересечения для всех ребер одновременно, используя матричные и векторные операции (я имел дело с вычислением точек пересечения таким образом, для пересечений лучей-треугольников ).
Ответ Джона точен:
Если вы хотите определить, никогда ли диагональ не покидает границу многоугольника, просто определите, пересекает ли она какие-либо линии между двумя соседними вершинами. Если да, то он покинул полигон.
Эффективный способ сделать это проверить, чтобы запустить алгоритм сканирующей Бентли-Оттман на данные. Это легко реализовать,но трудно сделать численную стабильность. Если у вас их меньше ... сказать... 20 ребер в ваших полигонах поиск грубой силы скорее всего, будет быстрее.
Comments