Merge pull request #29127 from Xrayez/geometry-delaunay-bind

Expose 2D Delaunay triangulation in Geometry singleton

4 files changed, 30 insertions, 0 deletions

diff --git a/core/bind/core_bind.cpp b/core/bind/core_bind.cpp
index 7562c82e8a..ddb60e1345 100644
--- a/core/bind/core_bind.cpp
+++ b/core/bind/core_bind.cpp
@@ -1501,6 +1501,11 @@ Vector<int> _Geometry::triangulate_polygon(const Vector<Vector2> &p_polygon) {
 	return Geometry::triangulate_polygon(p_polygon);
 }
 
+Vector<int> _Geometry::triangulate_delaunay_2d(const Vector<Vector2> &p_points) {
+
+	return Geometry::triangulate_delaunay_2d(p_points);
+}
+
 Vector<Point2> _Geometry::convex_hull_2d(const Vector<Point2> &p_points) {
 
 	return Geometry::convex_hull_2d(p_points);
@@ -1674,6 +1679,7 @@ void _Geometry::_bind_methods() {
 
 	ClassDB::bind_method(D_METHOD("is_polygon_clockwise", "polygon"), &_Geometry::is_polygon_clockwise);
 	ClassDB::bind_method(D_METHOD("triangulate_polygon", "polygon"), &_Geometry::triangulate_polygon);
+	ClassDB::bind_method(D_METHOD("triangulate_delaunay_2d", "points"), &_Geometry::triangulate_delaunay_2d);
 	ClassDB::bind_method(D_METHOD("convex_hull_2d", "points"), &_Geometry::convex_hull_2d);
 	ClassDB::bind_method(D_METHOD("clip_polygon", "points", "plane"), &_Geometry::clip_polygon);
 
diff --git a/core/bind/core_bind.h b/core/bind/core_bind.h
index 561449f29e..d4fa3bc735 100644
--- a/core/bind/core_bind.h
+++ b/core/bind/core_bind.h
@@ -404,6 +404,7 @@ public:
 
 	bool is_polygon_clockwise(const Vector<Vector2> &p_polygon);
 	Vector<int> triangulate_polygon(const Vector<Vector2> &p_polygon);
+	Vector<int> triangulate_delaunay_2d(const Vector<Vector2> &p_points);
 	Vector<Point2> convex_hull_2d(const Vector<Point2> &p_points);
 	Vector<Vector3> clip_polygon(const Vector<Vector3> &p_points, const Plane &p_plane);
 
diff --git a/core/math/geometry.h b/core/math/geometry.h
index c62573dd13..0e144e491f 100644
--- a/core/math/geometry.h
+++ b/core/math/geometry.h
@@ -31,6 +31,7 @@
 #ifndef GEOMETRY_H
 #define GEOMETRY_H
 
+#include "core/math/delaunay.h"
 #include "core/math/face3.h"
 #include "core/math/rect2.h"
 #include "core/math/triangulate.h"
@@ -857,6 +858,19 @@ public:
 		return points;
 	}
 
+	static Vector<int> triangulate_delaunay_2d(const Vector<Vector2> &p_points) {
+
+		Vector<Delaunay2D::Triangle> tr = Delaunay2D::triangulate(p_points);
+		Vector<int> triangles;
+
+		for (int i = 0; i < tr.size(); i++) {
+			triangles.push_back(tr[i].points[0]);
+			triangles.push_back(tr[i].points[1]);
+			triangles.push_back(tr[i].points[2]);
+		}
+		return triangles;
+	}
+
 	static Vector<int> triangulate_polygon(const Vector<Vector2> &p_polygon) {
 
 		Vector<int> triangles;
diff --git a/doc/classes/Geometry.xml b/doc/classes/Geometry.xml
index b95b888cf1..e2ba3fb7b0 100644
--- a/doc/classes/Geometry.xml
+++ b/doc/classes/Geometry.xml
@@ -428,6 +428,15 @@
 				Can be useful in conjuction with performing polygon boolean operations in CSG manner, see [method merge_polygons_2d], [method clip_polygons_2d], [method intersect_polygons_2d], [method exclude_polygons_2d].
 			</description>
 		</method>
+		<method name="triangulate_delaunay_2d">
+			<return type="PoolIntArray">
+			</return>
+			<argument index="0" name="points" type="PoolVector2Array">
+			</argument>
+			<description>
+				Triangulates the area specified by discrete set of [code]points[/code] such that no point is inside the circumcircle of any resulting triangle. Returns a [PoolIntArray] where each triangle consists of three consecutive point indices into [code]points[/code] (i.e. the returned array will have [code]n * 3[/code] elements, with [code]n[/code] being the number of found triangles). If the triangulation did not succeed, an empty [PoolIntArray] is returned.
+			</description>
+		</method>
 		<method name="triangulate_polygon">
 			<return type="PoolIntArray">
 			</return>