Lo Oosterwal describe es un caso especial de la descomposición trapezoidal, un bien comprendido en la primitiva computati geometría onal típicamente utilizada para la ubicación de puntos en una subdivisión planar. Se puede implementar en el tiempo O (n log n) con una constante razonable.
Cuando los rectángulos están en posición general, devolverá una "rectificación" con # rectángulos verdes = 3 * # rectángulos azules + 1, y esto es óptimo. La vecindad en forma de L de cada esquina azul debe ser cortada en una dirección u otra por un segmento verde (posición general: no podemos usar el mismo segmento para dos rectángulos azules), entonces para cada rectángulo azul, agregamos
4 bordes verdes
8 bordes verdes y 4 vértices (4 nuevos bordes más 4 subdivididos), disminuyendo el número de componentes conectados por 1 en el proceso. El resultado por la fórmula poliédrica es 3 caras más (rectángulos):
V - E + F = 1 + # componentes conectados.
Ejemplo:
abc
0+-----------+
1| |
2| +--+ |
3| |R | +-+ |
4| +--+ |S| |
5| | | |
6| +--+ | | |
7| |T | +-+ |
8| +--+ |
9+-----------+
Estamos corriendo una línea de barrido de arriba a abajo. Los eventos son
# (y, whichside, xmin, xmax)
(2, top, 3, 6) # R
(3, top, 8, a) # S
(4, bot, 3, 6) # R
(6, top, 2, 5) # T
(7, bot, 8, a) # S
(8, bot, 2, 5) # T
Configuramos un árbol binario de búsqueda ordenado por x que contiene los rectángulos verdes parcialmente construidos. Lo escribiré como una lista.
# (xmin, xmax, ymin)
(0, c, 0)
Ahora comenzamos a procesar eventos. Primero es (2, arriba, 3, 6). Encontramos que está anidado dentro del único rectángulo verde hasta el momento, (xmin = 0, xmax = c, ymin = 0, ymax = 2). (El intervalo de azul siempre anida siempre y cuando los rectángulos azules no se cruzan.) Empezamos dos nuevos rectángulos verdes, uno a cada lado del rectángulo azul, y el árbol de búsqueda contiene
(0, 3, 2) (6, c, 2)
Ahora que el proceso (3, arriba, 8, a). El intervalo (8, a) nidos dentro (6, c), por lo que terminar otro rectángulo (xmin = 6, xmax = c, ymin = 2, ymax = 3) y empezar a dos más:
(0, 3, 2) (6, 8, 3) (a, c, 3)
Ahora procesamos (4, bot, 3, 6). Esto termina los rectángulos verdes a su izquierda y derecha, (xmin = 0, xmax = 3, ymin = 2, ymax = 4) y (xmin = 6, xmax = 8, ymin = 3, ymax = 4). El árbol de búsqueda es
(0, 8, 4) (a, c, 3)
Creo que las cosas deberían estar claras en este punto.Aquí está el rectangulation final:
abc
0+-----------+
1| |
2+--+--+-----|
3| |R |-+-+-|
4+--+--+-|S| |
5| | | |
6+-+--+--+ | |
7| |T +--+-+-+
8+-+--+------+
9+-----------+
Una nota sobre el manejo de degeneraciones: eventos fondo se coloca antes de los eventos más importantes con la misma coordenada, y suprimen rectángulos con zona cero. Todavía habrá rectángulos "innecesarios" en general, que un procesador de eventos más sofisticado podría evitar (al manejar todos los eventos en una coordenada y dada a la vez).
parece que el algoritmo de su ejemplo explora de arriba abajo buscando obstrucciones. Cuando encuentra uno, completa el rectángulo de relleno actual e inicia dos nuevos. Cuando encuentra un final a una obstrucción, completa los rectángulos de relleno adyacentes actuales e inicia uno nuevo de mayor tamaño. – oosterwal
Esto podría estar relacionado con la pregunta más general de, dada una colección de rectángulos, encontrar el menor número de rectángulos que cubran precisamente esos rectángulos. No estoy seguro de qué algoritmos existen para ese problema, pero si hay una forma eficiente de resolver ese problema, debería darle una solución eficiente a este problema. – templatetypedef