Определение приблизительных перекрытий заданной полилинии с набором существующих полилиний

У меня есть набор полилиний (нумерация в 100s тысяч, причем каждая полилиния имеет около 200-300 вершин). Они представляют маршруты на карте (все взяты из API Карт Google, если это помогает). Вершины - это координаты широты/долготы.

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

Чтобы дать конкретное представление, в левой части изображения ниже, синяя полилиния (полилиния A) является полилинией в базе данных, а красная полилиния (полилиния B) является полилинией запроса. Алгоритм должен определить полилинию, обозначенную черным, как показано справа.

В настоящее время я склоняюсь к использованию пространственной базы данных (рассматриваемый вариант - PostgreSQL + PostGIS), но я не уверен, что латентность будет приемлемой - запрос должен немедленно возвращать результаты. Моя вычислительная геометрия-fu, по общему признанию, слаба, но мне было интересно: существуют ли какие-либо существующие алгоритмы или подходы, которые могут оказаться полезными для решения этой конкретной проблемы?

Большое спасибо заранее!

Ответ 1

Быстрый приближенный запрос, в котором вам не нужно находить все совпадения, такие как http://en.wikipedia.org/wiki/Locality-sensitive_hashing - и я подозреваю, что вы получите нагрузки хитов с этим. Некоторое время назад меня заинтриговало http://www.cs.ubc.ca/~lowe/papers/09muja.pdf - я понятия не имею, работает ли это на практике, но тот же поиск, что и найденный документ найден библиотека http://www.cs.ubc.ca/research/flann/. На странице wikipedia на прямой LSH есть указатели, по крайней мере, на одну реализацию внизу. Преимущество LSH заключается в том, что он отлично выполняет поиск базы данных с реляционными базами данных или файлами dbm.

Ответ 2

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

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

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

Одной из важных проблем является разрешение сетки. Слишком грубый результат приведет к неэффективному отказу кандидатов. Слишком тонкий будет увеличивать время/пространство предварительной обработки неприемлемым способом.

Предполагая, что размер сетки такой, что у вас есть пиксели W x H, вам понадобятся указатели ссылок W x H плюс указатели N x L (для N полилиний средней длины L, в пикселях - не в количестве вершин). Первый член растет как квадрат разрешения, а второй растет только линейно. Время предварительной обработки является линейным по размеру этой структуры данных (W x H для инициализации списков, N x L для чертежей линии Bresenham).

Запрос будет стоить примерно L 'x K, где L' - длина полилинии запроса, а K - количество совпадающих полилиний (в случае K → 1, используйте эффективную структуру словаря для учета K кандидаты). Это пропорционально разрешению.

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

Ответ 3

Сначала рассмотрим только ограничивающие прямоугольники строк, поэтому строка из (x1,y1)->(x2,y2) станет прямоугольником (x1,y1,x2,y2). Поиск перекрытий между одной ограничивающей рамкой и другими может быть выполнен в O (log n) времени с использованием двумерного дерева интервалов или дерево сегментов. Затем вы можете перебрать эти потенциальные совпадения, чтобы проверить, действительно ли линии пересекаются. Общая временная сложность была бы примерно равной O (n log n) для всех строк данных, имеющих несколько перекрывающихся ограничивающих полей.

Существует сообщение stackoverflow с хорошим описанием того, как проверить, пересекаются ли две строки