AgentFoundrySign in ↗
← All examples

mesh algorithms

2D Delaunay triangulation by Bowyer-Watson

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.

Recorded render of 2D Delaunay triangulation by Bowyer-Watson

What this component contains

  • ATTRIBUTION.md
  • LICENSE
  • README.md
  • component.json
  • delaunay_bowyer_watson.py
  • example.gltf
  • meshkit.py
  • preview.png
  • test_package.py
  • verification/native.json

How it works

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)

Recorded checks

godot 4.7.2.stable.official.ed1daf0bf

  • generator_runs_system_python
  • generator_runs_verifier_python
  • gltf_strict_structure
  • interpreters_agree
  • example_matches_generator
  • godot_headless_gltf_load
  • godot_compatibility_render

Limits to consider

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.