Тема: Пересечения отрезков.

Помогите, пожалуйста, с задачей. Для каждого отрезка найти количество других отрезков, с которыми он пересекается. Может имеется какой-либо алгоритм? Простой перебор не зайдет..

2

Re: Пересечения отрезков.

Такие задачи обычно решаются методом  sweep line (заметающей прямой)

Re: Пересечения отрезков.

А где можно поподробнее узнать об этом методе? Посоветуйте, пожалуйста, какую-нибудь литературу на эту тему.

4

Re: Пересечения отрезков.

Рядом подобная задача: http://e-maxx.ru/algo/intersecting_segments
Поиск всех пересечений:  http://ru.wikipedia.org/wiki/Алгоритм_Бентли_—_Оттмана
http://www.cs.tufts.edu/comp/163/notes0 … andout.pdf

Re: Пересечения отрезков.

Спасибо большое!!!:)