@thi.ng/geom-tessellate

[!NOTE] This is one of 199 standalone projects, maintained as part of the @thi.ng/umbrella monorepo and anti-framework.

🚀 Please help me to work full-time on these projects by sponsoring me on GitHub. Thank you! ❤️

About
- Tessellators
- The ITessellation interface & implementation
Status
Installation
Dependencies
Usage examples
API
- Basic usage
Authors
License

About

2D/3D convex polygon tessellators. This is a support package for @thi.ng/geom.

Tessellators

The following tessellator algorithms are provided, but the package is designed to be fully extensible. See code examples further below.

The following diagrams each show the effect of a single tessellator applied to a triangle, square, hexagon and octagon.

Ear cut

earCut

Complex polygons

earCutComplex

Higher order tessellator for concave polygons and/or polygons with holes...

TODO add comments, credits & example

Edge split

edgeSplit

Inset

inset

Higher order tessellator with configurable inset distance (normalized) toward centroid and option to keep center polygon (empty by default).

The `ITessellation` interface & implementation

The tessellators provided all operate in conjunction with a ITessellation implementation which is used to collect (or index) points/vertices and generated faces (not necessarily triangles).

Currently, there're two implementations available:

BasicTessellation is used as the default and merely collects points & faces into arrays
MeshTessellation uses a kD-tree to deduplicate/weld and re-use points (with configurable tolerance) and is recommended for use cases when the result tessellation should be converted or used for graph-like analysis or other post-processing.

Status

STABLE - used in production

Search or submit any issues for this package

Installation

yarn add @thi.ng/geom-tessellate

ESM import:

import * as gt from "@thi.ng/geom-tessellate";

Browser ESM import:

<script type="module" src="https://esm.run/@thi.ng/geom-tessellate"></script>

JSDelivr documentation

For Node.js REPL:

const gt = await import("@thi.ng/geom-tessellate");

Package sizes (brotli'd, pre-treeshake): ESM: 3.32 KB

Dependencies

Note: @thi.ng/api is in most cases a type-only import (not used at runtime)

Usage examples

Three projects in this repo's /examples directory are using this package:

Description	Live demo	Source
Hex grid generation & tessellations	Demo	Source
Animated, recursive polygon tessellations	Demo	Source
Live coding playground for 2D geometry generation using @thi.ng/pointfree-lang	Demo	Source

API

Generated API docs

This is a low(er)-level support package for thi.ng/geom and most users are encouraged to use the polymorphic tessellate() function provided by that package.

In addition to the actual tessellator algorithms described above, this package also provides its own set of tessellate() functions to simplify recursive/iterative application of multiple tessellation passes:

Basic usage

import * as gt from "@thi.ng/geom-tessellate";

// points of a square polygon
const points = [[0,0], [100,0], [100,100], [0, 100]];

// tessellate square into a triangle fan
console.log(gt.tessellate(points, gt.triFan));
// BasicTessellation {
//   points: [[ 0, 0 ], [ 100, 0 ], [ 100, 100 ], [ 0, 100 ], [ 50, 50 ]],
//   faces: [[ 4, 0, 1 ], [ 4, 1, 2 ], [ 4, 2, 3 ], [ 4, 3, 0 ]],
//   ...
// }

// tessellate square first into a triangle fan, then each triangle into a quad fan
console.log(gt.tessellate(points, [gt.triFan, gt.quadFan]));
// BasicTessellation {
//   points: [
//     [ 0, 0 ], [ 100, 0 ], [ 100, 100 ], [ 0, 100 ],
//     [ 50, 50 ], [ 50, 16.666 ], [ 75, 25 ], [ 25, 25 ],
//     [ 50, 0 ], [ 83.333, 50 ], [ 75, 75 ], [ 75, 25 ],
//     [ 100, 50 ], [ 50, 83.333 ], [ 25, 75 ], [ 75, 75 ],
//     [ 50, 100 ], [ 16.666, 50 ], [ 25, 25 ], [ 25, 75 ], [ 0, 50 ]
//   ],
//   faces: [
//     [ 5, 6, 4, 7 ], [ 5, 7, 0, 8 ], [ 5, 8, 1, 6 ], [ 9, 10, 4, 11 ],
//     [ 9, 11, 1, 12 ], [ 9, 12, 2, 10 ], [ 13, 14, 4, 15 ], [ 13, 15, 2, 16 ],
//     [ 13, 16, 3, 14 ], [ 17, 18, 4, 19 ], [ 17, 19, 3, 20 ], [ 17, 20, 0, 18 ]
//   ],
//   ...
// }

// apply quadfan twice and use a custom tessellation instance
// (here to dedupe generated edge midpoints)
console.log(gt.tessellateWith(new gt.MeshTessellation(2), points, gt.quadFan, 2));
// MeshTessellation {
//   points: [
//     [ 0, 0 ], [ 100, 0 ], [ 100, 100 ], [ 0, 100 ],
//     [ 50, 50 ], [ 0, 50 ], [ 50, 0 ], [ 100, 50 ],
//     [ 50, 100 ], [ 25, 25 ], [ 50, 25 ], [ 25, 50 ],
//     [ 0, 25 ], [ 25, 0 ], [ 75, 25 ], [ 75, 50 ],
//     [ 75, 0 ], [ 100, 25 ], [ 75, 75 ], [ 50, 75 ],
//     [ 100, 75 ], [ 75, 100 ], [ 25, 75 ], [25, 100], [ 0, 75 ]
//   ],
//   faces: [
//     [ 9, 10, 4, 11 ], [ 9, 11, 5, 12 ], [ 9, 12, 0, 13 ], [ 9, 13, 6, 10 ],
//     [ 14, 15, 4, 10 ], [ 14, 10, 6, 16 ], [ 14, 16, 1, 17 ], [ 14, 17, 7, 15 ],
//     [ 18, 19, 4, 15 ], [ 18, 15, 7, 20 ], [ 18, 20, 2, 21 ], [ 18, 21, 8, 19 ],
//     [ 22, 11, 4, 19 ], [ 22, 19, 8, 23 ], [ 22, 23, 3, 24 ], [ 22, 24, 5, 11 ]
//   ],
//   ...
// }

Authors

Karsten Schmidt

If this project contributes to an academic publication, please cite it as:

@misc{thing-geom-tessellate,
  title = "@thi.ng/geom-tessellate",
  author = "Karsten Schmidt",
  note = "https://thi.ng/geom-tessellate",
  year = 2013
}