Обработка пересечений
 

Посоветуйте...
Есть прямоуголная площадка с препятствиями, например в массиве. Нужно сделать что-то типа LinePick`а математически, т.е. обработать к примеру выстрел. Как бы это реализовать наиболее оптимально?
Есть мысль использовать алгоритм пересечения линий - проверять на пересечение со всеми объектами в цикле, но мне кажется это будет слишком ресурсоемко...
Можт кто-то уж сталкивался с такой проблемой?:)

Ответ: Обработка пересечений
 

Вложение 17041
If(dl<L-(A +B )
//пересеченька
где dl заранее подготовленная константа
НО придеться считать длины отрезков...
Хотя проверку на принадлежность отрезка к расчетам можно сделать "прямоугольником":
Линия-есть диагональ прямоугольника, если туда входит точка-считаем,нет-на нет и суда нет

Ответ: Обработка пересечений
 

Все препятствия в списке - в виде отрезков с известными координатами. Как быстрее произвести просчет на пересечение линии (выстрела) с отрезками (препятствиями)?

В голову приходит два варианта:
1. Перебирать все препятствия в цикле методом как писал товарищ Greymem в треде Пересечение линий

2. Тоже перебирать все препятствия, но просчитывать углы. Каждое препятствие имеет две точки - ATan2 от положения стреляющего до каждой точки, получаем сектор попадания в это препятствие, далее сравниваем с углом выстрела...

Вопрос - как будет быстрее?
Кстати в обоих случаях надо будет делать специальную проверку на то препятствие которое ближе всего к стреляющему...

Ответ: Обработка пересечений
 

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

Также находить конкретный список сегментов для просчёта - тоже на твоих плечах задача.

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