I'm designing a procedural city generator, and the first step of the generation process is the creation of city streets. These streets extend out in a straight line to a point, then they can either branch, rotate, or continue in the same direction. If a street would hit another street, it can either stop growing or attach to the nearest junction.
I've been thinking of the junctions as vertices and the streets as edges. From this, I should be able to break the network up into a collection of the smallest possible polygons -- i.e., a space enclosed on all sides by streets.
So long as a street has 2 junctions on either side, I would like to have that as the edge of a polygon. I remove streets that are "dead ends" (vertices that only have one edge attaching to them) from consideration before processing, so they're not an issue.
So given a collection of vertices and edges, what is a good way to break them up into the smallest possible polygons? It doesn't matter if the polygon is convex or concave, as it would primarily be used as a way to load in bits of the city and mark an area as loaded or unloaded and selectively choose bits of the city for simulation. It's also important that I am able to create new areas at runtime to allow for a semi-infinite map.
You'll have to pardon my hastily-thrown-together image, but say I have a network that looks like this:
I'd like the output to produce something like this:
I've tried to accomplish this on my own, but I had a few issues (mainly when it came to determining if an edge would be "shared" by 2 polygons -- in my above example, the edge F is shared by AEF and FGMOL, while A only belongs to AEF).
Since this seems like a problem that would be common in the graphics industry, I figured there should be a readily-accessible algorithm for it. I looked at Andrew's Monotone Chain Algorithm, but it seems like it does the opposite (returning the LARGEST polygon from a set of points).
It is entirely possible that I'm looking at this in completely the wrong way, so any help would be appreciated. My apologies if I posted this to the wrong section -- I tried posting this question to StackOverflow, and they redirected me here.