Ближайшая точка, типа прикладная |
Добро пожаловать, гость ( Вход | Регистрация )
Ближайшая точка, типа прикладная |
alan |
23.1.2010, 22:31
Сообщение
#1
|
zzz... Группа: Администраторы Braingames Сообщений: 13 480 Регистрация: 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 665 Регистрация: 22.4.2007 Пользователь №: 211 |
Сколько платишь?
-------------------- Я - человек-простой
|
alan |
23.1.2010, 22:43
Сообщение
#3
|
zzz... Группа: Администраторы Braingames Сообщений: 13 480 Регистрация: 23.2.2009 Из: Симферополь Пользователь №: 13 114 |
Для примера очевидное и далекое от оптимальности решение:
I) 1. Организация. Точки в произвольном порядке записываем в масив. 2. Поиск. Перебираем весь масив от первого элемента до последнего. И для каждого элемента считаем расстояние до точки B, по формуле sqrt((b_x-x_i)^2+(b_y-y_i)^2). Из растояний выбираем минимальное(б) N минимальных, в) меньшие, чем R). Находим точку, которой соотвествует это расстояние. Сколько платишь? А как платить? За что? За решение + доказательство оптимальности? Не думаю что такое существует. Поэтому и передумал в соответствующем разделе писать. Хотя хорошо было бы иметь раздел в котором каждый мог бы делиться, "тем, что его беспокоит" |
idler_ |
23.1.2010, 23:10
Сообщение
#4
|
Лентяй Группа: Администраторы Braingames Сообщений: 8 665 Регистрация: 22.4.2007 Пользователь №: 211 |
А как платить? За что? За решение + доказательство оптимальности? Не думаю что такое существует. Платить деньгами) За то, что тебе нужно. Смотри: тебя интересует решение какой-то задачи, то есть решение идёт тебе на пользу. Вряд ли кого-то ещё это интересует) Какого-то особого логического интереса задача не вызывает. Зачем тратить время просто так? ) -------------------- Я - человек-простой
|
JK |
23.1.2010, 23:39
Сообщение
#5
|
Kорифей Группа: Пользователи Braingames Сообщений: 1 116 Регистрация: 26.9.2007 Из: Саратов/Москва Пользователь №: 3 789 |
Зачем тратить время просто так? ) Человек с таким ником не может задавать таких вопросов :-) Но возможно, если человек тратит время "просто так" ему доставляет это удовольствие, или он хочет помочь, или он не тратит время на раздумья над вопросом "Зачем тратить время просто так? " -------------------- Дорогу осилит идущий!
|
idler_ |
23.1.2010, 23:52
Сообщение
#6
|
Лентяй Группа: Администраторы Braingames Сообщений: 8 665 Регистрация: 22.4.2007 Пользователь №: 211 |
Человек с таким ником не может задавать таких вопросов :-) Но возможно, если человек тратит время "просто так" ему доставляет это удовольствие, или он хочет помочь, или он не тратит время на раздумья над вопросом "Зачем тратить время просто так? " Да я кучу времени трачу на всяких хлам, но хлам должен быть интересен мне зы: Юлия, вы постоянно апеллируете к моему нику. Почему? -------------------- Я - человек-простой
|
NLIzer |
24.1.2010, 0:43
Сообщение
#7
|
Активный участник Группа: Пользователи Braingames Сообщений: 353 Регистрация: 7.3.2009 Из: Москва Пользователь №: 13 325 |
Представьте, что у вас есть множество А из 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 Сообщений: 13 480 Регистрация: 23.2.2009 Из: Симферополь Пользователь №: 13 114 |
Первое что приходит на ум, это представление областей, в которых находятся точки, в виде квадрантного дерева. Для точки B определяется квадрант относительно других квадрантов в дереве и далее вычисляются квадранты ближайших точек обходом по дереву. В квадранте ближайших точек вычисляется R для каждой точки в квадранте, ну и т.д. Давай подробнее, пожалуйста А то мало что понял... 1. Что за квадратное дерево? Как его образовывать? 2. Как для В определять квадрант? Что значит определение квадранта Относительно других квадратнов? П.С. А может еще есть и не первое приходящее на ум? |
NLIzer |
24.1.2010, 15:04
Сообщение
#9
|
Активный участник Группа: Пользователи Braingames Сообщений: 353 Регистрация: 7.3.2009 Из: Москва Пользователь №: 13 325 |
Давай подробнее, пожалуйста А то мало что понял... 1. Что за квадратное дерево? Как его образовывать? 2. Как для В определять квадрант? Что значит определение квадранта Относительно других квадратнов? П.С. А может еще есть и не первое приходящее на ум? Все точки А описываются одним квадратом. Этот квадрат делится на 4 равные квадратные части – квадранты, каждый из квадрантов опять делится на 4 части и т.д. Таким образом строится квадрантное дерево, все родительские узлы этого дерева – квадранты, листья дерева – точки или списки точек входящие в родительский квадрант. Для каждого узла дерева вычисляется количество точек содержащиеся в квадранте. Ну и далее все операции выполняются сначала для квадрантов в которых есть точки, а потом для точек в них. |
alan |
24.1.2010, 16:07
Сообщение
#10
|
zzz... Группа: Администраторы Braingames Сообщений: 13 480 Регистрация: 23.2.2009 Из: Симферополь Пользователь №: 13 114 |
Все точки А описываются одним квадратом. Этот квадрат делится на 4 равные квадратные части – квадранты, каждый из квадрантов опять делится на 4 части и т.д. Таким образом строится квадрантное дерево, все родительские узлы этого дерева – квадранты, листья дерева – точки или списки точек входящие в родительский квадрант. Для каждого узла дерева вычисляется количество точек содержащиеся в квадранте. Ну и далее все операции выполняются сначала для квадрантов в которых есть точки, а потом для точек в них. Ого, даже рисунок А какой в этом смысл? Почему просто не разбить все на D^2 квадратов? Например, так что бы в каждом было или 0 или 1 точка. |
NLIzer |
24.1.2010, 16:44
Сообщение
#11
|
Активный участник Группа: Пользователи Braingames Сообщений: 353 Регистрация: 7.3.2009 Из: Москва Пользователь №: 13 325 |
А какой в этом смысл? Почему просто не разбить все на D^2 квадратов? Например, так что бы в каждом было или 0 или 1 точка. 1) Память экономится 2) Поиск происходит быстрее за счет структурированной информации о точках, квадранты точек не попадающие в область поиска не обрабатываются. |
alan |
24.1.2010, 17:50
Сообщение
#12
|
zzz... Группа: Администраторы Braingames Сообщений: 13 480 Регистрация: 23.2.2009 Из: Симферополь Пользователь №: 13 114 |
Ну давай забудем лучше о памяти, а то если все помнить и учитывать останемся с носом.
Итак главное скорость. Я так понял, что для поиска ближайшей точки ты предлагаешь проследовать от верха дерева к низу? Итого порядка log(N) операций? Если разбить на одинаковые квадратики, то мы сможем сразу получить номер квадрата имея координаты точки В. Если везет то ближайшая точка получается за 1 операцию. Мне вот только не ясно, что будет если не везет... |
NLIzer |
24.1.2010, 18:40
Сообщение
#13
|
Активный участник Группа: Пользователи Braingames Сообщений: 353 Регистрация: 7.3.2009 Из: Москва Пользователь №: 13 325 |
Я так понял, что для поиска ближайшей точки ты предлагаешь проследовать от верха дерева к низу? Итого порядка log(N) операций? Думаю, что поиск ближайшей точки будет происходить следующим образом: Для точки B проходом по дереву сверху-вниз определяется минимальный квадрант имеющий точки (точка В принадлежит этому квадранту). В этом квадранте последовательно определяется подквадрант имеющий точки и ближайший к точке В. В этом подквадранте определяется ближайшая точка к B и определяется ее расстояние до точки B – расстояние R. Далее ищем все точки на расстоянии меньше чем R от B (поиск в)) с учетом уже просмотренных квадрантов. Если точка на меньшем расстоянии найдена, то опять вычисляем R и повторяем поиск. |
telepnev |
30.1.2010, 0:35
Сообщение
#14
|
Раздолбай Группа: Модераторы BrainGames Сообщений: 836 Регистрация: 27.9.2008 Из: Санкт-Петербург Пользователь №: 10 095 |
А как платить? За что? За решение + доказательство оптимальности? Не думаю что такое существует. Вы заблуждаетесь. Это вычгеом, а в нем все давно изучено, решено и доказано!Если тема еще актуальна, могу кинуть полезные ссылки. -------------------- Беспокоится заранее глупо, разберёмся по ситуации
|
alan |
30.1.2010, 7:37
Сообщение
#15
|
zzz... Группа: Администраторы Braingames Сообщений: 13 480 Регистрация: 23.2.2009 Из: Симферополь Пользователь №: 13 114 |
telepnev, это не выч геом, это кибернетика
кидай. |
NLIzer |
9.2.2010, 17:16
Сообщение
#16
|
Активный участник Группа: Пользователи Braingames Сообщений: 353 Регистрация: 7.3.2009 Из: Москва Пользователь №: 13 325 |
alan, как задачка то, решилась?
|
telepnev |
9.2.2010, 21:11
Сообщение
#17
|
Раздолбай Группа: Модераторы BrainGames Сообщений: 836 Регистрация: 27.9.2008 Из: Санкт-Петербург Пользователь №: 10 095 |
-------------------- Беспокоится заранее глупо, разберёмся по ситуации
|
NLIzer |
10.2.2010, 0:00
Сообщение
#18
|
Активный участник Группа: Пользователи Braingames Сообщений: 353 Регистрация: 7.3.2009 Из: Москва Пользователь №: 13 325 |
|
Упрощённая версия | Сейчас: 26.4.2024, 6:27 |