Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.56/9: Рейтинг темы: голосов - 9, средняя оценка - 4.56
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
1

Расстояние от точки до отрезков

06.02.2014, 12:50. Просмотров 1641. Ответов 17
Метки нет (Все метки)

Здравствуйте

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

- есть N отрезков на плоскости (или в пространстве, здесь без разницы) каждый задан парой точек (p0, p1). Для запросной точки P необходимо уметь быстро находить отрезок расстояние до которого минимально.

Не мудрствуя лукаво, я свел задачу к известной: представил отрезки в виде окружностей (сфер) и дальше использовал OcTree. Это работает медленно т.к. радиусы окружностей оказываются приличными. Нет ли лучшего решения?

Спасибо
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.02.2014, 12:50
Ответы с готовыми решениями:

Как узнать расстояние от центра окружности до любой точки?
Subj.

Показать,что ГМТ точки, расстояние которой от прямой Х=45 в 3 рза больше, чем расстояние от точки А(5,0)
показать,что ГМТточки ,расстояние которой от прямой Х=45 в 3 рза...

Найти расстояние от начала координат до каждой точки и расстояние между точками
задача на С++ На плоскости заданы точки своими координатами. Найти расстояние...

Аналитическая геометрия: расстояние между точками, расстояние от точки до прямой и т.д
всем привет! есть несколько задачек, которые нужно реализовать на vb .net, буду...

Вывести наименьшее расстояние между концами отрезков
Пусть даны два отрезка, заданные координатами точек их концов. Найти с...

17
salam
182 / 163 / 29
Регистрация: 10.07.2012
Сообщений: 775
06.02.2014, 16:53 2
вы хотите решать в онлайне? (каждый новый запрос известен только после ответа на предыдущий)

какие ограничения на N?

Добавлено через 10 минут
за сколько примерно должно работать ваше решение со сферами? (и да, оно легко валится)
0
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
06.02.2014, 18:53  [ТС] 3
Цитата Сообщение от salam Посмотреть сообщение
вы хотите решать в онлайне? (каждый новый запрос известен только после ответа на предыдущий)
Нет, запросы независимы друг от друга, могут выполняться параллельно

Цитата Сообщение от salam Посмотреть сообщение
какие ограничения на N?
В общем случае - доступный размер RAM

Цитата Сообщение от salam Посмотреть сообщение
за сколько примерно должно работать ваше решение со сферами? (и да, оно легко валится)
Не вижу как оно свалится, т.к. это стандартное OcTree. За сколько - само время зависит от многих факторов, лучше оценить число перебираемых отрезков для 1 поиска. У меня получалось 250-300 (на примерно 100K отрезков) что явно слабо.

Ну вот, опять пошли "наводящие"
0
salam
182 / 163 / 29
Регистрация: 10.07.2012
Сообщений: 775
06.02.2014, 19:23 4
Ваше решение, как я понял, основано на предположении, что ближайшая сфера->ближайший отрезок?
0
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
06.02.2014, 19:30  [ТС] 5
Цитата Сообщение от salam Посмотреть сообщение
Ваше решение, как я понял, основано на предположении, что ближайшая сфера->ближайший отрезок?
Нет, это было бы просто неверно. ОсTree позволяет рассматривать только те сферы внутри которых лежит запросная точка P. Для каждой из них я вычисляю расстояние до отрезка и выбираю наименьшее
0
AndrSlav
65 / 53 / 14
Регистрация: 20.12.2013
Сообщений: 461
06.02.2014, 21:42 6
Не понимаю- как рисуются сферы?
0
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
07.02.2014, 12:04  [ТС] 7
Цитата Сообщение от AndrSlav Посмотреть сообщение
Не понимаю- как рисуются сферы?
Да бог с ними - давайте не цепляться за старое решение, тем более жизнь показала что оно просто плохо. Свежие идеи?
0
salam
182 / 163 / 29
Регистрация: 10.07.2012
Сообщений: 775
07.02.2014, 13:15 8
Я думаю, всем понятно, почему для этой задачи придумывание какого-то нового по своей сути решения будет равносильно придумываю колеса. Поэтому я и просил ограничения. Мне не видится ничего лучше, чем поподбирать константу, согласно которой можно будет побить большие отрезки "на поменьше". Тем самым сможем побить удобно плоскость на полоски. Ну и квадродерево.
0
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
07.02.2014, 13:37  [ТС] 9
Цитата Сообщение от salam Посмотреть сообщение
Я думаю, всем понятно, почему для этой задачи придумывание какого-то нового по своей сути решения будет равносильно придумываю колеса. Поэтому я и просил ограничения.
Мне непонятно Конечно хорошо бы свести "к известным образцам", но пока не вижу как это сделать

Цитата Сообщение от salam Посмотреть сообщение
Мне не видится ничего лучше, чем поподбирать константу, согласно которой можно будет побить большие отрезки "на поменьше". Тем самым сможем побить удобно плоскость на полоски. Ну и квадродерево.
Так ресурсы уже разбазарили (отрезки-то могут быть и длинными), а чего добились? Ну спустились по дереву в квадратик запросной точки P - а там из отрезков никого нет. Что дальше?
0
salam
182 / 163 / 29
Регистрация: 10.07.2012
Сообщений: 775
07.02.2014, 15:53 10
Цитата Сообщение от Igor3D Посмотреть сообщение
Мне непонятно Конечно хорошо бы свести "к известным образцам", но пока не вижу как это сделать
я имел ввиду придумыванию колеса в тот момент, когда о нем еще никто не слышал.

Цитата Сообщение от Igor3D Посмотреть сообщение
Так ресурсы уже разбазарили (отрезки-то могут быть и длинными), а чего добились? Ну спустились по дереву в квадратик запросной точки P - а там из отрезков никого нет. Что дальше?
все эти мудреные разбиения очевидно были как раз для того, чтобы можно было примерно равномерно делить на куски, содержащие хоть что-нибудь.
0
palva
3165 / 2281 / 466
Регистрация: 08.06.2007
Сообщений: 8,250
Записей в блоге: 4
07.02.2014, 17:48 11
Может быть, я не в теме. А разве нельзя написать функцию, вычисляющую расстояние точки p от отрезка [p0,p1]. А потом, перебрав все отрезки, найти минимальное расстояние. Конечно для экономии проще вычислять не само расстояние, а его квадрат.
А для вычисления функции сначала определить является ли тупым один из углов p p0 p1 или p p1 p0. Если является, то расстоянием будет расстояние от точки p до вершины тупого угла. (Вычислять, конечно, квадрат расстояния.) Если же оба угла острые, то квадрат площади параллелограмма построенного на векторах p0p p0p1, делим на квадрат отрезка p0p1. Получаем квадрат расстояния до отрезка. Как видите, не нужно даже извлекать квадратный корень.
0
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
07.02.2014, 18:14  [ТС] 12
Цитата Сообщение от palva Посмотреть сообщение
...перебрав все отрезки..
А зачем тогда сортировка, ассоциативные контейнеры, хеши, масса деревьев и многое другое? Ведь в любом случае можно решить задачу "перебрав все"
0
palva
3165 / 2281 / 466
Регистрация: 08.06.2007
Сообщений: 8,250
Записей в блоге: 4
07.02.2014, 18:23 13
Цитата Сообщение от Igor3D Посмотреть сообщение
А зачем тогда сортировка, ассоциативные контейнеры
Как зачем? Вообще говоря, это всё придумано, чтобы ускорить счет. Только в ветку я не вчитывался, тем более, что с алгоритмом, названным OcTree, я все равно не знаком. Вы просили свежих мыслей, безотносительно к тому что уже написано. Может быть перебор будет медленнее, чем тот неизвестный алгоритм, который был предложен. Это вам решать.
0
AndrSlav
65 / 53 / 14
Регистрация: 20.12.2013
Сообщений: 461
07.02.2014, 18:36 14
Цитата Сообщение от palva Посмотреть сообщение
Может быть, я не в теме. А разве нельзя написать функцию, вычисляющую расстояние точки p от отрезка [p0,p1]. А потом, перебрав все отрезки, найти минимальное расстояние. Конечно для экономии проще вычислять не само расстояние, а его квадрат.
А для вычисления функции сначала определить является ли тупым один из углов p p0 p1 или p p1 p0. Если является, то расстоянием будет расстояние от точки p до вершины тупого угла. (Вычислять, конечно, квадрат расстояния.) Если же оба угла острые, то квадрат площади параллелограмма построенного на векторах p0p p0p1, делим на квадрат отрезка p0p1. Получаем квадрат расстояния до отрезка. Как видите, не нужно даже извлекать квадратный корень.
Во-во, у меня примерно такая же мысль
Только не понимаю что является расстоянием до отрезка- до середины, до ближайшей точки отрезка?
Если до ближайшей точки, то проще всего даже углы не вычислять, а сразу квадрат расстояния.
0
palva
3165 / 2281 / 466
Регистрация: 08.06.2007
Сообщений: 8,250
Записей в блоге: 4
07.02.2014, 18:41 15
Цитата Сообщение от AndrSlav Посмотреть сообщение
Только не понимаю что является расстоянием до отрезка- до середины, до ближайшей точки?
Ну как я понимаю, это расстояние до ближайшей точки. Только в случае отрезка это будет либо расстояние до одного из концов отрезка, либо длина перпендикуляра, опущенного на прямую, содержащую отрезок -- это если основание этого перпендикуляра окажется на отрезке, а не на его продолжении.
0
AndrSlav
65 / 53 / 14
Регистрация: 20.12.2013
Сообщений: 461
07.02.2014, 19:07 16
Цитата Сообщение от palva Посмотреть сообщение
либо длина перпендикуляра
а, точно, не подумал.
0
Mysterious Light
Эксперт по математике/физике
4079 / 1993 / 404
Регистрация: 19.07.2009
Сообщений: 3,009
Записей в блоге: 21
07.02.2014, 19:46 17
И я свой пятак вставлю.

Если дано N отрезков и внешняя точка P, то время на поиск самого близкого отрезка ограничено снизу http://www.cyberforum.ru/cgi-bin/latex.cgi?\geq O(N) хотя бы потому, что каждый отрезок нужно прочитать и обработать.
С другой стороны, не сложно подобрать алгоритм полным перебором, работающий O(N).
palva на это обращает внимание: любой алгоритм будет O(N) и сыграть можно только на коэффициенте при N в пределе больших N.

Суть же вопроса, как я понял, состоит в следующем:
Есть N отрезков и M точек. Если для каждой точки считать полным перебором, то будет суммарно O(N*M).
Поскольку мы знаем, что набор отрезков постоянен, то имеет смысл пошаманить над ним и создать некую структуру данных, которая была бы более удобной для дальнейшей обработки.
Очевидно, что время в таком случае состоит из двух частей:
http://www.cyberforum.ru/cgi-bin/latex.cgi?T(N,M) \;=\; T_{preparation}(N) \;+\; M\,\times\, T_{process}(N)
И для M=1 будет http://www.cyberforum.ru/cgi-bin/latex.cgi?T(N,1)=T_{prep}(N) + T_{proc}(N) = O(N), как это было показано выше.
Однако за счёт такой вот факторизации задачи, разделения её, для больших M (например, M>>N) можно что-то как-то улучшить.

Например, если удастся сделать так, чтоб http://www.cyberforum.ru/cgi-bin/latex.cgi?T_{process}(N) = O(\log N), то вместо O(N*M) мы получим O(M*log N). Вся фишка в том, что подготовительный этап, который просто анализирует отрезки, может работать довольно долго (между тем, можно даже не O(N), а что-то более сложное использовать), но он не зависит от числа точек, а поэтому в пределе больших M этот член уйдёт сам собой.

Ещё раз подчеркну, что для M=1 (одна точка) самый оптимальный (в ассимптоте) алгоритм — полный перебор, и ничего более. По запросам ТС я делаю вывод, что набор отрезков задаётся разово (единожды), а потом идёт асинхронная последовательность запросов мин. длины для разных точек, коих довольно много, и задача минимизаровать именно время отклика на каждую точку, что соотв. случаю http://www.cyberforum.ru/cgi-bin/latex.cgi?M\to \infty
0
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
07.02.2014, 20:10  [ТС] 18
Цитата Сообщение от Mysterious Light Посмотреть сообщение
По запросам ТС я делаю вывод, что набор отрезков задаётся разово (единожды), а потом идёт асинхронная последовательность запросов мин. длины для разных точек, коих довольно много, и задача минимизаровать именно время отклика на каждую точку, что соотв. случаю http://www.cyberforum.ru/cgi-bin/latex.cgi?M\to \infty
Совершенно верно, ключевое слово "запросная". Для простоты набор отрезков вообще никогда не меняется. Близкая задача - меняется слабо, напр 1 отрезок (из 100K) заменяется 2-мя, но это уже др задача за рамками данной темы. Разумеется для 1 точки (запроса) чего-то городить незачем - ведь это одна операция. А вот если запросов много - время поиска очень критично. Да, любые структуры данных могут/должны быть построены для отрезков и время их построения может быть достаточно велико, опять-таки потому что это операция разовая на этапе предрасчета. Но если уж построили - извольте быстро находить.
0
07.02.2014, 20:10
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.02.2014, 20:10

Найдите расстояние между серединами отрезков AE1
1. В правильной шестиугольной призме ABCDEFA1B1C1D1E1F1 сторона основания равна...

Подпрограммы. Для точки на плоскости найти расстояние от точки до начала координат
Для точки на плоскости с заданными координатами (x,y) найти расстояние l от...

Вывести расстояние от заданной точки до точки пересечения диагоналей прямоугольников
Прямоугольники заданы координатами их вершин. 1)Вывести расстояние от...


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

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

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