C ++: Найти соседние точки сетки из калибровочного изображения из несортированного списка

У меня есть 4 списка координат x и y точек калибровки. Те в нет конкретного заказа и не выровнены по какой-либо оси (они получены из реальной калибровочной картинки с небольшим поворотом и искажением), но списки имеют одинаковую индексацию и не может быть отсортировано таким образом, что каждый список возрастает / убывает. Они также содержат не целочисленные значения, а с плавающей точкой. Сейчас я пытаюсь найти четыре соседние точки для данной точки.

Например. поиск соседей точки [150,150] вернул бы [140,140], [140,160], [160,140], [160,160] (за исключением того, что они на самом деле больше похожи на [139.581239,138.28812]).

На данный момент я должен просмотреть все точки калибровки для каждой точки, чтобы проверить. Есть около 500 точек калибровки.

Позже во время этого процесса мне нужно будет знать 4 соседей для случайной точки в сетке 1600×1400 несколько миллионов раз. Поэтому очень важно найти эти точки как можно быстрее, чтобы избежать расчета времени дней или даже недель.

Мой первый подход состоял в проверке каждой из ~ 500 калибровочных точек для каждой точки, чтобы проверить и посмотреть их относительное положение относительно контрольной точки (x_calib> x и y_calib> y будут где-то в верхней, правой области точки) и вычислить их расстояние до него. Ближайшая точка в каждой области (вверху слева, вверху справа, внизу слева, внизу справа) будет соответствующей соседней точкой. Кажется, это не совсем эффективно и занимает много времени.

Вторым подходом было создание радужной таблицы для каждой из точек 1600×1400 и сохранение соответствующих соседей (а точнее, сохранение индекса в списке координат). Позже, процесс будет проверять эту радужную таблицу в позициях [x, y, 0], [x, y, 1], [x, y, 2] и [x, y, 3], чтобы получить 4 индекса 4 соседних очка. Хотя вычисление радужной таблицы занимает некоторое время (~ 20 минут для этих ~ 2 миллионов точек), этот подход ускоряет последующую обработку. К сожалению, этот подход затрудняет отладку последующих этапов процесса, потому что требуется много времени, прежде чем остальные запустятся.

Я все еще думаю, что должно быть место для оптимизации, и я был бы признателен за любое предложение или помощь, чтобы ускорить все это. Я уже читал о kd-дереве, но не совсем видел возможность использовать его здесь. Я надеюсь, что есть подход для такого рода несортированного (и несортируемого) списка точек, который более эффективен, чем радужный стол — или который по крайней мере быстрее при создании таблицы.

Заранее спасибо!