HLFX.Ru Forum
профиль •  правила •  регистрация •  календарь •  народ •  FAQ •  поиск •  новое •  сутки •  главная •  выход  
HLFX.Ru Forum HLFX.Ru Forum > Наш форум > Технические вопросы > Поиск ближайшего соседа для точки в пространстве
  Предыдущая тема   Следующая тема
Автор
Тема Новая тема    Ответить
SNMetamorph
Житель форума

Дата регистрации: Jun 2018
Проживает: Ижевск
Сообщений: 560

Рейтинг



Поиск ближайшего соседа для точки в пространстве

Есть у меня список точек с их координатами, находящихся в рандомных местах на карте. Стоит задача найти соседей возле определенной точки в пространстве в некоем радиусе из этого списка. Как это можно сделать быстрее, чем линейным перебором? Учитывая, что все это происходит в контексте голдсурса, где можно BSP-дерево использовать для каких-то своих целей.

__________________
PrimeXT
GoldSrc Monitor
SMD Splitter
mdl-flip (gFlip analog)
Xash3D Modding Discord

Сообщить модератору | | IP: Записан
Сообщение: 195440

Старое сообщение 06-07-2020 13:09
- За что?
ncuxonaT
каков стол, таков и стул

Группа: Опытный
Дата регистрации: Oct 2009
Проживает: город/село/деревня
Сообщений: 1626
Возраст: 33

Рейтинг



kd деревья хорошо для этого подходят

Сообщить модератору | | IP: Записан
Сообщение: 195441

Старое сообщение 06-07-2020 13:19
- За что?
SNMetamorph
Житель форума

Дата регистрации: Jun 2018
Проживает: Ижевск
Сообщений: 560

Рейтинг



А сам алгоритм в чем заключается? Со всякими деревьями и теорией информатики у меня пока дела плохо обстоят, было бы хорошо если кто-то указал где можно найти информацию по этой теме.

__________________
PrimeXT
GoldSrc Monitor
SMD Splitter
mdl-flip (gFlip analog)
Xash3D Modding Discord

Сообщить модератору | | IP: Записан
Сообщение: 195442

Старое сообщение 06-07-2020 13:25
- За что?
ncuxonaT
каков стол, таков и стул

Группа: Опытный
Дата регистрации: Oct 2009
Проживает: город/село/деревня
Сообщений: 1626
Возраст: 33

Рейтинг



SNMetamorph алгоритм есть на википедии
https://ru.wikipedia.org/wiki/K-d_%...%B5%D0%B2%D0%BE
Если дела плохо обстоят, можно другие варианты рассмотреть. Ты говоришь про БСП - точки являются частью карты, и для них уже построено дерево?

Сообщить модератору | | IP: Записан
Сообщение: 195447

Старое сообщение 06-07-2020 15:15
- За что?
 Дядя Миша
racing for fish

Дата регистрации: Oct 2005
Проживает: Кубань
Сообщений: 32188
Нанёс повреждений: 392 ед.

Рейтинг



Цитата:
SNMetamorph писал:
Как это можно сделать быстрее, чем линейным перебором?

сколько у тебя точек?

__________________
My Projects: download page

F.A.Q по XashNT
Блог разработчика в телеграме

Цитата:

C:\DOCUME~1\C4C5~1\LOCALS~1\Temp\a33328if(72) : see declaration of 'size_t'

Сообщить модератору | | IP: Записан
Сообщение: 195451

Старое сообщение 06-07-2020 15:51
-
SNMetamorph
Житель форума

Дата регистрации: Jun 2018
Проживает: Ижевск
Сообщений: 560

Рейтинг



Цитата:
Дядя Миша писал:
сколько у тебя точек?

В среднем несколько тысяч, ну максимум 10-15 тысяч.

__________________
PrimeXT
GoldSrc Monitor
SMD Splitter
mdl-flip (gFlip analog)
Xash3D Modding Discord

Сообщить модератору | | IP: Записан
Сообщение: 195463

Старое сообщение 07-07-2020 06:41
- За что?
 Дядя Миша
racing for fish

Дата регистрации: Oct 2005
Проживает: Кубань
Сообщений: 32188
Нанёс повреждений: 392 ед.

Рейтинг



SNMetamorph ты можешь их в AABB-tree затолкать, типа того, в которое линкуются энтити в квейке-халфе. KD-tree там избыточно, его сложнее строить.

__________________
My Projects: download page

F.A.Q по XashNT
Блог разработчика в телеграме

Цитата:

C:\DOCUME~1\C4C5~1\LOCALS~1\Temp\a33328if(72) : see declaration of 'size_t'

Сообщить модератору | | IP: Записан
Сообщение: 195468

Старое сообщение 07-07-2020 08:27
-
SNMetamorph
Житель форума

Дата регистрации: Jun 2018
Проживает: Ижевск
Сообщений: 560

Рейтинг



Проблема еще в том, что они могут постоянно менять своё расположение.

__________________
PrimeXT
GoldSrc Monitor
SMD Splitter
mdl-flip (gFlip analog)
Xash3D Modding Discord

Сообщить модератору | | IP: Записан
Сообщение: 195472

Старое сообщение 07-07-2020 09:39
- За что?
 Дядя Миша
racing for fish

Дата регистрации: Oct 2005
Проживает: Кубань
Сообщений: 32188
Нанёс повреждений: 392 ед.

Рейтинг



Цитата:
SNMetamorph писал:
Проблема еще в том, что они могут постоянно менять своё расположение.

Вот AABB-tree идеально для этого подходит. Энтити ведь тоже постоянно меняют своё положение, думаешь что делает UTIL_SetOrigin? Из одного узла дерева убирает, в другой добавляет.

__________________
My Projects: download page

F.A.Q по XashNT
Блог разработчика в телеграме

Цитата:

C:\DOCUME~1\C4C5~1\LOCALS~1\Temp\a33328if(72) : see declaration of 'size_t'

Сообщить модератору | | IP: Записан
Сообщение: 195475

Старое сообщение 07-07-2020 11:16
-
SNMetamorph
Житель форума

Дата регистрации: Jun 2018
Проживает: Ижевск
Сообщений: 560

Рейтинг



Цитата:
Дядя Миша писал:
AABB-tree

А как его построить собственно?

__________________
PrimeXT
GoldSrc Monitor
SMD Splitter
mdl-flip (gFlip analog)
Xash3D Modding Discord

Сообщить модератору | | IP: Записан
Сообщение: 200664

Старое сообщение 23-03-2021 17:06
- За что?
 Дядя Миша
racing for fish

Дата регистрации: Oct 2005
Проживает: Кубань
Сообщений: 32188
Нанёс повреждений: 392 ед.

Рейтинг



Делишь боксы до желаемого объема и линкуешь к ним все объекты, которые имели неосторожность их пересечь. Ну или полностью уместились внутри.
Это немного разные типы деревьев, в вики можешь глянуть.

__________________
My Projects: download page

F.A.Q по XashNT
Блог разработчика в телеграме

Цитата:

C:\DOCUME~1\C4C5~1\LOCALS~1\Temp\a33328if(72) : see declaration of 'size_t'

Сообщить модератору | | IP: Записан
Сообщение: 200665

Старое сообщение 23-03-2021 17:29
-
Тема: (Опционально)
Ваш ответ:



Переводчик транслита


[проверить длину сообщения]
Опции: Автоматическое формирование ссылок: автоматически добавлять [url] и [/url] вокруг интернет адресов.
Уведомление по E-Mail: отправить вам уведомление, если кто-то ответил в тему (только для зарегистрированных пользователей).
Отключить смайлики в сообщении: не преобразовывать текстовые смайлики в картинки.
Показать подпись: добавить вашу подпись в конец сообщения (только зарегистрированные пользователи могут иметь подписи).

Временная зона GMT. Текущее время 17:53. Новая тема    Ответить
  Предыдущая тема   Следующая тема
HLFX.Ru Forum HLFX.Ru Forum > Наш форум > Технические вопросы > Поиск ближайшего соседа для точки в пространстве
Версия для печати | Отправить тему по E-Mail | Подписаться на эту тему

Быстрый переход:
Оцените эту тему:

Правила Форума:
Вы not можете создавать новые темы
Вы not можете отвечать в темы
Вы not можете прикреплять вложения
Вы not можете редактировать ваши сообщения
HTML Код ВЫКЛ
vB Код ВКЛ
Смайлики ВКЛ
[IMG] Код ВКЛ
 

< Обратная связь - HLFX.ru >

На основе vBulletin
Авторское право © 2000 - 2002, Jelsoft Enterprises Limited.
Дизайн и программирование: Crystice Softworks © 2005 - 2024