Utilice un algoritmo de línea de barrido, haciendo uso del hecho de que un polígono rectilíneo se define por sus vértices.
Representa los vértices junto con el rectángulo al que pertenecen, es decir, algo así como (x, y, #rect). A este conjunto de puntos, agregue los puntos que resultan de las intersecciones de todos los bordes. Estos nuevos puntos tienen el formato (x, y, final), ya que sabemos que pertenecen al conjunto de puntos resultante.
Ahora:
- tipo todos los puntos de su valor de x
- utilizar una línea de barrido, a partir de los primeros coordenada x; para cada punto nuevo:
- si es un "punto de inicio", agréguelo a un conjunto temporal
T. Marcarlo como "final" si se trata de un punto del rectángulo A y entre coordenadas y de puntos del rectángulo B en T (o viceversa).
- si es un "punto final", y eliminar y su correspondiente punto de inicio de T.
Después de eso, todos los puntos que están marcados "final" denotan los vértices del polígono resultante.
Sea N el número total de puntos. Suponiendo además que probar si debemos marcar un punto como "final" toma tiempo O (log (n)) buscando T, todo este algoritmo está en O (N * log (N)).
Tenga en cuenta que la tarea de encontrar todas las intersecciones se puede incorporar al algoritmo anterior, ya que encontrar todas las intersecciones de manera eficiente es en sí mismo un algoritmo de línea de barrido. También tenga en cuenta que el conjunto resultante de puntos puede contener más de un polígono, lo que hace que sea un poco más difícil reconstruir los polígonos de solución fuera de los vértices "finales".
son los bordes del polígono rectilíneo y los rectángulos paralelos a los ejes? –
@Andre - sí - todas las líneas son paralelas – jedierikb
Como primer pensamiento, almacenar el polígono rectilíneo en un [árbol de segmentos] (http://en.wikipedia.org/wiki/Segment_tree) (para dos dimensiones) viene a mi mente. Suponiendo que los polígonos rectilíneos son los que no cambian y los rectángulos varían. –