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

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

 

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

 

Дико извиняюсь, но ИМХО бредъ.
Задача решается за один просмотр массива, на неквантовом компе быстрее некуда.

 

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

 

Зато радиус-векторы каждый раз совершенно новые, тебе ведь именно они нужны...

 

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

 

Мда... Проще но дольше перебрать данный квадрат и восемь ближайших.

 

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

Point *pt = map[x][y];

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

 

persicum
Для этого нужно делить плоскость так, чтобы в каждом квадрате была хоть одна точка. Есть у меня подозрение что здесь уже будут не квадраты.

 

Есть мысль разбить всю область, содержащую точки, на равные квадраты таким образом, чтобы каждый квадрат содержал не более одной точки. Потом для каждого квадрата составить список ближайших квадратов, содержащих точки.
Тогда на первый взгляд все становится тривиально.
Однако.
1) Наталкиваемся на чисто технические трудности, при большом количестве точек элементарно не хватит оперативы для запоминания всех квадратов. В исходной задаче предполагается около 10^6 точек.
2) Непонятно как определять понятие "квадрат, ближайший к заданному". Т.е. с близостью квадратов все ясно, а вот с близостью точек в этих квадратах - не совсем. Если заданная точка и точка в "ближайшем квадрате" расположены по противоположным углам, а сами квадраты расположены про диагонали относительно друг друга, то далеко не факт, что расстояние между этими точками будет наименьшим из всех возможных. Возможно будет существовать точка в квадрате, который "дальше", но она расположена рядом с "ближней" стороной(углом)

 

Так же непонятно как быть, когда заданная точка попадает в область, далекую от области, содержащей исходные точки. К примеру весь массив точек попадает в квадрат (0,0) (100, 100). А если заданная точка будет (1000, 1000) ?

 

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

 

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

 

У деревьев вычислительная сложность будет O(log n) , типа бинарного поска...
А у квадратов будет сложность O(1), что ближе к хешам...

 

Определяем для массива точек максимальное расстояние Dmax между ними (условно поперечник облака точек), и определяем центр масс M(xm,ym). Для новой точки T(x,y) определяем расстояние MT и сравниваем с Dmax/2. Если меньше - мы внутри облака точек, иначе - вне его. Строим окружность с центром в новой точке, радиуса R=min(Dmax/2;MT)/2. Для избежания вычислений с квадратами, синусами и косинусами, вместо окружности будем исследовать квадрат, между (x-R,y-R)-(x+R,y+R). Если внутри квадрата не обнаружено ни одной точки, увеличиваем радиус на некоторую величину (можно продумать оптимальный шаг, или даже сделать его переменным). Для всех точек P, попавших внутрь квадрата, ищем расстояние TP(i), отбираем минимальное. Если расстояние получается больше R, значит, точка из угла квадрата, берем это расстояние за новое R и повторяем операцию. Вычисление расстояния - длительная операция, сравнительно. Квадраты, корень квадратный - или тригонометрия. А вот проверка, попадает ли точка в окрестности, с заданным радиусом - более быстрая, сравнение координаты на больше-меньше. Если массив точек изначально сортирован по Х, то даже сравнение не будет происходить со всем массивом. Чего-то такое видится.

 

Правда, будет особый случай, когда центр масс пустой (а это вполне вероятно), а новая точка попала тютелька в него, расстояние =0.

 

FatMoon

Не-не, продолжай - мне твоя идея нравиццо. Может как-то отсортировать кругами вокруг центра масс (или не центра масс но точки где Sum(Ri)=min (минимальная сумма модулей векторов до всех точек).

 

проход всего массива и поиск минимума r=sqtr((xi-x)^2+(yi-y)^2)
элементарная геометрия чего мудрите то ???

 

medstrax1
а как не исследовав точку что то узнать о ней ???
по любому нужно один раз пройти весь массив -иначе никак

 

Rockphorr

Ты уже третий кто высказывает такое неправильное мнение