Как определить диагональ внутри или из вогнутого многоугольника?

Question

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

Answer 1

Если диагональ имеет хотя бы одно пересечение с ребрами, то она частично находится внутри и частично вне многоугольника, однако, если диагональ не имеет пересечения с ними, существует только два состояния: она полностью входит или полностью выходит из нее. многоугольника.

Чтобы определить, находится ли он в многоугольнике или вне его:

Предположим, что вершины многоугольника отсортированы против часовой стрелки. Рассмотрим одну из конечных точек диагонали, лежащую на вершине с именем 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.

Как определить, находится ли V3 между V1 и V2, когда мы идем от V1 к V2 против часовой стрелки? перейдите к здесь .

Я написал программу с использованием этого метода, и она работает эффективно.

Answer 2

Как определить, находится ли он полностью в многоугольнике?

Если вы хотите определить, не покидает ли диагональ границу многоугольника, просто определите, пересекает ли она какие-либо линии между двумя смежными вершинами.

• Если это так, он частично входит в полигон и частично выходит из него.

• Если нет, он либо полностью, либо полностью вне полигона. Отсюда самый простой способ - использовать точку-многоугольник в любой точке на диагонали, но если вы не хотите этого делать, используйте алгоритм намотки .

Answer 3

Я полагаю, что в ответе Джона отсутствует важный случай: когда диагональ полностью выходит за пределы полигона с самого начала. Представьте себе, что вы делаете диагональный «мост» двумя башнями своего многоугольника в форме буквы «u».

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

Способ, которым я решил это, состоял в том, чтобы выполнить тесты пересечения линии диагонали по каждому ребру в многоугольнике. Затем у вас есть два возможных случая: у вас было хотя бы одно пересечение или у вас не было пересечений. Если вы получаете какие-либо пересечения, диагональ не находится внутри многоугольника.

Если вы не получили никаких пересечений, вам нужно определить, находится ли диагональ полностью внутри или полностью вне многоугольника. Допустим, диагональ соединяет p [i] с p [j], что i

Как только вы это сделаете, 2D-угол диагонали будет положительным, если диагональ находится за пределами многоугольника, или отрицательным, если он находится внутри многоугольника.

Answer 4

Что касается проверки пересечений между отрезками (что является первым шагом, который вам, вероятно, придется сделать), я нашел объяснения по SoftSurfer полезными. Вам нужно будет проверить пересечение между диагональю и любым из ребер многоугольника. Если вы используете MATLAB, вы сможете найти эффективный способ проверки пересечений для всех ребер одновременно, используя матричные и векторные операции (я имел дело с вычислением точек пересечения таким образом для пересечений лучей и треугольников ).

Answer 5

Джон отвечает по адресу:

Если вы хотите определить, не покидает ли диагональ границу многоугольника, просто определите, пересекает ли он какие-либо линии между двумя смежными вершинами. Если это так, он покинул многоугольник.

Эффективным способом сделать эту проверку является запуск алгоритма развертки Bentley-Ottman для данных. Это легко реализовать, но трудно сделать численно стабильным. Если у вас меньше ... скажем ... 20 ребер в ваших многоугольниках, поиск грубой силы, скорее всего, будет быстрее.