Диагональ многоугольника внутри или снаружи?

Question

У меня есть три последовательных точки многоугольника, скажем, p1, p2, p3. Теперь я хотел бы знать, находится ли ортогональ между p1 и p3 внутри многоугольника или вне многоугольника.

Я делаю это, беря три вектора v1, v2 и v3. А точку перед точкой p1 в многоугольнике скажем p0.
v1 = (p0 - p1)<br> v2 = (p2 - p1)<br> v3 = (p3 - p1)

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

Я также знаю, что весь мой многоугольник по часовой стрелке или против часовой стрелки. И соответственно я выбираю векторы v1 и v2. Но все же я получаю некоторые проблемы. Я показываю один случай, когда у меня проблемы.

альтернативный текст http://i42.tinypic.com/2dt8aaw.jpg

Этот многоугольник против часовой стрелки. и это начинается с происхождения v1 и v2.

Answer 1

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

С математической стороны, на самом деле не так уж много различий между внутренней и внешней частью, за исключением таких мелких деталей, как внешняя сторона, имеющая бесконечную площадь. (По крайней мере, для 2D-плоскости; на сфере внутренность и внешность плигона не различаются резко.)

У вас также есть вопрос о порядке расположения ребер полигона. Самый простой способ - суммировать все углы между соседними ребрами по порядку. Это добавит до N * (pi / 2). Для полигонов против часовой стрелки N положительно.

[править] Как только вы знаете направление и если у вас нет ни одного из сложных случаев, перечисленных выше, вопрос становится легким. Угол p0-p1-p2 меньше угла p0-p1-p3. Следовательно, ребро p1-p3 лежит, по крайней мере, частично вне многоугольника. И если он не пересекает никакой другой край, он, очевидно, полностью лежит вне многоугольника.

Answer 2

Поскольку ваши точки являются cseosecutive, вы можете решить эту проблему, проверив ориентацию треугольника p1 p2 p3. Если ориентация такая же, как и у многоугольника, то диагональ находится внутри, а остальное снаружи.

Чтобы определить ориентацию треугольника, самый простой способ - вычислить подписанную область и проверить знак. Вычислим

p1.x * p2.y + p2.x * p3.y + p3.x * p1.y - p2.x * p1.y - p3.x * p2.y - p1.x * p3.y

Если знак этого значения положительный, ориентация против часовой стрелки. Если знак отрицательный, ориентация по часовой стрелке.

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

Answer 3

Угол между любыми двумя векторами равен

alpha = acos(v1.x * v2.x + v1.y * v2.y)

Поскольку теперь вы можете иметь угол между

v1 and v3 = alpha1; v1 and v2 = alpha2; 

Вы можете проверить, находится ли альфа2 внутри альфа1:

function normalize(a):
    if a > 2 * pi then a - 2 * pi
    else if a < 2 * pi then a + 2 * pi
    else a

alpha1 = normalize(alpha1)
alpha2 = normalize(alpha2)

if (alpha2 < alpha1) then is_between
else is_not_between

Это не очень полно, но вы должны понять.

РЕДАКТИРОВАТЬ : это не будет работать, если многоугольник перекрывается, как заметил MSalters.