Sto progettando un generatore di città procedurale e il primo passo del processo di generazione è la creazione di strade cittadine. Queste strade si estendono in linea retta fino a un punto, quindi possono diramarsi, ruotare o continuare nella stessa direzione. Se una strada colpisce un'altra strada, può smettere di crescere o attaccarsi allo svincolo più vicino.
Ho pensato ai raccordi come ai vertici e alle strade come bordi. Da questo, dovrei essere in grado di suddividere la rete in una raccolta dei più piccoli poligoni possibili, ad esempio uno spazio racchiuso da tutte le parti lungo le strade.
Finché una strada ha 2 svincoli su entrambi i lati, mi piacerebbe averlo come margine di un poligono. Rimuovo le strade che sono "vicoli ciechi" (i vertici che hanno solo un lato che li attacca) dalla considerazione prima dell'elaborazione, quindi non rappresentano un problema.
Quindi, dato un insieme di vertici e spigoli, qual è un buon modo per scomporli nei poligoni più piccoli possibili? Non importa se il poligono è convesso o concavo, poiché dovrebbe essere usato principalmente come un modo per caricare in bit della città e contrassegnare un'area come caricata o scaricata e scegliere selettivamente i bit della città per la simulazione. È anche importante che io sia in grado di creare nuove aree in fase di esecuzione per consentire una mappa semi-infinita.
Dovrai perdonare la mia immagine frettolosamente gettata insieme, ma diciamo che ho una rete che assomiglia a questa: 
Mipiacerebbechel'outputproducessequalcosadelgenere:
Ho provato a realizzare questo da solo, ma ho avuto alcuni problemi (principalmente quando si trattava di determinare se un edge sarebbe stato "condiviso" da 2 poligoni - nel mio esempio precedente, il bordo F è condiviso da AEF e FGMOL, mentre A solo appartiene ad AEF).
Poiché questo sembra un problema che sarebbe comune nel settore della grafica, ho pensato che ci sarebbe stato un algoritmo facilmente accessibile per questo. Ho esaminato l'algoritmo della catena monotono di Andrew , ma sembra che faccia l'opposto (restituendo il PIÙ GRANDE poligono da un insieme di punti).
È del tutto possibile che io stia guardando questo in modo completamente sbagliato, quindi qualsiasi aiuto sarebbe apprezzato. Le mie scuse se ho postato questo nella sezione sbagliata - Ho provato a postare questa domanda a StackOverflow, e mi hanno reindirizzato qui.
Grazie!