Aree rettangolari di unione (unione booleana) con precisione intera

Question

Dato un numero qualsiasi di rettangoli di intersezione, disgiunti e toccanti, come trovare le polilinee (multiple) del profilo? I rettangoli sono definiti in coordinate pixel in modo da avere una precisione intera, ma possono essere migliaia di unità di grandi dimensioni.

Ho davvero bisogno coordinate numeriche per i contorni, fondendo regioni GDI non farà. So che posso semplificare il problema creando una regione GDI e chiamando GetRegionScans, ma ancora non risolverà il problema.

Questo fa parte dell'interfaccia utente in tempo reale, quindi l'algoritmo deve essere ragionevolmente veloce (non indovinerò mai più di una dozzina di scatole, forse un centinaio).

Lo sto facendo in C#, ma poiché questa è una domanda algoritmica, non mi interessa davvero il linguaggio. Qualche idea benvenuta.

Answer 1

ho idea se questo soddisfa le tue esigenze di prestazioni, ma dovrebbe funzionare:

1. Inizia con un insieme vuoto di rettangoli.
2. Aggiungere ciascun rettangolo al set. Se un rettangolo si sovrappone a un rettangolo esistente, dividi i rettangoli in tutti i rettangoli necessari, in modo che nessun rettangolo si sovrapponga a un altro.
3. Aggiungi i quattro lati di ciascun rettangolo non sovrapposto a un insieme di linee.
4. Rimuovi tutte le linee che non sono univoche.

Il set risultante contiene tutte le linee che compongono il contorno.

---