ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Диаграмма Вороного, поиск ближайшей точки
216 сообщений из 216, показаны все 9 страниц
  все  
Диаграмма Вороного, поиск ближайшей точки
    #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
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #38970087
Фотография tchingiz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tchingizПривилегированный пользователь
Участник
вопросы по поиску столкновений астероидов тут можно задавать?
Это правильная тема?
...
Рейтинг: 0 / 0
27.05.2015, 18:06
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #38971185
Фотография tchingiz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tchingizПривилегированный пользователь
Участник
авторФормат входного файла

В первой строке задано число астероидов N (1 ≤ N ≤ 10).
В следующей строке указаны характеристики корабля: радиус R (1 ≤ R ≤ 1000), степень полинома C1 равная p1 (0 ≤ p1 ≤ 9) с последующим указанием (p1 + 1) коэффициентов многочлена (-1000 ≤ С1i ≤ 1000) начиная от младшего, степень полинома C2 с дальнейшим указанием коэффициентов и степень полинома C3 с дальнейшим указанием коэффициентов полинома (ограничения на размер и коэффициенты полиномов одинаковые).
...
Рейтинг: 0 / 0
28.05.2015, 19:40
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #38971331
Фотография iv_an_ru
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
iv_an_ru
Участник
maytonЕсли плоскость - дискретная то можно закрашивать каждый дискретный элемент цветом.А если не дискретная, то дискретизировать, и закрашивать каждый дискретный элемент списком цветов, встречающихся в нём :)

Трудно что-то подсказывать без знания N, неравномерности данных, чисел поисков для каждого набора из N точек (всего поисков для одного набора, последовательных поисков с одним набором) и ожидаемых оптимальности результата и бюджета разработки.
...
Рейтинг: 0 / 0
28.05.2015, 23:29
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #38973761
mikhail_n
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikhail_n
Участник
Диаграмма Вороного или триангуляция Делоне нужны для более сложных задач, в этой ветке несколько лет назад White Owl решал задачу где триангуляция Делоне могла бы снизить трудоёмкость алгоритма с кубического до линейно-логарифмического. Если мне не изменяет память, трудоёмкость триангуляции Делоне методом Форчуна - N*ln(N). Поэтому как уже сказал Valer - тупым последовательным перебором вы гарантировано находите решение за N шагов.

Любая попытка оптимизировать алгоритм будет основана на неявном предположении что какой-то добрый дядя собрал для вас статистику о характере распределения этих ваших N точек (затратив при этом как минимум те же N операций), а потом абсолютно бескорыстно подарил её вам. Ну или исчо может быть вариант что вам каким-то образом доступна априорная информация о характере распределения точек. Если это ваш случай, то тогда есть смысл колупаться. Если же на вас одномоментно вываливается случайный набор N точек - полный перебор.
...
Рейтинг: 0 / 0
01.06.2015, 20:06
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #38973773
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
mikhail_nЕсли же на вас одномоментно вываливается случайный набор N точек - полный перебор.
Вроде как набор не случайный, а очень даже известный, если я правильно понял ТЗ. Случайная точка одна, относительно которой искать.
...
Рейтинг: 0 / 0
01.06.2015, 20:24
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #38973819
Фотография ПЕНСИОНЕРКА
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ПЕНСИОНЕРКА
Участник
Antipich,

я бы шла от этого макета решения(точки заменила на случайные)
Код: vbnet
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.
Sub x150601()
Dim x1, x, y1, y, z1, z, j1, j1k, j2, dt1
z = 999999  'заведомо больщое число
dt1 = Timer
j1 = 0
j1k = 1000000  'количество циклов
j2 = 0
x = 600  'искомая точка
y = 100
Do While j1 < j1k
j1 = j1 + 1
x1 = Rnd(1) * 999 \ 1
y1 = Rnd(1) * 999 \ 1
z1 = (x1 - x) * (x1 - x) + (y1 - y) * (y1 - y)
If z1 < z Then
j2 = j2 + 1
Debug.Print j1, j2, x1, y1, z1
z = z1
End If
Loop
Debug.Print "время выполнения в сек="; (Timer - dt1)
'' цикл------------------x1----------y1---------расстояние в квадрате
'' 1             1             279           444           221377
'' 2             2             453           348           83113
'' 3             3             578           84            740
'' 314           4             607           117           338
'' 1607          5             598           90            104
'' 1616          6             600           99            1
''время выполнения в сек= 1,203125
End Sub
...
Рейтинг: 0 / 0
01.06.2015, 22:00
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #38974514
Фотография iv_an_ru
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
iv_an_ru
Участник
mikhail_nЛюбая попытка оптимизировать алгоритм будет основана на неявном предположении что какой-то добрый дядя собрал для вас статистику о характере распределения этих ваших N точек (затратив при этом как минимум те же N операций), а потом абсолютно бескорыстно подарил её вам.Если карта набор этих точек повторяется миллион раз, только с другой случайной мухой-параметром, то амортизация сбора статистики в пересчёте на одну муху мало отличится от "абсолютно бескорыстно".
...
Рейтинг: 0 / 0
02.06.2015, 17:26
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39045325
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
AntipichДобрый день.
Есть у меня такая задача:
Есть множество N точек на плоскости. Оно фиксированное.
Есть произвольная точка p.
Задача - найти из множества N точку, ближайшую к p.
Везде в интернете ссылаются на kd деревья или диаграмму Вороного.
Но я хоть убей не могу понять, как они применимы именно к этой задаче.

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

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

Заранее благодарю за помощь.

Зачем усложнять.
Делаете массв точек и 2 массива указателей на точки
для осей координат.
Массивы указателей на точки сортируете по возрастанию координат

Берете на вход точку ищете точки в массиве указателей
между которыми
нужно вставить вашу новою точку.
Из 2-х соседних выбираете ту, которая ближе.
...
Рейтинг: 0 / 0
07.09.2015, 21:18
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39045326
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
ДохтаРAntipichДобрый день.
Есть у меня такая задача:
Есть множество N точек на плоскости. Оно фиксированное.
Есть произвольная точка p.
Задача - найти из множества N точку, ближайшую к p.
Везде в интернете ссылаются на kd деревья или диаграмму Вороного.
Но я хоть убей не могу понять, как они применимы именно к этой задаче.

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

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

Заранее благодарю за помощь.

Зачем усложнять.
Делаете массв точек и 2 массива указателей на точки
для осей координат.
Массивы указателей на точки сортируете по возрастанию координат

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

Можно обойтись и 2 массивам , массив с точками отсортировать
значению оси Х
а массив указателей на эти точки отсортировать по значению оси Y.
Делаете поиск методом половинного деления
типа для вставки координат новой точки.
Получаете координаты 2-х ближайших точек, из них выбираете
ту которая ближе к вашей точке.
...
Рейтинг: 0 / 0
07.09.2015, 21:31
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39045329
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
ДохтаРМассивы указателей на точки сортируете по возрастанию координат

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

По какому возрастанию координат?

Х и Y.

Первый массив
1 1,5
2 3.2
3 4.1
4 8.7
5 9.4

второй массив
3
2
5
1
4

на вход приходит точка с координатами 5.3
Ближайшие точки 4.1 , 8.7 , 3.2 , 9.4

Ошибся будет выбор из 4 точек.
Из них нужно выбрать самую близ лежащую.

То есть методом половинного деления задача сводится
к выбору из 4 точек.
...
Рейтинг: 0 / 0
07.09.2015, 21:53
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39045338
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
ДохтаР, я убеждён что корректность результата зависит от выбора направления
ранжирования точек. К примеру сверху-вниз + слева направо в силу дихотомии
пропускают важную точку которая лежит на 2 ячейки от искомой.

Тоже самое если ты выбираешь обход слева направо + сверху вниз я могу
указать такие исходные данные при которых ты промахнёшся мимо нужной точки.
...
Рейтинг: 0 / 0
07.09.2015, 22:09
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39045341
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
maytonДохтаРМассивы указателей на точки сортируете по возрастанию координат

По какому возрастанию координат?

Массив точек сортируется по возрастанию координаты Х
Массив указателей на точку
сортируется по возрастанию значения координат Y точек на которые они
ссылаются .

Если точек очень много, то вместо массива нужно строить дерево блоков
и подбирать их размер под линейку кеша процессора, что бы
половинное деление не продувало кеши.
Но это уже следующий этап оптимизации.
...
Рейтинг: 0 / 0
07.09.2015, 22:13
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39045346
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
maytonДохтаР, я убеждён что корректность результата зависит от выбора направления
ранжирования точек. К примеру сверху-вниз + слева направо в силу дихотомии
пропускают важную точку которая лежит на 2 ячейки от искомой.

Тоже самое если ты выбираешь обход слева направо + сверху вниз я могу
указать такие исходные данные при которых ты промахнёшся мимо нужной точки.

ИМХО
Не промахнусь.
в одномерной системе координат задача оптимизируется
до 2 ближайших точек,
в двухмерной системе координат до 4
, в трех мерной до 9 .
итд....
...
Рейтинг: 0 / 0
07.09.2015, 22:19
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39045350
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
ДохтаРв одномерной системе координат задача оптимизируется
до 2 ближайших точек,
Док ты сильно ошибаешся. Я могу нарисовать тебе этот частный случай. Ну лучше ты сам
порисуй и найди неблагоприятный расклад.
...
Рейтинг: 0 / 0
07.09.2015, 22:24
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39045372
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
maytonДохтаРв одномерной системе координат задача оптимизируется
до 2 ближайших точек,
Док ты сильно ошибаешся. Я могу нарисовать тебе этот частный случай. Ну лучше ты сам
порисуй и найди неблагоприятный расклад.

Подумал ничего не придумал
в 2- мерной системе координат алгоритм
выходит 4 точки , из который нужно выбрать ближайшую
собрав в отдельный массив и отсортировав по длине гипотенуз
прямоугольные треугольники .
...
Рейтинг: 0 / 0
08.09.2015, 00:07
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39045373
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
ДохтаРПодумал ничего не придумал
в 2- мерной системе координат алгоритм
выходит 4 точки , из который нужно выбрать ближайшую
собрав в отдельный массив и отсортировав по длине гипотенуз
прямоугольные треугольники .
ОК. Возможно я не так понял твою сортировку.
Давай исходник. Можно на псевдо-языке.
...
Рейтинг: 0 / 0
08.09.2015, 00:09
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39124420
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
maytonДохтаРПодумал ничего не придумал
в 2- мерной системе координат алгоритм
выходит 4 точки , из который нужно выбрать ближайшую
собрав в отдельный массив и отсортировав по длине гипотенуз
прямоугольные треугольники .
ОК. Возможно я не так понял твою сортировку.
Давай исходник. Можно на псевдо-языке.


Извини что с большой задержкой , я было начал реализовывать идею в коде
и погряз в реализиции а потом отвлекся и забыл.
Приблизительный алгоритм сортировки описан тут для более простого случая:
18534524
...
Рейтинг: 0 / 0
09.12.2015, 19:42
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39124426
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
ДохтаРmaytonпропущено...

ОК. Возможно я не так понял твою сортировку.
Давай исходник. Можно на псевдо-языке.


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


Суть идеи в том что сначала массив точек нужно отсорировать
отдельно по каждой координате.
Потом поиском в диапазоне по Х Y ищется ближайшая, через расчет
разности гипотинуз.
Реализация достаточно просто масштабирется
до пространства любой размерности, вплодь до дефайном или параметром.

У меня сначала было желание реализовать универсальный поисковик ,
для разумной многомерности пространства, но я не нашел ему практического
применения и бысро потерял мотивацию.
...
Рейтинг: 0 / 0
09.12.2015, 19:53
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39126350
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
ДохтаР,
mayton тут прав, сортировкой можно только для одномерного случая
для двухмерного и больше применяются k-d деревья и их разновидности для нахождения 2^k соседних точек (к - размерность пространства) из которых можно выбрать ближайшую. Cтоимость поиска в готовом k-d дереве - O(k*ln(N))

самый быстрый алгоритм который я знаю по построению k-d дерева выполняется за O(N*ln(N)), скоро я надеюсь напишу о нём в блоге
PS: проблема самобалансировки k-d деревьев пока не решена даже для 2-х мерного случая
...
Рейтинг: 0 / 0
12.12.2015, 13:15
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39126365
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
пардон, поиск ближайшей точки если верить википедии несколько хуже O(H*Ln(H)) H - высота дерева
А вот здесь готовая реализация
...
Рейтинг: 0 / 0
12.12.2015, 13:51
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39126441
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Нашёл апплет-демку. С К-Д деревом. Пока не понял чем он отличается от R-деревев.

Вобщем накидал случайных точек. Умышленно неоднородно. Получилось вот такое разбиение пространства.
...
Рейтинг: 0 / 0
12.12.2015, 17:38
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39126494
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
mayton,
 

википедияКаждая вершина R-дерева имеет переменное количество элементов (не более некоторого заранее заданного максимума). Каждый элемент нелистовой вершины хранит два поля данных: способ идентификации дочерней вершины и ограничивающий прямоугольник (кубоид), охватывающий все элементы этой дочерней вершины. Все хранимые кортежи хранятся на одном уровне глубины, таким образом, дерево идеально сбалансировано. При проектировании R-дерева нужно задать некоторые константы:


данные хранятся только в "листьях", дополнительно используются агрегатные значения (координаты вмещающего объекта)

в k-d дереве многомерная точка хранится в каждой ноде
...
Рейтинг: 0 / 0
12.12.2015, 19:46
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39126500
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
А выводы?

Автору нужно искать ближайшие точки. В силу распространённости технологий oct-tree, r-tree я-бы начал
решение с них. Если нет доводов против.

Какие доводы против?
...
Рейтинг: 0 / 0
12.12.2015, 20:04
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39126514
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
mayton,
всё зависит от того что нужно автору
если геймдев, то обычно квадродерево, читай модификация k-d
если БД, то R-tree, оно обычно и используется в качестве индексов, но его и делать не надо, оно обычно уже в БД есть - надо просто научиться им пользоваться
...
Рейтинг: 0 / 0
12.12.2015, 20:59
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39126520
Фотография Малыхин Сергей
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Малыхин Сергей
Участник
Решал схожею задачу сканирование линией вроде самый легко реализуемый вариант
...
Рейтинг: 0 / 0
12.12.2015, 21:22
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39126902
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Малыхин Сергей, для данный способ не работает для вещественных координат
точек до тех пор пока мы не определимся с шагом сетки.

Вопрос определения этого шага пока остался за кадром.
...
Рейтинг: 0 / 0
14.12.2015, 01:28
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39127284
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
kealon(Ruslan)пардон, поиск ближайшей точки если верить википедии несколько хуже O(H*Ln(H)) H - высота дерева
А вот здесь готовая реализация


Я предлагаю этот вариант

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

Для этого нужно отдельно осортировать все точки по координатам, отдельно по X
отдельно по Y, когда вы попытаетесь вставить вашу точку
в деревья индексов координат, соседние к ней точки по осям ( 2 по оиси Х 2 по оиси Y )
дадут 4 точки вершин 4-х угольника, содержащего заданную на поверхности.
Останется из 4 точек найти ближайшую.
...
Рейтинг: 0 / 0
14.12.2015, 13:50
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39127971
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
ДохтаР,

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

Вопрос ко всем, вы возможно знаете как реализовать, у меня пока нет идей.
Пусть у нас есть точка x, множество точек p_i, i=1..n.
Как сделать так:
1. Точка x начинает распространять волну.
2. Как только любая из точек p_i получит сигнал, она останавливает алгоритм и говорит о том что она первая получила сигнал.
...
Рейтинг: 0 / 0
15.12.2015, 04:47
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39127984
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
SashaMercuryДохтаР,

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

Вопрос ко всем, вы возможно знаете как реализовать, у меня пока нет идей.
Пусть у нас есть точка x, множество точек p_i, i=1..n.
Как сделать так:
1. Точка x начинает распространять волну.
2. Как только любая из точек p_i получит сигнал, она останавливает алгоритм и говорит о том что она первая получила сигнал.
вот для этого как раз и нужно разбиение плоскости на треугольники по условию Делоне
...
Рейтинг: 0 / 0
15.12.2015, 06:43
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39127987
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
ДохтаР
Я предлагаю этот вариант

ДохтаР, вы предлагаете мой вариант, но кажется не представляете сложность построения K-d дерева. По пробуйте сделать дерево для начала или хотя бы оценить сложность его построения
...
Рейтинг: 0 / 0
15.12.2015, 06:48
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39128145
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
kealon(Ruslan)ДохтаРЯ предлагаю этот вариант

ДохтаР, вы предлагаете мой вариант, но кажется не представляете сложность построения K-d дерева. По пробуйте сделать дерево для начала или хотя бы оценить сложность его построения

Я не предлагаю чистое k-d дерево , а упрощенный вариант.

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

в kd дереве задаче сведется к 2-м прямоугольникам,
а потом по вашему алгоритму.

Что касается реализации , то когда в длинных срачах в разделе
другие СУБД я постил 2 класса которые должны хранить в себе
самобалансирующееся Р -дерево.

Задача интересная , но в своем окружении я не вижу ее монетизанции,
и поэтому у меня нет мотива развивать мысль и писать код.
...
Рейтинг: 0 / 0
15.12.2015, 10:18
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39128165
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
SashaMercuryДохтаР,

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


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

Многомернойсть отличается только масштабируемой реализацией.
Для многомерного случая коодинтаты точки хранятся не в переменных , а в массиве
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
enum space_dim {
    X = 0,
    Y= 1,
    Z= 2,
   space_SIZE=3
};

class point
{
int  place[space_SIZE];
......
}



приблизительно так....


SashaMercuryВопрос ко всем, вы возможно знаете как реализовать, у меня пока нет идей.
Пусть у нас есть точка x, множество точек p_i, i=1..n.
Как сделать так:
1. Точка x начинает распространять волну.
2. Как только любая из точек p_i получит сигнал, она останавливает алгоритм и говорит о том что она первая получила сигнал.

Кому говорит ?
Какая разница в скорости распостранения волны и сигнала говорения?

Физическая суть волны в том, что если волна ( импульс) запущена, то ее получат все
точки пространства пока она будет иметь достаточную аплитуду для сенсоров точек.
...
Рейтинг: 0 / 0
15.12.2015, 10:35
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39128181
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
kealon(Ruslan)ДохтаРЯ предлагаю этот вариант

ДохтаР, вы предлагаете мой вариант, но кажется не представляете сложность построения K-d дерева. По пробуйте сделать дерево для начала или хотя бы оценить сложность его построения

Я не вижу необходимости применения универсального алгоритма kd дерева
для данной задачи. Задача решается проще.
...
Рейтинг: 0 / 0
15.12.2015, 10:48
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39128204
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
kealon(Ruslan)SashaMercuryДохтаР,

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

Вопрос ко всем, вы возможно знаете как реализовать, у меня пока нет идей.
Пусть у нас есть точка x, множество точек p_i, i=1..n.
Как сделать так:
1. Точка x начинает распространять волну.
2. Как только любая из точек p_i получит сигнал, она останавливает алгоритм и говорит о том что она первая получила сигнал.
вот для этого как раз и нужно разбиение плоскости на треугольники по условию Делоне

Кстате вы правы , я вчера подумал над своим алгоритмом , в большенстве случаев ,
и в частности в этом 17691216
алгоритм будет выходить не на 4 угольник , а вырождаться в треугольник.
В данном случае совпадение точек найденных по индексам
X Y будет ближайшей точкой, но это совпадение , в результате поиска алгоритм
должен получить именно четерехугольник из 4 ближайших точек
на плоскости которого содержится заданная координата
от которой мы ищем ближайшую точку.
То есть в некоторых случаях нужно брать не только ближайшие соседние X Y
но и просматривать следующие за ними.
...
Рейтинг: 0 / 0
15.12.2015, 11:02
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39128221
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
SashaMercuryДохтаР,
о чём вы написали. К сожалению вы предлагаете ссылку на википедию, потому спрошу лучше у вас. Какова асимптотика в многомерном случае?


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

Методы поиска ближайшей точки (условно)

МетодСложностькомментарииПолный переборo(n)Тривиально и долгоДиаграмма Вороного (триангуляция Делоне?)?В обсужденииОбход Змейкой by maytono(n)Быстрее но линейное время остаётся в формулеK-D дерево?В обсужденииДихотомический метод ДохтарА?В обсужденииМетод ДохтарА на К-деревьях?В обсуждении

Можете оспаривать и дополнять. Я не против.
...
Рейтинг: 0 / 0
15.12.2015, 13:09
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39128491
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
maytonПредлагаю в качестве промежуточного итога такую табличку

Методы поиска ближайшей точки (условно)

МетодСложностькомментарииПолный переборo(n)Тривиально и долгоДиаграмма Вороного (триангуляция Делоне?)?В обсужденииОбход Змейкой by maytono(n)Быстрее но линейное время остаётся в формулеK-D дерево?В обсужденииДихотомический метод ДохтарА?В обсужденииМетод ДохтарА на К-деревьях?В обсуждении

Можете оспаривать и дополнять. Я не против.

Последний вычеркивай ,
это заключительный этап предыдущего пункта.
На этом этапе идет полный перебор как в первом пункте,
только из гораздо меньшего числа точек.
...
Рейтинг: 0 / 0
15.12.2015, 13:42
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39128518
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
maytonДихотомический метод ДохтарА;?;В обсуждении


Скорость зависит от алгоритма скорости вставки
значения в дерево или сортированный список .

Время работы с одним множеством умножатеся на количество
измерений пространства + О 4..8 ( как для полного перебора)
...
Рейтинг: 0 / 0
15.12.2015, 13:56
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39128542
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
maytonПредлагаю в качестве промежуточного итога такую табличку

Методы поиска ближайшей точки (условно)

МетодСложностькомментарииПолный переборo(n)Тривиально и долгоДиаграмма Вороного (триангуляция Делоне?)?В обсужденииОбход Змейкой by maytono(n)Быстрее но линейное время остаётся в формулеK-D дерево?В обсужденииДихотомический метод ДохтарА?В обсужденииМетод ДохтарА на К-деревьях?В обсуждении

Можете оспаривать и дополнять. Я не против.

Все что я тут написал это развитие идеи
17691463

Поэтому прошу к авторству добавить Dima T
...
Рейтинг: 0 / 0
15.12.2015, 14:07
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39128548
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
ДохтаРmaytonДихотомический метод ДохтарА;?;В обсуждении


Скорость зависит от алгоритма скорости вставки
значения в дерево или сортированный список в зависимости от
реализации алгоритма поиска места вставки числа в списко.

Время работы с одним множеством умножатеся на количество
измерений пространства S + О 2,3,4*s ( как для полного перебора)

Так будет точнее универсальнее и масштабируемее.
...
Рейтинг: 0 / 0
15.12.2015, 14:11
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39128561
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
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
15.12.2015, 14:17
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39128600
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
ДохтаРДохтаРпропущено...


Скорость зависит от алгоритма скорости вставки
значения в упорядоченое множество в зависимости от
реализации алгоритма поиска места для вставки .

Время работы с одним множеством умножатеся на количество
измерений пространства S + О 2,3,4*s ( как для полного перебора)

Так будет точнее универсальнее и масштабируемее.

Так ще более фундаментально получается.

зы задача интересная и точно где то пригодится ,
меня мучает мысль как это можно продать :)
...
Рейтинг: 0 / 0
15.12.2015, 14:36
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39128630
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
ДохтаР, есть целый сегмент ПО - это ГИС, геолокация, геопоиск. Там всё давно уже испахано
вдоль и поперёк. И имплементировано в БД, Spatial, GeoSearch requests.

Единственное где (я так думаю) есть возможность применить мозг - это геймдев и позиционирование. Там где отклики
меряются микросекундами и есть особые требования к скорости.
...
Рейтинг: 0 / 0
15.12.2015, 14:55
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39128636
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Версия 2.0
МетодСложностькомментарииПолный переборo(n)Тривиально и долгоДиаграмма Вороного (триангуляция Делоне?)?В обсужденииОбход Змейкой by maytono(n)Быстрее но линейное время остаётся в формулеK-D дерево?В обсужденииДихотомический метод ДохтарА и Димы-Т?В обсуждении
...
Рейтинг: 0 / 0
15.12.2015, 14:59
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39129140
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
mayton,

сложности будет две, подготовка вспомогательной структуры и сам поиск с помощью неё
...
Рейтинг: 0 / 0
15.12.2015, 20:26
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39129145
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
kealon(Ruslan), ты имеешь в виду геймдев?
...
Рейтинг: 0 / 0
15.12.2015, 20:33
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39129152
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
kealon(Ruslan)mayton,

сложности будет две, подготовка вспомогательной структуры и сам поиск с помощью неё

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

Это нормальная цена решения?
...
Рейтинг: 0 / 0
15.12.2015, 20:54
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39129172
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
maytonДля целочисленной плоскости в диапазоне short можно весь универсум
проиндексировать. Каждому пикселу сопоставить ссылку на ближайший
объект точки.

Это нормальная цена решения?

Думаю что нет, потому что алгоритмика решения в такой постановке
не масштабируется на 3D.
...
Рейтинг: 0 / 0
15.12.2015, 21:03
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39129275
Фотография Малыхин Сергей
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Малыхин Сергей
Участник
maytonМалыхин Сергей, для данный способ не работает для вещественных координат
точек до тех пор пока мы не определимся с шагом сетки.

Вопрос определения этого шага пока остался за кадром.

При чем тут шаг?
точки сортируются по одной из координат после этого перебираются по очереди

http://blog.ivank.net/fortunes-algorithm-and-implementation.html описание и реализация
...
Рейтинг: 0 / 0
16.12.2015, 00:42
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39129295
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
ДохтаР
Я не вижу необходимости применения универсального алгоритма kd дерева
для данной задачи. Задача решается проще.

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


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

В этом основная суть идеи многомерного дерева
...
Рейтинг: 0 / 0
16.12.2015, 02:05
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39129297
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
автор топикаА вот потом пойдет неслабый поток случайных точек, которым надо найти ближайшую

то о чём я и говорил. Мы могли бы и за линейное время задачу решить, если бы нам нужна была информация только для одной точки.

С трудом представляю вариант быстрее классического упорядочивания, только в данном случае, данное упорядочивание будет происходить по нескольким индексам. Один из примеров многомерное дерево.

Выше были таблицы с линейным временем по некоторым алгоритмам, что достаточно странно. Ещё раз, основное то, что нужно, фактически, найти для каждой точки ближайшую. Таким образом необходимо рассчитать асимптотику тех самых предварительных вычислений о которых писал автор, и учесть время доступа для каждого значения(время поиска в организованной структуре) при работе с потоком точек
...
Рейтинг: 0 / 0
16.12.2015, 02:12
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39129314
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
mayton Версия 2.0
МетодСложностькомментарииПолный переборo(n)Тривиально и долгоДиаграмма Вороного (триангуляция Делоне?)?В обсужденииОбход Змейкой by maytono(n)Быстрее но линейное время остаётся в формулеK-D дерево?В обсужденииДихотомический метод ДохтарА и Димы-Т?В обсуждении
подытожим
МетодСложность построенияСложность поискакомментарииПолный перебор0o(n)Тривиально и долгоДиаграмма Вороного (триангуляция Делоне?)o(n) - o(n*ln(n))o(Sqrt(n))Построить можно только для двумерного случая, применим только для численных значенийОбход Змейкой by mayton0o(n)Быстрее но линейное время остаётся в формулеK-D деревостремится к o(n^2)o(h*ln(h)), где h~ln(n)алгоритм в википедии Дихотомический метод ДохтарА и Димы-Т??В обсуждении
...
Рейтинг: 0 / 0
16.12.2015, 06:52
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39129632
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
kealon(Ruslan)mayton Версия 2.0
МетодСложностькомментарииПолный переборo(n)Тривиально и долгоДиаграмма Вороного (триангуляция Делоне?)?В обсужденииОбход Змейкой by maytono(n)Быстрее но линейное время остаётся в формулеK-D дерево?В обсужденииДихотомический метод ДохтарА и Димы-Т?В обсуждении
подытожим
МетодСложность построенияСложность поискакомментарииПолный перебор0o(n)Тривиально и долгоДиаграмма Вороного (триангуляция Делоне?)o(n) - o(n*ln(n))o(Sqrt(n))Построить можно только для двумерного случая, применим только для численных значенийОбход Змейкой by mayton0o(n)Быстрее но линейное время остаётся в формулеK-D деревостремится к o(n^2)o(h*ln(h)), где h~ln(n)алгоритм в википедии Дихотомический метод ДохтарА и Димы-ТO(n*2*S)в иделале s*O(С)+O(8)В обсуждении

расшифровка:

O(n*2*S) - нужно 2 сканирования точек на каждое имерение пространства.
1. набор статистики и инициализация хеш слотов по каждому изменению.
2. загрузка в сортированный hash_set.


в иделале s*O(С)+O(8) - поиск по hash_set - O(С) умноженная на количество измерений пространства S.
...
Рейтинг: 0 / 0
16.12.2015, 12:44
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39129654
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
ДохтаР1. набор статистики и инициализация хеш слотов по каждому изменению.


В этом случае появляется зависимость
реализации ( кода ) от аппаратной платформы(Endianness).
...
Рейтинг: 0 / 0
16.12.2015, 12:58
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39129692
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
SashaMercuryДохтаР
Я не вижу необходимости применения универсального алгоритма kd дерева
для данной задачи. Задача решается проще.

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


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

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

KD дерево было бы полезным, если бы множество точек подвергалось
изменению в процессе работы алгоритма.
Если множестово точкек константно в процессе работы , то грех не использовать
это обстоятельство для оптимизации.
...
Рейтинг: 0 / 0
16.12.2015, 13:18
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39129764
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
ДохтаРKD дерево оперирует прямоугольниками , а для решения задачи
проще использовать 4 угольники получая напрямую из индекса координат.
Единственное преимущество использования KD дерева , готовые библиотеки.

мне кажется проще всё же прямоугольниками, потому что даже с треугольниками не всё так просто
(да и прямоугольники в дереве неявные агрегаты)ДохтаРУчитывая пришедшую мне мысль использовать динамическое хеш распределение
путем сбора статистки сложением битовых масок координат ,
и равномерного разбрасывания точек по хеш слотам, можно
предполагать выход на константное время поиска , после того
как индексы массива точек будет подготовлены.
чем это лучше индексирования пространства на сетку?ДохтаРKD дерево было бы полезным, если бы множество точек подвергалось
изменению в процессе работы алгоритма.
Если множестово точкек константно в процессе работы , то грех не использовать
это обстоятельство для оптимизации.
к сожалению пока не придумали адекватного алгоритма авто-балансировки k-d дерева близкого к o(ln(n)) даже для двумерного случая:-(

PS: o(const) равноценно o(1), соответственно o(const * n) равноценно o(n)
...
Рейтинг: 0 / 0
16.12.2015, 14:03
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39129803
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Малыхин СергейmaytonМалыхин Сергей, для данный способ не работает для вещественных координат
точек до тех пор пока мы не определимся с шагом сетки.

Вопрос определения этого шага пока остался за кадром.

При чем тут шаг?
точки сортируются по одной из координат после этого перебираются по очереди

http://blog.ivank.net/fortunes-algorithm-and-implementation.html описание и реализация
Просто демка так была показана как будто мы работаем с методом сеток
или чем-то численным. Надо было другое видео приаттачить где
хм... больше аналитики штоль.
...
Рейтинг: 0 / 0
16.12.2015, 14:30
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39129819
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
ДохтаРmaytonДля целочисленной плоскости в диапазоне short можно весь универсум
проиндексировать. Каждому пикселу сопоставить ссылку на ближайший
объект точки.

Это нормальная цена решения?

Думаю что нет, потому что алгоритмика решения в такой постановке
не масштабируется на 3D.
Он одинаково хреново масштабируется или не-масштабируется для 2D и 3D.
Но прежде чем решать задачу старым дедовским научным методом
я обычно предлагаю тривиальные, хардкорные и табличные решения.

В дополнение к "сопоставить ссылку" - раскрасить многоугольники Вороного-Делоне
(от 1 до 256) каждый в свой цвет. В какой цвет попали - та и точка.
...
Рейтинг: 0 / 0
16.12.2015, 14:40
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39129834
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
maytonДохтаРпропущено...


Думаю что нет, потому что алгоритмика решения в такой постановке
не масштабируется на 3D.
Он одинаково хреново масштабируется или не-масштабируется для 2D и 3D.
Но прежде чем решать задачу старым дедовским научным методом
я обычно предлагаю тривиальные, хардкорные и табличные решения.

В дополнение к "сопоставить ссылку" - раскрасить многоугольники Вороного-Делоне
(от 1 до 256) каждый в свой цвет. В какой цвет попали - та и точка.

О!!!, это уже похоже на хеш......
...
Рейтинг: 0 / 0
16.12.2015, 14:50
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39129843
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
ДохтаР, это лучше чем хэш. Док. Это блджад O(1) без промахов.
...
Рейтинг: 0 / 0
16.12.2015, 15:02
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39129858
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
kealon(Ruslan)ДохтаРKD дерево оперирует прямоугольниками , а для решения задачи
проще использовать 4 угольники получая напрямую из индекса координат.
Единственное преимущество использования KD дерева , готовые библиотеки.

мне кажется проще всё же прямоугольниками, потому что даже с треугольниками не всё так просто
(да и прямоугольники в дереве неявные агрегаты)

чем это лучше индексирования пространства на сетку?


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



kealon(Ruslan)PS: o(const) равноценно o(1), соответственно o(const * n) равноценно o(n)


Нет,
О(С) - сложность не зависит от количества
элементов множества , которым оперирует алгоритм.

намомню используя терминологию О(n,ln(n), С) мы переходим
от оперирования значениями, в жонглирование теорией пределов из матана.
Там другая сетка :)
...
Рейтинг: 0 / 0
16.12.2015, 15:11
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39129864
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
maytonДохтаР, это лучше чем хэш. Док. Это блджад O(1) без промахов.


Посчитай сколько в среднем вершин попадет фигуру одного цвета,
я думаю, что около 6-и, твоя раскраска стремится к О(n/6).



Вспомни , это базисту на пальцах обьясняли ,
когда он нес пургу о хешах в #стебельке.
...
Рейтинг: 0 / 0
16.12.2015, 15:21
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39129894
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
ДохтаРПосчитай сколько в среднем вершин попадет фигуру одного цвета,
я думаю, что около 6-и, твоя раскраска стремится к О(n/6).

Вообще не понял суть твоего пассажа! Что куда стремиться?

Я предложил целочисленно - точное решение. Как раскрасил - так и будет.

И причём тут базист с хешами? Я про хеши вообще ничего не сказал.
...
Рейтинг: 0 / 0
16.12.2015, 15:44
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39129932
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
maytonДохтаРПосчитай сколько в среднем вершин попадет фигуру одного цвета,
я думаю, что около 6-и, твоя раскраска стремится к О(n/6).

Вообще не понял суть твоего пассажа! Что куда стремиться?

Я предложил целочисленно - точное решение. Как раскрасил - так и будет.

И причём тут базист с хешами? Я про хеши вообще ничего не сказал.

Если мы оперируем терминами О(n,ln(n), С) , то мы оперируем теорией пределов,
а именно отношением стремления
количества элементов в множестве обрабатываемым алгоритмом
к тактам процессора к нулю или безконечности.

Давайте будем использовать одинаковую терминологию
либо целочисленную, либо О(n,ln(n), С) что бы не путаться,
потому что у них принципиально разные попугаи влияющие на кост,
я например не понимаю , в каких попугаях кто что считает и имеет ввиду.

В таблице пишем одно , когда что то аргументируем используем другое.
...
Рейтинг: 0 / 0
16.12.2015, 16:13
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39129946
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
maytonДохтаРПосчитай сколько в среднем вершин попадет фигуру одного цвета,
я думаю, что около 6-и, твоя раскраска стремится к О(n/6).

Вообще не понял суть твоего пассажа! Что куда стремиться?

Я предложил целочисленно - точное решение. Как раскрасил - так и будет.

И причём тут базист с хешами? Я про хеши вообще ничего не сказал.

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

Поэтому хотелось бы услвшать об алгоритме,
как зависит количество цветов от количества точек.

И как ты планируешь искать конкретный цвет среди 10 млн цветов
и 100 000 000 млн точек.

Сколко по твоему должно быть цветов в палитре
при 1000 точек при 100 000 точек и при 100 000 000 точек .
...
Рейтинг: 0 / 0
16.12.2015, 16:20
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39129963
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
ДохтаР, да никак не планирую. Я предложил тупой маргинальный табличный алгоритм.
С кучей ограничений на memory и разрядность цвета. Да и нет никакого цвета.
Просто метафора.

Но он (алгоритм) имеет место в нашей дискуссии как отправная точка для СРАВНЕНИЯ
алгоритмов. А если у тебя дискретное поле 10 на 10 и точек штук 20 - так это и будет самая
лучшая имплеметнация. Я гарантирую это (с)
...
Рейтинг: 0 / 0
16.12.2015, 16:33
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39129972
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
maytonДохтаР, да никак не планирую. Я предложил тупой маргинальный табличный алгоритм.
С кучей ограничений на memory и разрядность цвета. Да и нет никакого цвета.
Просто метафора.

Но он (алгоритм) имеет место в нашей дискуссии как отправная точка для СРАВНЕНИЯ
алгоритмов. А если у тебя дискретное поле 10 на 10 и точек штук 20 - так это и будет самая
лучшая имплеметнация. Я гарантирую это (с)

Для простых случаев 100 на 100 я согласен,
но тут уже начали оперировать порядками и сеткой
стремящими к бесконечности исполюзуя O(ln(n)).

Надо бы у ТС спросить о каких подяках идет речь , о десятках точек
или о сотнях миллионов.

С точки зрения интелектуальных трудозатрат на кодинг это имет огромное значение.
В большенсве практических случаев
нет смысла экономить на спичках и забивать свою голову и ломать копья
вокруг теории пределов.
...
Рейтинг: 0 / 0
16.12.2015, 16:44
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39130032
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Еще зависит от гистограммы. К примеру взять Quad-Tree.
При некоторых раскладах оно работает хуже простого
разбиения пространства на одинаковые сегменты. Тоесть
мы можем найти наихудший случай при котором дерево
теряет смысл и вырождается в "матрицу с уровнями".
...
Рейтинг: 0 / 0
16.12.2015, 17:34
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39130070
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
МетодСложность построенияСложность поискакомментарииПолный перебор0o(n)Тривиально и долгоДиаграмма Вороного (триангуляция Делоне?)o(n) - o(n*ln(n))o(Sqrt(n))Построить можно только для двумерного случая, применим только для численных значенийОбход Змейкой by mayton0o(n)Быстрее но линейное время остаётся в формулеK-D деревостремится к o(n^2)o(h*ln(h)), где h~ln(n)алгоритм в википедии Дихотомический метод ДохтарА и Димы-Т??В обсужденииДиаграмма Вороного (триангуляция Делоне?) + раскраска Мейтонаo(n) - o(n*ln(n))o(1)Жрёт память. Целочисленные координаты. Зависит от разрядности координат. Зависит разрядности цвета 8/16/24/32.
...
Рейтинг: 0 / 0
16.12.2015, 18:10
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39130192
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
ДохтаР
kealon(Ruslan)PS: o(const) равноценно o(1), соответственно o(const * n) равноценно o(n)


Нет,
О(С) - сложность не зависит от количества элементов множества , которым оперирует алгоритм.

потому o(const) и равноценно o(1), что не зависит от N (N никак не константа для алгоритма), просто функции "o" разные в каждом случае, но индекс мы опускаем
пределы из матана тут ни при чём, это принятая o-нотация сложности вычислений
...
Рейтинг: 0 / 0
16.12.2015, 20:42
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39130250
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ребята. Док. Дима. Руслан. Саша.

Я думал о тестовых данных. И вот к чему пришёл. У нас есть минимум 5 измерений по классам алгоритмов.
Но у нас нет представления о том как наши 5 алгоритмов соотносятся с различными наборами входных
данных. Поэтому беру на себя обязательство нагенерировать наборы.

1) 1% равномерное заполнение (очень мало точек)
2) 3% равномерное заполнение (мало точек)
3) 50% шум (много точек)
4) Один кластер точек с ярко выраженным центром (по Гауссу). Трёхсигмовая зона - не выходит за пределы картинки.
5) Два кластера точек. Центры - разнесены на расстояние.
6) Три кластера точек (с неодинаковым количеством точек в кластерах). Распределение - аналогично п (4) и (5).
7) Точки с ярко-выраженной географической составляющей (линия берега).
8) Точки с ярко-выраженной исскусственной географией (линии домов, кварталов, дорог).

Для пунктов (4) (5) (6) количество точек я определю чуть позже. Главное требование - чтобы
в центре не было наложения точки на точку.

Пункты (7) и (8) я постараюсь взять из реальных фотоснимков местности.

Наборы будут сохранены в виде

1) Ч.Б картинок с размером 256x256 где точки - черный цвет.
2) В виде CSV-файлов с координатами.
Для простоты - целочисленными.

Итого - 8 файлов с картинками + 8 csv файлов.
...
Рейтинг: 0 / 0
16.12.2015, 22:43
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39130251
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Да. Если есть пожелания по добавлению новых наборов - пишите. Учту.
...
Рейтинг: 0 / 0
16.12.2015, 22:45
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39130254
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
kealon(Ruslan)ДохтаРпропущено...


Нет,
О(С) - сложность не зависит от количества элементов множества , которым оперирует алгоритм.

потому o(const) и равноценно o(1), что не зависит от N (N никак не константа для алгоритма), просто функции "o" разные в каждом случае, но индекс мы опускаем
пределы из матана тут ни при чём , это принятая o-нотация сложности вычислений

кем принятая ?

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

Так же как есть физический смысл в килограмах(кг) , метрах(м) ,
метрах в секунду(s/t)
или метрах в секунду в квадрате(s/t 2 ).

будьте добры, сформулируейте смысл O нотации в вашем понимании,
аналогично как я его софрмулировал тут 18568636 для теории пределов из матана.
...
Рейтинг: 0 / 0
16.12.2015, 22:48
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39130337
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Существуют классические определения асимптотических обозначений, и всё. В любой приличной книге по алгоритмам их можно встретить, и везде они будут написаны в одном и том-же смысле и в очень похожей формулировке. Асимптотика должна зависеть от количества входных экземпляров, от n в нашем случае.

Только мне непонятно как у вас асимптотика построения Диаграммы Вороного получается отрицательной, объясните пожалуйста
...
Рейтинг: 0 / 0
17.12.2015, 02:12
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39130391
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
SashaMercuryСуществуют классические определения асимптотических обозначений, и всё. В любой приличной книге по алгоритмам их можно встретить, и везде они будут написаны в одном и том-же смысле и в очень похожей формулировке. Асимптотика должна зависеть от количества входных экземпляров, от n в нашем случае.

Только мне непонятно как у вас асимптотика построения Диаграммы Вороного получается отрицательной, объясните пожалуйста
это я просто так указал интервал: o(n) - некотрые алгоритмы работают за это время, o(n*ln(n)) - крайний предел за который работает нормальный алгоритм. Надо было наверное от o1(n) до o2(n*ln(n))
...
Рейтинг: 0 / 0
17.12.2015, 07:36
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39130535
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
kealon(Ruslan)SashaMercuryСуществуют классические определения асимптотических обозначений, и всё. В любой приличной книге по алгоритмам их можно встретить, и везде они будут написаны в одном и том-же смысле и в очень похожей формулировке. Асимптотика должна зависеть от количества входных экземпляров, от n в нашем случае.

Только мне непонятно как у вас асимптотика построения Диаграммы Вороного получается отрицательной, объясните пожалуйста
это я просто так указал интервал: o(n) - некотрые алгоритмы работают за это время, o(n*ln(n)) - крайний предел за который работает нормальный алгоритм. Надо было наверное от o1(n) до o2(n*ln(n))



То есть от O(n= 2 980 .957983014) до ( n*ln(n)= 23 847 .663864116)
разница в скорости 8 раз.

или O(n= 8 886 110 .496494895) до О(n*ln(n)= 142 177 767 .943918322)
разница в 16 раз .

Числа взяты специально , что бы получить целочисленное число
раз сравнения скорости работы алгоритма в зависимости от n.
ln( 2 980.957983014)=8
ln(8 886 110.496494895) =16


Я правильно понял порядок попугаев зависимости скорости от n
когда мы оперируем терминологией О(n, ln(C) ) ?
...
Рейтинг: 0 / 0
17.12.2015, 10:44
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39130557
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
Резюмирую:
на значениях порядках n 1000 наши абстрактные алгоритмы могут отличаться
по производительности в 8 раз.
теже алгоритмы на порядках n-миллионы в 16 раз.

Но на прктике мы иногда радуемся 30% приросту производительности
не зависимо от n.

ps все это к вопросу о разрядной сетке измерений алгоритмов
привязанной к теории пределов.
...
Рейтинг: 0 / 0
17.12.2015, 11:03
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39130590
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
авторЧисла взяты специально , что бы получить целочисленное число
раз сравнения скорости работы алгоритма в зависимости от n.
ln( 2 980.957983014)=8
ln(8 886 110.496494895) =16


А вобще , как я себе это предстваляю
О(n=2 980) и О(ln(n=2 980)=8)
отношение в тактах процессора затраченных на алгоритм
работы с множеством O(n) / O(ln(n)) =372.5 раза
а для n =8 886 110 O(n) / O(ln(n) =5 55 381.875 раз

отношение илюситруется графиком


О(n) по оси Х
О(ln(n)) по оси Y
начиная с точки х=1
...
Рейтинг: 0 / 0
17.12.2015, 11:30
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39130641
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Чювачки.

Наша тема in general называется NNS (Nearest neighbor search)
https://en.wikipedia.org/wiki/Nearest_neighbor_search

Правильно ли я понимаю?
...
Рейтинг: 0 / 0
17.12.2015, 12:08
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39130686
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
ДохтаР, на практике в наши алгортмы а точнее в их реализацию (на малых объёмах N) будет внесена
офигенская константа. Надо об это не забыть.
...
Рейтинг: 0 / 0
17.12.2015, 12:54
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39130702
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
maytonДохтаР, на практике в наши алгортмы а точнее в их реализацию (на малых объёмах N) будет внесена
офигенская константа. Надо об это не забыть.

ИМХО
Эта офигенная константа погрешности уже имперически( статистически) заложена
при выборе натурального логарифма в формуле О(ln(n)).
2,718281828 n=1 -2 n=1 =0.718281828
...
Рейтинг: 0 / 0
17.12.2015, 13:06
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39130720
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
ДохтаРmaytonДохтаР, на практике в наши алгортмы а точнее в их реализацию (на малых объёмах N) будет внесена
офигенская константа. Надо об это не забыть.

ИМХО
Эта офигенная константа погрешности уже имперически( статистически) заложена
при выборе натурального логарифма в формуле О(ln(n)).
2,718281828 n=1 -2 n=1 =0.718281828


Как минимум для реализации деревьев и прочих алгоритмов
имеющих формулу О(ln(n))

Вопрос почему там натуральный логарифм, а не двоичный,
математичских обоснований для выбора натурального логарифма вместо
двоичного я не нашел.
...
Рейтинг: 0 / 0
17.12.2015, 13:12
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39130857
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Я говорю о другой поправке. Которая зависит к примеру от cost реализации 1-й
итерации цикла к примеру или от 1 дискового IOPS. Я говорю о реальном затраченном
времени. Об execution time. И об его связи с этими графиками.

Не на бесконечности. А на малых значения.
...
Рейтинг: 0 / 0
17.12.2015, 14:38
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39130866
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Чювачки.

Я создал репку для экспериментов. Регайтесь.
...
Рейтинг: 0 / 0
17.12.2015, 14:51
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39130867
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
https://sourceforge.net/p/nnsexperiments/code/HEAD/tree/
...
Рейтинг: 0 / 0
17.12.2015, 14:51
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39130966
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
maytonЯ говорю о другой поправке. Которая зависит к примеру от cost реализации 1-й
итерации цикла к примеру или от 1 дискового IOPS. Я говорю о реальном затраченном
времени. Об execution time. И об его связи с этими графиками.

Не на бесконечности. А на малых значения.

Все относительно.

Для кого то 10 000 бесконечность ,
кто делает 10 000 ! ( факториал ) переборов.

а для кого то 10 млн рядовая задача,
кто использует алгоритм О(ln(n)).
...
Рейтинг: 0 / 0
17.12.2015, 16:03
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39132585
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
ДохтаРВопрос почему там натуральный логарифм, а не двоичный,
математичских обоснований для выбора натурального логарифма вместо
двоичного я не нашел.
наверное потому, что ln(a) по основанию b = ln(a)/ ln(b) ?

ДохтаРТо есть от O(n= 2 980.957983014) до ( n*ln(n)= 23 847.663864116)
разница в скорости 8 раз.

или O(n=8 886 110.496494895) до О(n*ln(n)=142 177 767.943918322)
разница в 16 раз .
я кажется специально там индексы поставил около O >> o 1 (n) до o 2 (n*ln(n))
O выражает только масштабируемость нагрузки алгоритма от N

PS: алгоритм Фюррера например O(N*ln(N)), но никто же в здравом уме его не будет на мелких числах применять, медленнее чем столбиком выйдет O(N^2)

mayton Я создал репку для экспериментов. Регайтесь.
Извиняй, напряг со временем совсем, новая работа, в блог занести хоть что-то никак не соберусь
линка на простой инкрементальный алгоритм триангуляции. при правильной подаче данных будет линейно работать, в отличие от оригинала
 
Код: plaintext
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.
Speed Test in my PC
10000 points
Random construction triangulation sorted time in ms: 62 pure time(47)
Random construction triangulation one-by-one time in ms: 47 pure time(47)
30000 points
Random construction triangulation sorted time in ms: 172 pure time(172)
Random construction triangulation one-by-one time in ms: 312 pure time(312)
50000 points
Random construction triangulation sorted time in ms: 343 pure time(327)
Random construction triangulation one-by-one time in ms: 780 pure time(780)
100000 points
Random construction triangulation sorted time in ms: 967 pure time(936)
Random construction triangulation one-by-one time in ms: 2637 pure time(2637)
CgalTriangulationTest.exe:
Enter number of points for triangulation :10000
Random construction triangulation time in ms: 48
Random construction triangulation one-by-one time in ms: 1134
Enter number of points for triangulation :30000
Random construction triangulation time in ms: 152
Random construction triangulation one-by-one time in ms: 8060
Enter number of points for triangulation :50000
Random construction triangulation time in ms: 271
Random construction triangulation one-by-one time in ms: 17546
Enter number of points for triangulation :100000
Random construction triangulation time in ms: 700
Random construction triangulation one-by-one time in ms: 61943
...
Рейтинг: 0 / 0
20.12.2015, 18:06
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39132967
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonСтранно. Как-то в браузере они бледненько смотряться. Хотя я включал 100% черный цвет для точек.
Браузер "оптимизирует". Если в паинт скопировать - черные точки.
...
Рейтинг: 0 / 0
21.12.2015, 12:31
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39133259
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
maytonСтранно. Как-то в браузере они бледненько смотряться. Хотя я включал 100% черный цвет для точек.
Извини,
Я не специались в парсинге png формата ,
что бы из него координаты точек выдергивать.
:)
...
Рейтинг: 0 / 0
21.12.2015, 15:33
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39133396
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Всё будет чики-пики док. Я приложу CSV с координанами для каждой картинки.

Кстате... нафига ты самозобанился? Вот мозохист
...
Рейтинг: 0 / 0
21.12.2015, 16:23
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39138331
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
maytonВсё будет чики-пики док. Я приложу CSV с координанами для каждой картинки.

Кстате... нафига ты самозобанился? Вот мозохист


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

А где координаты, которые будем тестить и сравнивать ?
...
Рейтинг: 0 / 0
25.12.2015, 16:56
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39226357
nikichale
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
nikichale
Гость
Вообще то для решения таких задач используется 2х мерный индекс. Его прямое назначение за log(N) операций выбирать точки в заданном прямоугольнике (и не обязательно точки). Для поиска ближайших точек к заданной делается несколько итераций начиная с малой окрестности и увеличивая радиус поиска вдвое, пока не будет найдено хоть что-то. Такие индексы реализованы во всех ГИС. Имею свою довольно простую реализацию 2х мерного индекса.
Если не отвечу - пишите сюда nikichale@yahoo.com
...
Рейтинг: 0 / 0
28.04.2016, 09:56
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39226417
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Кривую Мортона можно использовать. Для разложения 2D -> 1D
...
Рейтинг: 0 / 0
28.04.2016, 10:58
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39226550
nikichale
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
nikichale
Гость
ну да, типа замешиваешь побитно X и Y координаты и получаешь из двух чисел одно. Потом упорядочиваешь массив из таких XY для всех точек. Потом сложнее, для поиска точек в квадрате нужно просканировать 4 интервала в этом массиве.
...
Рейтинг: 0 / 0
28.04.2016, 12:37
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39228774
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
nikichaleВообще то для решения таких задач используется 2х мерный индекс. Его прямое назначение за log(N) операций выбирать точки в заданном прямоугольнике (и не обязательно точки). Для поиска ближайших точек к заданной делается несколько итераций начиная с малой окрестности и увеличивая радиус поиска вдвое, пока не будет найдено хоть что-то. Такие индексы реализованы во всех ГИС. Имею свою довольно простую реализацию 2х мерного индекса.
Если не отвечу - пишите сюда nikichale@yahoo.com

Вы не говорите о сложности построения данного индекса и о побочных эффектах. Приведите пожалуйста пример вашей простой реализации
...
Рейтинг: 0 / 0
04.05.2016, 04:22
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39228775
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Откуда такая информация про все ГИС ?
...
Рейтинг: 0 / 0
04.05.2016, 04:23
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39228781
Фотография iv_an_ru
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
iv_an_ru
Участник
SashaMercuryОткуда такая информация про все ГИС ?Ну в общем-то без четревьев или R-дерева производительность ГИС будет абсолютно удрючающей, так что во всех взрослых системах это действительно есть.
...
Рейтинг: 0 / 0
04.05.2016, 05:56
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39228782
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
iv_an_ruSashaMercuryОткуда такая информация про все ГИС ?Ну в общем-то без четревьев или R-дерева производительность ГИС будет абсолютно удрючающей, так что во всех взрослых системах это действительно есть.

Как я понял, nikichale не имел ввиду R-деревья
...
Рейтинг: 0 / 0
04.05.2016, 05:59
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39229026
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Не будьте так категоричны. Недавно Док мне дал ссылку на M-Деревья.
Вобщем - это окружности по своей сути. Поэтому я-бы предположил что Spatial-структур
данных или Spatial индексов мы можем брать бесконечно много способов
деления пространства на гипер-кубики, *-плоскости или *-сферы.
Главное чтобы соблюдались принципы не-линейного роста времени поиска.
...
Рейтинг: 0 / 0
04.05.2016, 12:42
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39229145
д0k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0k
Гость
maytonНе будьте так категоричны. Недавно Док мне дал ссылку на M-Деревья.
Вобщем - это окружности по своей сути. Поэтому я-бы предположил что Spatial-структур
данных или Spatial индексов мы можем брать бесконечно много способов
деления пространства на гипер-кубики, *-плоскости или *-сферы.
Главное чтобы соблюдались принципы не-линейного роста времени поиска.

+1

Вибирайте на свой вкус и цвет :)
...
Рейтинг: 0 / 0
04.05.2016, 14:40
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39229493
nikichale
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
nikichale
Гость
SashaMercury,

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

Ну действительно есть способ, как делать выборку по одномерному индексу построенному на замешанных побитно XY чтобы выбрать точки в прямоугольнике (правда с запасом).
Механизм успешно работает (лет 15) в некоем ГИС.
А R-деревья здесь действительно не причем...

Сложность:
на каждую точку одно вхождение замешанных побитно XY в индекс
Побочные эффекты:
1. для поиска в прямоугольнике нужно просканировать НЕСКОЛЬКО интервалов индекса (мин. количество - 4)
2. будут найдены лишние точки - на самом деле ищутся точки находящиеся в прямоугольнике выравненном по сетке и содержащем данный; данный эффект можно уменьшить за счет увеличения числа интервалов сканирования
...
Рейтинг: 0 / 0
04.05.2016, 23:06
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39229495
nikichale
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
nikichale
Гость
iv_an_ru,

"четревьев" может это оно и есть о чем я?
...
Рейтинг: 0 / 0
04.05.2016, 23:16
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39229534
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
nikichale, какова сложность построения индекса, вставки нового элемента и удаления элемента?
...
Рейтинг: 0 / 0
05.05.2016, 02:40
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39229550
nikichale
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
nikichale
Гость
SashaMercurynikichale, какова сложность построения индекса, вставки нового элемента и удаления элемента?

Дык это просто способ свести задачу к обычному одномерному индексу.
Вот если нужно искать не точки, а протяженные объекты, тогда на один объект вставляется/удаляется до 4х значений XY и результат выборки нужно группировать
...
Рейтинг: 0 / 0
05.05.2016, 06:43
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39229577
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
nikichaleiv_an_ru,

"четревьев" может это оно и есть о чем я?
Я-бы не вводил коллег в ступор такими терминами. Есть-же
английский или англоицизм. Мы к нему достаточно адаптипрованы.
...
Рейтинг: 0 / 0
05.05.2016, 08:43
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39229585
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
nikichaleSashaMercurynikichale, какова сложность построения индекса, вставки нового элемента и удаления элемента?

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

Каким образом вы будете это делать? Что за 'просто способ' ?
...
Рейтинг: 0 / 0
05.05.2016, 09:13
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39229677
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
На стыке классических баз данных и ГИС используется

https://en.wikipedia.org/wiki/Z-order_curve

Ее иногда называют Z-кривая, она-же Кривая Мортона и она-же Порядок Мортона e.t.c.
...
Рейтинг: 0 / 0
05.05.2016, 10:52
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39229704
Фотография iv_an_ru
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
iv_an_ru
Участник
maytonnikichaleiv_an_ru,

"четревьев" может это оно и есть о чем я?
Я-бы не вводил коллег в ступор такими терминами. Есть-же
английский или англоицизм. Мы к нему достаточно адаптипрованы.Кнут, "сортировка и поиск". В англицком это quad-trees. В случае плоскости это деление квадрата на 4 или больше квадрата на каждом уровне индекса, в пространстве куб на 8 кусков. Хотя бывает, что дробят сразу на 16--64--256 кусков, особенно в САПРах.
...
Рейтинг: 0 / 0
05.05.2016, 11:21
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39229711
д0k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0k
Гость
iv_an_rumaytonпропущено...

Я-бы не вводил коллег в ступор такими терминами. Есть-же
английский или англоицизм. Мы к нему достаточно адаптипрованы.Кнут, "сортировка и поиск". В англицком это quad-trees. В случае плоскости это деление квадрата на 4 или больше квадрата на каждом уровне индекса , в пространстве куб на 8 кусков. Хотя бывает, что дробят сразу на 16--64--256 кусков, особенно в САПРах.

В подавляющем большенстве случаев этот матан используется как империческая
константа определяющая критерии балансировки дерева.
Более простыми словами , от корня до значения
должено быть не более 4 адресный операций.
3 ветви + 1 листовой блок хранящий непосредствено само значение.
...
Рейтинг: 0 / 0
05.05.2016, 11:32
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39229721
Фотография iv_an_ru
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
iv_an_ru
Участник
maytonНа стыке классических баз данных и ГИС используется

https://en.wikipedia.org/wiki/Z-order_curve

Ее иногда называют Z-кривая, она-же Кривая Мортона и она-же Порядок Мортона e.t.c.Один только недостаток у этой кривой --- мрачная непредсказуемость селективности, поэтому при попытке использовать её на большой дисковой памяти SQL-процессор встаёт колом. Для хорошего пространственного индекса N точек на квадрате площади 1, матожидание трудоёмкости выборки "рамкой" со стороной 1/x почти пропорционально 2 ln(x) + N/(pagesize * x^2), а Z-ордер с вероятностью, экспоненциально падающей с ростом x, выкидывает "фортели", приводящие к чтению до половины точек набора, давая разброс от 2 ln(x) + N/(pagesize * x^2) до 2 ln(x) + N/(pagesize * 2). Для иных задач простая выборка по X и потом по Y может оказатьcя не хуже :)
...
Рейтинг: 0 / 0
05.05.2016, 11:43
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39229729
Фотография iv_an_ru
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
iv_an_ru
Участник
д0kiv_an_ruпропущено...
Кнут, "сортировка и поиск". В англицком это quad-trees. В случае плоскости это деление квадрата на 4 или больше квадрата на каждом уровне индекса , в пространстве куб на 8 кусков. Хотя бывает, что дробят сразу на 16--64--256 кусков, особенно в САПРах.
В подавляющем большенстве случаев этот матан используется как империческая
константа определяющая критерии балансировки дерева.
Не понял, какой матан и какая балансировка.
д0kБолее простыми словами , от корня до значения должено быть не более 4 адресный операций. 3 ветви + 1 листовой блок хранящий непосредствено само значение.Ну подсчитайте. 8К дисковая страница, пусть в среднем 4 байта жатое инкрементом значение и 4 байта адрес следующей страницы, итого ветвление 1000x от уровня к уровню. 3 ветви дадут всего миллиард адресов страниц-ветвей, это только 8 терабайт диска. Детский размерчик, для бедных :)
...
Рейтинг: 0 / 0
05.05.2016, 11:51
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39229731
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
iv_an_ruОдин только недостаток у этой кривой --- мрачная непредсказуемость селективности, поэтому при попытке использовать её на большой дисковой памяти SQL-процессор встаёт колом. Для хорошего пространственного индекса N точек на квадрате площади 1, матожидание трудоёмкости выборки "рамкой" со стороной 1/x почти пропорционально 2 ln(x) + N/(pagesize * x^2), а Z-ордер с вероятностью, экспоненциально падающей с ростом x, выкидывает "фортели", приводящие к чтению до половины точек набора, давая разброс от 2 ln(x) + N/(pagesize * x^2) до 2 ln(x) + N/(pagesize * 2). Для иных задач простая выборка по X и потом по Y может оказатьcя не хуже :)
Чувствуется опыт. Ты работал с ГИС-ами?
...
Рейтинг: 0 / 0
05.05.2016, 11:55
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39229742
д0k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0k
Гость
iv_an_ruд0kпропущено...

В подавляющем большенстве случаев этот матан используется как империческая
константа определяющая критерии балансировки дерева.
Не понял, какой матан и какая балансировка.
д0kБолее простыми словами , от корня до значения должено быть не более 4 адресный операций. 3 ветви + 1 листовой блок хранящий непосредствено само значение.Ну подсчитайте. 8К дисковая страница, пусть в среднем 4 байта жатое инкрементом значение и 4 байта адрес следующей страницы , итого ветвление 1000x от уровня к уровню. 3 ветви дадут всего миллиард адресов страниц-ветвей, это только 8 терабайт диска. Детский размерчик, для бедных :)

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

Жаль что грохнули срачи в других СУБД , я бы вам показал 2 класса
реализующие страницы самобалансирующегося дерева.

Там, в сраче, речь шла о виртуально непрерывном адресном пространстве,
блоках, экстентах , фрагментах...
Профильным термином ресурса о rowid в терменологии СУБД, который придуман
за царя гороха, в большенстве случаев ( СУБД) строится исходя имперического
числа 4 ( адресных операции) .

Когда балансировка вылазит за импирическое число 4 , производители СУБД,
как правило, рекомендую перестроить индекс ( поменять опции хранения) ,
если у них нет функционала автоматической балансировки.
...
Рейтинг: 0 / 0
05.05.2016, 12:11
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39229764
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
д0kПрофильным термином ресурса о rowid в терменологии СУБД, который придуман
за царя гороха, в большенстве случаев ( СУБД) строится исходя имперического
числа 4 ( адресных операции) .

Речь идет о 4 физических чтениях (IOPS) ?
...
Рейтинг: 0 / 0
05.05.2016, 12:25
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39229777
д0k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0k
Гость
maytonд0kПрофильным термином ресурса о rowid в терменологии СУБД, который придуман
за царя гороха, в большенстве случаев ( СУБД) строится исходя имперического
числа 4 ( адресных операции) .

Речь идет о 4 физических чтениях (IOPS) ?

Это в самом худшем случае....

А речь идет о 4 адресных операциях ( накладных расходах
на реализацию виртуально непрырывного адресного пространства).

При правильно построенном и разогретом LRU кеше,
как правило требуется дисковый 1 IOPS для получения
rowid записи из листовго блока индекса по ключу
и еще 1 IOPS для получения самой записи.
...
Рейтинг: 0 / 0
05.05.2016, 12:34
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39229838
д0k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0k
Гость
iv_an_ruд0kпропущено...

В подавляющем большенстве случаев этот матан используется как империческая
константа определяющая критерии балансировки дерева.
Не понял, какой матан и какая балансировка.


Упомянутый ранее вами частный случай "четревьев" как импирическая константа.
...
Рейтинг: 0 / 0
05.05.2016, 13:19
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39229865
Фотография iv_an_ru
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
iv_an_ru
Участник
maytonТы работал с ГИС-ами?Писал один решатель транспортной задачи, и потом большую часть геометрии в СУБД OpenLink Virtuoso.
...
Рейтинг: 0 / 0
05.05.2016, 13:37
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230070
nikichale
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
nikichale
Гость
iv_an_rumaytonНа стыке классических баз данных и ГИС используется

https://en.wikipedia.org/wiki/Z-order_curve

Ее иногда называют Z-кривая, она-же Кривая Мортона и она-же Порядок Мортона e.t.c.Один только недостаток у этой кривой --- мрачная непредсказуемость селективности, поэтому при попытке использовать её на большой дисковой памяти SQL-процессор встаёт колом. Для хорошего пространственного индекса N точек на квадрате площади 1, матожидание трудоёмкости выборки "рамкой" со стороной 1/x почти пропорционально 2 ln(x) + N/(pagesize * x^2), а Z-ордер с вероятностью, экспоненциально падающей с ростом x, выкидывает "фортели", приводящие к чтению до половины точек набора, давая разброс от 2 ln(x) + N/(pagesize * x^2) до 2 ln(x) + N/(pagesize * 2). Для иных задач простая выборка по X и потом по Y может оказатьcя не хуже :)


Не понял, причем тут свойства Z-кривой, по моему доступ по любому индексу в большой файл плох, если порядок записей в таблице и в индексе не коррелируют. В худшем случае каждая из N/(x^2) выбираемых точек ляжет в свою страницу и трудоемкость будет N/(x^2), т.е. по крайней мере будет зависеть от размера рамки. Если же упорядочить записи в таблице по ключу индекса, проблем с выборкой рамкой вообще не должно быть.
...
Рейтинг: 0 / 0
05.05.2016, 16:17
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230113
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
nikichaleНе понял, причем тут свойства Z-кривой, по моему доступ по любому индексу в большой файл плох, если порядок записей в таблице и в индексе не коррелируют. В худшем случае каждая из N/(x^2) выбираемых точек ляжет в свою страницу и трудоемкость будет N/(x^2), т.е. по крайней мере будет зависеть от размера рамки. Если же упорядочить записи в таблице по ключу индекса, проблем с выборкой рамкой вообще не должно быть.
Я почти согласен со всеми ораторами. Добавлю. КМК Z-order curve это наивная попытка уменьшить стоимость
I/O для старых типов накопителей (диск) где есть цена позиционирования и где есть выбор между index access
и FTS 50:50.

Впервые о Z-кривой вычитал у Шеши Шекхар - Основы Пространственных БД.
...
Рейтинг: 0 / 0
05.05.2016, 16:36
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230144
Фотография iv_an_ru
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
iv_an_ru
Участник
nikichaleiv_an_ruпропущено...
Один только недостаток у этой кривой --- мрачная непредсказуемость селективности, поэтому при попытке использовать её на большой дисковой памяти SQL-процессор встаёт колом. Для хорошего пространственного индекса N точек на квадрате площади 1, матожидание трудоёмкости выборки "рамкой" со стороной 1/x почти пропорционально 2 ln(x) + N/(pagesize * x^2), а Z-ордер с вероятностью, экспоненциально падающей с ростом x, выкидывает "фортели", приводящие к чтению до половины точек набора, давая разброс от 2 ln(x) + N/(pagesize * x^2) до 2 ln(x) + N/(pagesize * 2). Для иных задач простая выборка по X и потом по Y может оказатьcя не хуже :)

Не понял, причем тут свойства Z-кривой, по моему доступ по любому индексу в большой файл плох, если порядок записей в таблице и в индексе не коррелируют.В случае случайного доступа к "зету" на случайных данных, плох не только доступ к записям таблицы по индексу, но и доступ к страницам самого индекса.

С другой стороны, есть алгоритмы, как раз хорошо оптимизируемые под Z-порядок. Например, микрософтовская пирамида растров. В ней k-ая плитка N-го уровня получается склейкой плиток уровня 0 с Z-номерами от 4^N * k до 4^N * (k+1) - 1 включительно, либо склейкой плиток уровня N-1 с Z-номерами от 4k до 4k+3. Сплошные последовательные чтения, для диска это удобнее некуда.
...
Рейтинг: 0 / 0
05.05.2016, 16:51
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230248
д0k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0k
Гость
iv_an_runikichaleпропущено...


Не понял, причем тут свойства Z-кривой, по моему доступ по любому индексу в большой файл плох, если порядок записей в таблице и в индексе не коррелируют.В случае случайного доступа к "зету" на случайных данных , плох не только доступ к записям таблицы по индексу, но и доступ к страницам самого индекса.

С другой стороны, есть алгоритмы, как раз хорошо оптимизируемые под Z-порядок. Например, микрософтовская пирамида растров. В ней k-ая плитка N-го уровня получается склейкой плиток уровня 0 с Z-номерами от 4^N * k до 4^N * (k+1) - 1 включительно, либо склейкой плиток уровня N-1 с Z-номерами от 4k до 4k+3. Сплошные последовательные чтения, для диска это удобнее некуда.


Не знаю получится ли , но попробую поумничать :)

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

Как только при решении задачи всплывает тригонометрические функции ,
то переход в полярную систему координат вопрос времени выделенного
на борьбу с гемороем.
...
Рейтинг: 0 / 0
05.05.2016, 18:09
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230292
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
iv_an_ruОдин только недостаток у этой кривой --- мрачная непредсказуемость селективности, поэтому при попытке использовать её на большой дисковой памяти SQL-процессор встаёт колом. Для хорошего пространственного индекса N точек на квадрате площади 1, матожидание трудоёмкости выборки "рамкой" со стороной 1/x почти пропорционально 2 ln(x) + N/(pagesize * x^2), а Z-ордер с вероятностью, экспоненциально падающей с ростом x, выкидывает "фортели", приводящие к чтению до половины точек набора, давая разброс от 2 ln(x) + N/(pagesize * x^2) до 2 ln(x) + N/(pagesize * 2). Для иных задач простая выборка по X и потом по Y может оказатьcя не хуже :)
тут к сожалению или к счастью он прав, при выборе алгоритма Z-обхода нужно "что-то знать о данных"

д0kВ подавляющем большенстве случаев этот матан используется как империческая
константа определяющая критерии балансировки дерева.
автобалансировку для 2D-дерева пока не придумали, насколько мне известно

можно построить совсем не идеальное, но очень простое дерево
модификация декартова дерева:
задать каждой координате случайное число Z - O(n)

отсортировать по Z - O(n*ln(n))

последовательно по уменьшению или увеличению Z добавлять в 2D-дерево, для определения направления С-Ю или З-В использовать н-р чётность Z проходимого узла - O (Ln(n!))

в целом получится O(n*ln(n)) на составление дерева

д0kНе знаю получится ли , но попробую поумничать :)
ИМХО
это только кажется, что данные случайны
потому что система представления физических сущьностей неверная.
Иногда достаточно первести представление для хранения из
декартовой плоскости в полярную систему координат или наоборот
и все оптимизируется само собой...
обычная задача ГИС - поиск окрестностей точки, для любой точки - не прокатит
...
Рейтинг: 0 / 0
05.05.2016, 19:08
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230297
д0k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0k
Гость
Коль мы уже докопались до Дзет
и окончательно замкнуть мысль на конекретике
давайте рассмотрим магические "четревья" и Z курвы

Дзетта функция (4)

Наиболее точно соотвествует 1 ( единице ) эвклидового пространства ,
а дальше путем сокращений мы выходим на школьную
программу НОК и НОД , для оптимизации хранения и доступа
многомерных структур и разных представлений в
одномерной ( декартовой) оперативной памяти
с минимальными затратами на адресную арифметику.

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

приблизительно так ....
постенно переходим к лямбда исчислению в котром я не спец,
поэтому передаю эстафету майтону :)
...
Рейтинг: 0 / 0
05.05.2016, 19:17
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230299
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Док. Фак мой мозг. Дай мне сначала хоть осмыслить что тут и зачем.

P.S. У меня геопоиск горит...

P.P.S. Крабы киснут. Вот какое дело...
...
Рейтинг: 0 / 0
05.05.2016, 19:21
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230309
д0k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0k
Гость
kealon(Ruslan)д0kВ подавляющем большенстве случаев этот матан используется как империческая
константа определяющая критерии балансировки дерева.
автобалансировку для 2D-дерева пока не придумали, насколько мне известно

можно построить совсем не идеальное, но очень простое дерево
модификация декартова дерева:
задать каждой координате случайное число Z - O(n)

отсортировать по Z - O(n*ln(n))

последовательно по уменьшению или увеличению Z добавлять в 2D-дерево, для определения направления С-Ю или З-В использовать н-р чётность Z проходимого узла - O (Ln(n!))

в целом получится O(n*ln(n)) на составление дерева




Мне кажется ИМХО , если хранение перевести в радиальную систему координат
то дерево сбалансируется ....
...
Рейтинг: 0 / 0
05.05.2016, 19:37
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230313
д0k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0k
Гость
maytonДок. Фак мой мозг. Дай мне сначала хоть осмыслить что тут и зачем.

P.S. У меня геопоиск горит...

P.P.S. Крабы киснут. Вот какое дело...

 
офтоп
Кстате , я ориентировочно с 16 -19 мая буду в Киеве по делам.
собираемся пивка попить с Жуком Ботаном , подтягивайся, если ты в Киеве,
за кружкой пива поделимся фундаментальными мыслями
о том как натягивать матан высшго порядка на лямбда исчисление
использущее линейную ( декартову) адресацию памяти ...
...
Рейтинг: 0 / 0
05.05.2016, 19:46
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230336
д0k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0k
Гость
kealon(Ruslan)автобалансировку для 2D-дерева пока не придумали, насколько мне известно



Я не понял вашу терминологию 2D.
k-d деревья, да , не балансруются.
...
Рейтинг: 0 / 0
05.05.2016, 20:24
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230352
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
д0kkealon(Ruslan)автобалансировку для 2D-дерева пока не придумали, насколько мне известно



Я не понял вашу терминологию 2D.
k-d деревья, да , не балансруются.
ага, 2D это K-d при k=2

по поводу придумали или нет для k>=2 может iv_an_ru подправит, ему ближе - а я уже довольно давно не занимаюсь ГИСами
...
Рейтинг: 0 / 0
05.05.2016, 21:05
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230355
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
д0kМне кажется ИМХО , если хранение перевести в радиальную систему координат
то дерево сбалансируется ....
я что-то под вечер так с наскоку не осилю ..., но чем принципиально это отличается от Z-обхода?
...
Рейтинг: 0 / 0
05.05.2016, 21:11
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230358
Фотография iv_an_ru
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
iv_an_ru
Участник
д0kКоль мы уже докопались до Дзет
и окончательно замкнуть мысль на конекретике
давайте рассмотрим магические "четревья" и Z курвы

Дзетта функция (4)

Наиболее точно соотвествует 1 ( единице ) эвклидового пространства ,
а дальше путем сокращений мы выходим на школьную
программу НОК и НОД , для оптимизации хранения и доступа
многомерных структур и разных представлений в
одномерной ( декартовой) оперативной памяти
с минимальными затратами на адресную арифметику.

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

приблизительно так ....
постенно переходим к лямбда исчислению в котром я не спец,
поэтому передаю эстафету майтону :)Это я зря столько лет кусал гранит науки --- все равно дураком помру, или это такой стёб?
...
Рейтинг: 0 / 0
05.05.2016, 21:15
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230375
Фотография iv_an_ru
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
iv_an_ru
Участник
Для почти любых индексных деревьев есть какая-нибудь "операция вращения" (для 2D и 3D деревьев с чередованием полей, по которым делается разбиение, вращение захватывает и одну или две вершины между вершинами с вращаемой координатой --- "операция совращения"). Если она есть, то всегда можно сделать случайное встряхивание на худшем случае --- постоянно отслеживать самый длинный из встречавшихся путей (точнее ключ, который искали и глубину), а в чекпойнт выбирать случайную вершину на пути от корня к тому "глубже всех зарытому" ключу и делать вращение вокруг неё.
...
Рейтинг: 0 / 0
05.05.2016, 21:39
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230380
д0k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0k
Гость
iv_an_ruд0kКоль мы уже докопались до Дзет
и окончательно замкнуть мысль на конекретике
давайте рассмотрим магические "четревья" и Z курвы

Дзетта функция (4)

Наиболее точно соотвествует 1 ( единице ) эвклидового пространства ,
а дальше путем сокращений мы выходим на школьную
программу НОК и НОД , для оптимизации хранения и доступа
многомерных структур и разных представлений в
одномерной ( декартовой) оперативной памяти
с минимальными затратами на адресную арифметику.

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

приблизительно так ....
постенно переходим к лямбда исчислению в котром я не спец,
поэтому передаю эстафету майтону :)Это я зря столько лет кусал гранит науки --- все равно дураком помру, или это такой стёб?

Это размышления на тему оптимизации хранения ,
и сжатия обрабатываемых многомерных пространств
в одномерную адресацию памяти
для минимизации накладных расходов метаданные и адресную арифметику.

Попытка обосновать частный случай , почему магическое число именно 4.....
...
Рейтинг: 0 / 0
05.05.2016, 21:42
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230386
д0k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0k
Гость
д0kiv_an_ruпропущено...
Это я зря столько лет кусал гранит науки --- все равно дураком помру, или это такой стёб?

Это размышления на тему оптимизации хранения ,
и сжатия обрабатываемых многомерных пространств
в одномерную адресацию памяти
для минимизации накладных расходов метаданные и адресную арифметику.

Попытка обосновать частный случай , почему магическое число именно 4.....


Там есть и другие оптимальные часнтные случаи

- число делителей числа n

Но это уже очень глубокое погружение,

а ИМХО заныривать нужно отсюда
...
Рейтинг: 0 / 0
05.05.2016, 22:00
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230477
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
iv_an_ruДля почти любых индексных деревьев есть какая-нибудь "операция вращения" (для 2D и 3D деревьев с чередованием полей, по которым делается разбиение, вращение захватывает и одну или две вершины между вершинами с вращаемой координатой --- "операция совращения"). Если она есть, то всегда можно сделать случайное встряхивание на худшем случае --- постоянно отслеживать самый длинный из встречавшихся путей (точнее ключ, который искали и глубину), а в чекпойнт выбирать случайную вершину на пути от корня к тому "глубже всех зарытому" ключу и делать вращение вокруг неё.
а есть примеры? слабо представляю возможные совращения даже для 2D-дерева без нарушения инварианта
...
Рейтинг: 0 / 0
06.05.2016, 07:06
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230579
д0k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0k
Гость
kealon(Ruslan)iv_an_ruДля почти любых индексных деревьев есть какая-нибудь "операция вращения" (для 2D и 3D деревьев с чередованием полей, по которым делается разбиение, вращение захватывает и одну или две вершины между вершинами с вращаемой координатой --- "операция совращения"). Если она есть, то всегда можно сделать случайное встряхивание на худшем случае --- постоянно отслеживать самый длинный из встречавшихся путей (точнее ключ, который искали и глубину), а в чекпойнт выбирать случайную вершину на пути от корня к тому "глубже всех зарытому" ключу и делать вращение вокруг неё.
а есть примеры? слабо представляю возможные совращения даже для 2D-дерева без нарушения инварианта

Я тоже не совсем понял как вращать обьект внутри индекса вокруг вершины.
Вероянтее всего имеется ввиду не вращение , а обход вокруг, вращается не обьект ,
а наблюдатель вокруг обьекта,
То есть так называемая встряска это
фоновое, между делом, решение задачи комивояжера или о наполнении рюкзака.
...
Рейтинг: 0 / 0
06.05.2016, 10:18
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230659
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
д0kсобираемся пивка попить с Жуком Ботаном , подтягивайся, если ты в Киеве,
за кружкой пива поделимся фундаментальными мыслями
о том как натягивать матан высшго порядка на лямбда исчисление
использущее линейную ( декартову) адресацию памяти ...
У тебя есть ВК, фейсбук, linkedin или ченить такое?
...
Рейтинг: 0 / 0
06.05.2016, 11:14
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230663
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
iv_an_ruС другой стороны, есть алгоритмы, как раз хорошо оптимизируемые под Z-порядок. Например, микрософтовская пирамида растров.
Че за пирамида растров? Это из DirectX/MipMapping?
...
Рейтинг: 0 / 0
06.05.2016, 11:15
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230677
д0k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0k
Гость
kealon(Ruslan)д0kМне кажется ИМХО , если хранение перевести в радиальную систему координат
то дерево сбалансируется ....
я что-то под вечер так с наскоку не осилю ..., но чем принципиально это отличается от Z-обхода?

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

В некоторых случаях (наборе данных) всплавают ее достоинсва в некоторых недостатки.

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

То есть в одномерном адресном пространстве с использованием арифметики указателей
необходимо создать механизм ( алгоритм)
перемещения в многомерном пространстве с минимальными накладными затратами.
...
Рейтинг: 0 / 0
06.05.2016, 11:33
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230681
д0k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0k
Гость
maytonд0kсобираемся пивка попить с Жуком Ботаном , подтягивайся, если ты в Киеве,
за кружкой пива поделимся фундаментальными мыслями
о том как натягивать матан высшго порядка на лямбда исчисление
использущее линейную ( декартову) адресацию памяти ...
У тебя есть ВК, фейсбук, linkedin или ченить такое?

ВК нет, остальное есть .
...
Рейтинг: 0 / 0
06.05.2016, 11:35
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230693
nikichale
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
nikichale
Гость
iv_an_runikichaleпропущено...


Не понял, причем тут свойства Z-кривой, по моему доступ по любому индексу в большой файл плох, если порядок записей в таблице и в индексе не коррелируют.В случае случайного доступа к "зету" на случайных данных, плох не только доступ к записям таблицы по индексу, но и доступ к страницам самого индекса.

С другой стороны, есть алгоритмы, как раз хорошо оптимизируемые под Z-порядок. Например, микрософтовская пирамида растров. В ней k-ая плитка N-го уровня получается склейкой плиток уровня 0 с Z-номерами от 4^N * k до 4^N * (k+1) - 1 включительно, либо склейкой плиток уровня N-1 с Z-номерами от 4k до 4k+3. Сплошные последовательные чтения, для диска это удобнее некуда.

Ну так это как раз то, что нужно для поиска точек в рамке: "k-ая плитка N-го уровня" это рамка некоторого размера для поиска, а плитки уровня 0 с Z-номерами в интервале от 4^N * k до 4^N * (k+1) - 1 это Z-номера точек которые в ней содержаться! Если рамка поиска не совпадает с плитками - ее нужно покрыть с запасом несколькими плитками так, чтобы минимизировать запас при небольшом количестве плиток. Т.е., чтобы найти точки в некоторой окрестности нужно просканировать несколько интервалов в упорядоченном массиве с Z-номерами точек. И все. И никакие несбалансированные 2D деревья тут не нужны.
...
Рейтинг: 0 / 0
06.05.2016, 11:43
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230695
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
д0kТо есть в одномерном адресном пространстве с использованием арифметики указателей
необходимо создать механизм ( алгоритм)
перемещения в многомерном пространстве с минимальными накладными затратами.
Док. Я пока сабж Z-curves и кодов мортона только изучаю. И планирую его заюзать
в оптимизации Оракловых процессов которые процессят и компилируют саму карту.

И я для себя пока пытаюсь смоделировать наихудший (или просто плохой вариант)
работы с z-последовательностью когда выборка (viewport) смотрит в такой кусочек
планеты Земля где z-кривая бъется на большое число последовательностей с разрывами.

Например. Если за точку отсчета взят 0.0 N, 0.0 Е - нулевой меридиан на экваторе
и z-кривая покрывает весь Земной шарик (WGS-84, Меркатор).
...
Рейтинг: 0 / 0
06.05.2016, 11:45
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230711
д0k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0k
Гость
maytoniv_an_ruС другой стороны, есть алгоритмы, как раз хорошо оптимизируемые под Z-порядок. Например, микрософтовская пирамида растров.
Че за пирамида растров? Это из DirectX/MipMapping?

Исходя из выше озвученной мной гепотизы ,
наборы данных, которые описываются волновыми процессам
( имеющие число Пи в формуле функции) будут удачно ложиться в Z-порядок и "четревья",

Потому что там есть переход от радиальной системы координат ( Пи )
в приблизительно единицу
декартовой системы координат ( адресация памяти)
через Дзета функцию римана и магическое число 4.

Приблизительно так....
...
Рейтинг: 0 / 0
06.05.2016, 11:55
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230737
д0k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0k
Гость
maytonд0kТо есть в одномерном адресном пространстве с использованием арифметики указателей
необходимо создать механизм ( алгоритм)
перемещения в многомерном пространстве с минимальными накладными затратами.
Док. Я пока сабж Z-curves и кодов мортона только изучаю. И планирую его заюзать
в оптимизации Оракловых процессов которые процессят и компилируют саму карту.

И я для себя пока пытаюсь смоделировать наихудший (или просто плохой вариант)
работы с z-последовательностью когда выборка (viewport) смотрит в такой кусочек
планеты Земля где z-кривая бъется на большое число последовательностей с разрывами.

Например. Если за точку отсчета взят 0.0 N, 0.0 Е - нулевой меридиан на экваторе
и z-кривая покрывает весь Земной шарик (WGS-84, Меркатор).

Я думаю что из готовых известных мне архитектурно алгоритмических
вариантов представления
z-кривая будет лучшим выбором , если пренебречь тем что Земля не шар, а геоид.
Как выстрелит эта погрешность я не знаю.
...
Рейтинг: 0 / 0
06.05.2016, 12:18
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230757
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Для решаемой нами задачи геоид или сфера - не суть важно. Есть небольшая неопределённость
на полюсах но там нет картографических данных и как следствие нет зафейленых тесткейсов.
...
Рейтинг: 0 / 0
06.05.2016, 12:29
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230761
д0k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0k
Гость
maytonДля решаемой нами задачи геоид или сфера - не суть важно. Есть небольшая неопределённость
на полюсах но там нет картографических данных и как следствие нет зафейленых тесткейсов.

Если ты когда то планируешь развивать систему до учета высоты над уровнем моря
то рекомендую взгнянуть на Преобразования Мёбиуса при выборе формата предстваления данных для хранения и поиска.
...
Рейтинг: 0 / 0
06.05.2016, 12:36
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230766
д0k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0k
Гость
д0kmaytonДля решаемой нами задачи геоид или сфера - не суть важно. Есть небольшая неопределённость
на полюсах но там нет картографических данных и как следствие нет зафейленых тесткейсов.

Если ты когда то планируешь развивать систему до учета высоты над уровнем моря
то рекомендую взгнянуть на Преобразования Мёбиуса при выборе формата предстваления данных для хранения и поиска.

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

и запиешь в себе профит дополнительно 100500 оплаченных человекочасов.
...
Рейтинг: 0 / 0
06.05.2016, 12:41
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230797
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
д0kЕсли ты когда то планируешь развивать систему до учета высоты над уровнем моря
то рекомендую взгнянуть на Преобразования Мёбиуса при выборе формата предстваления данных для хранения и поиска.
Задача digital terran model существует. Но это - опция. И в основных алгоритмах она пока не участвует.
...
Рейтинг: 0 / 0
06.05.2016, 13:02
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230815
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
д0kЯ думаю что из готовых известных мне архитектурно алгоритмических
вариантов представления
z-кривая будет лучшим выбором , если пренебречь тем что Земля не шар, а геоид.
Как выстрелит эта погрешность я не знаю.

тут проблема в том, что желательно что бы все точки "поискового прямоугольника" выпадали на один интервал Z-преобразования
Тогда поиск будет очень быстрым
в противном случае придётся перебирать весь Z-индекс, что iv_an_ru и пытался как я понимаю сказать
...
Рейтинг: 0 / 0
06.05.2016, 13:19
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230833
nikichale
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
nikichale
Гость
kealon(Ruslan)д0kЯ думаю что из готовых известных мне архитектурно алгоритмических
вариантов представления
z-кривая будет лучшим выбором , если пренебречь тем что Земля не шар, а геоид.
Как выстрелит эта погрешность я не знаю.

тут проблема в том, что желательно что бы все точки "поискового прямоугольника" выпадали на один интервал Z-преобразования
Тогда поиск будет очень быстрым
в противном случае придётся перебирать весь Z-индекс, что iv_an_ru и пытался как я понимаю сказать

Почему обязательно на один, покрой "поисковый прямоугольник" несколькими интервалами с запасом. Любой прямоугольник можно покрыть 4мя интервалами сравнимого с ним размера. На картинке черным - прямоугольник поиска
...
Рейтинг: 0 / 0
06.05.2016, 13:34
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230837
д0k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0k
Гость
kealon(Ruslan)д0kЯ думаю что из готовых известных мне архитектурно алгоритмических
вариантов представления
z-кривая будет лучшим выбором , если пренебречь тем что Земля не шар, а геоид.
Как выстрелит эта погрешность я не знаю.

тут проблема в том, что желательно что бы все точки "поискового прямоугольника" выпадали на один интервал Z-преобразования
Тогда поиск будет очень быстрым
в противном случае придётся перебирать весь Z-индекс, что iv_an_ru и пытался как я понимаю сказать

ИМХО , что бы попадать в интервал
нужно понимание глубины детализации.
То есть масштаб или возможные варианты выбора масштаба должны быть известны заранее.

Добавление нового масштаба потом вызовет критическую деградацию производительности.

По хорошему нужно строить хранение обьектов на радиальных координатах от центра Земли,
но мне неизвестны ГИС библиотеки, которые таким образом хранят первичные данные.
тогда любой масштаб будет достаточно просто пересчитываться через синус угла и преобразование
мебиуса.
...
Рейтинг: 0 / 0
06.05.2016, 13:44
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230843
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
nikichale, эта картинка - обладает полнотой информации для Quad-Trees. Но для Z-curve на ней
недостаточно информации. В частности порядок связей не учтен.
...
Рейтинг: 0 / 0
06.05.2016, 13:49
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230850
д0k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0k
Гость
nikichalekealon(Ruslan)пропущено...


тут проблема в том, что желательно что бы все точки "поискового прямоугольника" выпадали на один интервал Z-преобразования
Тогда поиск будет очень быстрым
в противном случае придётся перебирать весь Z-индекс, что iv_an_ru и пытался как я понимаю сказать

Почему обязательно на один, покрой "поисковый прямоугольник" несколькими интервалами с запасом. Любой прямоугольник можно покрыть 4мя интервалами сравнимого с ним размера. На картинке черным - прямоугольник поиска

Прошу прощения но другой простой аналогии я не смог быстро придумать.

Помнишь мультик Винипух в госятх у кролика ?

YouTube Video
YouTube Video
...
Рейтинг: 0 / 0
06.05.2016, 13:54
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230856
nikichale
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
nikichale
Гость
maytonnikichale, эта картинка - обладает полнотой информации для Quad-Trees. Но для Z-curve на ней
недостаточно информации. В частности порядок связей не учтен.

Важно только то, что все точки внутри каждого квадратика на картинке (любого уровня) лежат в одном непрерывном интервале Z-порядка, или, по другому, каждый квадратик это непрерывный кусок Z-curve.
...
Рейтинг: 0 / 0
06.05.2016, 14:00
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230858
д0k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0k
Гость
maytonnikichale, эта картинка - обладает полнотой информации для Quad-Trees. Но для Z-curve на ней
недостаточно информации. В частности порядок связей не учтен.

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

в 16 раз , Карл !!!!
:)
...
Рейтинг: 0 / 0
06.05.2016, 14:02
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230864
nikichale
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
nikichale
Гость
д0k,

В чем проблема, если нужно пробежать 4е маленьких интервала в индексе. Размер интервалов зависит от размера прямоугольника поиска. И точек в них будет на намного больше, чем реально содержит прямоугольник поиска.
...
Рейтинг: 0 / 0
06.05.2016, 14:08
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230866
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
д0kmaytonnikichale, эта картинка - обладает полнотой информации для Quad-Trees. Но для Z-curve на ней
недостаточно информации. В частности порядок связей не учтен.

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

в 16 раз , Карл !!!!
:)
Ну почему-же. Если мы вернемся к стоимости дисковых операций и вспомним что
иногда проще читать 1 длинный IOPS, чем 2 коротких то возможно не все так
и печально, Карл.

Надо только придумать как сделать UNION.
...
Рейтинг: 0 / 0
06.05.2016, 14:10
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230871
nikichale
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
nikichale
Гость
д0kmaytonnikichale, эта картинка - обладает полнотой информации для Quad-Trees. Но для Z-curve на ней
недостаточно информации. В частности порядок связей не учтен.

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

в 16 раз , Карл !!!!
:)

Боитесь считать лишнего - покройте не 4мя квадратами, а 9 или 16. Кроме того, если говорить о ГИС, то информация вблизи уже запрошенной очень даже может понадобиться в последствии - типа user двигает карту на экране...
...
Рейтинг: 0 / 0
06.05.2016, 14:15
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230874
д0k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0k
Гость
nikichaleд0k,

В чем проблема, если нужно пробежать 4е маленьких интервала в индексе. Размер интервалов зависит от размера прямоугольника поиска. И точек в них будет на намного больше, чем реально содержит прямоугольник поиска.

Зависит от масштабной сетки.
Если для каждой масштабной сетки свой индекс , то да не много.
Если индекс для всех масштабных сеток один, то внутри вашего диапазона могут оказаться
точки неинтересующих вас объектов.
...
Рейтинг: 0 / 0
06.05.2016, 14:16
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230879
д0k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0k
Гость
nikichaleд0kпропущено...


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

в 16 раз , Карл !!!!
:)

Боитесь считать лишнего - покройте не 4мя квадратами, а 9 или 16. Кроме того, если говорить о ГИС, то информация вблизи уже запрошенной очень даже может понадобиться в последствии - типа user двигает карту на экране...

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

Это ваше право , но я тут что бы пообсуждать фунтаментальные возможности ,
и получить направления развития мысли,
а не подпорки и костыли в проекте работающем по принципу go-go.

Извините, мне экстенсивные решения не интересно обсуждать.
...
Рейтинг: 0 / 0
06.05.2016, 14:25
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230885
д0k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0k
Гость
maytonд0kпропущено...


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

в 16 раз , Карл !!!!
:)
Ну почему-же. Если мы вернемся к стоимости дисковых операций и вспомним что
иногда проще читать 1 длинный IOPS, чем 2 коротких то возможно не все так
и печально, Карл.

Надо только придумать как сделать UNION.

Шо тут думать, тут прыгать надо :)

man 7 aio lio_listio(3) Enqueue multiple I/O requests using a single function
call.
...
Рейтинг: 0 / 0
06.05.2016, 14:32
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230887
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
д0kЭто ваше право , но я тут что бы пообсуждать фунтаментальные возможности ,
и получить направления развития мысли, а не подпорки и костыли в проекте работающем по принципу go-go.
Извините, мне экстенсивные решения не интересно обсуждать.
Док. Извини но мы всю жизнь тут решаем фундаментально-практические 50:50 вопросы.
Такова жизсть иначе сиделы-бы в форуме математиков.

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

Собственно за это мы и получаем деньги. За умение совокуплять математику и эти странные
limitations железа и уже имеющегося ПО.
...
Рейтинг: 0 / 0
06.05.2016, 14:33
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230911
д0k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0k
Гость
maytonд0kЭто ваше право , но я тут что бы пообсуждать фунтаментальные возможности ,
и получить направления развития мысли, а не подпорки и костыли в проекте работающем по принципу go-go.
Извините, мне экстенсивные решения не интересно обсуждать.
Док. Извини но мы всю жизнь тут решаем фундаментально-практические 50:50 вопросы.
Такова жизсть иначе сиделы-бы в форуме математиков.

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

Собственно за это мы и получаем деньги. За умение совокуплять математику и эти странные
limitations железа и уже имеющегося ПО.

Была бы конкретная постановка задачи , можно было бы ее обсуждать.
1 , 5, 1024 масштабных сеток , поличическая карта мира итд итп....

А так как постановка сферическая в вакуме , то я и обсуждаю задачу в этом колюче.
Если потом скажут.
а зделайте как на политической карте кнопку для ее преобразования в топографическую .
2 дня вам хватит что бы кнопку на форму разместить ?

Это общая дискуссия , а не конкретная , поэтому я стараюсь , что бы
найденные в ней решения покрывали максимальную масштабируемость ГИС системы.
...
Рейтинг: 0 / 0
06.05.2016, 14:51
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230917
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
д0k, кстати залогонься. Я тебе тогда мыло смогу отправлять.
...
Рейтинг: 0 / 0
06.05.2016, 14:56
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230924
д0k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0k
Гость
maytonд0k, кстати залогонься. Я тебе тогда мыло смогу отправлять.

Я самозабанился навсегда , потому что у меня выработалась зависимость от ПТ,
если появится функционал отписываться от целых разделов форума, может быть заведу
новый логин.

пиши на
doxtap вухо гмило.ком
...
Рейтинг: 0 / 0
06.05.2016, 15:03
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230935
nikichale
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
nikichale
Гость
д0k,

Насчет масштабных сеток что-то не понял. Есть таблица с графикой, есть границы максимальные. Вводим дискретизацию, например, 2^28 дискретов (28 уровней). Если это география, то в дискрете меньше метра. Для точек в таблице строим индекс по Z-порядку 28+28 - ключ влезает в Int64. Для поиска точек в прямоугольнике от 1м и больше используем этот индекс. Причем на лицо явная избыточность - маловероятно, что на 1м будет находиться много географических объектов. Где же тут нарушена универсальность? Если же речь о чертеже микросхемы и нужно искать в миллиметровых интервалах - положите эти данные в другую таблицу отдельно от географии.
...
Рейтинг: 0 / 0
06.05.2016, 15:18
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230950
д0k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0k
Гость
nikichaleд0k,

Насчет масштабных сеток что-то не понял. Есть таблица с графикой, есть границы максимальные. Вводим дискретизацию, например, 2^28 дискретов (28 уровней). Если это география, то в дискрете меньше метра. Для точек в таблице строим индекс по Z-порядку 28+28 - ключ влезает в Int64. Для поиска точек в прямоугольнике от 1м и больше используем этот индекс. Причем на лицо явная избыточность - маловероятно, что на 1м будет находиться много географических объектов. Где же тут нарушена универсальность? Если же речь о чертеже микросхемы и нужно искать в миллиметровых интервалах - положите эти данные в другую таблицу отдельно от географии.

согласен , простота сестра таланта, что то в этом есть.
Но и вопросы есть

Почему 28 ?
можете обьяснить лоигическую и физическую суть этого магического числа ?

Почему не 38 ? ( если я не ошибся , площадь Земли в квадратных метрах 38 разнядное
двоичное число )

И какой по вашему лучше выбрать площадь одного Z квадрата ?
...
Рейтинг: 0 / 0
06.05.2016, 15:32
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230962
д0k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0k
Гость
Следующий вопрос ,
у вас есть улица длиной 5 км и шириной 30 м.
Как должно быть построено индексное хранение , что бы тыцнув
мышей в карту в любом месте улицы , получить ее название и координаты
всех перекрестков и названия пересекающих улиц.
Не вычитвая с диска квадрат 5км на 5 км со всеми его обьектами.
...
Рейтинг: 0 / 0
06.05.2016, 15:44
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230966
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
д0kу вас есть улица длиной 5 км и шириной 30 м.
Как должно быть построено индексное хранение , что бы тыцнув
мышей в карту в любом месте улицы , получить ее название и координаты

дОК я тебя умоляю. Ну никто не ответит на твой вопрос.
...
Рейтинг: 0 / 0
06.05.2016, 15:49
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230975
д0k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0k
Гость
maytonд0kу вас есть улица длиной 5 км и шириной 30 м.
Как должно быть построено индексное хранение , что бы тыцнув
мышей в карту в любом месте улицы , получить ее название и координаты

дОК я тебя умоляю. Ну никто не ответит на твой вопрос.

Я знаю, поэтому и веду диалог на уровне сравнения архитектурных концеций
хранения индексов, что бы потом можно было выбирать
лучшую для конкретной задачи или универсальную покрывающую
максимальную масштабируемость.
...
Рейтинг: 0 / 0
06.05.2016, 15:58
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230982
д0k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0k
Гость
maytonд0kу вас есть улица длиной 5 км и шириной 30 м.
Как должно быть построено индексное хранение , что бы тыцнув
мышей в карту в любом месте улицы , получить ее название и координаты

дОК я тебя умоляю. Ну никто не ответит на твой вопрос.

Это кстате задача по сабжу, только мы ищем не точки ,
а анлогичные объекты ( улицы и перекрестки) .



подругому задача звучит так.
обьект находитесь возле фонтана , и вам нужно найти ближайший к нему фонтан,
Хотя на карте ( квадрате) могут быть и отдельные деревья , скверы ,
автобусные остановки , дома, парковки,
, ну и фонтаны ....
...
Рейтинг: 0 / 0
06.05.2016, 16:06
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230985
nikichale
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
nikichale
Гость
д0kСледующий вопрос ,
у вас есть улица длиной 5 км и шириной 30 м.
Как должно быть построено индексное хранение , что бы тыцнув
мышей в карту в любом месте улицы , получить ее название и координаты
всех перекрестков и названия пересекающих улиц.
Не вычитвая с диска квадрат 5км на 5 км со всеми его обьектами.

Ну положим, чтобы найти саму улицу, квадрат 5*5км читать и не надо, достаточно задать квадрат в метрах соответствующий 2-3 пикселям экрана. А вот после этого придется взять ее MBR и читать все объекты в нем. Хотя можно конечно покрыть саму линию мелкими квадратиками, но количество сканируемых интервалов индекса (и подлых seek) будет велико и эффекта может и не получиться.

Кстати в Oracle Spatial объект при индексации покрывается такими квадратиками и при запросе where Intersect (найти объекты пересекающие данный) видимо будет делаться ровно это. Но стоит такой индекс дорого, т.к. при изменении объекта в индекс вставляется/удаляется куча ключей.
...
Рейтинг: 0 / 0
06.05.2016, 16:13
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39230995
nikichale
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
nikichale
Гость
д0k,

Для не точек можно использовать тот же индекс, но кроме Z-порядка нужно еще хранить уровень покрывающих квадратиков. 28+28+8(байт для уровня)=64 - секрет магического числа 28.
...
Рейтинг: 0 / 0
06.05.2016, 16:24
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39231000
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ну вобщем док вкурсе. А всем остальным кому интересна география - пыщ сюда

http://www.sql.ru/forum/1212851/tyapnichnoe-kruchenie-zemnogo-sharika
...
Рейтинг: 0 / 0
06.05.2016, 16:29
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39231004
nikichale
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
nikichale
Гость
д0kmaytonпропущено...

дОК я тебя умоляю. Ну никто не ответит на твой вопрос.

Это кстате задача по сабжу, только мы ищем не точки ,
а анлогичные объекты ( улицы и перекрестки) .



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

Ну можно сделать составной индекс type+Z-order, но тогда тип нужно задать точно (на равенство)
...
Рейтинг: 0 / 0
06.05.2016, 16:30
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39231011
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Z-кривая не отменяет обычных индексов. Это скорее кластеризация
объектов с координатами (x,y) близкими, в соседних HDD blocks.
Я-же собирался использовать в БД Oracle дополнительное поле
z-code как еще одно измерение для оптимизаций.
...
Рейтинг: 0 / 0
06.05.2016, 16:36
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39231012
д0k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0k
Гость
nikichaleд0k,

Для не точек можно использовать тот же индекс, но кроме Z-порядка нужно еще хранить уровень покрывающих квадратиков. 28+28+8(байт для уровня)=64 - секрет магического числа 28.

Уточнение.
Еще указатели на страницу спарва лева вверху и низу того же уровня .
8*5=40 а страница должна быть 4 к, 8к ......
так как читать из файловой системы меньше чем 4к обейдется дороже чем 4 к.

собственно возврашаясь вопросу оптимизации , как расположить
страницы на диске так , что бы максимальное количество условий поиска обьекта
размазанного по страницам
покрывать мультиблочным чтением не читая лишних страниц
( не содержащих информацию о нужном нам обьекте) .
...
Рейтинг: 0 / 0
06.05.2016, 16:37
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39231018
д0k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0k
Гость
nikichaleд0kпропущено...


Это кстате задача по сабжу, только мы ищем не точки ,
а анлогичные объекты ( улицы и перекрестки) .



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

Ну можно сделать составной индекс type+Z-order, но тогда тип нужно задать точно (на равенство)


Аналог PK-FK только c только с разрешенным в FK значением null ( пока не классифицирован ).
...
Рейтинг: 0 / 0
06.05.2016, 16:45
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39231027
д0k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0k
Гость
maytonZ-кривая не отменяет обычных индексов. Это скорее кластеризация
объектов с координатами (x,y) близкими, в соседних HDD blocks.
Я-же собирался использовать в БД Oracle дополнительное поле
z-code как еще одно измерение для оптимизаций.


Сходил покурил , поразмыслил и в очередной раз утвердился в мысли 18561522
что лучше иметь много
индексов всяких и разных и их мержить , чем бить пространство на
квадраты и прочие области.
...
Рейтинг: 0 / 0
06.05.2016, 17:04
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39231195
д0k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0k
Гость
д0kmaytonZ-кривая не отменяет обычных индексов. Это скорее кластеризация
объектов с координатами (x,y) близкими, в соседних HDD blocks.
Я-же собирался использовать в БД Oracle дополнительное поле
z-code как еще одно измерение для оптимизаций.


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

У ораклового СВО есть проблемы c мержем индексов , это тема ораклового раздела.
а тут я пытаюсь рассуждуть фундаментально.

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

Нам пока не удалось найти оптимальные параметры сбора ститистики что бы заставить СВО
мержить индексы без хинтов, вспоминаем старый добрый деприейтед руле :).

Максимум, на что получилось выйти с более менее пердсказуемым результатом в планах ,
это мерж индексов через джоин таблицы сам с собой.
...
Рейтинг: 0 / 0
07.05.2016, 00:37
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39231210
Фотография iv_an_ru
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
iv_an_ru
Участник
д0kСледующий вопрос ,
у вас есть улица длиной 5 км и шириной 30 м.
Как должно быть построено индексное хранение , что бы тыцнув
мышей в карту в любом месте улицы , получить ее название и координаты
всех перекрестков и названия пересекающих улиц.
Не вычитвая с диска квадрат 5км на 5 км со всеми его обьектами.Для этого надо индексировать не только шейпы, но и дополнительно их ключевые точки, при этом для прямых линий, "слишком протяжённых" в обычном зуме, надо дополнительно накидать точек вдоль линий (и при необходимости штриховку внутри них), а для объектов, слишком больших по площади в этом зуме, надо держать отдельные списки. Перед этим шейпам объектов разных типов назначаются, само собой, разные уровни "обычного зума" и разные уровни зума, при котором объекты вообще скрываются с карты. Тогда вы будете вычитывать квадрат с размером в полторы-две-три характерных ширины улицы, то есть для улицы это будет 50x50 метров.

Правда, тогда полезут большие вопросы производительности для мультилиний со слишком большим количеством точек, но я не уверен, что могу рассказать, как они решаются, не нарушив контракт :|

Но можно этого и не делать. Все улицы квадрата 5x5 километров уютно улягутся в памяти и дадут вам интерактивное время без фокусов. Вот когда всё очертание побережья мирового океана разбито на всего лишь три десятка мультиполигонов, и все изобаты разбиты так же, у вас карта раскрашена 20 слоями изобат с заливкой контуров, и вы даёте зум в Индонезию с её тясячами островов... одним неловким движением мыши в QGIS... вам придётся немножко подождать, прежде чем вы сможете сделать следующее движение карты :)
...
Рейтинг: 0 / 0
07.05.2016, 01:39
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39231379
nikichale
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
nikichale
Гость
д0kmaytonZ-кривая не отменяет обычных индексов. Это скорее кластеризация
объектов с координатами (x,y) близкими, в соседних HDD blocks.
Я-же собирался использовать в БД Oracle дополнительное поле
z-code как еще одно измерение для оптимизаций.


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

Нашел 2000 года статью
"Comparing Z-order B-tree and R-tree Family for Spatial Query Processing"

по http://webcache.googleusercontent.com/search?q=cache:CglmEYxoLcwJ:europa.nvc.cs.vt.edu/~ctlu/Publication/1998-2006/Z-order-B-tree.ps &cd=8&hl=ru&ct=clnk&gl=ru

и вывод, что Z-order B-tree индекс для пространственных выборок не хуже, чем R-tree, но проще.

А тут
http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-indexing-with-Quadtrees-and-Hilbert-Curves
джентлемен все заново изобрел только для точек, но в коментах ему объяснили
...
Рейтинг: 0 / 0
07.05.2016, 21:59
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39231421
Фотография iv_an_ru
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
iv_an_ru
Участник
nikichaleд0kпропущено...



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

Нашел 2000 года статью
"Comparing Z-order B-tree and R-tree Family for Spatial Query Processing"

по http://webcache.googleusercontent.com/search?q=cache:CglmEYxoLcwJ:europa.nvc.cs.vt.edu/~ctlu/Publication/1998-2006/Z-order-B-tree.ps &cd=8&hl=ru&ct=clnk&gl=ru

и вывод, что Z-order B-tree индекс для пространственных выборок не хуже, чем R-tree, но проще.

А тут
http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-indexing-with-Quadtrees-and-Hilbert-Curves
джентлемен все заново изобрел только для точек, но в коментах ему объяснилиС 2000 года в СУБД поменялось почти всё :)
...
Рейтинг: 0 / 0
08.05.2016, 05:53
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39231466
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
В PDF:

http://europa.nvc.cs.vt.edu/~ctlu/Publication/1998-2006/Z-order-B-tree.pdf
...
Рейтинг: 0 / 0
08.05.2016, 10:35
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39232114
д0k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0k
Гость
iv_an_ruНо можно этого и не делать. Все улицы квадрата 5x5 километров уютно улягутся в памяти и дадут вам интерактивное время без фокусов. Вот когда всё очертание побережья мирового океана разбито на всего лишь три десятка мультиполигонов, и все изобаты разбиты так же, у вас карта раскрашена 20 слоями изобат с заливкой контуров , и вы даёте зум в Индонезию с её тясячами островов... одним неловким движением мыши в QGIS... вам придётся немножко подождать, прежде чем вы сможете сделать следующее движение карты :)


Я так думаю ИМХО, с фунтаментальной точки зрения,
на определенном масштабе математика оптимального хранения
должна быть другая .
...
Рейтинг: 0 / 0
10.05.2016, 10:08
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39232336
Фотография iv_an_ru
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
iv_an_ru
Участник
д0k Я так думаю ИМХО, с фунтаментальной точки зрения,
на определенном масштабе математика оптимального хранения
должна быть другая . Фракталы хороши только тогда, когда ты сначала рисуешь побережье, а потом приводишь местность в соотвествие с картой. Ну а вообще да, для мелкого хранения нужны уже не изобаты, а просто 3D-треугольная сетка. Одна беда --- если есть именно изобаты, да ещё заранее неизвестно, валидны ли они, то к 3d сетке без потерь данных не перейти.
...
Рейтинг: 0 / 0
10.05.2016, 13:04
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39232360
д0k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0k
Гость
iv_an_ruд0k Я так думаю ИМХО, с фунтаментальной точки зрения,
на определенном масштабе математика оптимального хранения
должна быть другая . Фракталы хороши только тогда, когда ты сначала рисуешь побережье, а потом приводишь местность в соотвествие с картой. Ну а вообще да, для мелкого хранения нужны уже не изобаты, а просто 3D-треугольная сетка. Одна беда --- если есть именно изобаты, да ещё заранее неизвестно, валидны ли они, то к 3d сетке без потерь данных не перейти.


Я не понял, что вы имеете ввиду( выделено).

Карта уже нарисована , ее нужно оптимально хранить и быстро искать участки .
...
Рейтинг: 0 / 0
10.05.2016, 13:22
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39232421
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ребяты. Фракталы и прочие аты-баты - совсем срыв мозка. Мы так далеко уеедем от темы.
...
Рейтинг: 0 / 0
10.05.2016, 14:22
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39232432
Фотография iv_an_ru
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
iv_an_ru
Участник
д0kiv_an_ruпропущено...
Фракталы хороши только тогда, когда ты сначала рисуешь побережье, а потом приводишь местность в соотвествие с картой. Ну а вообще да, для мелкого хранения нужны уже не изобаты, а просто 3D-треугольная сетка. Одна беда --- если есть именно изобаты, да ещё заранее неизвестно, валидны ли они, то к 3d сетке без потерь данных не перейти.


Я не понял, что вы имеете ввиду( выделено).

Карта уже нарисована , ее нужно оптимально хранить и быстро искать участки .Тогда фракталы не нужны.
...
Рейтинг: 0 / 0
10.05.2016, 14:31
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39232681
д0k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0k
Гость
iv_an_ruд0kпропущено...



Я не понял, что вы имеете ввиду( выделено).

Карта уже нарисована , ее нужно оптимально хранить и быстро искать участки .Тогда фракталы не нужны.

не согласен

Теже "четревья", вид с боку .....

зы я пытаюсь рассуждать о формате оптимального хранения ....
...
Рейтинг: 0 / 0
10.05.2016, 17:24
| Ответить | Цитировать | Написать  
216 сообщений из 216, показаны все 9 страниц
  все  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Диаграмма Вороного, поиск ближайшей точки
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?all=1&fid=16&tid=1340722]:
 0ms
get settings:
 9ms
get forum list:
 14ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 54ms
get topic data:
 6ms
get forum data:
 1ms
get page messages:
 122ms
get tp. blocked users:
 1ms
others: 287ms
total:  498ms
созд. / загр.: 498ms
x
x
Закрыть


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