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 PositionVector.h
15 : /// @author Daniel Krajzewicz
16 : /// @author Jakob Erdmann
17 : /// @author Michael Behrisch
18 : /// @date Sept 2002
19 : ///
20 : // A list of positions
21 : /****************************************************************************/
22 : #pragma once
23 : #include <config.h>
24 :
25 : #include <vector>
26 : #include <limits>
27 : #include "AbstractPoly.h"
28 :
29 :
30 : // ===========================================================================
31 : // class declarations
32 : // ===========================================================================
33 :
34 : class Boundary;
35 :
36 : // ===========================================================================
37 : // class definitions
38 : // ===========================================================================
39 : /**
40 : * @class PositionVector
41 : * @brief A list of positions
42 : */
43 58223998 : class PositionVector : public AbstractPoly, private std::vector<Position> {
44 :
45 : private:
46 : /// @brief vector of position
47 : typedef std::vector<Position> vp;
48 :
49 : public:
50 : /// @brief Constructor. Creates an empty position vector
51 : PositionVector();
52 :
53 : /// @brief Copy Constructor. Create a positionVector with the same elements as other positionVector
54 : /// @param[in] v The vector to copy
55 : PositionVector(const std::vector<Position>& v);
56 :
57 : /// @brief Parameter Constructor. Create a positionVector using a part of other positionVector
58 : /// @param[in] beg The begin iterator for copy
59 : /// @param[in] end The end iterator to copy
60 : PositionVector(const std::vector<Position>::const_iterator beg, const std::vector<Position>::const_iterator end);
61 :
62 : /// @brief Parameter Constructor used for lines
63 : /// @param[in] p1 the first position
64 : /// @param[in] p2 the second position
65 : PositionVector(const Position& p1, const Position& p2);
66 :
67 : /// @brief Destructor
68 : ~PositionVector();
69 :
70 : /// @brief empty Vector
71 : static const PositionVector EMPTY;
72 :
73 : /// @name methode for iterate over PositionVector
74 : /// @{
75 : /// @brief iterator
76 : using vp::iterator;
77 :
78 : /// @brief constant iterator
79 : using vp::const_iterator;
80 :
81 : /// @brief contant reference
82 : using vp::const_reference;
83 :
84 : /// @brief value type
85 : using vp::value_type;
86 :
87 : /// @brief begin of position vector
88 : using vp::begin;
89 :
90 : /// @brief end of position vector
91 : using vp::end;
92 :
93 : /// @brief push a position in the back of position vector
94 : using vp::push_back;
95 :
96 : /// @brief push a position in the front of position vector
97 : using vp::pop_back;
98 :
99 : /// @brief clear all elements of position vector
100 : using vp::clear;
101 :
102 : /// @brief returns size of position vector
103 : using vp::size;
104 :
105 : /// @brief returns whether the position vector is empty
106 : using vp::empty;
107 :
108 : /// @brief get the front element of position vector
109 : using vp::front;
110 :
111 : /// @brief get back element of position vector
112 : using vp::back;
113 :
114 : /// @brief get a reference of position vector
115 : using vp::reference;
116 :
117 : /// @brief erase a position of position vector gived by iterator
118 : using vp::erase;
119 :
120 : /// @brief insert a position in position vector gived by iterator
121 : using vp::insert;
122 : /// @}
123 :
124 : /// @brief Returns the information whether the position vector describes a polygon lying around the given point
125 : /// @note The optional offset is added to the polygon's boundaries
126 : bool around(const Position& p, double offset = 0) const;
127 :
128 : /// @brief Returns the information whether the given polygon overlaps with this
129 : /// @note Again a boundary may be specified
130 : bool overlapsWith(const AbstractPoly& poly, double offset = 0) const;
131 :
132 : /// @brief Returns the maximum overlaps between this and the given polygon (when not separated by at least zThreshold)
133 : double getOverlapWith(const PositionVector& poly, double zThreshold) const;
134 :
135 : /// @brief Returns the information whether this list of points interesects the given line
136 : bool intersects(const Position& p1, const Position& p2) const;
137 :
138 : /// @brief Returns the information whether this list of points interesects one the given lines
139 : bool intersects(const PositionVector& v1) const;
140 :
141 : /// @brief Returns the position of the intersection
142 : Position intersectionPosition2D(const Position& p1, const Position& p2, const double withinDist = 0.) const;
143 :
144 : /// @brief For all intersections between this vector and other, return the 2D-length of the subvector from this vectors start to the intersection
145 : std::vector<double> intersectsAtLengths2D(const PositionVector& other) const;
146 :
147 : /// @brief For all intersections between this vector and line, return the 2D-length of the subvector from this vectors start to the intersection
148 : std::vector<double> intersectsAtLengths2D(const Position& lp1, const Position& lp2) const;
149 :
150 : /// @brief Returns the position of the intersection
151 : Position intersectionPosition2D(const PositionVector& v1) const;
152 :
153 : /// @brief open polygon
154 : void openPolygon();
155 :
156 : /// @brief ensures that the last position equals the first
157 : void closePolygon();
158 :
159 : /// @brief returns the constant position at the given index, negative indices are interpreted python style
160 : /// @throws OutOfBoundsException if index >= size or index < -size
161 : const Position& operator[](int index) const;
162 :
163 : /// @brief returns the position at the given index, negative indices are interpreted python style
164 : /// @throws OutOfBoundsException if index >= size or index < -size
165 : Position& operator[](int index);
166 :
167 : /// @brief Returns the position at the given length
168 : Position positionAtOffset(double pos, double lateralOffset = 0) const;
169 :
170 : /// @brief Returns the position at the given length
171 : Position positionAtOffset2D(double pos, double lateralOffset = 0, bool extrapolateBeyond = false) const;
172 :
173 : /* @brief Returns position similar to positionAtOffset but instead of applying the
174 : * lateral offset orthogonal to the shape, apply it orthogonal to the given angle */
175 : Position sidePositionAtAngle(double pos, double lateralOffset, double angle) const;
176 :
177 : /// @brief Returns the rotation at the given length
178 : double rotationAtOffset(double pos) const;
179 :
180 : /// @brief Returns the rotation at the given length
181 : double rotationDegreeAtOffset(double pos) const;
182 :
183 : /// @brief Returns the slope at the given length
184 : double slopeDegreeAtOffset(double pos) const;
185 :
186 : /// @brief Returns the position between the two given point at the specified position
187 : static Position positionAtOffset(const Position& p1, const Position& p2, double pos, double lateralOffset = 0.);
188 :
189 : /// Returns the position between the two given point at the specified position
190 : static Position positionAtOffset2D(const Position& p1, const Position& p2, double pos, double lateralOffset = 0, bool extrapolateBeyond = false);
191 :
192 : /* @brief Returns position similar to positionAtOffset but instead of applying the
193 : * lateral offset orthogonal to the shape, apply it orthogonal to the given angle */
194 : static Position sidePositionAtAngle(const Position& p1, const Position& p2, double pos, double lateralOffset, double angle);
195 :
196 : /// @brief Returns a boundary enclosing this list of lines
197 : Boundary getBoxBoundary() const;
198 :
199 : /// @brief Returns the arithmetic of all corner points
200 : /// @note: this is different from the centroid!
201 : Position getPolygonCenter() const;
202 :
203 : /// @brief Returns the centroid (closes the polygon if unclosed)
204 : Position getCentroid() const;
205 :
206 : /// @brief enlarges/shrinks the polygon by a factor based at the centroid
207 : void scaleRelative(double factor);
208 :
209 : /// @brief enlarges/shrinks the polygon by an absolute offset based at the centroid
210 : void scaleAbsolute(double offset);
211 :
212 : /// @brief get line center
213 : Position getLineCenter() const;
214 :
215 : /// @brief Returns the length
216 : double length() const;
217 :
218 : /// @brief Returns the length
219 : double length2D() const;
220 :
221 : /// @brief Returns the area (0 for non-closed)
222 : double area() const;
223 :
224 : /// @brief Returns the information whether this polygon lies partially within the given polygon
225 : bool partialWithin(const AbstractPoly& poly, double offset = 0) const;
226 :
227 : /// @brief Returns the two lists made when this list vector is splitted at the given point
228 : std::pair<PositionVector, PositionVector> splitAt(double where, bool use2D = false) const;
229 :
230 : //// @brief Output operator
231 : friend std::ostream& operator<<(std::ostream& os, const PositionVector& geom);
232 :
233 : //// @brief check if two positions crosses
234 : bool crosses(const Position& p1, const Position& p2) const;
235 :
236 : //// @brief add an offset to all positions
237 : void add(double xoff, double yoff, double zoff);
238 :
239 : //// @brief add an offset to all positions
240 : void add(const Position& offset);
241 :
242 : //// @brief subtract an offset from all positions
243 : void sub(const Position& offset);
244 :
245 : //// @brief adds a position without modifying the vector itself but returning the result
246 : PositionVector added(const Position& offset) const;
247 :
248 : //// @brief mirror coordinates along the x-axis
249 : void mirrorX();
250 :
251 : //// @brief rotate all points around (0,0) in the plane by the given angle
252 : void rotate2D(double angle);
253 :
254 : //// @brief rotate all points around the given position in the plane by the given angle
255 : void rotate2D(const Position& pos, double angle);
256 :
257 : //// @brief rotate all points around the first element
258 : void rotateAroundFirstElement2D(double angle);
259 :
260 : //// @brief append the given vector to this one
261 : void append(const PositionVector& v, double sameThreshold = 2.0);
262 :
263 : //// @brief prepend the given vector to this one
264 : void prepend(const PositionVector& v, double sameThreshold = 2.0);
265 :
266 : /// @brief get subpart of a position vector
267 : PositionVector getSubpart(double beginOffset, double endOffset) const;
268 :
269 : /// @brief get subpart of a position vector in two dimensions (Z is ignored)
270 : PositionVector getSubpart2D(double beginOffset, double endOffset) const;
271 :
272 : /// @brief get subpart of a position vector using index and a cout
273 : PositionVector getSubpartByIndex(int beginIndex, int count) const;
274 :
275 : /// @brief sort as polygon CW by angle
276 : /// @remark this function works for non-convex polygons but won't possibly yield the desired polygon
277 : void sortAsPolyCWByAngle();
278 :
279 : /// @brief sort by increasing X-Y Positions
280 : void sortByIncreasingXY();
281 :
282 : /// @brief extrapolate position vector
283 : void extrapolate(const double val, const bool onlyFirst = false, const bool onlyLast = false);
284 :
285 : /// @brief extrapolate position vector in two dimensions (Z is ignored)
286 : void extrapolate2D(const double val, const bool onlyFirst = false);
287 :
288 : /// @brief reverse position vector
289 : PositionVector reverse() const;
290 :
291 : /// @brief get a side position of position vector using a offset
292 : static Position sideOffset(const Position& beg, const Position& end, const double amount);
293 :
294 : /// @brief move position vector to side using certain amount
295 : void move2side(double amount, double maxExtension = 100);
296 :
297 : /// @brief move position vector to side using a custom offset for each geometry point
298 : void move2sideCustom(std::vector<double> amount, double maxExtension = 100);
299 :
300 : /// @brief get angle in certain position of position vector (in radians between -M_PI and M_PI)
301 : double angleAt2D(int pos) const;
302 :
303 : /**@brief inserts p between the two closest positions
304 : * @param p position to be inserted
305 : * @param interpolateZ flag to enable/disable interpolation of Z Value between the two closest positions
306 : * @return the insertion index
307 : */
308 : int insertAtClosest(const Position& p, bool interpolateZ);
309 :
310 : /// @brief removes the point closest to p and return the removal index
311 : int removeClosest(const Position& p);
312 :
313 : /// @brief comparing operation
314 : bool operator==(const PositionVector& v2) const;
315 :
316 : /// @brief comparing operation
317 : bool operator!=(const PositionVector& v2) const;
318 :
319 : /// @brief subtracts two vectors (requires vectors of the same length)
320 : PositionVector operator-(const PositionVector& v2) const;
321 :
322 : /// @brief adds two vectors (requires vectors of the same length)
323 : PositionVector operator+(const PositionVector& v2) const;
324 :
325 : /// @brief class for CW Sorter
326 : class as_poly_cw_sorter {
327 : public:
328 : /// @brief constructor
329 : as_poly_cw_sorter();
330 :
331 : /// @brief comparing operation for sort
332 : int operator()(const Position& p1, const Position& p2) const;
333 :
334 : private:
335 : /// @brief computes the angle of the given vector, in the range $[0,2*\pi[$
336 : double atAngle2D(const Position& p) const;
337 : };
338 :
339 : /// @brief clase for increasing Sorter
340 : class increasing_x_y_sorter {
341 : public:
342 : /// constructor
343 : explicit increasing_x_y_sorter();
344 :
345 : /// comparing operation
346 : int operator()(const Position& p1, const Position& p2) const;
347 : };
348 :
349 : /// @brief get left
350 : /// @note previously marked with "!!!"
351 : double isLeft(const Position& P0, const Position& P1, const Position& P2) const;
352 :
353 : /// @brief returns the angle in radians of the line connecting the first and the last position
354 : double beginEndAngle() const;
355 :
356 : /// @brief return the nearest offest to point 2D
357 : double nearest_offset_to_point2D(const Position& p, bool perpendicular = true) const;
358 :
359 : /// @brief return the nearest offest to point 2D projected onto the 3D geometry
360 : double nearest_offset_to_point25D(const Position& p, bool perpendicular = true) const;
361 :
362 : /** @brief return position p within the length-wise coordinate system
363 : * defined by this position vector. The x value is the same as that returned
364 : * by nearest_offset_to_point2D(p) and the y value is the perpendicular distance to this
365 : * vector with the sign indicating the side (right is postive).
366 : * if extend is true, the vector is extended on both sides and the
367 : * x-coordinate of the result may be below 0 or above the length of the original vector
368 : */
369 : Position transformToVectorCoordinates(const Position& p, bool extend = false) const;
370 :
371 : /* @brief index of the closest position to p
372 : * @in twoD whether all positions should be projected onto the plan
373 : @note: may only be called for a non-empty vector
374 : */
375 : int indexOfClosest(const Position& p, bool twoD = false) const;
376 :
377 : /// @brief distances of all my points to s and all of s points to myself
378 : /// @note if perpendicular is set to true, only the perpendicular distances are returned
379 : std::vector<double> distances(const PositionVector& s, bool perpendicular = false) const;
380 :
381 : /// @brief closest 2D-distance to point p (or -1 if perpendicular is true and the point is beyond this vector)
382 : double distance2D(const Position& p, bool perpendicular = false) const;
383 :
384 : /// @brief insert in front a Position
385 : void push_front(const Position& p);
386 :
387 : /// @brief pop first Position
388 : void pop_front();
389 :
390 : /// @brief insert in back a non double position
391 : void push_back_noDoublePos(const Position& p);
392 :
393 : /// @brief insert in front a non double position
394 : void push_front_noDoublePos(const Position& p);
395 :
396 : /// @brief insert in front a non double position
397 : void insert_noDoublePos(const std::vector<Position>::iterator& at, const Position& p);
398 :
399 : /// @brief check if PositionVector is closed
400 : bool isClosed() const;
401 :
402 : /// @brief check if PositionVector is NAN
403 : bool isNAN() const;
404 :
405 : /// @brief round all coordinates to the given precision
406 : void round(int precision, bool avoidDegeneration = true);
407 :
408 : /// @brief ensure minimum length so that the geometry will not degenerate to 0-length on writing with the given precision
409 : void ensureMinLength(int precision);
410 :
411 : /** @brief Removes positions if too near
412 : * @param[in] minDist The minimum accepted distance; default: POSITION_EPS
413 : * @param[in] assertLength Whether the result must at least contain two points (be a line); default: false, to ensure original behaviour
414 : */
415 : void removeDoublePoints(double minDist = POSITION_EPS, bool assertLength = false, int beginOffset = 0, int endOffset = 0, bool resample = false);
416 :
417 : /// @brief return whether two positions differ in z-coordinate
418 : bool hasElevation() const;
419 :
420 : /// @brief return the same shape with intermediate colinear points removed
421 : PositionVector simplified() const;
422 : // test implementation of an alternative check
423 : const PositionVector simplified2(const bool closed, const double eps = NUMERICAL_EPS) const;
424 :
425 : /** @brief return orthogonal through p (extending this vector if necessary)
426 : * @param[in] p The point through which to draw the orthogonal
427 : * @param[in] extend how long to extend this vector for finding an orthogonal
428 : * @param[in] front Whether to take the segment before or after the base point in case of ambiguity
429 : * @param[in] length the length of the orthogonal
430 : * @param[in] deg the rotation angle relative to the shape direction
431 : */
432 : PositionVector getOrthogonal(const Position& p, double extend, bool before, double length = 1.0, double deg = 90) const;
433 :
434 : /// @brief returned vector that is smoothed at the front (within dist)
435 : PositionVector smoothedZFront(double dist = std::numeric_limits<double>::max()) const;
436 :
437 : /// @brief returned vector that varies z smoothly over its length
438 : PositionVector interpolateZ(double zStart, double zEnd) const;
439 :
440 : /**@brief resample shape (i.e. transform to segments, equal spacing)
441 : * @param[in] maxLength length of every segment
442 : * @param[in] adjustEnd enable or disable adjust end (i.e. result has the same original length, last segment could be short)
443 : */
444 : PositionVector resample(double maxLength, const bool adjustEnd) const;
445 :
446 : /// @brief return the offset at the given index
447 : double offsetAtIndex2D(int index) const;
448 :
449 : /* @brief return the maximum grade of all segments as a fraction of zRange/length2D
450 : * @param[out] maxJump The maximum vertical jump (with grade infinity)
451 : */
452 : double getMaxGrade(double& maxJump) const;
453 :
454 : /// @brief return minimum z-coordinate
455 : double getMinZ() const;
456 :
457 : /// @brief check if the two vectors have the same length and pairwise similar positions
458 : bool almostSame(const PositionVector& v2, double maxDiv = POSITION_EPS) const;
459 :
460 : /// @brief return a bezier interpolation
461 : PositionVector bezier(int numPoints);
462 :
463 : static double localAngle(const Position& from, const Position& pos, const Position& to);
464 :
465 : /* @brief checks if the polygon represented by the PositionVector is clockwise-oriented
466 : @remark this function works for non-convex polygons
467 : */
468 : bool isClockwiseOriented(void);
469 :
470 : private:
471 : /// @brief return whether the line segments defined by Line p11,p12 and Line p21,p22 intersect
472 : static bool intersects(const Position& p11, const Position& p12, const Position& p21, const Position& p22, const double withinDist = 0., double* x = 0, double* y = 0, double* mu = 0);
473 : };
|
