ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Диаграмма Вороного, поиск ближайшей точки
25 сообщений из 216, страница 1 из 9
  1  все
Диаграмма Вороного, поиск ближайшей точки
    #38968413
Antipich
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Antipich
Гость
Добрый день.
Есть у меня такая задача:
Есть множество N точек на плоскости. Оно фиксированное.
Есть произвольная точка p.
Задача - найти из множества N точку, ближайшую к p.
Везде в интернете ссылаются на kd деревья или диаграмму Вороного.
Но я хоть убей не могу понять, как они применимы именно к этой задаче.

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

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

Заранее благодарю за помощь.
...
Рейтинг: 0 / 0
26.05.2015, 10:51
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #38968475
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Если плоскость - дискретная то можно закрашивать каждый дискретный элемент цветом.
...
Рейтинг: 0 / 0
26.05.2015, 11:40
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #38968645
Antipich
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Antipich
Гость
Нет, не дискретная
...
Рейтинг: 0 / 0
26.05.2015, 13:31
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #38968652
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
AntipichНо я хоть убей не могу понять, как они применимы именно к этой задаче.

А с чего ты решил что твою задачу можно решить только Вороным? Ты это сам придумал?
...
Рейтинг: 0 / 0
26.05.2015, 13:38
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #38968657
Antipich
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Antipich
Гость
Я не говорил, что только.
Я же написал, что когда искал решение, то много где в интернете наталкивался на нее и kd-деревья.

Мне не важно, каким образом я решу задачу, главное, чтобы максимально быстро искалась ближайшая точка.
Множество точек N фиксированное и задается в начале. Поэтому время "подготовительной работы" не критично.
А вот потом пойдет неслабый поток случайных точек, которым надо найти ближайшую. И как раз этот процесс и надо оптимизировать.
Сейчас там стоит тупой перебор всех точек, что, понятное дело, не вариант...
...
Рейтинг: 0 / 0
26.05.2015, 13:41
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #38968667
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
AntipichСейчас там стоит тупой перебор всех точек, что, понятное дело, не вариант...

Наложи прямоугольную сетку (16x16 там или ... 256 на 256). И ищи по ячейкам которые ближе по "спирали".

Вариант?
...
Рейтинг: 0 / 0
26.05.2015, 13:54
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #38968721
Antipich
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Antipich
Гость
mayton,

В смысле, по спирали?
О сетке думал, но есть ньюанс.
Разделили на ячейки, определили, в какую мы попали. Перебрали в ней точки и нашли ближайшую. Но суть в том, что ближайшая может быть не среди них, а в соседней клетке и т.д. Т.е. так вроде не катит.
...
Рейтинг: 0 / 0
26.05.2015, 14:24
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #38968746
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Antipichmayton,

В смысле, по спирали?
О сетке думал, но есть ньюанс.
Разделили на ячейки, определили, в какую мы попали. Перебрали в ней точки и нашли ближайшую. Но суть в том, что ближайшая может быть не среди них, а в соседней клетке и т.д. Т.е. так вроде не катит.
Всё прекрасно катит. Ты рисунок нарисуй. И сам посмотри.
...
Рейтинг: 0 / 0
26.05.2015, 14:32
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #38968816
Antipich
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Antipich
Гость
mayton,

Пожалуйста, вот тебе рисунок.
Я в paint рисовал, не суди строго :)
На примере четырех квадратов. Зеленая точка - входная. Синие - начальный набор.
Как видишь, синяя точка с правого "квадрата" значительно ближе, чем точки в том же "квадрате", где и зеленая...
...
Рейтинг: 0 / 0
26.05.2015, 15:11
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #38968818
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
1 обход змейкой сделай-то.

Змейкой.

1 обход.
...
Рейтинг: 0 / 0
26.05.2015, 15:12
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #38968819
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Тьфу. Спиралькой.
...
Рейтинг: 0 / 0
26.05.2015, 15:13
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #38968841
Antipich
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Antipich
Гость
mayton,

По какому алгоритму спиралькой? До какой степени обходить? Как понять, что обходить далее нужно или пора остановиться?
...
Рейтинг: 0 / 0
26.05.2015, 15:23
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #38968843
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Один круг. Если не нашёл точек - то еще один круг.
...
Рейтинг: 0 / 0
26.05.2015, 15:24
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #38968854
Antipich
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Antipich
Гость
Не прокатит.
Количество обходов спиралькой и т.д. зависит чисто от выбранного размера одного квадрата.
Рисовать еще одну картинку лень, если честно. Но она сразу приходит в голову :) Нет критерия остановки просмотра. Найденная точка на любой текущей итерации может быть дальше, чем точки на следующих.

Тут именно квадраты не катят. А вот в диаграмме Вороного как раз то, что надо. По ходу... Но куча других нюансов, с которыми хрен разберешься так, без тяжелой артиллерии и влезания в очень умные книги :) По ходу придется влезать и вспоминать студенческие годы и матан с дискреткой :) Внутренний голос подсказывает, что все же это - правильное направление.

Ладно, все равно спасибо за помощь :)
...
Рейтинг: 0 / 0
26.05.2015, 15:32
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #38968875
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Я бы так решал:
Если конечное множество фиксированное (в котором искать), то превратить его в два ассоциативных массива (или сортированных списка)
Mx[X] = Y и My[Y] = X
Например для точек (1,1), (5,3), (4,2)
Код: sql
1.
2.
3.
4.
5.
6.
Mx[1] = 1
Mx[4] = 2
Mx[5] = 3
My[1] = 1
My[2] = 4
My[3] = 5


для поиска ближайшей от (x,y) сначала проходим по массиву Mx, затем My. в обе стороны каждый. Затем из 4х выбрать ближайшую.
Например для точки (3,3) идем вверх. Следующая точка (4,2), расстояние до нее 1.4, поэтому следующую проверять не надо, т.к. (5,3) дальше.

Тут надо еще подумать как от корней избавится при расчете длины. Заменить на квадраты, т.к. умножение гораздо быстрее. И немного соптимизировать, добавить проверку для Mx => |x - xi| > |y - yi| чтобы не обсчитывать заведомо далекие точки.
...
Рейтинг: 0 / 0
26.05.2015, 15:48
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #38968878
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Извини конечно но из твоего месседжа
AntipichНо я хоть убей не могу понять, как они применимы именно к этой задаче.
как-бе напрашивается вывод об уровне знаний. Диаграммы Вороного потребуют от тебя мат-аппарата
в несколько раз большего чем простое деление пространства на прямоугольники, квадраты, Quad-Tree,
R-Tree, и прочие способы кластеризации метрического пространства.

Я тебе "сходу" предложил простой вариант индексирования пространства на уровне "лабы 1-го курса"
но ты почему-то решил что он - не рабочий. Что-ж удачи тебе в твоём нелёгком изучении трудов Вороного.

Надеюсь он тебе будет полезен. Кстати генерация разбиения Вороного вовсе не отменяет необходимость
создания "индекса" для этого разбиения.

Еще раз удачи.
...
Рейтинг: 0 / 0
26.05.2015, 15:48
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #38968891
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonСпиралькой.
по сути ты укрупнил точку до квадрата, т.е. ищем не ближайшую точку, а ближайший квадрат, а в нем точку. Оно сработает если точки боле-мене равномерно распределены и правильно выбрать размер квадрата. А если точки неравномерно, например закусочные на карте, куча пустых квадратов и в некоторых куча точек, то из тайги долго по спиральке идти придется, а в центре крупного города долго точки в квадрате перебирать.
...
Рейтинг: 0 / 0
26.05.2015, 15:56
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #38968896
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima T, это основная проблема пространственного поиска. Неравномерность данных.
...
Рейтинг: 0 / 0
26.05.2015, 15:58
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #38968902
Antipich
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Antipich
Гость
mayton,

Уровень знаний у меня неплохой, можешь поверить :) И матан для меня не является каким-то ужасным словом :)
И с Вороновым как раз вопрос у меня основной в его грамотной индексации и построении k размерности, а не обычный вариант.
Мне не нужна была лаба. И согласись, что твой вариант запросто допускает ошибки, т.е. работает неверно.
Если у тебя такие отличные знания, то что же ты про Вороного не объяснил, как к нему подойти, до чего я уже сам допер, а упирался, что твой вариант абсолютно рабочий?
...
Рейтинг: 0 / 0
26.05.2015, 16:00
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #38968919
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Dima Tпревратить его в два ассоциативных массива (или сортированных списка)
Массивы тут не пройдут, т.к. будут повторы индекса. Сортированные списки (один по X, второй по Y). В остальном должно заработать.
...
Рейтинг: 0 / 0
26.05.2015, 16:05
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #38968931
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Можно еще соптимизировать, сначала найти минимальный квадрат поисков, т.е. просто пройтись по спискам вверх/вниз, найти МИН(|x-xi|, |y - yi|), тут корней никаких не надо, только вычитания, модуль и сравнения, затем останется обсчитать точки в квадрате (x - MIN, y - MIN):(x + MIN, y + MIN).
...
Рейтинг: 0 / 0
26.05.2015, 16:14
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #38968932
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Antipichmayton,

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

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

Вот с этого момента я жду очень и очень конкретных вопросов.

Что именно непонятно?
...
Рейтинг: 0 / 0
26.05.2015, 16:14
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #38969271
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
AntipichДобрый день.
Есть у меня такая задача:
Есть множество N точек на плоскости. Оно фиксированное.
Есть произвольная точка p.
Задача - найти из множества N точку, ближайшую к p.
Везде в интернете ссылаются на kd деревья или диаграмму Вороного.
Но я хоть убей не могу понять, как они применимы именно к этой задаче.

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

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

Заранее благодарю за помощь.
Лучше равнозначным понятием воспользоваться - триангуляцией Делоне ( недавно делал перевод на fpc , в оригинальной библиотеке используется индексный поиск)
найдёшь вмещающий треугольник, а дальше останется проверить 3 его вершины

PS: треугольник может быть неполный
...
Рейтинг: 0 / 0
26.05.2015, 22:33
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #38969496
Valer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Valer
Участник
чем не устраивает простой перебор по массиву точек?
...
Рейтинг: 0 / 0
27.05.2015, 10:48
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #38969693
Valer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Valer
Участник
http://technomag.edu.ru/doc/624368.html
...
Рейтинг: 0 / 0
27.05.2015, 12:56
| Ответить | Цитировать | Написать  
25 сообщений из 216, страница 1 из 9
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Диаграмма Вороного, поиск ближайшей точки
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=38968657&tid=1340722]:
 0ms
get settings:
 10ms
get forum list:
 17ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 197ms
get topic data:
 8ms
get forum data:
 2ms
get page messages:
 63ms
get tp. blocked users:
 1ms
others: 249ms
total:  551ms
созд. / загр.: 551ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]