Все k ближайших соседей в 2D, C ++

Мне нужно найти для каждой точки набора данных всех ее ближайших соседей. Набор данных содержит ок. 10 миллионов 2D точек. Данные близки к сетке, но не образуют точной сетки ...

Эта опция исключает (на мой взгляд) использование деревьев KD, где основное предположение состоит в том, что никакие точки не имеют одинаковых координаты x и координаты y.

Мне нужен быстрый алгоритм O (n) или лучше (но не слишком сложный для реализации :-))) для решения этой проблемы ... Из-за того, что ускорение не стандартизировано, я не хочу его использовать ...

Спасибо за ваши ответы или образцы кода ...