python - Determinar el casco no convexo de la colección de segmentos de línea

algorithm language-agnostic

Question

Tengo un problema de geometría computacional que creo que debería tener una solución relativamente simple, pero no puedo entenderlo.

Necesito determinar el contorno no convexo de una región definida por varios segmentos de línea.

Soy consciente de varios algoritmos de casco no convexo (por ejemplo, formas alfa), pero no necesito un algoritmo completamente general, ya que los segmentos de línea definen una solución única en la mayoría de los casos.

Como @ Jean-FrançoisCorbett ha señalado, hay casos en los que hay múltiples soluciones. Claramente necesito pensar más acerca de mi definición.

Sin embargo, lo que estoy tratando de hacer es aplicar ingeniería inversa y usar un formato de archivo propietario para poder realizar análisis básicos sobre los datos que yo y otros recopilamos. El formato de archivo es bastante simple, pero determinar el algoritmo que utilizan para definir el límite es considerablemente más difícil.

Poner en muchos de los casos de borde que darían lugar a una solución no única hace que el software en cuestión se bloquee sin previo aviso o no pueda leer el archivo en silencio.

Por lo tanto, cuando hay múltiples soluciones, ya sea generar una de las soluciones aceptables o ser capaz de determinar que existen múltiples soluciones sería aceptable.

Definición del problema:

El contorno del polígono nunca debe cruzar ninguno de los segmentos y debe estar formado por líneas que unen todos los puntos finales de los segmentos. Todos los segmentos deben estar completamente dentro o a lo largo del límite del polígono. Ningún punto final se puede usar más de una vez en el esquema (omitiendo "cerrar" el polígono agregando el primer punto al final para las bibliotecas de software que requieren polígonos para cerrar).

En los casos en que haya varias soluciones que cumplan con este criterio, cualquiera de esas soluciones sería aceptable. (Sería bueno poder determinar cuándo la solución no es única, pero esto no es estrictamente necesario).

Ejemplos:

Como ejemplo, tengo algo en esta línea:

Y me gustaría delinear la siguiente área:

También debería funcionar para segmentos que no se intersectan. P.ej

Creo que (?) Hay una solución única en ambos casos, sujeto a los criterios descritos anteriormente. (Edición: No hay una solución única en general, como lo señaló @ Jean-FrançoisCorbett. Sin embargo, todavía estoy interesado en un algoritmo que genere una de las soluciones aceptables).

Casos de prueba

Para un caso de prueba, aquí está el código para generar las cifras anteriores. Estoy usando python aquí, pero la pregunta es agnóstica del lenguaje.

import matplotlib.pyplot as plt

def main():
    test1()
    test2()
    plt.show()

def test1():
    """Intersecting segments."""
    segments = [[(1, 1), (1, 3)],
                [(3.7, 1), (2, 4)],
                [(2, 0), (3.7, 3)],
                [(4, 0), (4, 4)],
                [(4.3, 1), (4.3, 3)],
                [(0, 2), (6, 3)]]

    desired_outline = [segments[0][0], segments[5][0], segments[0][1], 
                       segments[1][1], segments[2][1], segments[3][1],
                       segments[4][1], segments[5][1], segments[4][0],
                       segments[3][0], segments[1][0], segments[2][0],
                       segments[0][0]]

    plot(segments, desired_outline)

def test2():
    """Non-intersecting segments."""
    segments = [[(0, 1), (0, 3)],
                [(1, 0), (1, 4)],
                [(2, 1), (2, 3)],
                [(3, 0), (3, 4)]]

    desired_outline = [segments[0][0], segments[0][1], segments[1][1],
                       segments[2][1], segments[3][1], segments[3][0], 
                       segments[2][0], segments[1][0], segments[0][0]]

    plot(segments, desired_outline)


def plot(segments, desired_outline):
    fig, ax = plt.subplots()
    plot_segments(ax, segments)
    ax.set_title(''Segments'')

    fig, ax = plt.subplots()
    ax.fill(*zip(*desired_outline), facecolor=''gray'')
    plot_segments(ax, segments)
    ax.set_title(''Desired Outline'')

def plot_segments(ax, segments):
    for segment in segments:
        ax.plot(*zip(*segment), marker=''o'', linestyle=''-'')
    xmin, xmax, ymin, ymax = ax.axis()
    ax.axis([xmin - 0.5, xmax + 0.5, ymin - 0.5, ymax + 0.5])

if __name__ == ''__main__'':
    main()

¿Algunas ideas?

Estoy empezando a sospechar que el software cuyos resultados estoy tratando de reproducir utiliza un algoritmo de barrido radial en algún tipo de sistema de coordenadas "interno" (por ejemplo, un sistema de coordenadas con x-prime y y-prime escalado y girado a lo largo del ejes principales definidos por la dispersión de puntos. Esto hace que el problema sea más "circular"). Sin embargo, esto produce soluciones donde el contorno intersecta segmentos de línea en muchos casos. Es bastante fácil detectar esto y la fuerza bruta desde allí, pero seguramente hay una mejor manera?

Answer 1

1. Elija un punto de partida seguro. Puede ser, por ejemplo, el punto final con un máximo de x.
2. Marzo a lo largo del segmento de línea.
3. Al encontrar cualquier intersección, siempre gire a la izquierda y avance por este nuevo segmento.
4. Al encontrar un punto final, regístrelo. Ir a 2.
5. Deténgase cuando haya regresado a su punto de partida. Su lista de puntos finales registrados ahora conforma la lista ordenada de vértices de su casco cóncavo.

NB: esto fallará si hay un segmento de línea exterior "flotante" que no se interseca con ningún otro segmento de línea. Sin embargo, usted especifica que "las barras definen de forma única una solución", lo que descarta esta condición de falla. (Los segmentos periféricos hacen posible dos soluciones únicas).

EDITAR ... o, mejor dicho, los segmentos periféricos pueden hacer posibles dos soluciones únicas, dependiendo del diseño exacto. Prueba: A continuación se muestra un ejemplo en el que el segmento amarillo que agregué hace posible dos soluciones (líneas azules y grises horriblemente dibujadas a mano). Si el segmento amarillo estuviera orientado perpendicularmente a la forma en que se dibuja ahora, solo sería posible una solución. Parece que tu problema está mal definido.

EDITAR En realidad, esto también puede fallar si su colección de segmentos es "muy cóncava", es decir, si hay puntos finales ocultos en las esquinas reclusas de su pila de segmentos. En la siguiente figura, agregué un segmento negro. Mi algoritmo uniría ilegalmente su punto final a otro punto final (línea gris discontinua). Dejaré mi respuesta en caso de que otros estén inclinados a construir sobre ella.

EDITE después de reflexionar sobre esto: incluso en el caso "muy cóncavo", esta solución definitivamente le dará todos los puntos de su casco cóncavo en el orden correcto, pero pueden estar intercalados con puntos adicionales e inapropiados como el negro uno. Así que puede haber demasiados puntos.

La respuesta entonces es, por supuesto, hacer algunas podas. Sería una poda bastante complicada, especialmente si puedes tener múltiples "puntos reclusos" consecutivos como el negro, por lo que no tengo un algoritmo inteligente en mente. Pero incluso ciega, la fuerza bruta podría ser factible. Cada punto puede ser aceptado o rechazado (booleano), por lo que si tienes N puntos candidatos ordenados adecuadamente en tu casco cóncavo, entonces solo hay 2 ^ N posibilidades para verificar. Esto es mucho menos posibilidades que la fuerza bruta para su problema original de permutaciones, que tendrían SUM of (n!/(nk)!) for k=1:(n-1) posibilidades (perdónen mi notación). Así que este algoritmo reduce su problema significativamente.

Creo que este es el camino a seguir.

Answer 2

No es una idea totalmente concreta, pero de todos modos: suponga que comenzó con el algoritmo de barrido circular para un casco convexo (donde clasifica y luego procesa los puntos por su ángulo desde un punto central). Si todos los puntos terminan en este casco, ya está. Si no, tienes que "apretar" el casco para incluir estos puntos. Cada uno de estos puntos fue a la vez candidatos para el casco convexo, y se eliminaron porque rompieron la convexidad. A veces (como con el punto morado superior en el primer ejemplo), podemos simplemente dejarlos allí. Donde no podemos, porque el nuevo segmento del casco cruza un segmento (como ir del fondo verde al fondo morado en el primer ejemplo, asumiendo que el punto de fondo del agua se procesó antes que el verde), la solución es un poco más complicada (y la parte que no he desarrollado, y es la parte a la que se alude en la última edición de la pregunta).