#algorithm #data-structures #computational-geometry
#алгоритм #структуры данных #вычислительная геометрия
Вопрос:
Это проблема, с которой я часто сталкивался, и я ищу более эффективный способ ее решения. Взгляните на это фото:
Допустим, вы хотите найти кратчайшее расстояние от красной точки до отрезка a n. Предположим, вы знаете только начальную / конечную точку (x, y) сегментов и точку. Теперь это можно сделать в O (n), где n — отрезки, проверяя каждое расстояние от точки до отрезка. Это IMO неэффективно, потому что в худшем случае должно быть n-1 проверок расстояния, пока не будет найден правильный.
Это может быть реальной проблемой производительности для n = 1000 f.e. (что является вероятным числом), особенно если вычисление расстояния выполняется не только в евклидовом пространстве с помощью теоремы Пифагора, но, например, с помощью геодезического метода, такого как формула Хаверсина или Винсенти.
Это общая проблема в разных ситуациях:
- Находится ли точка внутри радиуса вершин?
- Какой набор вершин является ближайшим к точке?
- Окружена ли точка отрезками линии?
Чтобы ответить на эти вопросы, единственный известный мне подход — O (n) . Теперь я хотел бы знать, существует ли структура данных или другая стратегия для более эффективного решения этих проблем?
Короче говоря: я ищу способ, при котором отрезки / вершины могут быть каким-то образом «отфильтрованы», чтобы получить набор потенциальных кандидатов, прежде чем я начну вычисления расстояния. Что-нибудь, чтобы уменьшить сложность до O (m), где m < n .
Комментарии:
1. Может быть некоторая эффективность в проверке отдельных отрезков линии, например, когда они имеют общие конечные точки с другими отрезками линии, но я считаю, что вам всегда придется проверять все отрезки линии, поэтому ответ всегда будет порядка n .
2. Это может быть полезно — en.wikipedia.org/wiki/Point_location . Это для точечных запросов, но вы можете адаптировать его к своим целям
3. Это не проблема теории графов, она относится к области вычислительной геометрии. Я обновил тег.
4. вы могли бы изучить что-то вроде четырехъядерных деревьев , чтобы попытаться быстро отобрать несколько отрезков, которые находятся слишком далеко, чтобы быть «ближайшими», хотя этот подход может быть более дорогостоящим для запуска, если n мало, или все строки плотно упакованы
5. Следует иметь в виду, что эта проблема очень распараллеливаема. Если ваш ввод составляет порядка n = 1000, проблема фактически является O (1) временной сложностью, если выполняется на графическом процессоре.
Ответ №1:
Вероятно, это неприемлемый ответ, но слишком длинный для комментария: Наиболее подходящий ответ здесь зависит от деталей, которые вы не указали в вопросе.
Если вы хотите выполнить этот тест только один раз, то избежать линейного поиска будет невозможно. Однако, если у вас есть фиксированный набор строк (или набор строк, который не меняется слишком значительно с течением времени), вы можете использовать различные методы для ускорения запросов. Их иногда называют пространственными индексами, например, квадратичным деревом.
Вам придется ожидать компромисса между несколькими факторами, такими как время запроса и потребление памяти, или время запроса и время, необходимое для обновления структуры данных при изменении заданного набора строк. Последнее также зависит от того, является ли это структурным изменением (добавляемые или удаляемые линии) или меняются только позиции существующих линий.
Комментарии:
1. Таким образом, данные останутся фиксированными, только положение красной точки меняется. Означает, что я собираю данные один раз, выполняю некоторые вычисления и загружаю новый набор данных. Вполне вероятно, что использование более сложной структуры данных будет эффективным, если это может снизить общую производительность за счет низкой сложности запроса. Но, конечно, я должен его протестировать.