HLFX.Ru Forum
Показать все 11 сообщений этой темы на одной странице

HLFX.Ru Forum (https://hlfx.ru/forum/index.php)
- Технические вопросы (https://hlfx.ru/forum/forumdisplay.php?forumid=20)
-- Поиск ближайшего соседа для точки в пространстве (https://hlfx.ru/forum/showthread.php?threadid=5535)

Отправлено SNMetamorph 06-07-2020 в 13:09:

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

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

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

Отправлено ncuxonaT 06-07-2020 в 13:19:

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

Отправлено SNMetamorph 06-07-2020 в 13:25:

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

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

Отправлено ncuxonaT 06-07-2020 в 15:15:

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

Отправлено Дядя Миша 06-07-2020 в 15:51:

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

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

__________________
My Projects: download page

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

Цитата:

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

Отправлено SNMetamorph 07-07-2020 в 06:41:

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

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

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

Отправлено Дядя Миша 07-07-2020 в 08:27:

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'

Отправлено SNMetamorph 07-07-2020 в 09:39:

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

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

Отправлено Дядя Миша 07-07-2020 в 11:16:

Цитата:
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'

Отправлено SNMetamorph 23-03-2021 в 17:06:

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

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

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

Отправлено Дядя Миша 23-03-2021 в 17:29:

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

__________________
My Projects: download page

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

Цитата:

C:\DOCUME~1\C4C5~1\LOCALS~1\Temp\a33328if(72) : see declaration of 'size_t'
Временная зона GMT. Текущее время 11:08.
Показать все 11 сообщений этой темы на одной странице

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