1 files changed, 145 insertions, 0 deletions
diff --git a/core/math/delaunay.h b/core/math/delaunay.h
new file mode 100644
index 0000000000..09aebc773f
--- /dev/null
+++ b/core/math/delaunay.h
@@ -0,0 +1,145 @@
+#ifndef DELAUNAY_H
+#define DELAUNAY_H
+
+#include "math_2d.h"
+
+class Delaunay2D {
+public:
+	struct Triangle {
+
+		int points[3];
+		bool bad;
+		Triangle() { bad = false; }
+		Triangle(int p_a, int p_b, int p_c) {
+			points[0] = p_a;
+			points[1] = p_b;
+			points[2] = p_c;
+			bad = false;
+		}
+	};
+
+	struct Edge {
+		int edge[2];
+		bool bad;
+		Edge() { bad = false; }
+		Edge(int p_a, int p_b) {
+			bad = false;
+			edge[0] = p_a;
+			edge[1] = p_b;
+		}
+	};
+
+	static bool circum_circle_contains(const Vector<Vector2> &p_vertices, const Triangle &p_triangle, int p_vertex) {
+
+		Vector2 p1 = p_vertices[p_triangle.points[0]];
+		Vector2 p2 = p_vertices[p_triangle.points[1]];
+		Vector2 p3 = p_vertices[p_triangle.points[2]];
+
+		real_t ab = p1.x * p1.x + p1.y * p1.y;
+		real_t cd = p2.x * p2.x + p2.y * p2.y;
+		real_t ef = p3.x * p3.x + p3.y * p3.y;
+
+		Vector2 circum(
+				(ab * (p3.y - p2.y) + cd * (p1.y - p3.y) + ef * (p2.y - p1.y)) / (p1.x * (p3.y - p2.y) + p2.x * (p1.y - p3.y) + p3.x * (p2.y - p1.y)),
+				(ab * (p3.x - p2.x) + cd * (p1.x - p3.x) + ef * (p2.x - p1.x)) / (p1.y * (p3.x - p2.x) + p2.y * (p1.x - p3.x) + p3.y * (p2.x - p1.x)));
+
+		circum *= 0.5;
+		float r = p1.distance_squared_to(circum);
+		float d = p_vertices[p_vertex].distance_squared_to(circum);
+		return d <= r;
+	}
+
+	static bool edge_compare(const Vector<Vector2> &p_vertices, const Edge &p_a, const Edge &p_b) {
+		if (p_vertices[p_a.edge[0]].distance_to(p_vertices[p_b.edge[0]]) < CMP_EPSILON && p_vertices[p_a.edge[1]].distance_to(p_vertices[p_b.edge[1]]) < CMP_EPSILON) {
+			return true;
+		}
+
+		if (p_vertices[p_a.edge[0]].distance_to(p_vertices[p_b.edge[1]]) < CMP_EPSILON && p_vertices[p_a.edge[1]].distance_to(p_vertices[p_b.edge[0]]) < CMP_EPSILON) {
+			return true;
+		}
+
+		return false;
+	}
+
+	static Vector<Triangle> triangulate(const Vector<Vector2> &p_points) {
+
+		Vector<Vector2> points = p_points;
+		Vector<Triangle> triangles;
+
+		Rect2 rect;
+		for (int i = 0; i < p_points.size(); i++) {
+			if (i == 0) {
+				rect.position = p_points[i];
+			} else {
+				rect.expand_to(p_points[i]);
+			}
+		}
+
+		float delta_max = MAX(rect.size.width, rect.size.height);
+		Vector2 center = rect.position + rect.size * 0.5;
+
+		points.push_back(Vector2(center.x - 20 * delta_max, center.y - delta_max));
+		points.push_back(Vector2(center.x, center.y + 20 * delta_max));
+		points.push_back(Vector2(center.x + 20 * delta_max, center.y - delta_max));
+
+		triangles.push_back(Triangle(p_points.size() + 0, p_points.size() + 1, p_points.size() + 2));
+
+		for (int i = 0; i < p_points.size(); i++) {
+			//std::cout << "Traitement du point " << *p << std::endl;
+			//std::cout << "_triangles contains " << _triangles.size() << " elements" << std::endl;
+
+			Vector<Edge> polygon;
+
+			for (int j = 0; j < triangles.size(); j++) {
+				if (circum_circle_contains(points, triangles[j], i)) {
+					triangles[j].bad = true;
+					polygon.push_back(Edge(triangles[j].points[0], triangles[j].points[1]));
+					polygon.push_back(Edge(triangles[j].points[1], triangles[j].points[2]));
+					polygon.push_back(Edge(triangles[j].points[2], triangles[j].points[0]));
+				}
+			}
+
+			for (int j = 0; j < triangles.size(); j++) {
+				if (triangles[j].bad) {
+					triangles.remove(j);
+					j--;
+				}
+			}
+
+			for (int j = 0; j < polygon.size(); j++) {
+				for (int k = j + 1; k < polygon.size(); k++) {
+					if (edge_compare(points, polygon[j], polygon[k])) {
+						polygon[j].bad = true;
+						polygon[k].bad = true;
+					}
+				}
+			}
+
+			for (int j = 0; j < polygon.size(); j++) {
+
+				if (polygon[j].bad) {
+					continue;
+				}
+				triangles.push_back(Triangle(polygon[j].edge[0], polygon[j].edge[1], i));
+			}
+		}
+
+		for (int i = 0; i < triangles.size(); i++) {
+			bool invalid = false;
+			for (int j = 0; j < 3; j++) {
+				if (triangles[i].points[j] >= p_points.size()) {
+					invalid = true;
+					break;
+				}
+			}
+			if (invalid) {
+				triangles.remove(i);
+				i--;
+			}
+		}
+
+		return triangles;
+	}
+};
+
+#endif // DELAUNAY_H