Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2001-2025 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 : const Triangle Triangle::INVALID = Triangle();
30 :
31 :
32 : // ===========================================================================
33 : // method definitions
34 : // ===========================================================================
35 17224 : Triangle::Triangle() {}
36 :
37 :
38 0 : Triangle::Triangle(const Position& positionA, const Position& positionB, const Position& positionC) :
39 0 : myA(positionA),
40 0 : myB(positionB),
41 0 : myC(positionC) {
42 : // calculate boundary
43 0 : myBoundary.add(positionA);
44 0 : myBoundary.add(positionB);
45 0 : myBoundary.add(positionC);
46 0 : }
47 :
48 :
49 17224 : Triangle::~Triangle() {}
50 :
51 :
52 : bool
53 0 : Triangle::isPositionWithin(const Position& pos) const {
54 0 : return isPositionWithin(myA, myB, myC, pos);
55 : }
56 :
57 :
58 : bool
59 0 : Triangle::isBoundaryFullWithin(const Boundary& boundary) const {
60 0 : return isPositionWithin(Position(boundary.xmax(), boundary.ymax())) &&
61 0 : isPositionWithin(Position(boundary.xmin(), boundary.ymin())) &&
62 0 : isPositionWithin(Position(boundary.xmax(), boundary.ymin())) &&
63 0 : isPositionWithin(Position(boundary.xmin(), boundary.ymax()));
64 : }
65 :
66 :
67 : bool
68 0 : Triangle::intersectWithShape(const PositionVector& shape) const {
69 0 : return intersectWithShape(shape, shape.getBoxBoundary());
70 : }
71 :
72 :
73 : bool
74 0 : Triangle::intersectWithShape(const PositionVector& shape, const Boundary& shapeBoundary) const {
75 : // check if triangle is within shape
76 0 : if (shape.around(myA) || shape.around(myB) || shape.around(myC)) {
77 0 : return true;
78 : }
79 : // check if at leas two corners of the shape boundary are within triangle
80 0 : const int cornerA = isPositionWithin(Position(shapeBoundary.xmax(), shapeBoundary.ymax()));
81 0 : const int cornerB = isPositionWithin(Position(shapeBoundary.xmin(), shapeBoundary.ymin()));
82 0 : if ((cornerA + cornerB) == 2) {
83 : return true;
84 : }
85 0 : const int cornerC = isPositionWithin(Position(shapeBoundary.xmax(), shapeBoundary.ymin()));
86 0 : if ((cornerA + cornerB + cornerC) == 2) {
87 : return true;
88 : }
89 0 : const int cornerD = isPositionWithin(Position(shapeBoundary.xmin(), shapeBoundary.ymax()));
90 0 : if ((cornerA + cornerB + cornerC + cornerD) == 2) {
91 : return true;
92 : }
93 : // on this point, whe need to check if every shape line intersect with triangle
94 0 : for (int i = 0; i < ((int)shape.size() - 1); i++) {
95 0 : if (lineIntersectsTriangle(shape[i], shape[i + 1])) {
96 : return true;
97 : }
98 : }
99 : return false;
100 : }
101 :
102 :
103 : bool
104 0 : Triangle::intersectWithCircle(const Position& center, const double radius) const {
105 0 : const auto squaredRadius = radius * radius;
106 0 : return ((center.distanceSquaredTo2D(myA) <= squaredRadius) ||
107 0 : (center.distanceSquaredTo2D(myB) <= squaredRadius) ||
108 0 : (center.distanceSquaredTo2D(myC) <= squaredRadius) ||
109 0 : isPositionWithin(center) ||
110 0 : lineIntersectCircle(myA, myB, center, radius) ||
111 0 : lineIntersectCircle(myB, myC, center, radius) ||
112 0 : lineIntersectCircle(myC, myA, center, radius));
113 : }
114 :
115 :
116 : const Boundary&
117 0 : Triangle::getBoundary() const {
118 0 : return myBoundary;
119 : }
120 :
121 :
122 : const PositionVector
123 0 : Triangle::getShape() const {
124 0 : return PositionVector({myA, myB, myC});
125 : }
126 :
127 :
128 : std::vector<Triangle>
129 0 : Triangle::triangulate(PositionVector shape) {
130 : std::vector<Triangle> triangles;
131 : // first open polygon
132 0 : shape.openPolygon();
133 : // we need at leas three vertex
134 0 : if (shape.size() >= 3) {
135 : // greedy algorithm
136 0 : while (shape.size() > 3) {
137 0 : int shapeSize = (int)shape.size();
138 : int earIndex = -1;
139 : // first find an "ear"
140 0 : for (int i = 0; (i < shapeSize) && (earIndex == -1); i++) {
141 0 : const auto& earA = shape[(i + shapeSize - 1) % shapeSize];
142 0 : const auto& earB = shape[i];
143 0 : const auto& earC = shape[(i + 1) % shapeSize];
144 0 : if (isEar(earA, earB, earC, shape)) {
145 : earIndex = i;
146 : }
147 : }
148 0 : if (earIndex != -1) {
149 0 : triangles.push_back(Triangle(
150 0 : shape[(earIndex + shapeSize - 1) % shapeSize],
151 0 : shape[earIndex],
152 0 : shape[(earIndex + 1) % shapeSize])
153 : );
154 0 : shape.erase(shape.begin() + earIndex);
155 : } else {
156 : // simply remove the first three
157 0 : triangles.push_back(Triangle(shape[0], shape[1], shape[2]));
158 0 : shape.erase(shape.begin() + 1);
159 : }
160 : }
161 : // add last triangle
162 0 : triangles.push_back(Triangle(shape[0], shape[1], shape[2]));
163 : }
164 0 : return triangles;
165 0 : }
166 :
167 :
168 : bool
169 0 : Triangle::operator==(const Triangle& other) const {
170 0 : return myA == other.myA && myB == other.myB && myC == other.myC;
171 : }
172 :
173 :
174 : bool
175 0 : Triangle::operator!=(const Triangle& other) const {
176 0 : return !(*this == other);
177 : }
178 :
179 :
180 : bool
181 0 : Triangle::isPositionWithin(const Position& A, const Position& B, const Position& C, const Position& pos) {
182 : // Calculate cross products for each edge of the triangle
183 0 : const double crossAB = crossProduct(A, B, pos);
184 0 : const double crossBC = crossProduct(B, C, pos);
185 0 : const double crossCA = crossProduct(C, A, pos);
186 : // Check if all cross products have the same sign
187 0 : return ((crossAB >= 0) && (crossBC >= 0) && (crossCA >= 0)) ||
188 0 : ((crossAB <= 0) && (crossBC <= 0) && (crossCA <= 0));
189 : }
190 :
191 :
192 : bool
193 0 : Triangle::isEar(const Position& a, const Position& b, const Position& c, const PositionVector& shape) {
194 : // Check if triangle ABC is counter-clockwise
195 0 : if (crossProduct(a, b, c) <= 0) {
196 : return false;
197 : }
198 : // Check if any other point in the polygon lies inside the triangle
199 0 : for (const auto& pos : shape) {
200 0 : if ((pos != a) && (pos != b) && (pos != c) && isPositionWithin(a, b, c, pos)) {
201 : return false;
202 : }
203 : }
204 : return true;
205 : }
206 :
207 :
208 : double
209 0 : Triangle::crossProduct(const Position& a, const Position& b, const Position& c) {
210 0 : return (b.x() - a.x()) * (c.y() - a.y()) - (b.y() - a.y()) * (c.x() - a.x());
211 : }
212 :
213 :
214 : int
215 0 : Triangle::orientation(const Position& p, const Position& q, const Position& r) const {
216 0 : const double val = (q.y() - p.y()) * (r.x() - q.x()) - (q.x() - p.x()) * (r.y() - q.y());
217 0 : if (val > 0) {
218 : // Clockwise
219 : return 1;
220 0 : } else if (val < 0) {
221 : // Counterclockwise
222 : return -1;
223 : } else {
224 : // Collinear
225 0 : return 0;
226 : }
227 : }
228 :
229 :
230 : bool
231 0 : Triangle::onSegment(const Position& p, const Position& q, const Position& r) const {
232 0 : return (q.x() >= std::min(p.x(), r.x()) && q.x() <= std::max(p.x(), r.x()) &&
233 0 : q.y() >= std::min(p.y(), r.y()) && q.y() <= std::max(p.y(), r.y()));
234 : }
235 :
236 :
237 : bool
238 0 : Triangle::segmentsIntersect(const Position& p1, const Position& q1, const Position& p2, const Position& q2) const {
239 0 : const int o1 = orientation(p1, q1, p2);
240 0 : const int o2 = orientation(p1, q1, q2);
241 0 : const int o3 = orientation(p2, q2, p1);
242 0 : const int o4 = orientation(p2, q2, q1);
243 : // General case: segments intersect if they have different orientations
244 : // Special cases: checking if points are collinear and on segment
245 0 : if ((o1 != o2) && (o3 != o4)) {
246 : return true;
247 0 : } else if ((o1 == 0) && onSegment(p1, p2, q1)) {
248 : return true;
249 0 : } else if ((o2 == 0) && onSegment(p1, q2, q1)) {
250 : return true;
251 0 : } else if ((o3 == 0) && onSegment(p2, p1, q2)) {
252 : return true;
253 0 : } else if ((o4 == 0) && onSegment(p2, q1, q2)) {
254 : return true;
255 : } else {
256 0 : return false;
257 : }
258 : }
259 :
260 :
261 : bool
262 0 : Triangle::lineIntersectsTriangle(const Position& p1, const Position& p2) const {
263 0 : return segmentsIntersect(p1, p2, myA, myB) ||
264 0 : segmentsIntersect(p1, p2, myB, myC) ||
265 0 : segmentsIntersect(p1, p2, myC, myA);
266 : }
267 :
268 :
269 : bool
270 0 : Triangle::lineIntersectCircle(const Position& posA, const Position& posB, const Position& center, const double radius) const {
271 : // Calculate coefficients of the quadratic equation
272 0 : const double dx = posB.x() - posA.x();
273 0 : const double dy = posB.y() - posA.y();
274 0 : const double a = dx * dx + dy * dy;
275 0 : const double b = 2 * (dx * (posA.x() - center.x()) + dy * (posA.y() - center.y()));
276 0 : const double c = (posA.x() - center.x()) * (posA.x() - center.x()) + (posA.y() - center.y()) * (posA.y() - center.y()) - radius * radius;
277 : // Calculate the discriminant
278 0 : const double discriminant = (b * b - 4 * a * c);
279 : // Check the discriminant to determine the intersection
280 0 : if (discriminant >= 0) {
281 : // Calculate the two possible values of t
282 0 : const double sqrtDiscriminant = sqrt(discriminant);
283 0 : const double t1 = (-b + sqrtDiscriminant) / (2 * a);
284 0 : const double t2 = (-b - sqrtDiscriminant) / (2 * a);
285 : // if at least t1 or t2 is between [0,1], then intersect
286 0 : return (t1 >= 0 && t1 <= 1) || (t2 >= 0 && t2 <= 1);
287 : } else {
288 : return false;
289 : }
290 : }
291 :
292 : /****************************************************************************/
|
