From 078b869d9a93b7cdfe89461b713de8c123b96d7c Mon Sep 17 00:00:00 2001
From: Mariano Suligoy <marianognu.easyrpg@gmail.com>
Date: Sun, 3 Mar 2019 23:05:43 -0300
Subject: TileSet/TileMap: Decompose solid non-convex polygons into convexes.
 Real fix for #24003

---
 core/math/geometry.cpp | 35 +++++++++++++++++++++++++++++++++++
 1 file changed, 35 insertions(+)

(limited to 'core/math/geometry.cpp')

diff --git a/core/math/geometry.cpp b/core/math/geometry.cpp
index 12c88f43b3..194a6f6352 100644
--- a/core/math/geometry.cpp
+++ b/core/math/geometry.cpp
@@ -31,6 +31,7 @@
 #include "geometry.h"
 
 #include "core/print_string.h"
+#include "thirdparty/misc/triangulator.h"
 
 /* this implementation is very inefficient, commenting unless bugs happen. See the other one.
 bool Geometry::is_point_in_polygon(const Vector2 &p_point, const Vector<Vector2> &p_polygon) {
@@ -737,6 +738,40 @@ PoolVector<Face3> Geometry::wrap_geometry(PoolVector<Face3> p_array, real_t *p_e
 	return wrapped_faces;
 }
 
+Vector<Vector<Vector2> > Geometry::decompose_polygon_in_convex(Vector<Point2> polygon) {
+	Vector<Vector<Vector2> > decomp;
+	List<TriangulatorPoly> in_poly, out_poly;
+
+	TriangulatorPoly inp;
+	inp.Init(polygon.size());
+	for (int i = 0; i < polygon.size(); i++) {
+		inp.GetPoint(i) = polygon[i];
+	}
+	inp.SetOrientation(TRIANGULATOR_CCW);
+	in_poly.push_back(inp);
+	TriangulatorPartition tpart;
+	if (tpart.ConvexPartition_HM(&in_poly, &out_poly) == 0) { //failed!
+		ERR_PRINT("Convex decomposing failed!");
+		return decomp;
+	}
+
+	decomp.resize(out_poly.size());
+	int idx = 0;
+	for (List<TriangulatorPoly>::Element *I = out_poly.front(); I; I = I->next()) {
+		TriangulatorPoly &tp = I->get();
+
+		decomp.write[idx].resize(tp.GetNumPoints());
+
+		for (int i = 0; i < tp.GetNumPoints(); i++) {
+			decomp.write[idx].write[i] = tp.GetPoint(i);
+		}
+
+		idx++;
+	}
+
+	return decomp;
+}
+
 Geometry::MeshData Geometry::build_convex_mesh(const PoolVector<Plane> &p_planes) {
 
 	MeshData mesh;
-- 
cgit v1.2.3