I have a programming problem relating to mesh generation for city grids. I've recently created a city grid generator and I've come as far as being able to reliably generate the road mesh for the grid my system spits out. However, now I am stuck with finding a method to generate the lots and spaces in between the roads. Eventually, I want the city grid to have elevation changes and for that, I need to be able to fill in the spaces between the roads.
I've looked into triangulation methods like Delauney Triangulation, but the output is unreliable (maybe due to the way I am using it). Here's another example that shows the problem (the black lines are the road mesh, the magenta ones are the Delauney output):
For the most part, the Delauney output follows the mesh when I present it with only the vertices that make up the intersections. However, sometimes, the Delauney triangles overlap the ones from the road mesh (like with the wide road in the center of the image). I am using a port of as2Delauney for Unity and I simply create a list of all the vertices that make up the intersections and then pass it to the Delauney function and I wonder if there is something I need to consider before passing a bunch of points and letting the function sort it out.
Are there any special considerations I need to be aware of when using Delauney for this type of triangulation, or are there any other methods that I could use to create the fill ins for the road mesh?
I've thought about building a function that tries to follow the intersections in clockwise or counterclockwise order until it loops back to the start, but that would lead to infinite loops as some roads are dead ends.
Right now I am not really sure what to look for as I lack terminology and google has yielded no results as to the methods that I could use to generate the fill ins for the road mesh (there is some good stuff on city generation, however not on the mesh part).
Does anyone have any experience with this?
Edit: This is how my system works:
Basically, I use an open list of lines to grow my network and I check the lines against a bunch of constraints. Then I go through each line and I generate intersections for each start and endpoint. So if the end/start is already in my list, I add the other point as a destination for the current intersection.
I end up with a list of custom objects that hold their own position vector and all the position vectors of the intersections it connects to. With this I then create the mesh points for the intersection by checking the cutting points of the lines that make up the sides of the roads, so I have those points at my disposal and i use them to create the triangles for my mesh.
Now I just need to know how to organize them to create the fill ins that span multiple intersections.