Ближайшая точка из списка для каждой точки другого списка

Вы вступаете в целое поле интересных подходов к этой проблеме. Термины для Google — это двоичное разбиение пространства, деревья квадрантов и, конечно же, поиск ближайшего соседа.

Относительно простой, но эффективный подход, когда точки разбросаны гораздо больше, чем их «видимый диапазон»:

1. Выберите значение «размер сетки».
2. Создайте карту из координат сетки в список/набор сущностей
3. Для каждого источника пищи: поместите их на карту в их координатах сетки.
4. Для каждой точки: поместите их на карту в их координаты сетки и также в соседние "ячейки" сетки. Размер окрестности зависит от размера сетки и значения видимости точки.
5. Для каждой записи на карте, которая содержит хотя бы одну точку: либо выполните этот алгоритм рекурсивно с меньшим размером сетки, либо используйте подход грубой силы: проверьте каждую точку в этой ячейке сетки по каждому источнику пищи в этой ячейке сетки.

Это линейный алгоритм по сравнению с подходом квадратичного перебора.

Расчет координат сетки: grid_x = int(x / grid_size) ... то же самое для других координат.

Окрестность: steps = ceil(sight_value / grid_size) .. окрестность представляет собой квадрат со стороной 2×steps + 1 с центром в координатах сетки точки

Я считаю ваш подход неверным. Это можно проверить математически. Вместо этого вы можете рассчитать величину вектора, соединяющего точку с источником пищи, с помощью теоремы Пифагора и убедиться, что эта величина меньше предела наблюдения. Это касается исключительно определения относительного расстояния, определяемого декартовой системой координат, и стандартной единицей измерения. Что касается вопросов эффективности, в первую очередь необходимо определить, является ли применяемый подход с точки зрения вычислений в действительности менее эффективным с точки зрения времени, даже если логический компонент, ответственный за определенные расчеты, в силу этой альтернативы внедрение, занимает меньше времени. Грубо говоря, идеальным является тот, в котором затрачиваемое время уменьшается, а не просто численно ограничивается посредством рефакторинга. Теперь, если дело обстоит так, что положение точки может быть определено как любые два числа, которые можно выбрать, это, конечно, подразумевает систему отсчета, называемую базисом, а также систему, локальную для рассматриваемой точки. В отношении обоих можно количественно определить положение и другие подобные характеристики и свойства. В результате этого наблюдения может показаться, что вам нужно n*2 структур данных, где n — количество точек в окружении, содержащих отсортированные значения относительно каждой точки, и, откровенно говоря, неясно, так это или нет. подход будет даже работать или является оптимальным. Вы указываете проектное и программное ограничение, заключающееся в том, что решение не должно вычислять расстояния от каждой точки до каждого источника пищи. Но для этого необходимо реализовать другие подобные процедуры, чтобы получить правильные результаты. Эти комментарии сделаны в связи с моим обсуждением эффективности. Поэтому вам может быть лучше просто рассчитать расстояние в каждом случае. Это несколько элегантно.