Структура данных разделения двоичного пространства для двухмерного пространства пончика

У меня есть 2D-карта, которая оборачивается по краям. Поэтому, если вы отойдете от правого края, вы снова окажетесь в левой части карты. То же самое и с тремя другими краями.

Это наследуемая проблема для KDTree, которую я использую для поиска элементов в диапазоне точек. Обычно вы проверяете, сталкивается ли гиперсфера с гиперплоскостью, чтобы увидеть, следует ли продолжать поиск на другой стороне дерева, но эта проверка не работает с обертыванием краев.

Есть ли способ изменить дерево KD для работы с двумерными пространствами пончиков?

9
задан Kasper Holdum 9 October 2017 в 22:37
поделиться