Пересечение отрезка с масивом отрезков
 

Собствено сабж, нужно определить пересекается ли наш отрезок с каким либо из массива отрезков... Отрезки представлены плоскими прямоугольными координатами 2х точек их концов.

Решение проблемы "влоб" - в цикле перебирает все отрезки и проверяем каждый на пересечение с исходным..

Оценка производительности О(N) в худшем случае, и O(N/2) в среднем... что есть достаточно много.

Вопрос как извавиться от полного перебора? Можед деревья?

Re: Пересечение отрезка с масивом отрезков
 

SBJoker
координаты отрезков которые в масиве часто меняются ?
если нет - то octree и прочие деревья тут имеют место быть
если да - сам задаюсь таким вопросом

Re: Пересечение отрезка с масивом отрезков
 

Нет отрезки статичны дальше некуда... поясни про octree или линкой или примером..

Re: Пересечение отрезка с масивом отрезков
 

ответил тут http://www.boolean.name/showthread.p...0082#post70082

Re: Пересечение отрезка с масивом отрезков
 

Да quadtree дал 10 кратный прирост общей производительности..т.е. сам квадтри дал куда большую скорость на отдельной задаче нахождения пересечений.

Re: Пересечение отрезка с масивом отрезков
 

SBJoker
тоесть O(log(N)) все же достигли ? :) или там ~O(log(N)*2) ?

Re: Пересечение отрезка с масивом отрезков
 

Про перебор хз, но вот насчёт проверки перед коллизией, на BB (Bounding Box) обязательно нужно, и это увеличит производительность на много.
Вот кстати функции если нужно.