Как определить, есть ли у многоугольника самопересечения?

Question

Представьте, что у вас есть 2D-многоугольник (точнее, 2D замкнутая многоугольная цепочка ). Как вы проверяете, содержит ли он самопересечения? Он может быть выпуклым или вогнутым, ориентированным по часовой стрелке или против часовой стрелки.

Теперь я могу просто запустить стандартный алгоритм O(N log N), чтобы проверить, пересекаются ли какие-либо два сегмента. Но я считаю, что, поскольку у нас есть некоторая дополнительная структура - порядок сегментов и тот факт, что каждые два последовательных сегмента встречаются в конечных точках - может быть разработан более простой и более быстрый (возможно, O(N)?) Алгоритм.

Есть идеи?

Answer 1

Вам нужно просто проверить наличие самопересечений или найти их все?Последний сложнее, чем O(N log N), так как вы можете иметь O(n^2) пересечений с n сегментами.

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