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
    • Ear cut
    • Edge split
    • Inset
    • Quad fan
    • Rim triangles
    • Tri fan (with boundary point)
    • Tri fan (with centroid)
    • Tri fan (with edge splitting)
  • 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).

Quad fan

• quadFan

Rim triangles

• rimTris

Tri fan (with boundary point)

• triFanBoundary

Tri fan (with centroid)

• triFan

Tri fan (with edge splitting)

• triFanSplit

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

• @thi.ng/api
• @thi.ng/checks
• @thi.ng/geom-accel
• @thi.ng/geom-isec
• @thi.ng/geom-poly-utils
• @thi.ng/math
• @thi.ng/morton
• @thi.ng/transducers
• @thi.ng/vectors

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:

Screenshot	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:

• tessellate()
• tessellateWith()
• tessellateFaces()

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
}

License

© 2013 - 2024 Karsten Schmidt // Apache License 2.0