Algorithme pour rechercher les segments de ligne qui se chevauchent

Question

n4------------------n3--------------------n2--n1
|                    |                    |    |
|                    |                    | P1 |
|                    |                    |    |
|                    |                    n6--n5
|                    |                    |
|              n11--n10                   |
n17      P4     |    |         P2         |
|               | P3 |                    n7
|              n12---n9                   |
|               |                         n8
|               |                         |
n16------------n15---------n14------------n13

Dans la technique ASCII ci-dessus, il existe quatre polygones (P1, P2, P3, P4) avec des segments de ligne se chevauchant exactement. Par exemple, le polygone P2 (formé de segments de droite entre les nœuds n3, 10, 9, 12, 15, 14, 13, 8, 7, 6 et 2) et P1 (n1, 2, 5 et 6) se chevauchent à la segment de ligne entre n2 et n6.

Quel est le moyen le plus rapide de rechercher des segments de ligne qui se chevauchent exactement?

Answer 1

Si chaque forme est une liste d'arêtes, alors:

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

c'est O (bords), et tu ne vas pas faire mieux que ça. cette solution peut ne pas être satisfaisante en fonction de ce que vous voulez faire spécifiquement.

Answer 2

Soit N segments de ligne, dans le pire des cas, il peut y avoir O (n ^ 2) intersections. Pensons au cas où vous avez N polygones où chaque polygone partage le même bord. À moins d’une contrainte supplémentaire pour empêcher cette situation de se produire (que vous n’ayez pas ajouté), le meilleur algorithme que vous pouvez trouver sera O (N ^ 2) dans le pire des cas, car la liste des intersections est simplement O (N ^ 2).

En pratique, les algorithmes les plus efficaces en géométrie de calcul pour rechercher les intersections de segments de ligne sont les algorithmes de ligne balayée. Leur pire temps de parcours pour trouver toutes les intersections est O (k log n) où k est le nombre d'intersections (ce peut être N ^ 2, mais c'est rarement le cas.)

Vous trouverez une description exacte de l'algorithme dont vous avez besoin dans Introduction aux algorithmes de Thomas H Cormen dans la section relative à la géométrie informatique.

Answer 3

L'algorithme de twolfe18 semble bon. Cependant, il peut y avoir une complication supplémentaire si les arêtes correspondantes ne sont pas décrites de manière identique. Dans votre exemple, P1 et P2 partagent le même bord n2-n6. Mais le bord de P2 pourrait plutôt être décrit par le segment n2-n7 (si n2-n6 et n6-n7 sont colinéaires). Vous aurez ensuite besoin d'une méthode de hachage plus complexe pour déterminer si deux arêtes se chevauchent. Vous pouvez déterminer si deux arêtes se chevauchent en mappant des segments sur des lignes, en recherchant la ligne dans une table de hachage, puis en testant l'intersection de deux segments d'une ligne à l'aide d'un arbre d'intervalle dans l'espace des paramètres de la ligne.