Тест на строго простой полигон (разрешены отверстия)?

Question

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

В приведенном выше изображении B C и D не являются простыми многоугольниками, но только D может не выполнить проверку пересечения. Моя терминология (в терминах строго простого) также может быть немного неадекватной, но я думаю, что картина иллюстрирует, что я имею в виду.

Answer 1

Say две линии пересекаются, если они имеют по крайней мере одну точку.

Возьмите один край и посчитайте пересечения с любыми другими ребрами. Если у него есть

• 2 пересечения, то у него есть один край слева и один край справа, и все хорошо.
• более 2 пересечений, то он имеет более двух ребер, начиная с конечных точек (случай B), конечной точки ребра в середине (случай C) или пересечения с другой линией (случай D).

Итак, на мой взгляд, ваши заботы необоснованная:

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

Этот подход работает и здесь.

Answer 2

Эти три класса недействительных полигонов должны быть проверены независимо.

Случай B:

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

Случай C:

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

Случай D:

Как вы сказали, это можно найти, проверяя, если какие-либо ребра пересекаются.

Корпус E: Два края перекрываются (пересекаются в бесконечно много точек), а их вершины - нет.

Я не уверен, что это должен быть отдельный случай, но эта ситуация не может быть задержана проверкой на случай D (я думаю, что вы в конечном итоге разделите на ноль). Поэтому вам также нужно будет проверить, что два ребра не соответствуют точно такой же линии.

Я не могу думать ни о каких других случаях на данный момент