dcel — planar subdivisions for unit-side tessellations

dcel is the geometric model behind the Tessella editor. It represents edge-to-edge tessellations of unit-side polygons as a Doubly Connected Edge List — a classical planar-subdivision data structure in which every edge is split into two oppositely oriented half-edges, and each half-edge knows its origin vertex, its incident face, its twin, its predecessor, and its successor. On top of that base, the library provides builders, validation, topology and geometry operations, symmetry and uniformity analysis, and import/export.

The library is published for Scala 3 on the JVM and on Scala.js. A Scala Native build is scaffolded but blocked on Spire’s Native support.

Install

Add to your build.sbt:

libraryDependencies += "io.github.scala-tessella" %% "dcel" % "0.1.0"
// Use %%% instead of %% for Scala.js

What it gives you

• Construct tilings from regular or simple unit-side polygons (TilingDCEL.createRegularPolygon, TilingDCEL.createSimplePolygon).
• Build nets quickly: triangle, rhombus/square, and hexagon nets, rings, and holed triangle nets (TilingBuilder.createTriangleNet, createRhombusNet, createHexagonNet, createRing, createHoledTriangleNet).
• Grow and shrink with validation-aware APIs: maybeAddRegularPolygon*, maybeAddSimplePolygon*, maybeDeleteVertex, maybeDeleteEdge, maybeDeleteFace, fanAt, doubleArea.
• Analyse topology, symmetry, and uniformity: boundary, inner vertices, vertex angles, uniformityTree, gonalityTrees, boundary-equivalence grouping.
• Validate completeness, topology, geometry, and spatial consistency in one call (TilingValidation.validate). Failures surface as a sealed TilingError ADT.
• Export to SVG (with optional uniformity colouring, arrows, labels) and DOT, with round-trip serialisation through SVG metadata.

Quickstart

import io.github.scala_tessella.dcel.TilingDCEL
import io.github.scala_tessella.dcel.geometry.RegularPolygon
import io.github.scala_tessella.dcel.structure.VertexId

// start from a single hexagon
val base = TilingDCEL.createRegularPolygon(RegularPolygon(6))

// attach a triangle to one of its edges (returns Either[TilingError, TilingDCEL])
val grownEither =
  base.maybeAddRegularPolygonToBoundary(
    onEdgeStartingWith = VertexId(1),
    polygon            = RegularPolygon(3)
  )

// render to SVG
val svgEither = grownEither.map(_.toSVG(scale = 80.0))

Every mutating public API returns an Either[TilingError, TilingDCEL] and operates on an internal deep copy, so the input value is never modified. Methods ending in Unsafe skip defensive checks for hot paths; prefer the non-Unsafe counterparts from client code.

API shape

Errors are surfaced through a sealed TilingError ADT — ValidationError, IncompleteError, TopologyError, GeometryError, SpatialError, NotFoundError — plus a TilingError.combineErrors helper.

IDs are opaque types (VertexId, FaceId) and format themselves through the Prefixable trait (e.g. v1, f7), so log output and error messages stay readable.

The library is split into four packages:

Only the root package depends on the other three; conversion depends on everything, structure depends on geometry, geometry has no internal deps.

Where it’s used

• Tessella editor uses dcel for every tiling operation — adding and removing polygons, validating each move, computing uniformity colouring, drawing the SVG, and round-tripping saved files.

If you adopt it in a project, open an issue and we will add it to the list.

Install, docs and source