Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2001-2026 German Aerospace Center (DLR) and others.
4 : // This program and the accompanying materials are made available under the
5 : // terms of the Eclipse Public License 2.0 which is available at
6 : // https://www.eclipse.org/legal/epl-2.0/
7 : // This Source Code may also be made available under the following Secondary
8 : // Licenses when the conditions for such availability set forth in the Eclipse
9 : // Public License 2.0 are satisfied: GNU General Public License, version 2
10 : // or later which is available at
11 : // https://www.gnu.org/licenses/old-licenses/gpl-2.0-standalone.html
12 : // SPDX-License-Identifier: EPL-2.0 OR GPL-2.0-or-later
13 : /****************************************************************************/
14 : /// @file Triangle.cpp
15 : /// @author Pablo Alvarez Lopez
16 : /// @date Jan 2025
17 : ///
18 : // A simple triangle defined in 3D
19 : /****************************************************************************/
20 : #include <config.h>
21 :
22 : #include <algorithm>
23 : #include "Triangle.h"
24 :
25 :
26 : // ===========================================================================
27 : // static member definitions
28 : // ===========================================================================
29 :
30 : const Triangle Triangle::INVALID = Triangle();
31 : const double Triangle::EPSILON = 1e-9;
32 :
33 : // ===========================================================================
34 : // method definitions
35 : // ===========================================================================
36 51252 : Triangle::Triangle() {}
37 :
38 :
39 0 : Triangle::Triangle(const Position& positionA, const Position& positionB, const Position& positionC) :
40 0 : myA(positionA),
41 0 : myB(positionB),
42 0 : myC(positionC) {
43 : // calculate boundary
44 0 : myBoundary.add(positionA);
45 0 : myBoundary.add(positionB);
46 0 : myBoundary.add(positionC);
47 0 : }
48 :
49 :
50 51252 : Triangle::~Triangle() {}
51 :
52 :
53 : bool
54 0 : Triangle::isPositionWithin(const Position& pos) const {
55 0 : return isPositionWithin(myA, myB, myC, pos);
56 : }
57 :
58 :
59 : bool
60 0 : Triangle::isBoundaryFullWithin(const Boundary& boundary) const {
61 0 : return isPositionWithin(Position(boundary.xmax(), boundary.ymax())) &&
62 0 : isPositionWithin(Position(boundary.xmin(), boundary.ymin())) &&
63 0 : isPositionWithin(Position(boundary.xmax(), boundary.ymin())) &&
64 0 : isPositionWithin(Position(boundary.xmin(), boundary.ymax()));
65 : }
66 :
67 :
68 : bool
69 0 : Triangle::intersectWithShape(const PositionVector& shape) const {
70 0 : return intersectWithShape(shape, shape.getBoxBoundary());
71 : }
72 :
73 :
74 : bool
75 0 : Triangle::intersectWithShape(const PositionVector& shape, const Boundary& shapeBoundary) const {
76 : // Check if the triangle's vertices are within the shape
77 0 : if (shape.around(myA) || shape.around(myB) || shape.around(myC)) {
78 0 : return true;
79 : }
80 : // Check if at least two corners of the shape boundary are within the triangle.
81 : // (This acts as a heuristic to detect overlap without checking every edge first)
82 : int cornersInside = 0;
83 0 : if (isPositionWithin(Position(shapeBoundary.xmax(), shapeBoundary.ymax()))) {
84 : cornersInside++;
85 : }
86 0 : if (isPositionWithin(Position(shapeBoundary.xmin(), shapeBoundary.ymin()))) {
87 0 : cornersInside++;
88 : }
89 0 : if ((cornersInside < 2) && isPositionWithin(Position(shapeBoundary.xmax(), shapeBoundary.ymin()))) {
90 0 : cornersInside++;
91 : }
92 0 : if ((cornersInside < 2) && isPositionWithin(Position(shapeBoundary.xmin(), shapeBoundary.ymax()))) {
93 0 : cornersInside++;
94 : }
95 0 : if (cornersInside >= 2) {
96 : return true;
97 : }
98 : // At this point, we need to check if any line of the shape intersects with the triangle.
99 : // We treat the shape as a closed polygon.
100 0 : const int shapeSize = (int)shape.size();
101 0 : for (int i = 0; i < shapeSize; i++) {
102 0 : const Position& p1 = shape[i];
103 : // Wrap around to the first point
104 0 : const Position& p2 = shape[(i + 1) % shapeSize];
105 : // Avoid checking a zero-length segment if the shape is already explicitly closed in data
106 0 : if (p1 == p2) {
107 0 : continue;
108 0 : } else if (lineIntersectsTriangle(p1, p2)) {
109 : return true;
110 : }
111 : }
112 : return false;
113 : }
114 :
115 :
116 : bool
117 0 : Triangle::intersectWithCircle(const Position& center, const double radius) const {
118 0 : const auto squaredRadius = radius * radius;
119 0 : return ((center.distanceSquaredTo2D(myA) <= squaredRadius) ||
120 0 : (center.distanceSquaredTo2D(myB) <= squaredRadius) ||
121 0 : (center.distanceSquaredTo2D(myC) <= squaredRadius) ||
122 0 : isPositionWithin(center) ||
123 0 : lineIntersectCircle(myA, myB, center, radius) ||
124 0 : lineIntersectCircle(myB, myC, center, radius) ||
125 0 : lineIntersectCircle(myC, myA, center, radius));
126 : }
127 :
128 :
129 : const Boundary&
130 0 : Triangle::getBoundary() const {
131 0 : return myBoundary;
132 : }
133 :
134 :
135 : const PositionVector
136 0 : Triangle::getShape() const {
137 0 : return PositionVector({myA, myB, myC});
138 : }
139 :
140 :
141 : std::vector<Triangle>
142 0 : Triangle::triangulate(PositionVector shape) {
143 : std::vector<Triangle> triangles;
144 : // first open polygon
145 0 : shape.openPolygon();
146 : // we need at leas three vertex
147 0 : if (shape.size() >= 3) {
148 : // greedy algorithm
149 0 : while (shape.size() > 3) {
150 0 : int shapeSize = (int)shape.size();
151 : int earIndex = -1;
152 : // first find an "ear"
153 0 : for (int i = 0; (i < shapeSize) && (earIndex == -1); i++) {
154 0 : const auto& earA = shape[(i + shapeSize - 1) % shapeSize];
155 0 : const auto& earB = shape[i];
156 0 : const auto& earC = shape[(i + 1) % shapeSize];
157 0 : if (isEar(earA, earB, earC, shape)) {
158 : earIndex = i;
159 : }
160 : }
161 0 : if (earIndex != -1) {
162 0 : triangles.push_back(Triangle(
163 0 : shape[(earIndex + shapeSize - 1) % shapeSize],
164 0 : shape[earIndex],
165 0 : shape[(earIndex + 1) % shapeSize])
166 : );
167 0 : shape.erase(shape.begin() + earIndex);
168 : } else {
169 : // simply remove the first three
170 0 : triangles.push_back(Triangle(shape[0], shape[1], shape[2]));
171 0 : shape.erase(shape.begin() + 1);
172 : }
173 : }
174 : // add last triangle
175 0 : triangles.push_back(Triangle(shape[0], shape[1], shape[2]));
176 : }
177 0 : return triangles;
178 0 : }
179 :
180 :
181 : bool
182 0 : Triangle::operator==(const Triangle& other) const {
183 0 : return myA == other.myA && myB == other.myB && myC == other.myC;
184 : }
185 :
186 :
187 : bool
188 0 : Triangle::operator!=(const Triangle& other) const {
189 0 : return !(*this == other);
190 : }
191 :
192 :
193 : bool
194 0 : Triangle::isPositionWithin(const Position& A, const Position& B, const Position& C, const Position& pos) {
195 : // Calculate cross products for each edge of the triangle
196 0 : const double crossAB = crossProduct(A, B, pos);
197 0 : const double crossBC = crossProduct(B, C, pos);
198 0 : const double crossCA = crossProduct(C, A, pos);
199 : // check conditions
200 0 : const bool allPositive = (crossAB > -EPSILON) && (crossBC > -EPSILON) && (crossCA > -EPSILON);
201 0 : const bool allNegative = (crossAB < EPSILON) && (crossBC < EPSILON) && (crossCA < EPSILON);
202 0 : return allPositive || allNegative;
203 : }
204 :
205 :
206 : bool
207 0 : Triangle::isEar(const Position& a, const Position& b, const Position& c, const PositionVector& shape) {
208 : // Check if triangle ABC is counter-clockwise
209 0 : if (crossProduct(a, b, c) <= 0) {
210 : return false;
211 : }
212 : // Check if any other point in the polygon lies inside the triangle
213 0 : for (const auto& pos : shape) {
214 0 : if ((pos != a) && (pos != b) && (pos != c) && isPositionWithin(a, b, c, pos)) {
215 : return false;
216 : }
217 : }
218 : return true;
219 : }
220 :
221 :
222 : double
223 0 : Triangle::crossProduct(const Position& a, const Position& b, const Position& c) {
224 0 : return (b.x() - a.x()) * (c.y() - a.y()) - (b.y() - a.y()) * (c.x() - a.x());
225 : }
226 :
227 :
228 : int
229 0 : Triangle::orientation(const Position& p, const Position& q, const Position& r) const {
230 0 : const double val = (q.y() - p.y()) * (r.x() - q.x()) - (q.x() - p.x()) * (r.y() - q.y());
231 0 : if (std::abs(val) < EPSILON) {
232 : return 0;
233 0 : } else if (val > 0) {
234 : return 1;
235 : } else {
236 0 : return -1;
237 : }
238 : }
239 :
240 :
241 : bool
242 0 : Triangle::onSegment(const Position& p, const Position& q, const Position& r) const {
243 0 : return ((q.x() >= std::min(p.x(), r.x()) - EPSILON) &&
244 0 : (q.x() <= std::max(p.x(), r.x()) + EPSILON) &&
245 0 : (q.y() >= std::min(p.y(), r.y()) - EPSILON) &&
246 0 : (q.y() <= std::max(p.y(), r.y()) + EPSILON));
247 : }
248 :
249 :
250 : bool
251 0 : Triangle::segmentsIntersect(const Position& p1, const Position& q1, const Position& p2, const Position& q2) const {
252 0 : const int o1 = orientation(p1, q1, p2);
253 0 : const int o2 = orientation(p1, q1, q2);
254 0 : const int o3 = orientation(p2, q2, p1);
255 0 : const int o4 = orientation(p2, q2, q1);
256 : // General case: segments intersect if they have different orientations
257 : // Special cases: checking if points are collinear and on segment
258 0 : if ((o1 != o2) && (o3 != o4)) {
259 : return true;
260 0 : } else if ((o1 == 0) && onSegment(p1, p2, q1)) {
261 : return true;
262 0 : } else if ((o2 == 0) && onSegment(p1, q2, q1)) {
263 : return true;
264 0 : } else if ((o3 == 0) && onSegment(p2, p1, q2)) {
265 : return true;
266 0 : } else if ((o4 == 0) && onSegment(p2, q1, q2)) {
267 : return true;
268 : } else {
269 0 : return false;
270 : }
271 : }
272 :
273 :
274 : bool
275 0 : Triangle::lineIntersectsTriangle(const Position& p1, const Position& p2) const {
276 0 : return segmentsIntersect(p1, p2, myA, myB) ||
277 0 : segmentsIntersect(p1, p2, myB, myC) ||
278 0 : segmentsIntersect(p1, p2, myC, myA);
279 : }
280 :
281 :
282 : bool
283 0 : Triangle::lineIntersectCircle(const Position& posA, const Position& posB, const Position& center, const double radius) const {
284 : // Calculate coefficients of the quadratic equation
285 0 : const double dx = posB.x() - posA.x();
286 0 : const double dy = posB.y() - posA.y();
287 0 : const double a = dx * dx + dy * dy;
288 0 : const double b = 2 * (dx * (posA.x() - center.x()) + dy * (posA.y() - center.y()));
289 0 : const double c = (posA.x() - center.x()) * (posA.x() - center.x()) + (posA.y() - center.y()) * (posA.y() - center.y()) - radius * radius;
290 : // Calculate the discriminant
291 0 : const double discriminant = (b * b - 4 * a * c);
292 : // Check the discriminant to determine the intersection
293 0 : if (discriminant >= 0) {
294 : // Calculate the two possible values of t
295 0 : const double sqrtDiscriminant = sqrt(discriminant);
296 0 : const double t1 = (-b + sqrtDiscriminant) / (2 * a);
297 0 : const double t2 = (-b - sqrtDiscriminant) / (2 * a);
298 : // if at least t1 or t2 is between [0,1], then intersect
299 0 : return (t1 >= 0 && t1 <= 1) || (t2 >= 0 && t2 <= 1);
300 : } else {
301 : return false;
302 : }
303 : }
304 :
305 : /****************************************************************************/
|
