#wpf #algorithm #computational-geometry #polyline #line-intersection
#wpf #алгоритм #вычислительная геометрия #полилиния #линия-пересечение
Вопрос:
Алгоритм Бентли-Оттмана работает для нахождения пересечений множества прямых линий. Но у меня много полилиний:
Есть ли способ найти пересечения множества полилиний?
Я выясняю, но пока, если кто-нибудь может дать несколько советов или идей, это было бы полезно. Спасибо за чтение. Кстати, я использую WPF / C #, и все полилинии имеют геометрию пути.
Источник изображения: http://www.sitepen.com/blog/wp-content/uploads/2007/07/gfx-curve-1.png
Комментарии:
1. Вы все еще можете использовать Bentley-Ottmann.
2. Спасибо, Барт. Не могли бы вы объяснить, пожалуйста? Не найдет ли он точки пересечения, которые являются соединяющими точками самой полилинии?
3. да, всякий раз, когда вы находите пересечения, вы проверяете, является ли это «реальным» пересечением двух сегментов или точкой двух соединенных сегментов, которые принадлежат одной и той же полилинии.
4. добавил некоторые метаданные и сделал это. но существует ли какой-либо алгоритм специально для полилиний?
5. @Sam Возможно, вам повезет больше, если вы зададите этот вопрос на math.stackexchange.com
Ответ №1:
Алгоритм развертки линий имеет хорошую теорию, но его сложно надежно реализовать. Вам необходимо обрабатывать вертикальные сегменты, и могут быть случаи, когда более двух отрезков пересекаются в одной точке (или даже имеют общий отрезок).
Я бы использовал R-дерево для хранения ограничивающих рамок отрезков полилинии, а затем использовал R-дерево для поиска возможных пересекающихся элементов. Только они должны быть проверены на пересечение. Преимущество заключается в том, что вы можете использовать отдельное R-дерево для каждой полилинии и, таким образом, избежать обнаружения самопересечений, если это необходимо.
Рассмотрите возможность использования ядра точных предикатов CGAL для получения надежных результатов.
Ответ №2:
В дополнение к предложению Geom (R-дерево — это правильный путь), дальнейшего повышения производительности можно добиться, выполнив следующее:
1. Упростите полилинию — количество точек на полилинии можно уменьшить, сохранив общую форму полилинии. Это может быть сделано с использованием порогового значения угла и обработки каждой точки или с помощью алгоритма Рамера-Дугласа-Пекера. В зависимости от того, что вы делаете, вам может потребоваться отслеживать, какие точки исходной полилинии использовались в качестве начальной / конечной точек для каждого сегмента упрощенной полилинии (индексы точек исходной полилинии нужно будет где-то хранить).
В этом примере вы можете увидеть, как можно уменьшить количество точек на полилинии. Красными точками обозначены точки, которые не использовались на исходной полилинии, а зелеными точками обозначены точки, которые были сохранены для построения упрощенной полилинии.
2. Сохраните упрощенные полилинии в R-дереве и определите пересечения между каждым сегментом каждой полилинии (сравнение границ сегментов для сокращения вычислений полезно для производительности). При выполнении этого старые индексы из сегментов исходной полилинии сохраняются как информация, относящаяся к каждому обнаруженному пересечению, вместе с которым пересекались полилинии (может использоваться какой-то идентификатор). По сути, это дает вам начальную и конечную границы каждого сегмента в исходных полилиниях, где существуют пересечения друг с другом полилиний.
3. Этот шаг выполняется только в том случае, если местоположение пересечения должно точно соответствовать местоположению пересечений исходных полилиний. Вам нужно будет вернуться назад и использовать исходные неупрощенные полилинии вместе с данными из информации о пересечении, полученной на шаге 2. С каждым пересечением должны быть связаны начальный и конечный индексы, и эти индексы можно использовать для определения, какие конкретные сегменты исходной полилинии необходимо обработать. Это позволит вам обрабатывать только необходимые сегменты (заданные начальным и конечным индексами, хранящимися вместе с информацией о пересечении). Альтернативой этому было бы использовать саму точку и расширить ограничивающую рамку наружу, затем обработать сегменты исходных полилиний, которые пересекаются с этой ограничивающей рамкой (хотя это, вероятно, займет больше времени).
4. Может потребоваться выполнить дополнительный шаг для сверки конечных точек каждой полилинии с сегментами любой другой полилинии, поскольку процесс упрощения может исключить некоторые пересечения конечных точек. (обычно это довольно быстро).
Этот алгоритм может быть дополнительно улучшен с помощью алгоритма Бентли-Оттмана (это алгоритм развертки линий, на который ссылался Geom). Также обратите внимание, что в зависимости от используемого алгоритма упрощения и параметров, используемых для таких алгоритмов (например, угловой допуск), может возникнуть компромисс между производительностью и точностью (некоторые результаты пересечения могут быть потеряны в зависимости от того, насколько просты полилинии).
Очевидно, что существуют библиотеки, которые могут оказаться жизнеспособными, но если вы ограничены условиями лицензии из-за компании, в которой вы работаете, или продукта, над которым вы работаете, библиотеки сторонних производителей могут оказаться неподходящим вариантом. Кроме того, другие библиотеки могут работать не так хорошо, как может потребоваться.