|
Пересечение отрезка с масивом отрезков
Собствено сабж, нужно определить пересекается ли наш отрезок с каким либо из массива отрезков... Отрезки представлены плоскими прямоугольными координатами 2х точек их концов.
Решение проблемы "влоб" - в цикле перебирает все отрезки и проверяем каждый на пересечение с исходным..
Оценка производительности О(N) в худшем случае, и O(N/2) в среднем... что есть достаточно много.
Вопрос как извавиться от полного перебора? Можед деревья?
__________________
|