Algoritmo para encontrar segmentos de línea superpuestos

Question

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

En el arte ASCII anterior, hay cuatro polígonos (P1, P2, P3, P4) con segmentos de línea que se superponen exactamente. Por ejemplo, el polígono P2 (formado por segmentos de línea entre los nodos n3, 10, 9, 12, 15, 14, 13, 8, 7, 6 y 2) y P1 (n1, 2, 5 y 6) se superponen en el segmento de línea entre n2 y n6.

¿Cuál es la forma más rápida de encontrar segmentos de línea que se superpongan exactamente?

Answer 1

Si cada forma es una lista de bordes, entonces:

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

es O (bordes), y no vas a hacerlo mejor que eso. Sin embargo, esta solución puede no ser satisfactoria dependiendo de lo que desee hacer específicamente.

Answer 2

Dados N segmentos de línea, en el peor de los casos puede haber intersecciones O (n ^ 2). Solo piense en el caso en el que tiene N polígonos donde cada polígono comparte el mismo borde. A menos que haya una restricción adicional para evitar que ocurra esta situación (que omitió agregar), el mejor algoritmo que se le ocurrirá será O (N ^ 2) en el peor de los casos, ya que simplemente enumerar las intersecciones es O (N ^ 2).

En la práctica, los algoritmos más eficientes en geometría computacional para encontrar intersecciones de segmentos de línea son los algoritmos de línea de barrido. Su peor caso para encontrar todas las intersecciones es O (k log n) donde k es el número de intersecciones (esto puede ser N ^ 2, sin embargo, rara vez lo es).

Puede encontrar una descripción del algoritmo que necesita exactamente en Introducción a los algoritmos de Thomas H Cormen en la sección sobre geometría computacional.

Answer 3

El algoritmo de twolfe18 se ve bien. Sin embargo, puede haber una complicación adicional si los bordes coincidentes no se describen de manera idéntica. En su ejemplo, P1 y P2 comparten el borde n2-n6. Pero el borde de P2 podría describirse en su lugar por el segmento n2-n7 (si n2-n6 y n6-n7 son colineales). Luego necesitará un método de hash más complicado para determinar si dos bordes se superponen. Puede saber si dos bordes se superponen al mapear segmentos en líneas, buscar la línea en una tabla hash, luego probar si dos segmentos en una línea se cruzan usando un árbol de intervalos en el espacio de parámetros en la línea.