Извлечение многоугольников из многоугольника с коллинеарными краями

Question

Как я могу извлечь простые многоугольники из многоугольника, который содержит коллинеарные ребра?Для приведенного ниже очень простого случая ребра 2-3 и 6-0 коллинеарны.Я хочу разделить это как 0, 1, 2 и 3, 4, 5, 6.

Я мог бы сравнить коллинеарность каждого ребра с любым другим ребром, но это медленный подход O (n ^ 2),Есть ли более быстрый метод?

Answer 1

Найдите ограничивающий круг. Вычислите верхнее / правое пересечение между ограничительной окружностью и линией, на которой лежит каждое ребро. Это O (n). Теперь рассортируйте каждое ребро по кортежу по его углу и угловому положению пересечения с ограничивающим кругом. Это O (nlogn) и сгруппирует коллинеарные ребра в ваш отсортированный список.

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

Answer 2

Можете ли вы найти пересечение 1-2 и 6-0? Если это так, вы можете сгенерировать граф ребер и вершин. Тогда найти все непересекающиеся многоугольники просто.