# Algorithm to assign edges to smallest possible polygons?

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.

Thank you!

• Just wondering, would a data structure like this be useful? (disclaimer: I haven't used it myself, so I can't give an advice.) Jan 21, 2015 at 2:32
• @rwong That does seem interesting, particularly the (D, φ, α) map given as an example. I'm wondering whether that can be added to at runtime, however -- it seems like if I were to add a new face to the map, the entire structure would have to be regenerated. That's not too much of a burden, but it might impact performance when a lot of areas need to be generated (such as when the player is initially exploring the city). Jan 21, 2015 at 2:43

## 1 Answer

See here for an algorithm. Consider each undirected edge as actually two edges, one going in each direction. Basically, if you order the edges around each vertex by angle, that will let you walk around each face in a clockwise direction, and you cross off each edge as you walk it. Then you pick and edge that hasn't been crossed off, and walk around starting with it.

However, since you're the one generating the graph, it might be easier just to generate the faces in the first place. When you get to a vertex on the edge of a map, take a left, and follow the outside edge by keeping taking the first right. Then branch off to the right and keep going around clockwise until you get back to the original vertex, taking care not to create a loop that doesn't include the original vertex. Then perhaps split the face once or twice.