Docs: https://scala-tessella.github.io/dcel/

DCEL utilities for representing, building, editing and analysing edge-to-edge tessellations of unit-side polygons in Scala 3.

Tessellations are modelled as a Doubly Connected Edge List (DCEL): a classical planar-subdivision representation 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 this base representation the library provides builders, validation, topology/geometry operations, symmetry and uniformity analysis, and import/export.

Status: early development (pre-1.0). The API may still change between minor versions.

Add the dependency to your build.sbt:

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

Published for Scala 3 on the JVM and Scala.js. Scala Native is scaffolded but blocked by Spire's Native support (see Tech Stack below).

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

dcel/
├── build.sbt                  # Cross-project (JVM + JS) build and compiler flags
├── project/plugins.sbt        # sbt-scalajs, sbt-scalafmt, sbt-scalafix, sbt-ide-settings
├── shared/src/main/scala/io/github/scala_tessella/dcel/
│   ├── TilingDCEL.scala         # Main case class; container for vertices/edges/faces
│   ├── TilingBuilder.scala      # Nets, rings, simple & regular polygon constructors
│   ├── TilingAddition.scala     # In-place growth primitives (used by deep-copied tilings)
│   ├── TilingDeletion.scala     # In-place removal primitives
│   ├── TilingValidation.scala   # Completeness, topology, geometry, spatial checks
│   ├── TilingEquivalency.scala  # Boundary signature & equivalence grouping
│   ├── TilingUniformity.scala   # Uniformity/gonality trees
│   ├── TilingSymmetry.scala     # BoundaryLocation, BoundaryVertex, BoundaryEdge
│   ├── TilingError.scala        # Sealed error ADT + helpers
│   ├── Tree.scala               # Algebraic Leaf/Branch tree used for uniformity
│   ├── Utils.scala              # Small shared helpers (traverse, sequence, associate)
│   ├── geometry/                # BigDecimal-based primitives (see below)
│   ├── structure/               # DCEL entities: Vertex, HalfEdge, Face, IDs, Prefixable
│   └── conversion/              # SVG and DOT exporters + SVG-metadata reader
├── shared/src/test/scala/…      # Unit + ScalaCheck property tests
├── shared/src/test/resources/   # SVG fixtures used by tests
├── benchmarks/src/main/scala/…/benchmark/UniformityBenchmark.scala  # JMH (opt-in, unpublished)
├── generator/src/main/scala/…/TilingGenerator.scala  # Experimental n-uniform/n-archimedean search (opt-in, unpublished)
└── README.md

Two opt-in sbt subprojects live in this repo but are not part of the published dcel_3 artifact:

• benchmarks/ — JMH micro-benchmarks for the validation/uniformity hot paths. Run with sbt 'benchmarks/Jmh/run …'.
• generator/ — research-grade enumerator of n-uniform n-archimedean tilings (TilingGenerator.findTilings, expandRotationally, expandRotationallyMore). API and search heuristics are still in flux; several exploratory tests are disabled. Run with sbt generator/test. When the surface stabilises, this may be promoted to its own published artifact.

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

• JDK 17 or later (CI runs on Temurin 17).
• sbt (1.12.9 used by this project; launcher will pick up the version).
• Node.js on PATH for the Scala.js test runner.

# compile all modules
sbt compile

# run all tests
sbt test

# run target-specific tests
sbt dcelJVM/test
sbt dcelJS/test

# format + scalafix + tests (alias defined in build.sbt)
sbt qa

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

val base = TilingDCEL.createRegularPolygon(RegularPolygon(6))

val grownEither =
  base.maybeAddRegularPolygonToBoundary(
    onEdgeStartingWith = VertexId(1),
    polygon            = RegularPolygon(3)
  )

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.

import io.github.scala_tessella.dcel.TilingBuilder

val rhombusNetEither   = TilingBuilder.createRhombusNet(width = 3, height = 3)
val holedTriangleEither =
  TilingBuilder.createHoledTriangleNet(10, 10): (x, y) =>
    x > 2 && x < 7 && y > 2 && y < 7

The uniformity operations live as extension methods in TilingUniformity:

import io.github.scala_tessella.dcel.TilingUniformity.*

val tree         = base.uniformityTree
val uncompressed = base.uniformityTreeUncompressed()
val scan         = base.scanUniformityTree

import io.github.scala_tessella.dcel.conversion.TilingSVG.SvgOptions

val dot: String = base.toDOT
val svg: String = base.toSVG(SvgOptions(scale = 80.0, showUniformity = true))

import io.github.scala_tessella.dcel.conversion.TilingSVG.fromMetadata

val svgWithMeta  = base.toSVG(SvgOptions(scale = 80.0))
val reconstructed = fromMetadata(svgWithMeta)  // Either[TilingError, TilingDCEL]

• Public fallible APIs generally return Either[TilingError, A].
• TilingError is a sealed trait with ValidationError, IncompleteError, TopologyError, GeometryError, SpatialError, and NotFoundError alternatives, plus a TilingError.combineErrors helper.
• Methods ending in Unsafe skip defensive checks for performance on already-validated inputs; they are meant for internal or hot paths and can throw. Prefer the non-Unsafe counterparts from client code.
• IDs are opaque types (VertexId, FaceId) and format themselves through the Prefixable trait (e.g. v1, f7).

• Formatting: scalafmt via SBT plugin; scalafmtOnCompile is enabled.
• Lint / refactoring: scalafix with SemanticDB.
• Compiler hygiene: -deprecation -feature -unchecked -Wvalue-discard -Wnonunit-statement -Wunused:imports, elevated to -Werror in Compile only; tests are compiled with warnings, not fatal.
• Cross-building: JVM and Scala.js share all sources via crossType(Full). A Scala Native project is scaffolded in native/ and will be enabled as soon as Spire ships a compatible Native build.

Pure unit tests plus ScalaCheck property-based tests (see PropertyBasedDCELSpec.scala). SVG fixtures under shared/src/test/resources/ are used as reference snapshots for the builders and the SVG exporter.

Dual-licensed under either of

• Apache License, Version 2.0 (LICENSE-APACHE or https://www.apache.org/licenses/LICENSE-2.0)
• MIT license (LICENSE-MIT or https://opensource.org/licenses/MIT)

at your option.