My Dual-Mesh library is something I use for my own projects, to wrap the functions in the Delaunator Guide[1]. License: Apache-v2. I use this for my own projects and make breaking changes occasionally.
For some of my map generation projects I've used an unstructured grid[2] 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):
1 Structure#
Each element (r:region, s:side, t: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.
1.1. Ghost elements#
Lots of error-prone code is avoided by using sentinel values[3] 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 add ghost elements to complete the connectivity. The solid elements are the original elements. When drawing the Delaunay triangles or Voronoi regions, skip the ghost elements. We need one ghost region. Think of the ghost region as being on the "back" of the plane, or at infinity. We need one ghost triangle and two ghost sides per unpaired side.
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 r8 (red rectangle instead of a red point).
1.2. Boundary elements#
The ghost elements eliminate the boundary from a structural point of view, to avoid error-prone code, but I still want a visual boundary in the generated maps. The boundary regions (points) are between the main regions and the ghost region. In the mesh creation function the points are evenly spaced but that isn't necessary.
Visually, I think of them as nested regions:
The boundary points must be inside the bounding rectangle if used with Poisson Disc. These will be placed barely inside with the generateInteriorBoundaryPoints() function:
But, barely inside means there's a tiny gap between the boundary points and the bounding rectangle. To fill that gap, add a second layer of boundary points with generateExteriorBoundaryPoints():
2 Operations#
The accessor functions are named output = output_from_input(input). Some of them return an array, and will take an optional parameter to reuse an existing array (to avoid memory allocations).
- x_of_r(r), y_of_r(r), pos_of_r(r, out=[])
- the position of region
r(red point). - x_of_t(t), y_of_t(t), pos_of_t(t, out=[])
- the center position of triangle
t(blue point). - r_begin_s(s), r_end_s(s)
- the black edge endpoints (red). The black edge
s2begins at{{test('r_begin_s',2)}}and ends at{{test('r_end_s',2)}}. - t_inner_s(s), t_outer_s(s)
- the white edge endpoints (blue). The black edge
s2has a white edge connecting inner triangle{{test('t_inner_s',2)}}to outer triangle{{test('t_outer_s',2)}}. - s_next_s(s), s_prev_s(s)
- next/prev around triangle. The black edge
s2has next edge{{test('s_next_s',2)}}and previous edge{{test('s_prev_s',2)}}. - s_opposite_s(s)
- opposite of half-edge. The black edge
s2's opposite is{{test('s_opposite_s',2)}}ands5's opposite is{{test('s_opposite_s',5)}}. If an edge has no opposite, it will return-1. - s_around_t(t, out=[])
- sides around a triangle. Triangle
t0's sides are{{test('s_around_t',0)}} - r_around_t(t, out=[])
- regions around a triangle. Triangle
t0's regions are{{test('r_around_t',0)}} - t_around_t(t, out=[])
- triangles neighboring a triangle. Triangle
t0's neighbors are{{test('t_around_t',0)}}in this diagram, but more commonly there would be three neighbors. - s_around_r(r, out=[])
- sides around a region. Region
r0's sides are{{test('s_around_r',0)}}in this diagram, but more commonly would be more, as they form a voronoi cell for the region. - r_around_r(r, out=[])
- regions neighboring a region. Region
r0's neighbors are{{test('r_around_r',0)}}. - t_around_r(r, out=[])
- triangles around a region. Region
r0's triangles are{{test('t_around_r',0)}}in this diagram, but more commonly would be more. - r_ghost(r)
- the ghost r index (outer edge)(not shown in this diagram)
- is_ghost_{s,r,t}(id)
- whether an element is a ghost
- is_boundary_{s,r}(id)
- whether an element is on the boundary
If s_opposite_s(s1) = s2:
- s_opposite_s(s2)
=s1 - r_begin_s(s1)
=r_end_s(s2) - r_begin_s(s2)
=r_end_s(s1) - t_inner_s(s1)
=t_outer_s(s2) - t_inner_s(s2)
=t_outer_s(s1)
Properties of circulation:
- If
sis returned by s_around_r(r), then r_begin_s(s)=r - If
sis returned by s_around_t(t), then t_inner_s(s)=t
2.1. History#
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[4] and my blog post about the dual mesh data structure[5]. This library is an evolution of that dual mesh data structure, with ghost elements and different names. In 2023 I redesigned it to be more ergonomic and (hopefully) less error-prone.
2.2. Source code#
Feel free to look at @redblobgames/dual-mesh[6], 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.