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

Question

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

Answer 1

Эта проблема по существу эквивалентна обнаружению пересечений в произвольном наборе отрезков.

Например, алгоритм Бентли-Оттмана может быть использован для решения этой проблемы. Конечно, вы можете свернуть, как только найдете одно пересечение.

Наивная проверка будет просто проверять каждое ребро по сравнению с любым другим ребром (которое не является смежным в многоугольнике, потому что они не могут пересекаться), но, поскольку вам просто нужно найти одно пересечение, чувствительное к выходу алгоритмы (например, bentley-otmann) могут значительно ускорить проверку.