Эффективный алгоритм поиска пар соседних, параллельных улиц на карте

Question

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

1. Поместите все улицы (объекты улиц) в большой список
2. Найти каждую возможную пару из двух улиц в списке, используя вложенные for петли; Для каждой пары нарисуйте прямоугольник вокруг двух улиц и рассчитайте угол, под которым ориентирована каждая улица.
3. Если прямоугольники перекрываются, площадь перекрытия достаточно велика, и углы одинаковы, две улицы в паре считаются параллельными и близкими друг к другу.

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

Одна идея, о которой я думаю, это сортировка списка улиц по широте или долготе и сравнение только тех пар улиц, которые находятся, скажем, на расстоянии 50 позиций друг от друга в списке. Это, вероятно, будет более эффективным, но все равно не выглядит очень элегантно; есть ли лучший способ?

Каждая улица состоит из объектов Node, и я могу легко получить как объекты Node, так и координаты широты / долготы каждого узла. Я также могу легко найти угол, под которым ориентирована улица.

Answer 1

Я думаю, что первое, что нужно сделать, это отсортировать все улицы по углу, чтобы все параллельные улицы были расположены близко друг к другу.

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

Затем все отсортированные улицы можно разделить на группы одного направления. Внутри каждой такой группы существует естественный порядок, определяемый следующим образом. Рассмотрим другую линию, перпендикулярную всем улицам с одинаковым направлением. Для любой такой улицы рассмотрите точку пересечения с этой перпендикулярной линией и отсортируйте все эти улицы по этой точке пересечения (я предполагаю, что все улицы бесконечно длинные).

Эта сортировка может быть легко выполнена без какого-либо пересечения, вам нужно просто рассчитать для каждой улицы расстояние от исходного (или любой другой фиксированной точки) до этой линии улицы и отсортировать улицы по этому расстоянию. (Если у вас есть улица, определенная стандартным уравнением прямой Ax+By+C=0 то это расстояние от источника C/sqrt(A*A+B*B).)

Теперь у вас есть все необходимые параллельные близкие улицы очень близко друг к другу в таком порядке. Если бы все улицы были бесконечно длинными, то такие ближайшие пары всегда шли бы одна за другой; при конечной длине улиц между ними могут быть дополнительные улицы, но я думаю, что по любым реальным данным их будет очень мало. Таким образом, вы можете просто взять некоторый порог разницы расстояний и проверить все пары, попадающие в него.

Теперь давайте вспомним, что углы точно не определены. Тогда я могу предложить следующий подход. Поддерживать бинарное дерево поиска (что-то вроде C++ std::map) для улиц ключом поиска будет расстояние от начала координат до линии улицы. Идите по улицам в порядке их сортировки по углу. В дереве мы сохраним все улицы, для которых углы различаются менее чем на некоторый порог. Таким образом, в каждый момент времени для каждой улицы в дереве ее соседи по дереву будут иметь оба угла, отличающихся менее чем порогом, и расстояния от начала координат, отличающиеся менее чем некоторым порогом. Итак, для каждой улицы сделайте следующее:

• Добавьте эту улицу к дереву
• Для всех улиц, которые находятся в дереве, но их угол слишком отличается от угла текущей улицы, удалите эти улицы из дерева
• Теперь обработайте добавленную улицу: посмотрите на все улицы в дереве, у которого есть ключ поиска (расстояние от источника) в пределах требуемого порога, и проверьте пару (добавленная улица, другая улица).

Первый пункт O(log N) второе O(log N) на удаленную улицу, если вы просто удерживаете другой указатель вдоль массива отсортированных углов, указывающий на улицы, которые нужно удалить, а третий - O(log N) на соседнюю улицу считается.

Очень грубый псевдокод:

sort lines by angle
r = 0 // the street to be deleted from the tree
for l=0..n-1
    tree.add(street[l])
    while street[r].angle<streel[l].angle-angle_threshold
        tree.remove(street[r])
    other_street=tree.prev(street[l])
    while other_street.dist>street[l].dist-dist_threshold
        process(street[l], other_street)
        other_street = tree.prev(other_street)
    other_street=tree.next(street[l])
    while other_street.dist<street[l].dist+dist_threshold
        process(street[l], other_street)
        other_street = tree.next(other_street)

Вот tree.prev находит предыдущую улицу в дереве, то есть улицу с максимальным расстоянием, которое меньше расстояния для данной улицы, и tree.next аналогично находит следующую улицу. Обе операции могут быть выполнены в O(log N),

Это не "зацикливает" массив, то есть не учитывает пары улиц, одна из которых расположена в самом конце отсортированного массива, а другая в самом начале, но это легко исправить.

Answer 2

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

Другая идея состоит в том, чтобы преобразовать все участки дороги. Бесконечная линия, на которой лежит каждый сегмент, соответствует точке в 2-мерном пространстве Хо: полярный угол линии - одна ось, а расстояние до начала ближайшей точки линии - другая. Преобразование из двух точек на прямой в точку Хафа является простой алгеброй.

Теперь вы можете обнаружить почти коллинеарные отрезки дороги, используя алгоритм пары ближайших точек. К счастью, это можно сделать за O(n log n) ожидаемое время. Например, используя дерево кд. Вставьте все точки в дереве. Используйте стандартный алгоритм дерева kd, чтобы найти ближайшего соседа каждой точки. Отсортируйте расстояние между парами и примите префикс результата в виде пар, которые нужно учитывать, останавливаясь там, где пары находятся слишком далеко друг от друга, чтобы соответствовать критерию "рядом и параллельно". Есть O(n) таких пар ближайших соседей.

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

Есть достаточно хорошие статьи Википедии обо всех упомянутых здесь алгоритмах. Ищите их, если они не знакомы.