Тема: Пересечения отрезков.
Помогите, пожалуйста, с задачей. Для каждого отрезка найти количество других отрезков, с которыми он пересекается. Может имеется какой-либо алгоритм? Простой перебор не зайдет..
Re: Пересечения отрезков.
Такие задачи обычно решаются методом sweep line (заметающей прямой)
Re: Пересечения отрезков.
А где можно поподробнее узнать об этом методе? Посоветуйте, пожалуйста, какую-нибудь литературу на эту тему.
Re: Пересечения отрезков.
Рядом подобная задача: http://e-maxx.ru/algo/intersecting_segments
Поиск всех пересечений: http://ru.wikipedia.org/wiki/Алгоритм_Бентли_—_Оттмана
http://www.cs.tufts.edu/comp/163/notes0 … andout.pdf
Re: Пересечения отрезков.
Спасибо большое!!!:)