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

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

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 en 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 recostackmos. El formato del 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 varias soluciones, ya sea generando una de las soluciones aceptables o pudiendo determinar que existen soluciones múltiples, 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 (ignorando “cerrar” el polígono agregando el primer punto al final para las bibliotecas de software que requieren que los polígonos se cierren).

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:

A modo de ejemplo, tengo algo en este sentido: Segmentos que definen el área

Y me gustaría delinear la siguiente área: Esquema deseado

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

introduzca la descripción de la imagen aquíintroduzca la descripción de la imagen aquí

Creo que (?) Hay una solución única en ambos casos, sujeto al esquema de criterios anterior. (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 intentando 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 Principales ejes definidos por la extensión de los puntos. Esto hace que el problema sea más “circular”. Sin embargo, esto produce soluciones en las que el contorno intersecta segmentos de línea en muchos casos. Es bastante fácil detectar esto y la fuerza bruta desde allí, pero ¿hay alguna manera mejor?

  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, grabarlo. Goto 2.
  5. Pare cuando haya regresado a su punto de partida. Su lista de puntos finales grabados ahora constituye la lista ordenada de vértices de su casco cóncavo.

NB: esto fallará si hay un segmento de línea exterior “flotante libre” 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 distintas.)

EDITAR … o, mejor dicho, los segmentos periféricos pueden hacer posibles dos soluciones distintas, 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 perpendicular a la forma en que se dibuja ahora, solo sería posible una solución. Parece que su problema está mal definido.

introduzca la descripción de la imagen aquí

EDITAR En realidad, esto también puede fallar si su colección de segmentos es “muy cóncava”, es decir, si hay puntos finales escondidos en las esquinas reclusas de su stack de segmentos. En la figura de abajo 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 pensarlo un poco más: 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 es, por supuesto, hacer algunas podas. Sería una poda bastante complicada, especialmente si puedes tener “puntos de reclusión” múltiples y consecutivos como el negro, así que no tengo en mente un algoritmo inteligente. Pero incluso ciega, la fuerza bruta podría ser factible. Cada punto puede ser aceptado o rechazado (booleano), por lo que si tiene N puntos candidatos correctamente ordenados en su casco cóncavo, solo hay 2 ^ N posibilidades para verificar. Esta es una manera, menos posibilidades que la fuerza bruta para su problema original de permutaciones, que tendría SUM of (n!/(nk)!) for k=1:(n-1) posibilidades (perdone mi notación). Así que este algoritmo reduce su problema significativamente.

Creo que este es el camino a seguir.

introduzca la descripción de la imagen aquí

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 adentro. Donde no podemos, porque el nuevo segmento del casco cruza un segmento (como va del verde inferior al morado inferior 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).