алгоритма точки сетки (нахождение точки в сетке)

Question

Я ищу для алгоритма, таких как closest pair of points algorithm

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

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

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

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

Answer 1

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

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

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

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