Поиск наименьшего расстояния между точками.

ИМХО мнение правильное.
Для квадратов - вам надо будет определить в какой квадрат попадает каждая точка.
Для деревьев - знать координаты чтобы знать куда в дерево её добавить.
Обрабатывать в любом случае прийдётся каждую точку.
Единственное где может быть выигрыш - это если определение принадлежности точки квадрату будет быстрее чем вычисление расстояния.

 

Black_mirror, после такого уточнения, я четвёртый.

 

maksim_
не-не, вполне нормально. Исходный массив неизменен, мы его отсортируем по Х или У, как больше понравится. Потом - мой алгоритм должен прокатить. И ВСЕ точки проверятся не будут. Может произойти так, что будут проверены ВСЕ-1 точка, если одна из точек очень далеко, а остальные - очень близко, и собственно впритык к центру масс. Но условие ТС выполнено по любому - минимум будет вычислен без полного перебора массива )) правда, насчет оптимальности доказывать не возьмусь - мне просто вспомнилась "Элита" и кружок, в который попадали системы на расстоянии гиперпрыжка

 

А для сортировки что, будут проверяться не все точки?
Сортировка и будет полным перебором, другой вопрос в сложности/ресурсоёмкости вычислений относительно рассчёта расстояний.

 

cppasm
Первоначальная сортировка не играет никакой роли и проверкой точек не считается.
Пусть есть сотня базовых точек, которые нужно как-то подготовить заранее. После этого запускается проверка миллиона тестовых точек. Важно, чтобы для каждой тестовой точки не проводилось сравнение со всеми базовыми точками. Вот на этом этапе нужна оптимизация. Одноразовая предварительная сортировка — ерунда по сравнению с проверкой миллиона тестовых точек.

 

PSR1257

Центр масс тут ни причем, и если сортировать по расстоянию, то лучше, наоборот, относительно далеко удаленой точки. В этом сл. длины линий (дуг) равных расстояний не будут превышать размера облака точек Dmax и соотв-но среднее число проверяемых точек в радиусе R±dR будет меньше, чем при измерении расстояний о центра (макс.дуга в pi раз больше)

FatMoon

Если вычислять квадрат расстояния, то не факт, что будет заметная разница, т.к. если сравнивать 4 значения в лоб по if, то можно на непредсказанных условных переходах больше потерять. А если хитрить со знаками разностей, то получится фифти-фифти. Про вещественные координаты и говорить нечего
(ес-но вычислятьение квадрата расстояни

 

Как ты установишь отношения всех точек с базовыми, не проверяя их?
Надо либо сортировать весь массив точек, либо сортировать подмножество (базовые) и как-то определить отношение этого подмножества к остальным точкам.

 

так вопрос не стоял. вопрос стоял так:

 

cppasm

Не проверяя каждую тестовую с каждой базовой? Элементарно.
Упрощённый пример, где все точки имеют только одну координату. Имеется пять базовых точек с координатами:
1 2 3 4 5 — номера точек
7 10 4 13 1 — координата
Перед началом работы сортируем все точки по возрастанию координаты:
5 3 1 2 4 — номера точек
1 4 7 10 13 — координата

Теперь передаётся тестовая точка с координатой 18. Двоичным поиском находим, что она лежит правее точки четыре. Т.о. не проверяя точки 5 и 3 можно заключить, что ближайшая точка — точка номер 4.

Следующая тестовая точка с координатой 3. Двоичным поиском находим, что она лежит между точками 5 и 3.
Сравнивая расстояния между точками abs(4-3) и abs(1-3), находим, что ближе точка с координатой 4. Т.е. точка номер 3 — ближайшая. При этом для этой тестовой точки не проводилось сравнение с точками с номерами 2 и 4.

 

medstrax1

Мысль хорошая, но почему квадраты? Почему не треугольники или 13-ти-угольники?
medstrax1

Если мы можем хранить 10^6 точек, то почему бы не хранить 10^6 квадратов?
medstrax1

Во! В точку. Это главный недостаток квадратов. Надо брать многоугольники. Причём вокруг каждой точки p взять такой многоугольник, чтобы все его внутренние точки были бы ближе к p чем к p[j], при i != j (не знаю как по-русски называют такие области -- не интересовался, в англоязычной литературе их называют voronoi region).
Проверка точки на попадание в многоугольник -- это проверка на то, что точка лежит слева от всех прямых содержащих стороны. А это одно скалярное произведение и проверка знака.
Алгоритмов же поиска я вижу два. Не знаю какой лучше.
Мы будем перебирать многоугольники начиная с произвольного, и до тех пор, пока не найдём содержащий нашу точку v. Причём проверяя то точка лежит слева от прямой содержащей сторону, мы, найдя первую прямую, относительно которой точка справа, "шагнём" через эту прямую, и возьмём многоугольник смежный с текущим, которой по ту сторону этой прямой. Этот алгоритм приятен своей простотой. Правда у меня есть сомнения в его работоспособности. Надо формально доказывать.
Второй алгоритм -- мы опять же возьмём произвольный многоугольник. Соединим любую его точку с данной точкой v, получим отрезок. А теперь мы посмотрим какую сторону нашего многоугольника пересекает отрезок, и перейдём к многоугольнику который "по ту сторону" стороны (сорь за тафтологию). Этот алгоритм вероятно будет побыстрее, поскольку мы будем перебирать многоугольники двигаясь точно по направлению к нужной точке. Но он сложнее в реализации:
1. надо искать пересечение отрезков
2. придётся рассматривать специальные случаи, когда отрезок проходит через вершину многоугольника.
Может быть увеличенная сложность того стоит, а может и нет -- вовсе не факт, что алгоритм будет быстрее. Он может оказаться тормознее из-за сложности.

 

l_inc
Про диаграммы Воронина и алгоритмы поиска можно почитать в "Вычислительная геометрия введение (1989)Препарата Ф., Шеймос М."

Построим диаграммы Воронина будим искать в какой многоугольник попала наша точка. Сделать это можно быстрее всего если покрыть наше поле сеткой с клетками определенного размера. Если это невозможно то можно сделать квадро дерево

 

Pavia
Эм... если я правильно понимаю, речь идёт о диаграммах Вороного. О них r90 уже упоминал.
К сожалению (или к счастью) передо мной указанной задачи не стоит. До удачного алгоритма я не додумался, вместо чего взял на себя смелость разъяснить непонимающим смысл задачи. Только и всего.

 

ы. Буду знать. Задницей чувствовал, что это русская фамилия, но никак не мог сообразить какая именно.

 

Black_mirror

самая лучшая идея, имхо. дерево с поочередной сортировкой точек по x и по y. и поочередно минимизируя |a - x| и |b - y|

 

А зачем поочередно? Если рассматривать функцию F= abs(x-xi)+abs(y-yi), то для фиксированного F, расстояние лежит в пределах sqrt(2)/2*F - F. Отсюда следует алгоритм:
1. Сортируем по критерию F = abs(x-xi)+abs(y-yi)
2. Находим Fmin
3. Проверяем точки в пределах Fmin - Fmin*sqrt(2) на минимум (x-xi)^2+(y-yi)^2

 

Нашел решение, сейчас попробую код накатать

 

Ну? Как ты это сделаешь не обработав всех точек?
Твой метод даст преимущество если массив постоянен, а точки до которых надо определить расстояние меняются.
Тогда сортируем один раз, дальше всё упрощается.
В изначальной задаче сказано что массив один, и точка одна (постоянные) - задача разовая.
И просят найти точки в массиве с наименьшим расстоянием до заданной не перебирая весь массив.
Это невозможно в принципе.

 

Вообще то строго говоря, если массив сортировали, то его перебирали весь

 

Спасибо, то что доктор прописал ))

 

Код (Text):

1. #include <stdio.h>
2. #include <math.h>
3.  
4. struct Point
5. {
6.     float x;
7.     float y;
8. };
9.  
10. float get_dist(struct Point a, struct Point b)
11. {
12.     float cx = a.x-b.x;
13.     float cy = a.y-b.y;
14.     return sqrtf(cx*cx+cy*cy);
15. }
16.  
17. // Аргументы:
18. //  arr - массив точек, отсортированный по возрастанию абсциссы,
19. //  num_points - число точек в массиве,
20. //  target - точка, к которой нужно найти ближайшую
21. // Как работает:
22. //  1) в отсортированном массиве ищется точка, ближайшая к данной
23. //  2) от этой точки двигаемся влево и вправо
24. //     (сравнивая расстояние до текущей точки с минимальным на данный момент
25. //     и устанавливая новое минимальное расстояние), пока выполняются условия:
26. //   а) индекс не выходит за границы массива
27. //   б) расстояние по абсциссе до рассматриваемой точки меньше,
28. //      чем расстояние до ближайшей на данный момент точки
29. // Примечания:
30. //  1) не рассмотрен случай, когда существуют несколько точек,
31. //     расстояние до которых минимальное
32. struct Point get_nearest(struct Point *arr, unsigned num_points, struct Point target)
33. {
34.     unsigned i, ileft, iright;
35.  
36.     unsigned imin;
37.     float min_dist;
38.  
39.     // вычисляем индексы точек массива, ближайших к целевой по абсциссе
40.     // последовательный поиск приведен для простоты,
41.     // для сокращения перебора элементов нужно использовать бинарный поиск
42.     iright = num_points;
43.     for (i = 0; i < num_points; ++i)
44.     {
45.         if (arr[i].x >= target.x)
46.         {
47.             iright = i;
48.             break;
49.         }
50.     }
51.     ileft = iright-1;
52.  
53.     // расстояние до первой точке в качестве эталонного
54.     min_dist = get_dist(target, arr[0]);
55.     imin = 0;
56.  
57.     // рассматриваем точки, двигаясь влево и вправо от целевой,
58.     // пока не выйдем за границы массива
59.     // (означает, что ближайшая точка находится на границе)
60.     while (ileft > 0 || iright < num_points)
61.     {
62.         // по направлению влево
63.         if (ileft > 0)
64.         {
65.             // ВАЖНО:
66.             // если расстояние до текущей точки по абсциссе больше,
67.             // чем расстояние до ближайшей на данный момент точки,
68.             // то в этом направлении больше не двигаться
69.             if (target.x-arr[ileft].x < min_dist)
70.             {
71.                 float new_dist = get_dist(target, arr[ileft]);
72.                 if (new_dist < min_dist)
73.                 {
74.                     min_dist = new_dist;
75.                     imin = ileft;
76.                 }
77.                 ileft--;
78.             }
79.             else ileft = 0;
80.         }
81.         // по направлению вправо
82.         if (iright < num_points)
83.         {
84.             // аналогично как и по направлению влево
85.             if (arr[iright].x-target.x < min_dist)
86.             {
87.                 float new_dist = get_dist(target, arr[iright]);
88.                 if (new_dist < min_dist)
89.                 {
90.                     min_dist = new_dist;
91.                     imin = iright;
92.                 }
93.                 iright++;
94.             }
95.             else iright = num_points;
96.         }
97.     }
98.     return arr[imin];
99. }
100.  
101. int main(void)
102. {
103.     struct Point arr[] = {{0.0, 10.0}, {1.0, 5.0}, {2.0, 10.0}, {9.0, 1.0}};
104.     unsigned num_points = sizeof(arr)/sizeof(arr[0]);
105.     struct Point target = {4.0, 0.0};
106.     struct Point nearest = get_nearest(arr, num_points, target);
107.     printf("(%f, %f), %f\n", nearest.x, nearest.y, get_dist(target, nearest));
108.     return 0;
109. }