After the generation of the hydrology, the next key step in this terrain generation process is the division of the land into cells per §5.1 of Geneveaux et al. The edges of these cells are important, as many of them form elevated ridges that divide adjacent rivers and watersheds. With the hydrology, these edges define the overall shape of the terrain. The function TerrainHoneycombFunctions.initializeTerrainHoneycomb() partitions the land into cells centered around the river nodes, and then processes the edges of these cells, gathering important details about them, as well as truncating them according to the shoreline.

Voronoi partition

The first step is to partition the land into cells. This is done using the Scipy library.

The list of input points is assembled based on the full list of river nodes from the TerrainHydrology. Since the order is unchanged, the index of an input point corresponds to the index of a river node, and therefore the index of an input point corresponds to the ID of a river node. Note that it is necessary to add 4 extra points at the corners of the whole area to ensure that there aren't cell edges that go out to infinity.

The Voronoi represents the resulting partition with a set of lists. It is important to understand how it represents the partition, as many elements of the logic refer to it. Some of these lists contain points, some of them contain indexes to things in other lists, and some of them have lists that contain indexes to things in other lists. See the Scipy documentation for reference, and maybe try it yourself, as it is confusing.

Processing edges

The next step is to process all the cells and their edges. This is done cell-by cell.

As an example, consider the following cell from a Voronoi partition:

Chaining the edges together.

First, the edges of a cell, and their vertices, are put in order. This allows them to be thought of as being chained together, as the first vertex of each edge is the last vertex of the previous edge. This makes the subsequent logic a bit easier.

To do this, a single ridge is picked. The order of vertices in ridge_vertices is arranged to ensure that whichever vertex is more clockwise comes first. Then, the other edges are chained together. The edge that comes next is whichever one contains the last vertex of this edge. Its vertices are arranged so that its first vertex is the last vertex of this edge. This is repeated for all of the cell's edges.

Processing edges

Now that the edges of the cell have been put in order, it is time to process them. This is done with a stack of recursive functions. Each function will examine an edge, process it if it can, and decide which function to call next.

processRidge()

This is the function that is called first. At least the first vertex must be on land, which is why orderEdges() ensures that the list of edges meets this condition.

This function may also be called by itself, or by terminateShoreAndStartRidge(). Note that if a previous edge has already been processed, it doesn't matter how that edge was processed---whether it was a shore segment, or a previous ridge---this function can simply use the second vertex of the previous edge as the starting point for this one. This is why it is important to chain the edges together first.

If the edge that it has been asked to process is situated entirely on land, then it will process the edge itself. Then it will call processRidge() to process the next edge.

If the edge that it has been asked to process is not situated entirely on land---that is, its second vertex is in the sea, then it will not process the edge itself. Instead, it will call terminateRidgeAndStartShore() to process the edge.

terminateRidgeAndStartShore()

If this function has been called, it's because the current edge intersects with the shoreline, that is, the first vertex is on land and the second vertex is in the sea. This function will find the intersection between this edge and the shoreline and create an edge that runs from the first vertex up to that intersection. The second vertex will not be used, since it is in the sea. Rather, the intersection with the shoreline will become this edge's second Q.

Since this edge runs into the sea, the cell is now bounded by the shoreline, so now we will begin to process the shoreline instead of the Voronoi cell edges. Having processed this edge up to the sea, this function will now call processShoreSegment() to continue.

processShoreSegment()

If this function has been called, it is because the Voronoi polygon has run into the sea. This function will add edges based on shoreline segments until it finds out where the shoreline intersects with the Voronoi polygon again.

First, it checks to see if this shoreline segment intersects with any of the Voronoi edges that haven't been processed yet. If it doesn't, then the function processes this shore segment as an edge.

This function must check every single one of the remaining Voronoi edges because one or more of the edges may be entirely on the sea, and those edges must be skipped over.

It doesn't have to worry about whether or not this edge spans an entire shore segment, or if it started out as an intersection between a Voronoi edge and a shore segment. Its first vertex is simply the previous edge's second vertex, so it just uses that, regardless of how it was created.

If this shore segment does intersect with a Voronoi edge, then this function will not process the current shore segment, and will call terminateShoreAndStartRidge().

Note that this function will never be called last. Every single cell will have at least one vertex on land. This means that even if only one vertex is on land, then there are 2 Voronoi edges that intersect with the shore.

terminateShoreAndStartRidge()

If this function is called, it's because the current shore segment intersects with a Voronoi edge.

This function will create an Edge that goes from the end of the previous edge to the intersection of this shore segment with the Voronoi edge that it intersects. It will not process the next edge.

As a shoreline winds through a cell, it may cut out entire Voronoi edges. terminateShoreAndStartRidge() will ensure that these edges are skipped by removing them from the list of edges that haven't been processed yet.

It will then call processRidge() to process the next ridge.

Examples

Regular cell

Consider the most perfectly regular situation possible. All of the Voronoi vertices are on land, making the processing of this cell a simple matter. Moreover, suppose that this is the first cell to be processed.

In this situation, we can see 7 river nodes. This diagram is centered around node 64. It is the parent of node 4, and it has 2 upstream nodes: 13 and 65.

As it happens, the Voronoi cell around this node is an almost-perfect hexagon. The following is a subset of the Scipy Voronoi object containing data relevant to this cell. Note that dictionaries are used instead of lists for convenience:

vor.ridge_points = { 83: [64,4], 93: [64,6], 78: [64,65], 40: [64,20], 20: [64,13], 32: [64,95] }

vor.vertices = { 16: [61.4,-98.4], 57: [81.1,-127.2], 52: [122.0,-126.7], 46: [140.5,-97.6], 23: [119.1,-65.0], 31: [83.8,-63.9] }
vor.ridge_vertices = { 83: [57, 16], 93: [52, 57], 78: [52, 46], 40: [46, 23], 20: [31, 23], 32: [31, 16] }

Before starting to process cells, the point_ridges dictionary will have been created. Here is the subset of that dictionary that is relevant for this cell:

point_ridges = { 64: [32, 78, 40, 20, 93, 83] }

When this cell is processed, those edges will be re-arranged. Then their vertices will be re-arranged as well.

point_ridges = { 64: [32, 83, 93, 78, 40, 20] }
vor.ridge_vertices = { 83: [16, 57], 93: [57, 52], 78: [52, 46], 40: [46, 23], 20: [23, 31], 32: [31, 16] }

Then processing of the ridges can begin. processRidge() is called. It is the (ordered) indices of its Voronoi edges.

Edge 32 is first. Before doing anything, processRidge() checks to see if both points are on land. In this case, both points are on land, so it proceeds to process the ridge itself.

Since processRidge() can be called first, it does not assume that a previous edge has been created. So it checks to see if a previous edge has been processed. Sure enough, no previous edge has been processed. So it creates both Qs for this edge. It also determines whether or not this edge is transected by a river. It files the new edge away both in a list for the cell, and for the greater dictionary of created edges.

Finally, removes edge 32 from the edgesLeft list, and calls itself.

The next processRidge() processes edge 83. It makes very similar findings, but there are 2 differences. First, it finds that the previous edge, edge 32, has already been processed. So edge 83's first Q will be the second Q of edge 32. That is, edge 32 and edge 83 will both share the Q that is created from ridge vertex 16. Also, edge 83 is transected by a river.

Finally, it will remove edge 83 from edgesLeft and call itself again.

This will repeat until edge 20 is processed. When processRidge() checks to see whether or not vertex 31 has been processed, it will find that it already exists in the createdQs dictionary. Instead of creating another Q for the same vertex, it will use the existing one.

Cell that is transected by a shore segment

Consider a less simple example. In this case, the hydrology is almost the same, except that node 4 doesn't exist. Instead, node 64 is on the shore. All of the Voronoi data structures (ridge_points, vertices, ridge_vertices) are the same as before. This means that the process of re-arranging edges and vertices is the same as before.

point_ridges = { 64: [32, 83, 93, 78, 40, 20] }
vor.ridge_vertices = { 83: [16, 57], 93: [57, 52], 78: [52, 46], 40: [46, 23], 20: [23, 31], 32: [31, 16] }

As before, edge 32 is first. However, it sees that the second vertex, vertex 16, is not on land. Therefore, this edge intersects with the shore and runs into the sea. So it does nothing, calls terminateRidgeAndStartShore() instead.

terminateRidgeAndStartShore() first checks to see if the first vertex has been created. Since this is the first edge to be processed, it may have to do that.

Then it has to investigate the intersection with the shore. First it finds which shore segment it intersects with. In this case, it is the segment from 15 to 16 in the ShoreModel. A helper function does this. Then it finds the position of the intersection. This position becomes the location of the second vertex, instead of the actual second vertex as found by the Scipy Voronoi algorithm. Thus, the edge is 'terminated' at the shore.

From now on the we will follow the shoreline instead of the cell ridges. terminateRidgeAndStartShore() now removes edge 32 from the list and calls processShoreSegment().

However, the first thing that processShoreSegment() does is see if this shore segment intersects with any of the cell edges. It finds that it intersects with edge 93. So there's nothing for it to do. Just like the Voronoi edge, this shore segment must be terminated. So it calls terminateShoreAndStartRidge().

terminateShoreAndStartRidge() first investigates the intersection between this shore segment and edge 93. it creates an Edge for the shore segment, starting end of the previously processed edge, which happens to be edge 32, and terminates it at the intersection with edge 93. Then it calls processRidge().

processRidge() picks up where terminateShoreAndStartRidge() left off. It sees that a previous edge has been processed, so it uses the second Q from the previous edge as the first Q of this edge. Then, the rest of the cell is processed, as in the regular cell.

Cell that encloses multiple shore segments

Consider another cell on the coast, with exactly the same shape as the last one, but with instead of one shore segment transecting the whole cell, multiple shore segments are enclosed within the cell.

Just like the previous example, processRidge() will examine edge 32 and call terminateRidgeAndStartShore(). terminateRidgeAndStartShore() will process ridge 32, terminating it at the shoreline, and then call processShoreSegment().

This time, however, processShoreSegment() will not immediately call terminateShoreAndStartRidge(). It will see that segment (15,16) does not intersect any other edges, and will process that segment normally. Then, it will call itself to process the next shore segment.

Starting from the previously processed segment, processShoreSegment() will process segment (16,17). Then it will call itself to process segment (17,18). But segment (17,18) intersects Voronoi edge 93. So it will call terminateShoreAndStartRidge().

terminateShoreAndStartRidge() will process segment (17,18) up to its intersection with edge 93. However, before moving on, it will not only remove edge 93 from the list of edges that not been processed, it will also remove any edges that come before it. In this case, edge 83 must be skipped, as it is not part of the cell on land.

When terminateShoreAndStartRidge() calls processRidge(), the rest of the cell is processed normally.

Cell which has only one vertex on land

Consider another cell on the coast with exactly the same shape as in all the previous examples. But in this case, the shore passes through the cell such that only vertex 23 is on land.

Recall that the list of edges for a cell is sorted such that the first edge will be an edge whose first vertex is on land. In this cell, only one edge meets this criterion, edge 20. So the list of edges will be [20, 32, 83, 93, 78, 40].

When processRidge() is called, it will observe that vertex 31 is not on land, and call terminateRidgeAndStartShore().

terminateRidgeAndStartShore() will observe that no previous ridge has been created, and will create a Q for vertex 23. Then it will investigate the intersection with the shore. It will find that edge 20 intersects with shore segment (15,16). It will create a Q for this intersection, create an edge based on the 2 Qs that it created, remove edge 20 from the list of edges to be processed, and calls processShoreSegment().

processShoreSegment() will process the rest of segment (15,16) and call itself to process segment (16,17). It will also call itself to process segment (17,18). However, it will discover that segment (17,18) intersects with edge 40. It will immediately call terminateShoreAndStartRidge().

terminateShoreAndStartRidge() will terminate segment (17,18) at its intersection with edge 40, call processRidge() to continue.

processRidge() will process edge 40 from its intersection with the shoreline, already done by terminateShoreAndStartRidge() to vertex 23. Then it will call itself, and it will hit the termination condition.