Найти ближайший ребро в графе

Я хочу найти ближайшее крен в графе. Рассмотрим следующий пример:

Рисунок 1: желтый: вершины, черные: ребра, синий: точка запроса

Общая информация: График содержит около 10 миллионов вершин и около 15 миллионов краев. Каждая вершина имеет координаты. Края определяются двумя соседними вершинами.

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

Идея и трудности: Моя идея состояла в том, чтобы использовать некоторый пространственный индекс для ускорения запроса. Я уже реализовал kd-дерево, чтобы найти ближайшую вершину. Но, как показано на рисунке 1, ребра, попадающие в ближайшую вершину, не обязательно являются ближайшими к точке запроса. Я бы получил край 3-4 вместо более близкого края 7-8.

Вопрос: Есть ли алгоритм для нахождения ближайшего ребра в графе?

Ответы

Ответ 1

Существуют пространственные структуры запросов, которые подходят для других типов данных, чем точки. Наиболее общей является структура "R-tree" (и ее множество, множество вариантов), которая позволит вам хранить ограничивающие прямоугольники ваших сегментов линии. Затем вы можете искать наружу из своих точек запроса, анализируя сегменты в ограничивающих прямоугольниках и останавливаясь, когда ближайший оставшийся прямоугольник будет дальше, чем ближайшая строка, встречающаяся до сих пор. Это может иметь низкую производительность при многократном перекрытии длинной линии, но для PSLG, такого как вы, кажется, здесь, этого не должно быть.

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

Ответ 2

Очень простое решение (но, возможно, не самое сложное) - использовать quad tree для всех ваших ребер на основе их Ограничительная рамка. Затем вы просто извлекаете набор ребер, ближайших к вашей точке запроса, и перебираете их, чтобы найти ближайший край.

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

Квадратное дерево - это более простая структура данных, чем R-дерево. Он довольно распространен и должен быть легко доступен во многих средах. Например, в Java JTS Topology Suite имеет структуру QuadTree, которую можно легко обернуть для выполнения этой задачи.

Ответ 3

Вы можете вычислить диаграмму voronoi и запустить запрос для каждой ячейки voronoi. Вы можете разделить диаграмму voronoi, чтобы получить лучший результат. Вы можете комбинировать метрическую и воронную диаграмму: http://www.cc.gatech.edu/~phlosoft/voronoi/

Ответ 4

Без доказательства:
Вы начинаете с сдержанной триангуляции Delaunay, которая является триангуляцией, которая учитывает существующие ребра. Например. CGAL или Triangle может это сделать. Для каждой точки запроса вы определяете, к какому треугольнику принадлежит. Тогда вам нужно только проверить края, касаясь угла этого треугольника.
Я думаю, что это должно работать в большинстве случаев, но есть, конечно, угловые случаи, когда он терпит неудачу, например. когда существует множество вершин без какого-либо ребра, так что по крайней мере вам нужно удалить эти пустые вершины.

Ответ 5

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