Нахождение диагоналей многоугольника

Question

Учитывая вогнутый многоугольник (без самопересечений), узлы которого расположены по часовой стрелке, как мы можем определить все его внутренние диагонали (те, которые находятся внутри многоугольника)?

Меня интересует решение, которое не использует триггерные функции.

Фон и что я пробовал :

В моем классе вычислительной геометрии нам дали следующий алгоритм, чтобы проверить, является ли [pi, pj] внутренней диагональю в многоугольнике p0, p1, ... pn-1:

1. Проверьте, пересекает ли [pi, pj] край многоугольника, который не смежен с ним. Если да, это не внутренняя диагональ. Если нет, перейдите к шагу 2.
2. 1. если pi является выпуклой точкой (pi-1, pi, pi+1 повернуть направо), то [pi, pj] является внутренней диагональю, если pi, pj, pi+1 и pi, pi-1, pj повернуть налево.
   2. , если pi не является выпуклой точкой (pi-1, pi, pi+1 повернуть налево), то [pi, pj] является внутренней диагональю, если pj, pj-1, pi повернуть налево.

Этот алгоритм был дан нам для алгоритма триангуляции, включающего обрезание ушей. Я реализовал этот алгоритм, и он, кажется, отлично работает там, но суть в том, что алгоритм обрезания ушей использует только диагонали вида [pi, pi+2].

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

Легко проверить, что опубликованный мной алгоритм отклоняет внутреннюю диагональ [3, 6], хотя на самом деле это не должно быть:

3 не является выпуклой точкой, а 6, 5, 3 делает правый поворот вместо левого, поэтому он отклоняется.

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

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

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

Примечание : Я не мог решить, стоит ли размещать это на math.stackexchange.com или здесь, поскольку вычислительная геометрия имеет примерно одинаковую степень как с программированием, так и с математикой, однако я чувствовал, что программисты лучше знакомы с алгоритмами такого рода, чем математики, поскольку кто-то, вероятно, действительно реализовал это в какой-то момент.

Answer 1

Раздел 2.1 алгоритма выглядит так, как будто он проверяет, что pj находится во "внутренней части" выпуклого угла, определяемого pi-1, pi, pi+1.

Раздел 2.2 может быть получен из раздела 2.1, так что онпроверяет, что pj равно , а не во "внутренней части" выпуклого угла, определенного как pi+1, pi, pi-1.Это в основном NOT (pi, pj, pi-1 and pi, pi+1, pj make a left turn) == pi, pj, pi-1 or pi, pi+1, pj make a right turn.

Таким образом, весь пункт будет "если pi является вогнутой точкой, то [pi, pj] является внутренней диагональю, если либо pi, pj, pi-1 или pi, pi+1, pj (или оба)поверните направо.

Answer 2

Обратите внимание, насколько эффективно это будет, но вы можете вычислить выпуклую оболочку, а затем получить список полигонов («исключенных» полигонов), которые находятся в выпуклой оболочке, но не в исходном многоугольнике. (В вашем примере выпуклая оболочка будет иметь вершины 1,2,4,5,7, так что исключенные многоугольники будут (2,3,4), (5,6,7).) Тогда вам нужны следующие диагонали: диагонали исходного многоугольника, которые не пересекаются ни с одним из исключенных многоугольников. Но обратите внимание, что исключенные многоугольники могут не быть треугольниками, а могут и не быть выпуклыми, поэтому проверка пересечения линии может быть неудобной.

Answer 3

Несколько примечаний:

1) Легко проверить, является ли диагональ внутренней, сравнивая углы (например, для диагонали 4-6 угол 3-4-5 больше угла 3-4-6, так что это внутренняя диагональ).Я уверен, что это может быть упрощено векторным произведением, но моя математика не так хороша.

2) Чтобы проверить, не пересекает ли конкретная внутренняя диагональ другие ребра, вы можете проверить, если точкимногоугольника находятся на ожидаемой стороне.Пример: если мы попробуем диагональ 1-4, точки 2 и 3 должны быть с одной стороны, а точки 5, 6 и 7 - с другой.Если он не выполняется, диагональ пересекает ребро.