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