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

 
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.Алгоритм поиска перекрывающихся сегментов линий

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

источник

2009-09-15 magneticMonster

Описание вашего примера неверно. P1 имеет узлы 1,2,5,6, а P2 имеет узлы 2,3,10,9,12,15,14,13,8,7,6. – perimosocordiae

@perimosocordiae Спасибо. Полагаю, я исправил описание. – magneticMonster

Прежде чем ответить, вы должны указать, как сохраняются ваши фигуры. Это влияет на ответ. – twolfe18

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

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

источник

2009-09-15 03:52:52 twolfe18

+1. В качестве дополнительной заметки, если фигура хранится как список точек, вы можете просто пройти по точкам попарно и иметь ребро, представленное сортированной парой (p1, p2), где p1 < p2 => p1.x

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

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

Вы можете найти описание именно алгоритма вам нужно в Introduction to algorithms by Thomas H Cormen в разделе по вычислительной геометрии.

источник

2009-09-15 05:21:23 ldog

Как вы получаете O (n^2)? если у вас было n форм, каждый с m ребрами, это было бы O (n * m). вы явно не можете сделать этого лучше, потому что вы должны проверять каждый край. мой алгоритм O (n * m). также, вы не ответили на вопрос. – twolfe18

Я сказал * линейные сегменты *. Пример, который я дал с полигонами, был просто иллюстрацией.Алгоритм O (n^2), который вы дали, является очевидным и тривиальным. На практике алгоритмы sweepline значительно отличаются от тривиальных алгоритмов. – ldog

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

источник

2009-10-11 03:41:46

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

ответ

Смежные вопросы