riempire un poligono con minor quantità di rettangoli

Question

sto cercando di rendere i poligoni, ma possono essere resi solo con rettangoli asse-allineati. Quindi, sto cercando un algoritmo che possa riempire fondamentalmente un poligono usando la quantità di rettangoli possibile di minimo. Se aiuta a ridurre la quantità, i rettangoli possono sovrapporsi l'un l'altro.

ho già implementato this fill algorithm, che basta per lo più. La rovina è che limita i rettangoli per ogni riga di pixel. Alla fine voglio ridurre la quantità di rettangoli il più possibile.

Answer 1

rappresentazione Pixel del poligono è uguale a poligono rettilineo ed è possibile partizionare abbastanza veloce. Vedi la risposta a questo question.

Answer 2

Rimuovere questa restrizione (che ogni rettangolo ha un'altezza di un pixel) aiuta in alcuni casi speciali quando il poligono è composto da rettangoli grandi, ma non del tutto nel caso generale.

ne dite di questo: utilizzare tale algoritmo, ma si estendono ogni rettangolo verso l'alto e verso il basso per quanto è possibile, e quando tutti i rettangoli sono in atto, eliminare quelle ridondanti.

C'è ancora un po 'di spazio per migliorare, in quanto il ordine in cui si eliminano i rettangoli ridondanti potrebbero materia in alcuni casi molto rari, ma onestamente non credo che valga la pena di preoccuparsi per una soluzione pratica .