License: Apache v2
I'm using this library for my own projects; the interface isn't stable yet, so expect breaking changes in the future.
For some of my map generation projects I've used an unstructured grid instead of regular grids to add variety and interestingness to the maps. I need a way to represent polygon regions (red points, outline in white) including their corners (blue points):
But I also sometimes need to visit a region's neighbors (red points, black connecting lines):
Put together, these form a dual mesh structure that has both the polygons (white lines, blue points) and triangles (black lines, red points):
Each element (region, side, triangle) has an integer index starting from 0. The sides are half edges, so there are two of them between each pair of regions. The sides index both between red points (black lines) and blue points (white lines); for each pair of red and blue points there are two side half-edges. For example with r0, r2, t0, t1, there are two side half-edges, s2 from r2 → r0 and s5 from r0 → r2. These two sides are called opposites. There are three sides per triangle. For example triangle t1 has sides s3, s4, s5.
Regions are polygons. Each region has N sides and N corners. For example region r0 has sides s0, s11, s8, s17, s14, and corners t0, t3, t2, t5, t4.
Lots of error-prone code is avoided by using sentinel values instead of nulls. In this case, the mesh will have opposites[s] == -1 at the boundaries of the map. Checking whether each side has an opposite (≥ 0) leads to error-prone code. Iterating around the vertices of a polygon loop can fail if some vertices are missing. Switching to a side's opposite can fail if there is no opposite. Finding a triangle's neighbors can fail if some triangles are off the edge of the map. The solution is to “wrap” the map around the back so that there are no more boundaries.
The ghost elements are invisible elements of the dual mesh that provide the connectivity that nulls would complicate. Only the solid (non-ghost) elements are usually drawn, although it depends on context. The ghost region can be thought of as the “outside” of the map, or a region at “infinity” or the “back” of the map. Ghost triangles and sides connect the boundary of the map to the ghost region. Here are the additional ghost sides and vertices:
The ghost elements eliminate the boundary from a structural point of view, but I still want a boundary in the generated maps. The boundary elements are those adjacent to the outside of the map (ghost region). In the mesh creation function the points are evenly spaced but that isn't necessary.
If s2 === s_opposite_s(s1):
Properties of circulation:
For my 2010 polygon-map-generator project (Flash) I wrote a wrapper around the as3delaunay library that gave me access to the kinds of structures and operations I wanted to work with for polygon maps. For my 2017 map generator projects (Javascript) I wrote this wrapper around the delaunator library. See my blog post about centroid polygons and my blog post about the dual mesh data structure. This library is an evolution of that dual mesh data structure, with ghost elements and different names.
Take a look at @redblobgames/dual-mesh, but at the moment I'm writing it only for myself and don't intend for others to use it. I do make breaking changes.