0 / 0 / 0
Регистрация: 26.05.2015
Сообщений: 2
1

Поиск ближайшей точки в множестве к данной

26.05.2015, 14:07. Показов 7108. Ответов 10
Метки нет (Все метки)

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

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

Искал в интернете, часто наталкивался на советы посмотреть в сторону kd-деревьев и диаграммы Вороного.
Но я никак не могу понять, как они применимы к данной задаче, когда входная точка случайная, а не одна из множества N.

В какую сторону копать?

Заранее благодарю за помощь.
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
26.05.2015, 14:07
Ответы с готовыми решениями:

Вычислить координаты ближайшей точки, которая принадлежит отрезку и точки на плоскости
Есть плоскость с осями x и y, на ней расположен отрезок, координаты конца A и начала B этого...

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

Найти расстояние от данной точки до ближайшей стороны треугольника
Даны координаты вершин треугольника и координаты некоторой точки внутри него. Найти расстояние от...

Найти расстояние от данной точки до ближайшей стороны треугольника
Решение задач с использованием процедур или функций Даны координаты вершин треугольника и...

10
5058 / 3944 / 1303
Регистрация: 14.04.2014
Сообщений: 18,159
Записей в блоге: 18
26.05.2015, 14:59 2
зависит от количества точек наверняка
я делал очень просто по методу разбиения на квадраты
поиск идет только по 9 квадратам, далее перебор
вся карта содержит <10000 точек, разбита на 100 квадратов
скорость вполне достаточная
0
0 / 0 / 0
Регистрация: 26.05.2015
Сообщений: 2
26.05.2015, 15:06  [ТС] 3
Т.е. по принципу: разбили на квадраты, определили, в какой квадрат попала наша точка, перебираем в нем?
Не прокатит. Запросто может быть ситуация, что ближайшая точка не в том квадрате, в который попала наша входная...
0
291 / 263 / 47
Регистрация: 09.04.2013
Сообщений: 1,014
26.05.2015, 15:27 4
K-d дерево позволяет довольно быстро найти точки, ближайшие к заданной. Но, судя по картинкам для 2D варианта, прямым спуском ближайшую точку не получим, нужно будет проверить точки в соседних ветках дерева тоже.
0
5058 / 3944 / 1303
Регистрация: 14.04.2014
Сообщений: 18,159
Записей в блоге: 18
26.05.2015, 15:30 5
плохо прочитал
9 квадратов
это и есть дерево, только 1 уровень
0
291 / 263 / 47
Регистрация: 09.04.2013
Сообщений: 1,014
26.05.2015, 15:41 6
Цитата Сообщение от krapotkin Посмотреть сообщение
плохо прочитал
9 квадратов
это и есть дерево, только 1 уровень
Пусть в 8-ми крайних квадратах все точки лежат почти на границах, а в центральном точнехонько в середине квадрата. Пусть наша точка попала в центральный квадрат, но почти возле его вершины. Получается, что ближайшая точка множества будет не в центральном квадрате, а в одном из крайних.
0
5058 / 3944 / 1303
Регистрация: 14.04.2014
Сообщений: 18,159
Записей в блоге: 18
26.05.2015, 16:30 7
правильно
но все точки, не лежащие в 9 квадратах, заведомо дальше, чем лежащие
отсюда мораль
при равномерном распределении точек мы сократили поиски на 91 процент
0
Модератор
2833 / 1998 / 431
Регистрация: 26.03.2015
Сообщений: 7,684
26.05.2015, 18:23 8
Цитата Сообщение от krapotkin Посмотреть сообщение
но все точки, не лежащие в 9 квадратах, заведомо дальше, чем лежащие
Не верно.
Если мы почти в вершине одного из квадратов стороной 1, то расстояние до самой дальней точки в нашем квадрате чуть меньше https://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt{2} (а в одном из девяти - в 2 раза дальше может быть), а расстояние до самой ближайшей точки вне девяти квадратов, чуть больше 1.
0
5058 / 3944 / 1303
Регистрация: 14.04.2014
Сообщений: 18,159
Записей в блоге: 18
26.05.2015, 21:29 9
тоже согласен, но тут сильно выручает что при равномерном распределении вероятность такого случая крайне низка
можно свести этот случай к 0%, если заранее рассчитать максимальный минимум MM расстояния до соседней точки для всего множества, и задать разбиение с условием что x*sqrt(2) < MM. В этом случае вроде алгоритм должен сойтись

для точного разбиения можно использовать систему перекрывающихся на R/2 круглых зон
у точки будет более одной принадлежности к кругу, алгоритм будет чуть сложнее, но ненамного, и все равно позволит исключить довольно большое пространство
0
Модератор
2833 / 1998 / 431
Регистрация: 26.03.2015
Сообщений: 7,684
26.05.2015, 23:46 10
По-моему, нужно
0. Разбить всю "плоскость" на клетки квадратичным деревом (каждая клетка делится на четыре... и так далее рекурсивно).
1. искать все точки, которые могут быть не дальше R (квадрат самой мелкой сетки полностью или частично внутри круга)
1.1. если найдено приемлемое количество точек, то просто проверяем расстояния до всех
1.1.1. если расстояние R0 до ближайшей из них меньше R, то это ответ
1.1.2. иначе нужно повторить поиск с самого начала, взяв за R = R0
1.2. точек не найдено - повторяем с удвоенным расстоянием
1.3. точек найдено слишком много - уменьшаем расстояние

Добавлено через 2 минуты
начинать надо маленького расстояния
все эти холостые поиски с небольшим расстоянием в сумме будут весить, наверное, меньше, чем последний результативный
0
1213 / 615 / 78
Регистрация: 01.10.2012
Сообщений: 2,959
27.05.2015, 06:47 11
Цитата Сообщение от Antipich Посмотреть сообщение
Искал в интернете, часто наталкивался на советы посмотреть в сторону kd-деревьев и диаграммы Вороного.
Но я никак не могу понять, как они применимы к данной задаче, когда входная точка случайная, а не одна из множества N.
Прекрасно применимы, это общепринятый способ. Если надо расскажу как работает kd-tree, а если надо решение попроще и скорость поиска не особо волнует, то просто сортируете исходные точки по X или Y, а поиск выглядит так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int findNear( const Point & pt, const std::vector <Point> & vec )
{
  auto it = std::lower_bound(vec.begin(), vec.end(), pt);
  if (it == vec.end()) it = vec.begin();
 
  int index = it - vec.begin();
  int minIndex = index;
  float minD = distance2(pt, vec[index];  // квадрат расстояния
 
// просмотр вперед пока расстояние по X не превысит минимальное
  for (int i = index + 1; i < vec.size(); ++i) {
    float dx = vec[i].x - pt.x;
    if (dx * dx > minD) break;
    float curD = distance2(pt, vec[i]);
    if (curD >= minD) continue;
    minD = curD;
    minIndex = i;
  }
 
// просмотр назад
  for (int i = index - 1; i >= 0; --i) {
    float dx = vec[i].x - pt.x;
    if (dx * dx > minD) break;
    float curD = distance2(pt, vec[i]);
    if (curD >= minD) continue;
    minD = curD;
    minIndex = i;
  }
  return minIndex;
}
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
27.05.2015, 06:47

Найти расстояние от данной точки до ближайшей стороны треугольника
Даны координаты вершин треугольника и координаты некоторой точки внутри него. Найти расстояние от...

Найти расстояние от данной точки до ближайшей стороны треугольника
Даны координаты вершин треугольника и координаты некоторой точки внутри него. Найти расстояние от...

Найти расстояние от данной точки до ближайшей стороны треугольника.
Даны координаты вершин треугольника и координаты некоторой точки внутри него. Найти расстояние от...

Найти расстояние от данной точки до ближайшей стороны треугольника
Даны координаты вершин треугольника и координаты некоторой точки внутри него. Найти расстояние от...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.