Merge (unión booleana) regiones rectangulares con precisión de enteros

Question

Dada la cantidad de intersecciones, disyuntos y rectángulos en contacto, ¿cómo encontrar las polilíneas (múltiples)? Los rectángulos se definen en coordenadas de píxeles para que tengan una precisión entera, pero pueden ser miles de unidades de gran tamaño.

que realmente necesitan coordenadas numéricas para los contornos, la fusión de regiones GDI no es suficiente. Sé que puedo simplificar el problema creando una región GDI y llamando a GetRegionScans, pero todavía no resolverá el problema.

Esto es parte de la IU en tiempo real, por lo que el algoritmo debe ser razonablemente rápido (supongo que nunca más de una docena de cajas, quizás cien).

Estoy haciendo esto en C#, pero como esta es una pregunta algorítmica, realmente no me importa el lenguaje. Cualquier idea más bienvenida.

Answer 1

tengo ni idea de si esto satisface los requisitos de rendimiento, pero debería funcionar:

1. de inicio con un conjunto vacío de rectángulos.
2. Agregue cada rectángulo al conjunto. Si un rectángulo se superpone a un rectángulo existente, divida los rectángulos en tantos rectángulos como sea necesario, de modo que ningún rectángulo se superponga con otro.
3. Agregue los cuatro lados de cada rectángulo no superpuesto a un conjunto de líneas.
4. Elimina todas las líneas que no son únicas.

El conjunto resultante contiene todas las líneas que componen el contorno.

---