Тест на строго простой многоугольник (отверстия разрешены)? - PullRequest
Новая
       79

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

3 голосов
/ 01 апреля 2012

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

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

Ответы [ 3 ]

1 голос
/ 02 апреля 2012

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

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

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

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

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

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

0 голосов
/ 31 мая 2018

Случай F: вершины образуют замкнутый цикл и задаются в порядке CCW.Это можно сделать, пройдя по всем вершинам и суммируя углы соединения.Я выбираю обороты в качестве своих угловых единиц: (псевдокод)

vertex_n_minus1 = [x, y]

vertex_n = ..

vertex_n_plus1 = ..

DirectionVector входящий_Директ = новый НаправлениеВектор (vertex_n_minus1, vertex_n)

DirectionVector outgoingDir = новый НаправлениеВектор (vertex_n, vertex_n_plus1)

DirectionVector dirChange = [• исходящийDir • входящийDir *циркуляция] DIRD)

double jointTurnAmountRevs = dirChange.toAngle () / (2 * PI) (конвертировать dirVec -> angle_radians -> revs)

Если вы суммируете переменную jointTurnAmountRevs, CCW, полностью закрытый путь многоугольникаравен 1,0 (+ - EPSILON).Если он полностью закрыт, но CW, вы получите -1.0.

0 голосов
/ 02 апреля 2012

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

Случай B:

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

Случай C:

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

Случай D:

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

Случай E: два ребра перекрываются (пересекаются в бесконечном количестве точек), а их вершины нет.

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

На данный момент я не могу представить ни одного другого случая

...