Алгоритм поиска перекрывающихся отрезков

Question

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.

Какой самый быстрый способ найти отрезки, которые точно перекрываются?

Answer 1

Если каждая фигура представляет собой список ребер, то:

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 (края), и вы не будете делать лучше, чем это. хотя это решение может быть неудовлетворительным, в зависимости от того, что вы конкретно хотите сделать.

Answer 2

Учитывая N отрезков, в худшем случае может быть O (n ^ 2) пересечений. Вспомните случай, когда у вас есть N полигонов, где каждый полигон имеет одинаковое ребро. Если нет добавленного ограничения для предотвращения этой ситуации (которую вы не добавили), то лучшим алгоритмом, который вы можете придумать, будет O (N ^ 2) в худшем случае, поскольку просто перечисление пересечений - это O (N ^ 2).

На практике наиболее эффективными алгоритмами в вычислительной геометрии для нахождения пересечений отрезков являются алгоритмы стреловидности. Их наихудшее время выполнения для нахождения всех пересечений - O (k log n), где k - количество пересечений (это может быть N ^ 2, однако это редко бывает.)

Вы можете найти описание именно того алгоритма, который вам нужен, в Введение в алгоритмы Томаса Х. Кормена в разделе по вычислительной геометрии.

Answer 3

алгоритм twolfe18 выглядит хорошо. Однако может возникнуть дополнительное осложнение, если совпадающие ребра не описаны одинаково. В вашем примере P1 и P2 оба имеют ребро n2-n6. Но ребро P2 может быть описано сегментом n2-n7 (если n2-n6 и n6-n7 коллинеарны). Затем вам понадобится более сложный метод хеширования, чтобы определить, перекрываются ли два ребра. Вы можете определить, перекрываются ли два ребра, отображая сегменты на линии, просматривая линию в хеш-таблице, а затем проверяя, пересекаются ли два сегмента на линии, используя дерево интервалов в пространстве параметров на линии.