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

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

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

Есть идеи?