Rasterizar un polígono 2D

Question

Necesito crear un mapa de bits binario a partir de un polígono 2D cerrado representado como una lista de puntos. ¿Podría indicarme algoritmos eficientes y suficientemente simples para hacer eso o, mejor aún, algún código C++?

¡Muchas gracias!

PD: Me gustaría evitar agregar una dependencia a mi proyecto. Sin embargo, si sugiere una biblioteca de código abierto, siempre puedo ver el código, por lo que también puede ser útil.

Answer 1

La frase de google mágica que desea es "regla de bobinado distinta de cero" o "incluso relleno de polígono impar".

Ver las entradas de Wikipedia para:

• non-zero winding rule
• even odd polygon fill

Ambos son muy fáciles de implementar y suficientemente rápido para la mayoría de los propósitos. Con algo de astucia, también pueden hacerse antialias.

Answer 2

• Triangulate your polygon
• Raster cada uno de los triángulos (si está utilizando una GPU entonces se lo puede hacer por usted en su lugar, es una operación primitiva de las GPU)
  • Si el triángulo no tiene un segmento que es paralelo al eje x, luego divídalo en dos triángulos con una línea que es paralela al eje xy pasa por su punto con la mediana-y
  • Ahora la tarea restante es dibujar un triángulo que tiene un segmento que es paralelo al eje x. Dicho triángulo tiene un segmento del lado izquierdo y un segmento del lado derecho
  • Iterate las líneas de exploración del triángulo (min-y a max-y). Para cada y, calcule los puntos de los segmentos izquierdo y derecho en esas líneas de exploración. Complete el segmento de escaneo estos dos puntos (un memset simple).

La complejidad es O (Área en píxeles)

Answer 3

Usted puede comprobar fuera de la rutina de llenado de polígonos en Pygame. Mire la función draw_fillpoly.

El algoritmo es bastante simple. Encuentra todas las posiciones que cada segmento cruza a lo largo del eje Y. Estas intersecciones se ordenan y luego horizontalmente llena cada par de intersecciones.

Esto manejará formas complejas e intersecantes, pero obviamente podrías aplastar este algoritmo con grandes cantidades de segmentos.

Answer 4

Para una robusta implimentation del "even-odd rule"

Ver Darel Rex Finley's Efficient Polygon Fill o Blender's version de ella.

Este es un método par/impar de llenado que auto soporta las líneas de intersección, sin necesidad de código complejo para detectar tales situaciones, y no depende de bobinado (el polígono puede ser invertida y dió los mismos resultados).

---

actualización, he hecho una versión optimizada del método de Darel Rex que evita bucle sobre todas las coordenadas para cada y píxeles.

Stand Alone implementaciones:

• C99.
• Rust (con pruebas).

Mientras aceleración probablemente será exponencial, de una prueba rápida, su alrededor 7.5x más rápido (11x al retirar round llamada), utilizando una parte arbitraria dibujado garabatos sobre una región 2540x1600, tu caso es distinto.