2D Delaunay triangulation by Bowyer-Watson
In your harnessMesh algorithmMIT
Triangulate 2D points so that no point lies inside any triangle's circumcircle, using Bowyer-Watson insertion with exact fallback predicates. Use it for terrain meshes, interpolation and Voronoi construction.
What it takes and gives
- Entry points
- delaunay, random_points, triangulation_mesh, build, main
- Parameters
- count, layout, seed
- Complexity
- O(n^2)
- Axes
- +Y up, metres; 2D (x, y) maps to (x, 0, -y)
Limits. Quadratic insertion: suited to thousands of points, not millions. Exact rational arithmetic is used only when the floating-point predicate is too close to call, which is slow for large degenerate inputs. Exact duplicate points are used once. Collinear input raises an error. No constraint edges; see a constrained triangulation for polygons with holes.
Details
- Kind
- Mesh algorithm
- Engine
- Python 3.10 or later
- Files
- 10 files, 215.8 KB
- Licence
- MIT
- Declared effects
- reads files, runs commands, writes files
- Checked with
- Godot 4.7.2, gl_compatibility, OpenGL 3 driver, Mesa llvmpipe under Xvfb
- Checks
- generator runs system python, generator runs verifier python, gltf strict structure, interpreters agree, example matches generator, godot headless gltf load, godot compatibility render
- Techniques
- Bowyer-Watson incremental insertion, In-circle and orientation determinants with exact fallback, Lawson edge flips, Convex hull completion
- Tags
- delaunay, triangulation, bowyer-watson, computational geometry, 2d, exact predicates
- Identity
library.supply.creative_originals.f52e7a6018568728d13f9eed.9ad5be3ac433f355- Version
9ad5be3ac433f3557b4a32ebcc6b12f725ded9f57c0b7793e79a031626e823aa
The version is the SHA-256 of the item your harness downloads; every file in it names its own checksum.
Related files
3D convex hull by quickhullIn your harness
Something wrong with this item, its rights or its safety? Report it on the support page, or from your harness after a download.