I started this project shortly after I wrapped up my Object Aligned Bounding Box (OBB) implementation. I wanted to synthetically create a city layout (comprised solely of streets and buildings) that felt organic by combining several ideas: Poisson disk sampling, Voronoi diagrams, and OBB.

Firstly, Poisson disk sampling is used because it is an efficient way of generating random points throughout a two-dimensional space while still retaining control of the minimum amount of space between any two random points. If I just randomly selected points, there could figuratively be microscopic buildings if two points were too close together.

Once I have my points, I use the Bowyer–Watson algorithm to compute the Delaunay triangulation of my finite set of points. Using the triangulation, I can obtain my Voronoi diagram since it is the dual graph of the Delaunay triangulation. I then pass the Voronoi site as the polygon to be parceled by my OBB parceling implementation.

Lastly, I assign each polygon’s centroid a value using Simplex noise, and sort them in descending order. I get to control what proportion of the polygons are parceled, meaning the lowest value ones get discarded. This way, each render gets some interesting island shapes, lakes, peninsulas, etc.