1/**************************************************************************/
2/* delaunay_2d.h */
3/**************************************************************************/
4/* This file is part of: */
5/* GODOT ENGINE */
6/* https://godotengine.org */
7/**************************************************************************/
8/* Copyright (c) 2014-present Godot Engine contributors (see AUTHORS.md). */
9/* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur. */
10/* */
11/* Permission is hereby granted, free of charge, to any person obtaining */
12/* a copy of this software and associated documentation files (the */
13/* "Software"), to deal in the Software without restriction, including */
14/* without limitation the rights to use, copy, modify, merge, publish, */
15/* distribute, sublicense, and/or sell copies of the Software, and to */
16/* permit persons to whom the Software is furnished to do so, subject to */
17/* the following conditions: */
18/* */
19/* The above copyright notice and this permission notice shall be */
20/* included in all copies or substantial portions of the Software. */
21/* */
22/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */
23/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */
24/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. */
25/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */
26/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */
27/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */
28/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
29/**************************************************************************/
30
31#ifndef DELAUNAY_2D_H
32#define DELAUNAY_2D_H
33
34#include "core/math/rect2.h"
35#include "core/templates/vector.h"
36
37class Delaunay2D {
38public:
39 struct Triangle {
40 int points[3];
41 Vector2 circum_center;
42 real_t circum_radius_squared;
43 Triangle() {}
44 Triangle(int p_a, int p_b, int p_c) {
45 points[0] = p_a;
46 points[1] = p_b;
47 points[2] = p_c;
48 }
49 };
50
51 struct Edge {
52 int points[2];
53 bool bad = false;
54 Edge() {}
55 Edge(int p_a, int p_b) {
56 // Store indices in a sorted manner to avoid having to check both orientations later.
57 if (p_a > p_b) {
58 points[0] = p_b;
59 points[1] = p_a;
60 } else {
61 points[0] = p_a;
62 points[1] = p_b;
63 }
64 }
65 };
66
67 static Triangle create_triangle(const Vector<Vector2> &p_vertices, const int &p_a, const int &p_b, const int &p_c) {
68 Triangle triangle = Triangle(p_a, p_b, p_c);
69
70 // Get the values of the circumcircle and store them inside the triangle object.
71 Vector2 a = p_vertices[p_b] - p_vertices[p_a];
72 Vector2 b = p_vertices[p_c] - p_vertices[p_a];
73
74 Vector2 O = (b * a.length_squared() - a * b.length_squared()).orthogonal() / (a.cross(b) * 2.0f);
75
76 triangle.circum_radius_squared = O.length_squared();
77 triangle.circum_center = O + p_vertices[p_a];
78
79 return triangle;
80 }
81
82 static Vector<Triangle> triangulate(const Vector<Vector2> &p_points) {
83 Vector<Vector2> points = p_points;
84 Vector<Triangle> triangles;
85
86 int point_count = p_points.size();
87 if (point_count <= 2) {
88 return triangles;
89 }
90
91 // Get a bounding rectangle.
92 Rect2 rect = Rect2(p_points[0], Size2());
93 for (int i = 1; i < point_count; i++) {
94 rect.expand_to(p_points[i]);
95 }
96
97 real_t delta_max = MAX(rect.size.width, rect.size.height);
98 Vector2 center = rect.get_center();
99
100 // Construct a bounding triangle around the rectangle.
101 points.push_back(Vector2(center.x - delta_max * 16, center.y - delta_max));
102 points.push_back(Vector2(center.x, center.y + delta_max * 16));
103 points.push_back(Vector2(center.x + delta_max * 16, center.y - delta_max));
104
105 Triangle bounding_triangle = create_triangle(points, point_count + 0, point_count + 1, point_count + 2);
106 triangles.push_back(bounding_triangle);
107
108 for (int i = 0; i < point_count; i++) {
109 Vector<Edge> polygon;
110
111 // Save the edges of the triangles whose circumcircles contain the i-th vertex. Delete the triangles themselves.
112 for (int j = triangles.size() - 1; j >= 0; j--) {
113 if (points[i].distance_squared_to(triangles[j].circum_center) < triangles[j].circum_radius_squared) {
114 polygon.push_back(Edge(triangles[j].points[0], triangles[j].points[1]));
115 polygon.push_back(Edge(triangles[j].points[1], triangles[j].points[2]));
116 polygon.push_back(Edge(triangles[j].points[2], triangles[j].points[0]));
117
118 triangles.remove_at(j);
119 }
120 }
121
122 // Create a triangle for every unique edge.
123 for (int j = 0; j < polygon.size(); j++) {
124 if (polygon[j].bad) {
125 continue;
126 }
127
128 for (int k = j + 1; k < polygon.size(); k++) {
129 // Compare the edges.
130 if (polygon[k].points[0] == polygon[j].points[0] && polygon[k].points[1] == polygon[j].points[1]) {
131 polygon.write[j].bad = true;
132 polygon.write[k].bad = true;
133
134 break; // Since no more than two triangles can share an edge, no more than two edges can share vertices.
135 }
136 }
137
138 // Create triangles out of good edges.
139 if (!polygon[j].bad) {
140 triangles.push_back(create_triangle(points, polygon[j].points[0], polygon[j].points[1], i));
141 }
142 }
143 }
144
145 // Filter out the triangles containing vertices of the bounding triangle.
146 int preserved_count = 0;
147 Triangle *triangles_ptrw = triangles.ptrw();
148 for (int i = 0; i < triangles.size(); i++) {
149 if (!(triangles[i].points[0] >= point_count || triangles[i].points[1] >= point_count || triangles[i].points[2] >= point_count)) {
150 triangles_ptrw[preserved_count] = triangles[i];
151 preserved_count++;
152 }
153 }
154 triangles.resize(preserved_count);
155
156 return triangles;
157 }
158};
159
160#endif // DELAUNAY_2D_H
161