Obtener polígonos simples

Question

tengo un polígono C como a continuación:

C = 10  0 
    2  0 
    2  2 
    0  2 
    2  0 
    0  0 
    0 10 
    10 10 

donde la primera columna representa de coordenada x y la segunda columna es correspondiente a Y de la coordenada del polígono C. Como Puede ver en la imagen de arriba, este no es un simple polígono (este polígono contiene un agujero que está especificado por el color blanco), así que quiero obtener todos los subpolígonos simples de C que no contienen un agujero. En esta salida caso debe ser como la siguiente:

C1 = 0  2 
      2  0 
      0  0 

    C2 = 2  0 
      2  2 
      0  2 
      0 10 
     10 10 
     10  0 

donde C1 y C2 se corresponden con el pequeño triángulo rojo y grandes polígono rojo respectivamente.

¿El problema es cómo puedo generar estos subpolígonos?

Cualquier idea será apreciada.

Answer 1

En primer lugar, ¿podemos suponer que todos los puntos de intersección están presentes? Es fácil crear polígonos que se cruzan de formas interesantes. Sin embargo, usando algo como http://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm debería poder encontrar y agregar todas las intersecciones.

A continuación, haré la suposición simplificadora de que nunca se retrasa un segmento de línea. (Puede tratar ese caso patológico de varias maneras).

Con ese detalle cuidado, a continuación tenemos que ubicar todos los polígonos mínimos que se pueden definir por esos puntos, independientemente de que eventualmente se los cuente como dentro o fuera. (Para mayor comodidad, agregaremos un "punto" al infinito y contaremos el exterior como un polígono.) Para hacerlo, primero tomamos cada punto y enumeramos los puntos a los que se conecta directamente en el sentido contrario a las agujas del reloj. (Viajar paralelo al eje x es 0 grados, al eje y es 90 grados, el eje x negativo es 180 grados, y luego nos envolvemos a medida que avanzamos más abajo). Por lo tanto, para su ejemplo, obtendríamos algo de esta manera:

(0, 0): (2, 0), (0, 2) 
(2, 0): (10, 0), (2, 2), (0, 2), (0, 0) 
(10, 0): (10,10), (2, 0) 
(0, 2): (0, 0), (2, 0), (2, 2), (0,10) 
(2, 2): (2, 0), (0, 2) 
(0, 10): (0, 2), (10,10) 
(10, 10): (10, 0), (0,10) 

Ahora cada polígono simple se hará golpear cada punto entre dos de esos puntos, y viceversa podemos tomar uno de esos huecos (incluyendo la envoltura alrededor) y generar fácilmente el polígono asociado, por lo cada esquina hace el menor giro posible en el sentido contrario a las agujas del reloj (es decir, desde el punto en que llegamos al uno después, posiblemente envolviendo). Para cada segmento de línea, el polígono estará en el lado derecho. Sabemos que los tenemos todos cuando tenemos todos los puntos y brechas. Así que en el caso anterior comenzaríamos con un punto como (0, 0) y el siguiente punto (2, 0), a continuación, nos fijamos en (2, 0) y encontramos que (0, 0) es seguido por (10, 0), ir a (10, 0) y encuentra que es seguido por (2, 0)(10,10) y proceder de esta manera para trazar:

(0, 0), (2, 0), (10, 0), (10,10), (0,10), (0, 2), (0, 0) 

(. Tenga en cuenta, debido a la orientación de este trazó el área fuera)

Ahora empezamos con (0, 0) y el punto de partida alternativo (0, 2) y haga la misma operación para obtener:

(0, 0), (0, 2), (2, 0), (0, 0) 

(Este es el pequeño triángulo interior.)

Para (2, 0) aún no hemos viajado a (2, 2). Así que hagámoslo.

(2, 0), (2, 2), (0, 2), (0,10), (10,10), (10,0), (2, 0) 

(Este es el gran polígono irregular.)

Para (2, 0) aún no hemos viajado a (0, 2) por lo que vamos a hacer lo siguiente: (. Este es el pequeño triángulo blanco)

(2, 0), (0, 2), (2, 2), (2, 0) 

Y a continuación, una enumeración de todos los posibles segmentos de línea directa que nos gustaría viajar encontrará que los hemos cubierto todos. Entonces estos son nuestros polígonos. Ahora nos quedamos para descubrir qué hay dentro y qué está afuera. Hay un truco simple para eso. Encuentre un punto con el valor más bajo posible de y (si hay un empate, cualquiera lo hará). Por ejemplo, supongamos que elegimos (2, 0). Los puntos de conexión, dispuestos en sentido antihorario, fueron (10, 0), (2, 2), (0, 2), (0, 0). Esos son respectivamente exteriores, interiores, exteriores, interiores ... y, además, una vez que un borde de un polígono determinado se marca como fuera o dentro, todos sus bordes dirigidos son iguales. Así que fácilmente obtenemos:

outside: 
    - (10, 0), (2, 2), (0, 2), (0, 0) 
    - (2, 0), (0, 2), (2, 2), (2, 0) 

inside: 
    - (2, 0), (2, 2), (0, 2), (0,10), (10,10), (10, 0), (2, 0) 
    - (0, 0), (0, 2), (2, 0), (0, 0) 

Y su respuesta será sólo dentro de los polígonos.

(Pequeña optimización, no necesitamos dibujar los polígonos externos en absoluto. Podemos tomar el primer segmento de línea cuya orientación descubrimos, trazar un interior, luego ir a una de sus esquinas, identificar la orientación de los segmentos de línea que tocan esa esquina, y comienza a dibujar otros polígonos interiores. Si hacemos un seguimiento adecuado, eventualmente los obtendremos todos.)