Определите, есть ли между собой пересекающиеся сегменты

Question

У меня есть проблема. У меня есть некоторый массив сегментов (их координаты) и нужно определить, какие из них пересекаются. Я знаю, как определить, пересекаются ли 2 сегмента, это немного очевидно, но как делать с массивом сегментов и с хорошим временем. Все, что я знаю, что мы можем использовать AVL-дерево, но я не могу понять, как это сделать. Любое предложение, как это сделать? Заранее спасибо.

Answer 1

Поиск всех пересечений в произвольной группе сегментов является классической задачей, решаемой классическим методом sweep line. В Сети имеется огромное количество информации о том, как использовать линию развертки для решения проблемы пересечения сегментов.

http://www.cs.tufts.edu/comp/163/notes05/seg_intersection_handout.pdf