Esiste un algoritmo standard efficiente per RASTER un poligono compresa la zona interna

Question

Eventuali duplicati:
Rasterizing a 2D polygon

ho bisogno di raster un poligono compresa la zona interna (determinare tutte le tessere di una griglia che si trova all'interno del poligono). Attualmente determino le tessere di confine usando un semplice Bresenham ma non ho modo fino ad ora di rasterizzare "l'interno" del poligono (che potrebbe essere anche concavo). Il mio approccio finora è quello di limitare l'intervallo di tessere al rettangolo includendo il poligono e quindi determinare per ogni centro di tessere se si trova all'interno o all'esterno utilizzando l'algoritmo di avvolgimento poligonale. Questo è inefficace perché implica il controllo di ogni segmento di contorno di poligono per ogni piastrella. Da un primo punto di vista dovrebbe esserci un approccio più rapido, ad es. qc. come l'avvolgimento usando il confine rasterizzato. Esiste un algoritmo standard che affronta questo problema e forse anche un'implementazione di libreria in C++?

Answer 1

Ci sono un bel po 'di risorse in rete, ad esempio:

• Efficient Polygon Fill Algorithm With C Code Sample;