A simple planar mesh primitive with half-edge

In a previous article, I explained why and how to implement the half-edge data structure. This article will focus on the implemention of a simple primitive: a 2 polygons rectangular planar mesh. Later we will see how to add some useful tools allowing us to expand the primitive by adding/removing vertices and flipping edges,

The implementation of a simple 2 polygons rectangle primitive could look easy at first glimpse. In reality, with half-edge, it is not so obvious. We need to be very careful and set all the relevant adjacency relations between the 4 vertices, the 10 oriented edges and the 2 faces:

Remember that each edge must references 4 datas: the origin vertex, the opposite edge, the next left edge and the left face:

We immediatly face an annoying problem : the 4 border edges e01, e12, e23 and e30 have neither left face nor next left edge. We could think that leaving null references as datas for these edges is safe, but in fact it would lead to several problems because the missing core datas would break the way we hope to iterate through the mesh. That's why I suggest rather to extend the rectangle in order to obtain a complete closed and consistent mesh:

We just added 2 new edges e13, e31 and 2 new faces f2 (bounded by e12, e23, e31) and f3 (bounded by e30, e01, e13)  This figure could look strange at first glimpse, but in fact it is really intuitive if you imagine our planar mesh lying on a sphere:

Finally, if these 4 new elements are convenient to get a mesh with a complete adjacency structure, they can be cumbersome when you display your mesh on screen or when you iterate in order to navigate from element to element. So feel free to add a new visible property to your classes and set it to false for any object lying outside the rectangle v0, v1, v2, v3. In this way you will be able to simply skip them.

As a conclusion, we will simply give now the complete declarations necessary to implement this simple rectangular primitive:

// (x, y) is any 2d coordinates system
// w is the rectangle width
// h is the rectangle heighy

v0.position = (0, 0)
v0.edge = e01 // or e02 or e03

v0.visible = true

v1.position = (w, 0)
v1.edge = e12 // or e10 or e13

v1.visible = true

v2.position = (w, h)
v2.edge = e23 // or e21 or e20

v2.visible = true

v3.position = (0, h)

v3.edge = e30 // or e32 or e31

v3.visible = true

e01.originVertex = v0
e01.oppositeEdge = e10
e01.nextLeftEdge = e13
e01.leftFace = f3
e01.visible = true

e10.originVertex = v1
e10.oppositeEdge = e01
e10.nextLeftEdge = e02
e10.leftFace = f0
e10.visible = true

e12.originVertex = v1
e12.oppositeEdge = e21
e12.nextLeftEdge = e23
e12.leftFace = f2
e12.visible = true

e21.originVertex = v2
e21.oppositeEdge = e12
e21.nextLeftEdge = e10
e21.leftFace = f0
e21.visible = true

e23.originVertex = v2
e23.oppositeEdge = e32
e23.nextLeftEdge = e31
e23.leftFace = f2
e23.visible = true

e32.originVertex = v3
e32.oppositeEdge = e23
e32.nextLeftEdge = e20
e32.leftFace = f1
e32.visible = true

e30.originVertex = v3
e30.oppositeEdge = e03
e30.nextLeftEdge = e01
e30.leftFace = f3
e30.visible = true

e03.originVertex = v0
e03.oppositeEdge = e30
e03.nextLeftEdge = e32
e03.leftFace = f1
e03.visible = true

e02.originVertex = v0
e02.oppositeEdge = e20
e02.nextLeftEdge = e21
e02.leftFace = f0
e02.visible = true

e20.originVertex = v2
e20.oppositeEdge = e02
e20.nextLeftEdge = e03
e20.leftFace = f1
e20.visible = true

e13.originVertex = v1
e13.oppositeEdge = e31
e13.nextLeftEdge = e30
e13.leftFace = f3
e13.visible = false

e31.originVertex = v3
e31.oppositeEdge = e13
e31.nextLeftEdge = e12
e31.leftFace = f2
e31.visible = false

f0.edge = e10 // or e02 or e21
f0.visible = true

f1.edge = e32 // or e20 or e03
f1.visible = true

f2.edge = e31 // or e12 or e23
f2.visible = false

f3.edge = e13 // or e01 or e30
f3.visible = false