Если у вас не слишком много элементов, просто сравните каждый со всеми остальными. Это может быть намного быстрее, чем вы думаете; современные машины быстры. К сожалению, квадратный фактор рано или поздно вас поймает; Я полагаю, что линейный поиск миллиона объектов не займет слишком много времени, поэтому вам может хватить до 1000 элементов. Использование сетки или даже полос может существенно увеличить это число.
Но я думаю, что вы застряли с деревом квадрантов (особая форма дерева k-d). Вся ваша карта представляет собой один блок, который может содержать четыре подблока (верхний левый, верхний правый, нижний левый, нижний правый). Когда блок заполняется большим количеством элементов, чем вы хотите выполнить линейный поиск, разбейте его на более мелкие и перенесите элементы. (Элементы есть только у листовых узлов.) Легко искать в заданном радиусе от заданной точки. Начните сверху, и если часть блока находится в пределах досягаемости точки, проверьте его подблоки таким же образом, если они есть. Если это не так, проверьте его элементы.
(При поиске «ближайший» будьте осторожны. Квадратная сетка означает, что ближайший объект может находиться в дальнем блоке. Вы должны получить все в пределах заданного радиуса, а затем проверить их все. из 20 вы взяли только 5, вам нужно попробовать больший радиус.Возможно, у вас есть отклоненный предмет, который оказался на расстоянии 30, и вы думаете, что вам следует взять его и несколько других, чтобы составить свои 10. Однако может быть несколько предметы на расстоянии 25, чьи целые блоки были отклонены, и вы хотите их вместо этого. Должно быть лучшее решение для этого, но я еще не понял его. Я просто делаю предположение о радиусе и удваиваю его, пока не получу достаточно.)
Квадраты — это весело. Если вы можете настроить свои данные, а затем получить к ним доступ, это легко. Проблемы возникают, когда ваши отображаемые элементы появляются, исчезают и перемещаются, пока вы пытаетесь выяснить, кто рядом с чем.
person
RalphChapin
schedule
12.07.2012
