AntipichДобрый день.
Есть у меня такая задача:
Есть множество N точек на плоскости. Оно фиксированное.
Есть произвольная точка p.
Задача - найти из множества N точку, ближайшую к p.
Везде в интернете ссылаются на kd деревья или диаграмму Вороного.
Но я хоть убей не могу понять, как они применимы именно к этой задаче.

Вот взять диаграмму Вороного.
https://ru.wikipedia.org/wiki/Диаграмма_Вороного
http://neerc.ifmo.ru/wiki/index.php?title=Диаграмма_Вороного

Ну разбили мы на ячейки. А дальше что? Как понять, в какую ячейку попадает наша точка? Как пользоваться этими алгоритмами в данном случае?

Заранее благодарю за помощь.

Зачем усложнять.
Делаете массв точек и 2 массива указателей на точки
для осей координат.
Массивы указателей на точки сортируете по возрастанию координат

Берете на вход точку ищете точки в массиве указателей
между которыми
нужно вставить вашу новою точку.
Из 2-х соседних выбираете ту, которая ближе.

ДохтаРAntipichДобрый день.
Есть у меня такая задача:
Есть множество N точек на плоскости. Оно фиксированное.
Есть произвольная точка p.
Задача - найти из множества N точку, ближайшую к p.
Везде в интернете ссылаются на kd деревья или диаграмму Вороного.
Но я хоть убей не могу понять, как они применимы именно к этой задаче.

Вот взять диаграмму Вороного.
https://ru.wikipedia.org/wiki/Диаграмма_Вороного
http://neerc.ifmo.ru/wiki/index.php?title=Диаграмма_Вороного

Ну разбили мы на ячейки. А дальше что? Как понять, в какую ячейку попадает наша точка? Как пользоваться этими алгоритмами в данном случае?

Заранее благодарю за помощь.

Зачем усложнять.
Делаете массв точек и 2 массива указателей на точки
для осей координат.
Массивы указателей на точки сортируете по возрастанию координат

Берете на вход точку ищете точки в массиве указателей
между которыми
нужно вставить вашу новою точку.
Из 2-х соседних выбираете ту, которая ближе.

Можно обойтись и 2 массивам , массив с точками отсортировать
значению оси Х
а массив указателей на эти точки отсортировать по значению оси Y.
Делаете поиск методом половинного деления
типа для вставки координат новой точки.
Получаете координаты 2-х ближайших точек, из них выбираете
ту которая ближе к вашей точке.

maytonДохтаРМассивы указателей на точки сортируете по возрастанию координат

По какому возрастанию координат?

Х и Y.

Первый массив
1 1,5
2 3.2
3 4.1
4 8.7
5 9.4

второй массив
3
2
5
1
4

на вход приходит точка с координатами 5.3
Ближайшие точки 4.1 , 8.7 , 3.2 , 9.4

Ошибся будет выбор из 4 точек.
Из них нужно выбрать самую близ лежащую.

То есть методом половинного деления задача сводится
к выбору из 4 точек.

maytonДохтаРМассивы указателей на точки сортируете по возрастанию координат

По какому возрастанию координат?

Массив точек сортируется по возрастанию координаты Х
Массив указателей на точку
сортируется по возрастанию значения координат Y точек на которые они
ссылаются .

Если точек очень много, то вместо массива нужно строить дерево блоков
и подбирать их размер под линейку кеша процессора, что бы
половинное деление не продувало кеши.
Но это уже следующий этап оптимизации.

maytonДохтаР, я убеждён что корректность результата зависит от выбора направления
ранжирования точек. К примеру сверху-вниз + слева направо в силу дихотомии
пропускают важную точку которая лежит на 2 ячейки от искомой.

Тоже самое если ты выбираешь обход слева направо + сверху вниз я могу
указать такие исходные данные при которых ты промахнёшся мимо нужной точки.

ИМХО
Не промахнусь.
в одномерной системе координат задача оптимизируется
до 2 ближайших точек,
в двухмерной системе координат до 4
, в трех мерной до 9 .
итд....

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

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

maytonДохтаРПодумал ничего не придумал
в 2- мерной системе координат алгоритм
выходит 4 точки , из который нужно выбрать ближайшую
собрав в отдельный массив и отсортировав по длине гипотенуз
прямоугольные треугольники .
ОК. Возможно я не так понял твою сортировку.
Давай исходник. Можно на псевдо-языке.


Извини что с большой задержкой , я было начал реализовывать идею в коде
и погряз в реализиции а потом отвлекся и забыл.
Приблизительный алгоритм сортировки описан тут для более простого случая:
18534524

ДохтаРmaytonпропущено...

ОК. Возможно я не так понял твою сортировку.
Давай исходник. Можно на псевдо-языке.


Извини что с большой задержкой , я было начал реализовывать идею в коде
и погряз в реализиции а потом отвлекся и забыл.
Приблизительный алгоритм сортировки описан тут для более простого случая:
18534524


Суть идеи в том что сначала массив точек нужно отсорировать
отдельно по каждой координате.
Потом поиском в диапазоне по Х Y ищется ближайшая, через расчет
разности гипотинуз.
Реализация достаточно просто масштабирется
до пространства любой размерности, вплодь до дефайном или параметром.

У меня сначала было желание реализовать универсальный поисковик ,
для разумной многомерности пространства, но я не нашел ему практического
применения и бысро потерял мотивацию.