Algoritmo para reducir la imagen a rectángulos?

Question

Estoy intentando crear mapas de bits bastante grandes en una aplicación C# (6000x6000, aunque la mayoría es transparente) y necesito dibujarlos en una API de salida específica que solo admite dibujar rectángulos.

Ahora, me pregunto si alguien tiene un algoritmo para reducir un mapa de bits a una serie de rectángulos rellenos de mapas de bits de colores similares; ya que dibujar todo como un rectángulo 1x1 es demasiado lento para este propósito. Por ejemplo, un círculo debe reducirse a un gran rectángulo central, mientras que el resto del círculo se reduce a rectángulos eficientes. El algoritmo ni siquiera necesita ser tan rápido, ya que la mayor parte del tiempo que se toma con mi método de píxel único es mediante el bucle a través de cada rectángulo en la API.

Answer 1

Parece que necesitaría la estructura clásica QuadTree. Consulte este enlace para obtener una buena explicación de cómo usaría un quadtree para cuantizar una imagen en rectángulos.

Aquí hay una buena referencia en CodeProject que proporciona una implementación sencilla de muestra que puede modificar según sus necesidades.

Answer 2

Un algoritmo simple de implementar sería dibujar rectángulos 1xN.

Comience en la línea 0 y encuentre el primer píxel no en blanco. Continúe recorriendo píxeles hasta que cambie el color de los píxeles que está mirando. Ahora dibuja esa serie de píxeles del mismo color como un rectángulo 1xN.

Si sus imágenes reales tienen grandes regiones uniformes, esto podría ser "lo suficientemente bueno". Dependiendo de cómo se vean las imágenes, dibujar líneas verticales podría ser mejor.

si estoy haciendo la derecha matemáticas, usando este método, un círculo de radio 100 píxeles usarían 200 "líneas" para dibujar, en lugar de 30.000 píxeles si se hace un píxel a la vez. Me parece que la descomposición de un árbol cuádruple usaría al menos 1000 rectángulos o más para ese círculo, si tienes suerte con la caída de los cuadrantes.