Come scoprire se una tessera è coperta da un poligono?

Question

Come scoprire se una tessera è coperta da un poligono?

Naviga le tue risposte

#1 da (2 voti)

2

Dato un poligono (intersecante), mi piacerebbe scoprire quali tessere sono coperte dal poligono.

Esempio :

Dettagli:

Letesseresonoquadrate,1unitàlarga/alta
Lagrigliainiziain(0,0)
Gliangolidelpoligonopossonoaverecoordinateinvirgolamobile(ades.3.433,5.234)
Ingenerale,unlatodelpoligonopotrebbeesserelungo1000-10000riquadri

Hoprovatoaripeteretutteletessereecontrollaresesononelpoligono,tuttavia,datochedevoripeterepiùdi10000²dipiastrelle,civuoleunpo'ditempo.

Sonointeressatoaunasoluzionechemiconsentadirispondererapidamente"Tegola (x, y) coperta dal poligono?" senza ricalcolare tutto da zero per ogni domanda.

Qualunque soluzione / approccio / pseudo-codice / suggerimento che mi porta a una soluzione corretta sarà accettata.

geometry map

posta Ted 15.05.2014 - 08:33

fonte

1 risposta

Leggi altre domande sui tag geometry map

Test di composizioni complesse Operatore binario di sottoscrizione / assegnazione in C ++

score 2 · Answer 1

Sembra che tu voglia eseguire la rasterizzazione del poligono, in cui i tuoi "pixel" sono i tuoi elementi di griglia.

Un approccio che vorrei provare (poiché è probabile che troverai algoritmi pronti all'uso per farlo), è di utilizzare un rasterizzatore in memoria (ad esempio Cairo), regolando il filtro (e ovviamente le coordinate del tuo poligoni in modo che siano espressi in unità di griglia).

In alternativa puoi eseguire il rollover utilizzando gli algoritmi esistenti. Ad esempio:

dividi il poligono nelle sue parti convesse
disegna il contorno di ogni poligono (più preciso: il contorno di ciascuna convessa) con l'algoritmo di riga di Bresenham
riempi i buchi (che dovrebbe essere facile dato che stai lavorando con poligoni convessi)

Per il passaggio 2, se vuoi coprire tutti i pixel, vedi questa domanda SO .