В прошлом я использовал kd-дерево для решения подобных проблем. Попробуйте получить доступ к статье: Деревья Kd для полудинамики c Наборы точек Джона Луиса Бентли.
В простейшей форме он может найти ближайшего соседа к каждой точке в массивных наборах точек очень быстрый.
Подводя итог, все точки помещаются в ведра при построении дерева kd. Затем, выполняя поиск по каждой точке, вы спускаетесь вниз в дерево, удаляя половину оставшихся точек на каждом шаге с помощью быстрого теста, чтобы определить, на какой стороне стены вы находитесь.
С настройками вы можете выполнить тесты "точка-в-сфере", n-ближайшие соседи и т. д. c.
Для тестов, которые не являются сферически удобными, например, пересечения треугольников и в вашем случае пересечения кривой с кривой, вы можете создать выравнивание по оси. ограничивающий прямоугольник вокруг каждой кривой, и когда вы строите дерево, вы используете центр AABB, чтобы разделить пространство (так же, как с точками), но затем вы делаете еще один проход, где прикрепляете список перекрывающихся AABB к каждому сегменту. , Затем, когда дело доходит до поиска дерева для каждой кривой, вы заканчиваете тем, что проверяете его AABB против блоков, с которыми он перекрывается, и с другими кривыми в списке перекрытий этих блоков. Эти тесты на пересечение AABB очень быстро устраняют большую часть набора (тесты в статье), а затем вам остается выполнить реальный тест на пересечение кривой с несколькими объектами.
Вы получите множество Результаты Google для реализаций kdtree в matlab. Просто убедитесь, что они могут найти пересечения объектов в ограничивающих прямоугольниках.