алгоритм точки сетки (поиск точки в сетке)

Я ищу алгоритм, такой как алгоритм ближайшей пары точек

Вместо произвольного расстояния между всеми точками у меня есть сеточная система, в которой 4 точки - это верхний правый, нижний правый, верхний левый и нижний левый соответственно. Это сохраняет расстояние между всеми точками постоянным.

скажем, например, если бы я поместил внешнюю точку на эту сетку, мне нужно было бы найти, в каком квадрате сетки она будет, предполагая, что путем нахождения ближайших 4 точек (что дает мне конечные точки квадрата сетки).

Я собирался реализовать алгоритм для ближайших точек, но поскольку все точки все время находятся на одинаковом расстоянии друг от друга, я не знал, заслуживает ли это другого, более эффективного алгоритма.

Мне действительно не нужно подробное объяснение ответа, просто указание в правильном направлении.


algorithm euclidean-distance
person Jake B    schedule 02.06.2013    source источник
comment
Чтобы уточнить; у вас есть сетка из квадратов, и вы хотите знать, в каком квадрате находится произвольная точка? (Если не в этом, то наверное стоит добавить схему в свой пост ...)   -  person Oliver Charlesworth    schedule 02.06.2013
comment
нет, это именно то, что мне нужно сделать. Я предположил, что поиск 4 конечных точек сетки (верхний правый, нижний правый, верхний левый и нижний левый) будет наиболее эффективным способом.   -  person Jake B    schedule 02.06.2013

Ответы (1)


arrow_upward
2
arrow_downward

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

Разделите свое координатное пространство на фиксированное количество линий сетки в направлениях X и Y (что, кажется, вы уже сделали, равномерно расположив эти 4 точки).

Когда вы вставляете точку, разделите ее расстояние (целочисленное деление) от начала координат по осям X и Y на интервал шага сетки. Затем у вас остаются две координаты, которые определяют ближайшее пересечение сетки X / Y. Используйте остаток, чтобы определить, к какой стороне пересечения сетки принадлежит ваша точка.

Если вы хотите усложнить задачу, вы можете начать использовать kD-Trees и т. Д., Но я думаю, что этот пример достаточно прост, чтобы не требовать более сложного пространственного разделения.

person Andon M. Coleman    schedule 02.06.2013
comment
Спасибо за ваш совет, небольшое пояснение, когда вы говорите разделите расстояние от начала координат в направлениях X и Y на интервал шага вашей сетки. вы имеете в виду разделите его компоненты x и y, скажем, на 5 (размер каждого квадрата сетки) это даст мне (x, y) * 5 - ближайшее пересечение сетки? - person Jake B; 02.06.2013
comment
Да, допустим, у вас есть точка (100,50). Ваша сетка настроена так, чтобы иметь одинаковую ширину по X и Y (в данном случае 5), вы должны разделить 100/5 = 20, 50/5 = 10. Ваша точка фактически будет лежать точно на границе ячейки сетки (20 , 10). И это даст вам знать, что вы можете вставить его в эту ячейку; если бы был остаток в направлении X или Y, вы, вероятно, захотели бы протолкнуть его в следующую по высоте ячейку в этом направлении. - person Andon M. Coleman; 03.06.2013
comment
Спасибо за помощь. Это кажется намного более простым, чем то, о чем я думал. - person Jake B; 03.06.2013