|
13 / 13 / 1
Регистрация: 19.10.2019
Сообщений: 607
|
|
std::map для k-d дерева28.04.2021, 20:06. Показов 2184. Ответов 28
Метки нет (Все метки)
Добрый день.
Хочу найти SOTA для реализации K-D деревьев. Базовые варианты как я понимаю - либо самому делать структуру, либо использовать что то из стандартной библиотеки. Самый логичный вариант попробовать сочинить что то с использованием std::map, но компаратор у std::map всего один и этот компаратор как должен знать по какой оси ему проводить сравнение. В общем, если не лезть в недра либы, а обойтись стандартным апи пока непонятно как это делать. Сделать свою структурку не проблема, но в стандартной библиотеки уже все оптимизировано и навешено всяких пряников, а тут надо или обойтись скромными возможностями или писать самому. Есть конечно вариант со сторонними библиотека, например CGAL, но хочется обойтись стандартной библиотекой. Добавлено через 5 минут Вот если было понимание как находить корневой узел, то это облегчило бы дело. Никто ведь не запрещает использовать компаратор как статический оператор. Добавлено через 13 минут Пока склоняюсь к мысли создать класс наследник от std::map и переопределить все методы, которые приводят к поиску т.е. это оператор [], find, at В переопределенных методах сбрасывать циклический счетчик осей и вызывать основной метод. Но насколько это решение корректное ?
0
|
|
| 28.04.2021, 20:06 | |
|
Ответы с готовыми решениями:
28
Возможно ли создать контейнер std::map, в котором в качестве значения была бы ссылка на std::map? Emplace в std::map. Как добавить элемент в std::map без копирования?
|
|
13 / 13 / 1
Регистрация: 19.10.2019
Сообщений: 607
|
|
| 28.04.2021, 22:42 [ТС] | |
|
Я правда вынес за скобки вопрос инициализации мапы.
Добавлено через 2 минуты Алексей1153, Можно поподробнее. Взяли получили хеш от чего то там и как они помогу в поиске ближайшей точки ? Есть геохеши, но это не имеет никакого отношения к обычным хешам.
0
|
|
|
фрилансер
6510 / 5773 / 1135
Регистрация: 11.10.2019
Сообщений: 15,428
|
||
| 28.04.2021, 22:54 | ||
uint64_t id точки. Основная мапа - это просто свалка точек. Всё интересное - в индексах. А каждый индекс представляет собой связь id-> координатаПонятно, что нет возможности узнать, в каком первом из трёх индексов (x,y,z) нужно будет начинать искать. Берётся любой, там ищем ближайшие точки. Берём второй, там ищем ближайшие точки. Потом третий пересечение трёх поисков - результат основная затрата времени тут будет на поиск пересечения результатов
0
|
||
|
13 / 13 / 1
Регистрация: 19.10.2019
Сообщений: 607
|
|
| 28.04.2021, 22:59 [ТС] | |
|
Алексей1153, Есть k-d дерево.
Вы придумали что-то лучшее ? Тогда Вам надо срочно начинать диссер писать. Но тут тема про k-d.
0
|
|
|
фрилансер
6510 / 5773 / 1135
Регистрация: 11.10.2019
Сообщений: 15,428
|
||
| 28.04.2021, 23:21 | ||
![]() Добавлено через 1 минуту squareroot, мой вариант не будет, конечно, самый супер-пупер быстрым и оптимальным, но он рабочий на 100%. И его даже можно использовать при проверке супер-пуперского быстрого алгоритма
0
|
||
|
13 / 13 / 1
Регистрация: 19.10.2019
Сообщений: 607
|
|
| 28.04.2021, 23:24 [ТС] | |
|
Алексей1153, Спасибо за желание помочь, но я в
0
|
|
|
фрилансер
6510 / 5773 / 1135
Регистрация: 11.10.2019
Сообщений: 15,428
|
|
| 28.04.2021, 23:34 | |
|
squareroot, кстати, интернет не подсказал мне, что сие обозначает.
Не по теме: Там есть варианты: описание дерева в вики нашлось, но как я там увидел структуру описания узла, я сильно засомневался в его эффективности при реализации на C++
0
|
|
|
13 / 13 / 1
Регистрация: 19.10.2019
Сообщений: 607
|
|
| 28.04.2021, 23:39 [ТС] | |
|
Алексей1153, https://en.wikipedia.org/wiki/State_of_the_art
Добавлено через 3 минуты Наверно куча даёт больше гибкости чем мапа. Наверно стоит подумать в эту сторону.
0
|
|
|
фрилансер
6510 / 5773 / 1135
Регистрация: 11.10.2019
Сообщений: 15,428
|
|
| 28.04.2021, 23:46 | |
|
выражение
State-of-the-art - означает нечто новейшее, современнейшее, насколько я понялну, ок, что на эту тему нам говорит интернет даже статья на всеми любимом хабре имеется
0
|
|
|
13 / 13 / 1
Регистрация: 19.10.2019
Сообщений: 607
|
|
| 28.04.2021, 23:59 [ТС] | |
|
Алексей1153, Я ее видел, но хотелось проверить можно ли брать за основу std::map
Рукотворные деревья штука симпатичная, но бес всякой полезной обвязки, которая есть у контейнеров стандартной библиотеки узко применимая. А писать полноценный класс как то долго.
0
|
|
| 28.04.2021, 23:59 | |
|
Составной ключ для std::map Стоит ли очищать в деструкторе std::map , std::vecotor? std::map, std::vector и порядок обхода коллекции
Заголовочный файл для std::map<string,int> Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Просмотровщик HLP и конвертер в CHM
Argus19 16.11.2026
Просмотровщик HLP и конвертер в CHM
Давно хотел переделать справку Microsoft® Win32® Programmer's Reference, чтобы иметь её под рукой.
Но использовать несколько программ не удобно. Искал другие. . .
|
BitTorrent (версия 7.11 English) и Меню Настройки
russiannick 15.11.2026
Пункты, отвечающие за отключение обновлений в BitTorrent версии 7. 11 (английской)
Options
Preferences
General
Language
|
Транслитерация текста с кириллицы на латиницу (вариант №4)
Maks 15.11.2026
Что-то я перемудрил с предыдущими версиями, в этот раз сделал всё проще, обратившись к функции "СтрокаЛатиницей" из типового общего модуля "СтроковыеФункцииКлиент".
В данной функции нет апострофов,. . .
|
BitTorrent (версия 4.3.9) и Меню Настройки
russiannick 15.11.2026
В меню Настройки можно отключить автоматическое обновление программы.
Карта этого меню приложена ниже.
Нужный пункт выделен красным.
Сервис
Настройки
Поведение
|
|
Транслитерация текста с кириллицы на латиницу (вариант №3)
Maks 15.11.2026
Обновленная версия предыдущей обработки.
Изменения коснулись букв: Ъ, Ы, Ь, Э, отображения которых зависят от положения реквизита "Транслитерация имён".
Изменено отображение буквы Й.
Добавлена. . .
|
Транслитерация текста с кириллицы на латиницу (вариант №2)
Maks 13.11.2026
Обновленная версия ранее созданной обработки.
Добавлено:
- Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .
|
Часы с термометром и праздничным календарем
yariko 12.11.2026
Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы.
Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .
|
Транслитерация текста с кириллицы на латиницу (вариант №1)
Maks 11.11.2026
Решил облегчить жизнь себе и коллегам админам при создании электронных почтовых ящиков для пользователей, в результате написал обработку "Транслитерация текста" с кириллицы на латиницу, а в ней. . .
|