Нахождение ближайших соседей (помогите выбрать алгоритм)

Или ты задачу не до конца объяснил или тебя научить как расстояние между двумя точками считать?

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

А ты, кажется, предлагаешь мне сочинить велосипед с решением в лоб с полным перебором. Или нет?

Для каждой точки необходимо найти ближайших соседей.

Сколько-то ближайших? Или в определённом радиусе?

Прочитай внимательно все что я написал в топике. Там все написано.

Ограничением является только расположение соседей, т.е. например, для двумерного пространства, соседи будут являться вершинами (обязательно выпуклого) N-угольника минимальной площади.

исходная точка при этом где должна находиться? лежать внутри N-угольника, на грани, являться вершиной?

если минимальной площади то это всегда будет треугольник...

https://www.youtube.com/watch?v=uf1ky464340 не за что

Внутри. Треугольник? Верное утверждение! Меня это устраивает!

О! Это гляну!

судя по постановке задачи - читать про кластерный анализ

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

При этом замечу что треугольник минимальной площади на случайном наборе точек с большой вероятностью получится с длинным основанием и минимальной высотой (три точки, «почти» лежащие на одной прямой), расположен он будет черт те как, и при этом будет ближайшим для большого количества точек, не смотря на то что расстояние до его вершин будет большим. Поэтому, с одной стороны, поиск его вершин не получится ограничить какой-то окрестностью, и честно это решается за N³logN (N базовых точек, для каждой 2 вершины ищутся перебором, 3-я ищется максимально близко к получившейся из первых двух прямой, можно за логарифм, с другой можно просто найти K треугольников минимальной площади за N²logN и выбрать для каждой вершины наиболее удовлетворяющий условию (ближайший * минимальной площади).

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

Если у тебя есть один набор точек, по которому надо сделать многократный поиск, то сортируешь весь набор по одной координате. Перебираешь массив в стороны от целевой точки до тех пор, пока не найдешь нужное количество ближайших. Как правило тебе не понадобится перебирать весь массив, а только ближайшую группу. O(N*logN) на сортировку и O(N) на поиск, в надежде, что O(N) выродится в нечто гораздо меньшее.

Если в каждом поиске массив новый, то перебирать весь массив. Хочешь - не хочешь, а здесь O(N).

Ограничением является только расположение соседей, т.е. например, для двумерного пространства, соседи будут являться вершинами (обязательно выпуклого) N-угольника минимальной площади.

А если на плоскости 3 точки находятся на одной прямой (или близко к тому), но в разных концах пространства, то эта группа - ближайшие соседи?

Или применительно к 3-мерному пространству 4 точки находятся в одной плоскости и задают минимальный объем, то эта группа - ближайшие соседи?

Если так, то это NP проблема. Я так думаю.

Прочитай внимательно все что я написал в топике. Там все написано.

Ой-ли...

Ограничением является только расположение соседей, т.е. например, для двумерного пространства, соседи будут являться вершинами (обязательно выпуклого) N-угольника минимальной площади.

Из этого определения следует, что нам надо найти ОДИН треугольник минимальной площади, и образующие его точки будут являться ближайшими соседями (согласно Вашему определению) для ВСЕХ точек. Вы правда хотите именно этого?

Определитесь для начала с постановкой.

Я могу рассуждать только теоретически. Эффективного алгоритма в отрыве от специальной структуры данных не получить. Поэтому будет больно. Конвертация в структуру данных, обновление, проверка корректности и прочие радости тебе обеспечены. В качестве структуры данных рекомендуется R-дерево.

Там kd-дерево, оно хуже R-дерева. Пруфы на SO: http://stackoverflow.com/questions/4326332/could-anyone-tell-me-whats-the-dif...

Прочитав по диагонали думается что для двумерного случая диаграммы вороного спасут тс. Иди будут отправной точкой

knn

FNN, kknn, FastKNN тыщи их на https://cran.r-project.org/

треугольники, выпуклые многоугольники... чушь какая-то

прямоугольники — в декартовой системе координат — твой выбор

* отсортируй массив точек по x
* отсортируй массив точек по y
* выбери «характерный размер соседства» d
* пусть твоя рассматриваемая точка (x0,y0)
* в окне области ограниченном (x0-d/2,y0-d/2) ... (x0+d/2,y0+d/2) ищи /можно перебором/ пары координат принадлежащие одной точке
* если точек слишком много — уменьши «характерный размер соседства» d

если координаты полярные — оперируй, соответстсенно, r и alpha

select X,Y from PLOTS where X>(x0-d/2) and X<(x0+d/2) and Y>(y0-d/2) and Y<(y0+d/2) order by X;

Для каждой точки необходимо найти ближайших соседей.
например, для двумерного пространства, соседи будут являться вершинами (обязательно выпуклого) N-угольника минимальной площади.

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

Вот.

bass, slovazap, anto215, AIv, iVS, MKuznetsov, psv1967, ya-betmen и Анон:

Я тут успел переехать, сгореть до волдырей и поставить душевую кабину.

Но к делу.

Теперь почитал еще инфы про всякого что вы все писали выше.
Пришел к выводу что, да, мне нужны диаграмма вороного или триангуляция делоне (оно даже ближе «визуально») как отправная точка.
Дальше пока ничего еще не думал, но из той инфы что есть уже будет веселее.
Задачу помечаю как решенную.
Хотя оно и не до конца.
Если что кастану спросить в эту тему или сами чего вспомните/посоветуете.

Строите диаграмму Вороного, выбираете соседние (имеющие общие грани) точки. В чем проблема?

Мне не нужны грани, мне нужны «связи» как в триангуляции делоне. Пилю делоне. Да, я вычитал что вороного можно превратить в делоне. Но зачем? Это будет уже лишнее промежуточное преобразование. Ну или если будет время я потом вороного запрягу и сравню кто у меня лучше поскачет на живых данных — вороной или делоне.