|
Ответ: Обработка пересечений
Если отрезков очень много, и пространство не маленькое, то разбей его на сегменты.
И храни в сегментах списки препятствий а не в общем списке. Если нужно добавь два уровня глубины сегментации пространства - сегмент содержит сектор который уже содержит списки препятствий.
Далее проверяй сперва на пересечение AABB - тупо прямоугольник первого отрезка если пересекается с прямоугольником второго, то только тогда проверять на пересечение самих отрезков. Проверка пересечения прямоугольников простая задача - сверяешь минимальные и максимальные значения координат обоих вершин каждого отрезка.
Также находить конкретный список сегментов для просчёта - тоже на твоих плечах задача.
Таким образом у тебя не будет зависимости от размера пространства, и с ростом площади не будет никакого влияния на просчёт пересечений.
Далее главное избегать не нужных операций, таких как просчёт пересечений отрезков если у них даже их Bounding Box'ы не пересекаются.
|