Извините, ничего не найдено.

SBJoker · 11.12.2007, 20:31

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

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

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

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

11.12.2007, 21:35

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

SBJoker · 11.12.2007, 22:01

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

11.12.2007, 22:13

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

SBJoker · 13.12.2007, 13:24

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

13.12.2007, 13:55

SBJoker
тоесть O(log(N)) все же достигли ?

или там ~O(log(N)*2) ?

moka · 13.12.2007, 14:15

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