/*************************************************************************/ /* delaunay_2d.h */ /*************************************************************************/ /* This file is part of: */ /* GODOT ENGINE */ /* https://godotengine.org */ /*************************************************************************/ /* Copyright (c) 2007-2022 Juan Linietsky, Ariel Manzur. */ /* Copyright (c) 2014-2022 Godot Engine contributors (cf. AUTHORS.md). */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ /* "Software"), to deal in the Software without restriction, including */ /* without limitation the rights to use, copy, modify, merge, publish, */ /* distribute, sublicense, and/or sell copies of the Software, and to */ /* permit persons to whom the Software is furnished to do so, subject to */ /* the following conditions: */ /* */ /* The above copyright notice and this permission notice shall be */ /* included in all copies or substantial portions of the Software. */ /* */ /* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ /* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ /* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ /* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ /* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ /* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ /* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ /*************************************************************************/ #ifndef DELAUNAY_2D_H #define DELAUNAY_2D_H #include "core/math/rect2.h" #include "core/templates/vector.h" class Delaunay2D { public: struct Triangle { int points[3]; bool bad = false; Triangle() {} Triangle(int p_a, int p_b, int p_c) { points[0] = p_a; points[1] = p_b; points[2] = p_c; } }; struct Edge { int edge[2]; bool bad = false; Edge() {} Edge(int p_a, int p_b) { 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]].is_equal_approx(p_vertices[p_b.edge[0]]) && p_vertices[p_a.edge[1]].is_equal_approx(p_vertices[p_b.edge[1]])) { return true; } if (p_vertices[p_a.edge[0]].is_equal_approx(p_vertices[p_b.edge[1]]) && p_vertices[p_a.edge[1]].is_equal_approx(p_vertices[p_b.edge[0]])) { 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.get_center(); 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++) { Vector<Edge> polygon; for (int j = 0; j < triangles.size(); j++) { if (circum_circle_contains(points, triangles[j], i)) { triangles.write[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_at(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.write[j].bad = true; polygon.write[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_at(i); i--; } } return triangles; } }; #endif // DELAUNAY_2D_H