Извините, ничего не найдено.
Не расстраивайся! Лучше выпей чайку!
|
|
|
|
|
|||||||
| Алгоритмика Об алгоритмах вообще; методы, обсуждения способов решения |
 |
|
|
Опции темы |
16.06.2012, 16:53
|
#1 |
|
Разработчик
Регистрация: 27.06.2009
Адрес: Рязань-Москва
Сообщений: 471
Написано 401 полезных сообщений (для 1,072 пользователей) |
Обработка пересечений
Посоветуйте...
Есть прямоуголная площадка с препятствиями, например в массиве. Нужно сделать что-то типа LinePick`а математически, т.е. обработать к примеру выстрел. Как бы это реализовать наиболее оптимально? Есть мысль использовать алгоритм пересечения линий - проверять на пересечение со всеми объектами в цикле, но мне кажется это будет слишком ресурсоемко... Можт кто-то уж сталкивался с такой проблемой?  |
|
(Offline)
|
|
|
16.06.2012, 17:23
|
#2 |
|
Элита
Регистрация: 16.01.2010
Адрес: Новосибирск
Сообщений: 2,157
Написано 502 полезных сообщений (для 1,012 пользователей) |
Ответ: Обработка пересечений
If(dl<L-(A +B ) //пересеченька где dl заранее подготовленная константа НО придеться считать длины отрезков... Хотя проверку на принадлежность отрезка к расчетам можно сделать "прямоугольником": Линия-есть диагональ прямоугольника, если туда входит точка-считаем,нет-на нет и суда нет
__________________
Сайт: http://iexpo.ml |
|
(Offline)
|
|
| Сообщение было полезно следующим пользователям: |
DStalk (17.06.2012)
|
|
17.06.2012, 22:55
|
#3 |
|
Разработчик
Регистрация: 27.06.2009
Адрес: Рязань-Москва
Сообщений: 471
Написано 401 полезных сообщений (для 1,072 пользователей) |
Ответ: Обработка пересечений
Все препятствия в списке - в виде отрезков с известными координатами. Как быстрее произвести просчет на пересечение линии (выстрела) с отрезками (препятствиями)?
В голову приходит два варианта: 1. Перебирать все препятствия в цикле методом как писал товарищ Greymem в треде Пересечение линий 2. Тоже перебирать все препятствия, но просчитывать углы. Каждое препятствие имеет две точки - ATan2 от положения стреляющего до каждой точки, получаем сектор попадания в это препятствие, далее сравниваем с углом выстрела... Вопрос - как будет быстрее? Кстати в обоих случаях надо будет делать специальную проверку на то препятствие которое ближе всего к стреляющему... |
|
(Offline)
|
|
|
18.06.2012, 01:23
|
#4 |
|
.
Регистрация: 05.08.2006
Сообщений: 10,429
Написано 3,454 полезных сообщений (для 6,863 пользователей) |
Ответ: Обработка пересечений
Если отрезков очень много, и пространство не маленькое, то разбей его на сегменты.
И храни в сегментах списки препятствий а не в общем списке. Если нужно добавь два уровня глубины сегментации пространства - сегмент содержит сектор который уже содержит списки препятствий. Далее проверяй сперва на пересечение AABB - тупо прямоугольник первого отрезка если пересекается с прямоугольником второго, то только тогда проверять на пересечение самих отрезков. Проверка пересечения прямоугольников простая задача - сверяешь минимальные и максимальные значения координат обоих вершин каждого отрезка. Также находить конкретный список сегментов для просчёта - тоже на твоих плечах задача. Таким образом у тебя не будет зависимости от размера пространства, и с ростом площади не будет никакого влияния на просчёт пересечений. Далее главное избегать не нужных операций, таких как просчёт пересечений отрезков если у них даже их Bounding Box'ы не пересекаются. |
|
(Offline)
|
|
| Эти 4 пользователя(ей) сказали Спасибо moka за это полезное сообщение: |
