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
`s2`

*begins*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
`s2`

has 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
`s2`

has*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)}}`

and`s5`

'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
`s`

is returned by`s_around_r(r)`, then`r_begin_s(s)``=`

`r`

- If
`s`

is 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.**