Извините, ничего не найдено.

Не расстраивайся! Лучше выпей чайку!
Регистрация
Справка
Календарь

Вернуться   forum.boolean.name > Программирование в широком смысле слова > Алгоритмика

Алгоритмика Об алгоритмах вообще; методы, обсуждения способов решения

Ответ
 
Опции темы
Старый 28.05.2014, 12:58   #1
Reizel
Задрот
 
Аватар для Reizel
 
Регистрация: 24.07.2009
Адрес: Ивановская область, г. Кинешма
Сообщений: 1,574
Написано 407 полезных сообщений
(для 863 пользователей)
Поиск ближайшей точки в трёхмерном массиве

Т.е. есть массив размерностью X,Y,Z содержащий некие структуры. Но они есть не во всех клетках, в большинстве они заполнены null.

Задача: на вход функция принимает координаты ячейки в этом массиве, и если по ним расположен NULL - алгоритму нужно ОЧЕНЬ быстро найти ближайшую "точку-не-null"

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

Ещё сделал для оптимизации - в массиве могут храниться как сами объекты, так и ссылки на эти объекты. Т.е. если алгоритм уже искал в точке {x,y,z} ближайшую, он по этим координатам забъёт ссылку на найденный результат, чтобы второй раз не ходить типа кэш. Но всё это очень медленно, может уже есть какие нибудь алгоритмы оптимизации?

Подскажите в каком направлении читать, а то я даже запрос в гугл не могу правильно состряпать
(Offline)
 
Ответить с цитированием
Старый 28.05.2014, 13:01   #2
SBJoker
Злобный Админ
 
Аватар для SBJoker
 
Регистрация: 04.09.2005
Сообщений: 5,926
Написано 3,415 полезных сообщений
(для 9,330 пользователей)
Ответ: Поиск ближайшей точки в трёхмерном массиве

BSP деревья в помощь
или
OcTree
__________________
(Offline)
 
Ответить с цитированием
Старый 28.05.2014, 14:22   #3
Nex
Гигант индустрии
 
Аватар для Nex
 
Регистрация: 13.09.2008
Сообщений: 2,893
Написано 1,185 полезных сообщений
(для 3,298 пользователей)
Ответ: Поиск ближайшей точки в трёхмерном массиве

Волновой алгоритм может быть подойдет.
(Offline)
 
Ответить с цитированием
Ответ


Опции темы

Ваши права в разделе
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.


Часовой пояс GMT +4, время: 18:58.


vBulletin® Version 3.6.5.
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Перевод: zCarot
Style crйe par Allan - vBulletin-Ressources.com