Алгоритм поиска перекрывающихся отрезков
-
07-07-2019 - |
Вопрос
n4------------------n3--------------------n2--n1 | | | | | | | P1 | | | | | | | n6--n5 | | | | n11--n10 | n17 P4 | | P2 | | | P3 | n7 | n12---n9 | | | n8 | | | n16------------n15---------n14------------n13
В вышеприведенном искусстве ASCII есть четыре полигона (P1, P2, P3, P4) с точно перекрывающимися отрезками. Например, полигон P2 (образованный отрезками линии между узлами n3, 10, 9, 12, 15, 14, 13, 8, 7, 6 и 2) и P1 (n1, 2, 5 и 6) перекрываются на отрезок между n2 и n6.
Какой самый быстрый способ найти отрезки, которые точно перекрываются?
Решение
Если каждая фигура представляет собой список ребер, то:
initialize map<edge, list of shapes> map
for each Shape s
for each Edge e in s
list l = map.get(e)
if(l == null)
l = new list()
l.add(s)
map.put(e, l)
for each <edge, list> in map.entries
if(list.size > 1)
do something with this common edge
его O (края), и вы не будете делать лучше, чем это. хотя это решение может быть неудовлетворительным, в зависимости от того, что вы конкретно хотите сделать.
Другие советы
Учитывая N отрезков, в худшем случае может быть O (n ^ 2) пересечений. Вспомните случай, когда у вас есть N полигонов, где каждый полигон имеет одинаковое ребро. Если нет добавленного ограничения для предотвращения этой ситуации (которую вы не добавили), то лучшим алгоритмом, который вы можете придумать, будет O (N ^ 2) в худшем случае, поскольку просто перечисление пересечений - это O (N ^ 2). р>
На практике наиболее эффективными алгоритмами в вычислительной геометрии для нахождения пересечений отрезков являются алгоритмы стреловидности. Их наихудшее время выполнения для нахождения всех пересечений - O (k log n), где k - количество пересечений (это может быть N ^ 2, однако это редко бывает.)
Вы можете найти описание именно того алгоритма, который вам нужен, в Введение в алгоритмы Томаса Х. Кормена в разделе по вычислительной геометрии.
алгоритм twolfe18 выглядит хорошо. Однако может возникнуть дополнительное осложнение, если совпадающие ребра не описаны одинаково. В вашем примере P1 и P2 оба имеют ребро n2-n6. Но ребро P2 может быть описано сегментом n2-n7 (если n2-n6 и n6-n7 коллинеарны). Затем вам понадобится более сложный метод хеширования, чтобы определить, перекрываются ли два ребра. Вы можете определить, перекрываются ли два ребра, отображая сегменты на линии, просматривая линию в хеш-таблице, а затем проверяя, пересекаются ли два сегмента на линии, используя дерево интервалов в пространстве параметров на линии.