IPB

Добро пожаловать, гость ( Вход | Регистрация )

 
Ответить в эту темуОткрыть новую тему
> Ближайшая точка, типа прикладная
Рейтинг  3
alan
23.1.2010, 22:31
Сообщение #1


zzz...
*****

Группа: Администраторы Braingames
Сообщений: 12 100
Регистрация: 23.2.2009
Из: Симферополь
Пользователь №: 13 114



Представьте, что у вас есть множество А из M точек на плоскости (x_i,y_i). Есть информация о них - по две координаты.

Потом нам дают еще одну точку - B(b_x,b_y). Нужно найти:
а) Точку из множества А ближайшую к B.
б) N ближайших точек к B.
в) Все точки на растоянии меньше чем R от B

Задача - оптимально организовать информацию о точках А. Оптимальность определяется средней скоростью выполнения а), б) или в).
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
idler_
23.1.2010, 22:40
Сообщение #2


Лентяй
*****

Группа: Администраторы Braingames
Сообщений: 8 663
Регистрация: 22.4.2007
Пользователь №: 211



Сколько платишь? smile.gif
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
alan
23.1.2010, 22:43
Сообщение #3


zzz...
*****

Группа: Администраторы Braingames
Сообщений: 12 100
Регистрация: 23.2.2009
Из: Симферополь
Пользователь №: 13 114



Для примера очевидное и далекое от оптимальности решение:


I)
1. Организация. Точки в произвольном порядке записываем в масив.
2. Поиск. Перебираем весь масив от первого элемента до последнего. И для каждого элемента считаем расстояние до точки B, по формуле sqrt((b_x-x_i)^2+(b_y-y_i)^2). Из растояний выбираем минимальное(б) N минимальных, в) меньшие, чем R). Находим точку, которой соотвествует это расстояние.

QUOTE(idler_ @ 23.1.2010, 20:40) *

Сколько платишь? smile.gif

А как платить? За что? За решение + доказательство оптимальности? Не думаю что такое существует.
Поэтому и передумал в соответствующем разделе писать.
Хотя хорошо было бы иметь раздел в котором каждый мог бы делиться, "тем, что его беспокоит" smile.gifsmile.gif
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
idler_
23.1.2010, 23:10
Сообщение #4


Лентяй
*****

Группа: Администраторы Braingames
Сообщений: 8 663
Регистрация: 22.4.2007
Пользователь №: 211



QUOTE(alan @ 23.1.2010, 22:43) *
А как платить? За что? За решение + доказательство оптимальности? Не думаю что такое существует.

Платить деньгами)
За то, что тебе нужно.
Смотри: тебя интересует решение какой-то задачи, то есть решение идёт тебе на пользу.
Вряд ли кого-то ещё это интересует)
Какого-то особого логического интереса задача не вызывает.
Зачем тратить время просто так? )
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
JK
23.1.2010, 23:39
Сообщение #5


Kорифей
****

Группа: Пользователи Braingames
Сообщений: 1 116
Регистрация: 26.9.2007
Из: Саратов/Москва
Пользователь №: 3 789



QUOTE(idler_ @ 23.1.2010, 23:10) *

Зачем тратить время просто так? )

Человек с таким ником не может задавать таких вопросов :-)
Но возможно, если человек тратит время "просто так" ему доставляет это удовольствие, или он хочет помочь, или он не тратит время на раздумья над вопросом "Зачем тратить время просто так? "


--------------------
Дорогу осилит идущий!
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
idler_
23.1.2010, 23:52
Сообщение #6


Лентяй
*****

Группа: Администраторы Braingames
Сообщений: 8 663
Регистрация: 22.4.2007
Пользователь №: 211



QUOTE(JK @ 23.1.2010, 23:39) *

Человек с таким ником не может задавать таких вопросов :-)
Но возможно, если человек тратит время "просто так" ему доставляет это удовольствие, или он хочет помочь, или он не тратит время на раздумья над вопросом "Зачем тратить время просто так? "

Да я кучу времени трачу на всяких хлам, но хлам должен быть интересен мне smile.gif
зы: Юлия, вы постоянно апеллируете к моему нику. Почему? smile.gif
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
NLIzer
24.1.2010, 0:43
Сообщение #7


Активный участник
***

Группа: Пользователи Braingames
Сообщений: 347
Регистрация: 7.3.2009
Из: Москва
Пользователь №: 13 325



QUOTE(alan @ 23.1.2010, 22:31) *

Представьте, что у вас есть множество А из M точек на плоскости (x_i,y_i). Есть информация о них - по две координаты.

Потом нам дают еще одну точку - B(b_x,b_y). Нужно найти:
а) Точку из множества А ближайшую к B.
б) N ближайших точек к B.
в) Все точки на растоянии меньше чем R от B

Задача - оптимально организовать информацию о точках А. Оптимальность определяется средней скоростью выполнения а), б) или в).

Первое что приходит на ум, это представление областей, в которых находятся точки, в виде квадрантного дерева. Для точки B определяется квадрант относительно других квадрантов в дереве и далее вычисляются квадранты ближайших точек обходом по дереву. В квадранте ближайших точек вычисляется R для каждой точки в квадранте, ну и т.д.
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
alan
24.1.2010, 8:02
Сообщение #8


zzz...
*****

Группа: Администраторы Braingames
Сообщений: 12 100
Регистрация: 23.2.2009
Из: Симферополь
Пользователь №: 13 114



QUOTE(NLIzer @ 23.1.2010, 22:43) *

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

Давай подробнее, пожалуйста smile.gif А то мало что понял...
1. Что за квадратное дерево? Как его образовывать?
2. Как для В определять квадрант? Что значит определение квадранта Относительно других квадратнов?



П.С. А может еще есть и не первое приходящее на ум?smile.gif
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
NLIzer
24.1.2010, 15:04
Сообщение #9


Активный участник
***

Группа: Пользователи Braingames
Сообщений: 347
Регистрация: 7.3.2009
Из: Москва
Пользователь №: 13 325



QUOTE(alan @ 24.1.2010, 8:02) *

Давай подробнее, пожалуйста smile.gif А то мало что понял...
1. Что за квадратное дерево? Как его образовывать?
2. Как для В определять квадрант? Что значит определение квадранта Относительно других квадратнов?
П.С. А может еще есть и не первое приходящее на ум?smile.gif

Все точки А описываются одним квадратом. Этот квадрат делится на 4 равные квадратные части – квадранты, каждый из квадрантов опять делится на 4 части и т.д. Таким образом строится квадрантное дерево, все родительские узлы этого дерева – квадранты, листья дерева – точки или списки точек входящие в родительский квадрант. Для каждого узла дерева вычисляется количество точек содержащиеся в квадранте.
Ну и далее все операции выполняются сначала для квадрантов в которых есть точки, а потом для точек в них.
Изображение
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
alan
24.1.2010, 16:07
Сообщение #10


zzz...
*****

Группа: Администраторы Braingames
Сообщений: 12 100
Регистрация: 23.2.2009
Из: Симферополь
Пользователь №: 13 114



QUOTE(NLIzer @ 24.1.2010, 13:04) *

Все точки А описываются одним квадратом. Этот квадрат делится на 4 равные квадратные части – квадранты, каждый из квадрантов опять делится на 4 части и т.д. Таким образом строится квадрантное дерево, все родительские узлы этого дерева – квадранты, листья дерева – точки или списки точек входящие в родительский квадрант. Для каждого узла дерева вычисляется количество точек содержащиеся в квадранте.
Ну и далее все операции выполняются сначала для квадрантов в которых есть точки, а потом для точек в них.
Изображение

Ого, даже рисунок rolleyes.gif

А какой в этом смысл? Почему просто не разбить все на D^2 квадратов? Например, так что бы в каждом было или 0 или 1 точка.
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
NLIzer
24.1.2010, 16:44
Сообщение #11


Активный участник
***

Группа: Пользователи Braingames
Сообщений: 347
Регистрация: 7.3.2009
Из: Москва
Пользователь №: 13 325



QUOTE(alan @ 24.1.2010, 16:07) *

А какой в этом смысл? Почему просто не разбить все на D^2 квадратов? Например, так что бы в каждом было или 0 или 1 точка.

1) Память экономится
2) Поиск происходит быстрее за счет структурированной информации о точках, квадранты точек не попадающие в область поиска не обрабатываются.
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
alan
24.1.2010, 17:50
Сообщение #12


zzz...
*****

Группа: Администраторы Braingames
Сообщений: 12 100
Регистрация: 23.2.2009
Из: Симферополь
Пользователь №: 13 114



Ну давай забудем лучше о памяти, а то если все помнить и учитывать останемся с носом.

Итак главное скорость.
Я так понял, что для поиска ближайшей точки ты предлагаешь проследовать от верха дерева к низу? Итого порядка log(N) операций?

Если разбить на одинаковые квадратики, то мы сможем сразу получить номер квадрата имея координаты точки В. Если везет то ближайшая точка получается за 1 операцию.
Мне вот только не ясно, что будет если не везет...
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
NLIzer
24.1.2010, 18:40
Сообщение #13


Активный участник
***

Группа: Пользователи Braingames
Сообщений: 347
Регистрация: 7.3.2009
Из: Москва
Пользователь №: 13 325



QUOTE(alan @ 24.1.2010, 17:50) *

Я так понял, что для поиска ближайшей точки ты предлагаешь проследовать от верха дерева к низу? Итого порядка log(N) операций?

Думаю, что поиск ближайшей точки будет происходить следующим образом:
Для точки B проходом по дереву сверху-вниз определяется минимальный квадрант имеющий точки (точка В принадлежит этому квадранту). В этом квадранте последовательно определяется подквадрант имеющий точки и ближайший к точке В. В этом подквадранте определяется ближайшая точка к B и определяется ее расстояние до точки B – расстояние R. Далее ищем все точки на расстоянии меньше чем R от B (поиск в)) с учетом уже просмотренных квадрантов. Если точка на меньшем расстоянии найдена, то опять вычисляем R и повторяем поиск.
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
telepnev
30.1.2010, 0:35
Сообщение #14


Раздолбай
***

Группа: Модераторы BrainGames
Сообщений: 832
Регистрация: 27.9.2008
Из: Санкт-Петербург
Пользователь №: 10 095



QUOTE(alan @ 23.1.2010, 22:43) *
А как платить? За что? За решение + доказательство оптимальности? Не думаю что такое существует.
Вы заблуждаетесь. Это вычгеом, а в нем все давно изучено, решено и доказано!
Если тема еще актуальна, могу кинуть полезные ссылки.


--------------------
Беспокоится заранее глупо, разберёмся по ситуации
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
alan
30.1.2010, 7:37
Сообщение #15


zzz...
*****

Группа: Администраторы Braingames
Сообщений: 12 100
Регистрация: 23.2.2009
Из: Симферополь
Пользователь №: 13 114



telepnev, это не выч геом, это кибернетика smile.gif

кидай.
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
NLIzer
9.2.2010, 17:16
Сообщение #16


Активный участник
***

Группа: Пользователи Braingames
Сообщений: 347
Регистрация: 7.3.2009
Из: Москва
Пользователь №: 13 325



alan, как задачка то, решилась?
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
telepnev
9.2.2010, 21:11
Сообщение #17


Раздолбай
***

Группа: Модераторы BrainGames
Сообщений: 832
Регистрация: 27.9.2008
Из: Санкт-Петербург
Пользователь №: 10 095



QUOTE(alan @ 30.1.2010, 7:37) *
кидай.
Раз и два


--------------------
Беспокоится заранее глупо, разберёмся по ситуации
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
NLIzer
10.2.2010, 0:00
Сообщение #18


Активный участник
***

Группа: Пользователи Braingames
Сообщений: 347
Регистрация: 7.3.2009
Из: Москва
Пользователь №: 13 325



QUOTE(telepnev @ 9.2.2010, 21:11) *

О как!!! smile.gif Я был близок
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения

Ответить в эту темуОткрыть новую тему
2 чел. читают эту тему (гостей: 2, скрытых пользователей: 0)
Пользователей: 0 -

 



- Упрощённая версия Сейчас: 24.1.2020, 14:04