Собствено сабж, нужно определить пересекается ли наш отрезок с каким либо из массива отрезков... Отрезки представлены плоскими прямоугольными координатами 2х точек их концов.
Решение проблемы "влоб" - в цикле перебирает все отрезки и проверяем каждый на пересечение с исходным..
Оценка производительности О(N) в худшем случае, и O(N/2) в среднем... что есть достаточно много.
Вопрос как извавиться от полного перебора? Можед деревья?
SBJoker
координаты отрезков которые в масиве часто меняются ?
если нет - то octree и прочие деревья тут имеют место быть
если да - сам задаюсь таким вопросом
Сообщений: 10,429
Написано 3,454 полезных сообщений (для 6,863 пользователей)
Re: Пересечение отрезка с масивом отрезков
Про перебор хз, но вот насчёт проверки перед коллизией, на BB (Bounding Box) обязательно нужно, и это увеличит производительность на много. Вот кстати функции если нужно.