1 /********************************************************************** 2 * 3 * GEOS - Geometry Engine Open Source 4 * http://geos.osgeo.org 5 * 6 * Copyright (C) 2005-2006 Refractions Research Inc. 7 * Copyright (C) 2001-2002 Vivid Solutions Inc. 8 * 9 * This is free software; you can redistribute and/or modify it under 10 * the terms of the GNU Lesser General Public Licence as published 11 * by the Free Software Foundation. 12 * See the COPYING file for more information. 13 * 14 ********************************************************************** 15 * 16 * Last port: algorithm/RobustLineIntersector.java r785 (JTS-1.13+) 17 * 18 **********************************************************************/ 19 20 #ifndef GEOS_ALGORITHM_LINEINTERSECTOR_H 21 #define GEOS_ALGORITHM_LINEINTERSECTOR_H 22 23 #include <geos/export.h> 24 #include <string> 25 26 #include <geos/geom/Coordinate.h> 27 28 // Forward declarations 29 namespace geos { 30 namespace geom { 31 class PrecisionModel; 32 } 33 } 34 35 namespace geos { 36 namespace algorithm { // geos::algorithm 37 38 /** \brief 39 * A LineIntersector is an algorithm that can both test whether 40 * two line segments intersect and compute the intersection point 41 * if they do. 42 * 43 * The intersection point may be computed in a precise or non-precise manner. 44 * Computing it precisely involves rounding it to an integer. (This assumes 45 * that the input coordinates have been made precise by scaling them to 46 * an integer grid.) 47 * 48 */ 49 class GEOS_DLL LineIntersector { 50 public: 51 52 /// \brief 53 /// Return a Z value being the interpolation of Z from p0 and p1 at 54 /// the given point p 55 static double interpolateZ(const geom::Coordinate& p, const geom::Coordinate& p0, const geom::Coordinate& p1); 56 57 58 /// Computes the "edge distance" of an intersection point p in an edge. 59 /// 60 /// The edge distance is a metric of the point along the edge. 61 /// The metric used is a robust and easy to compute metric function. 62 /// It is <b>not</b> equivalent to the usual Euclidean metric. 63 /// It relies on the fact that either the x or the y ordinates of the 64 /// points in the edge are unique, depending on whether the edge is longer in 65 /// the horizontal or vertical direction. 66 /// 67 /// NOTE: This function may produce incorrect distances 68 /// for inputs where p is not precisely on p1-p2 69 /// (E.g. p = (139,9) p1 = (139,10), p2 = (280,1) produces distanct 70 /// 0.0, which is incorrect. 71 /// 72 /// My hypothesis is that the function is safe to use for points which are the 73 /// result of <b>rounding</b> points which lie on the line, 74 /// but not safe to use for <b>truncated</b> points. 75 /// 76 static double computeEdgeDistance(const geom::Coordinate& p, const geom::Coordinate& p0, const geom::Coordinate& p1); 77 78 static double nonRobustComputeEdgeDistance(const geom::Coordinate& p, const geom::Coordinate& p1, 79 const geom::Coordinate& p2); 80 81 LineIntersector(const geom::PrecisionModel* initialPrecisionModel = nullptr) 82 : precisionModel(initialPrecisionModel)83 precisionModel(initialPrecisionModel), 84 result(0), 85 isProperVar(false) 86 {} 87 ~LineIntersector()88 ~LineIntersector() {} 89 90 /** \brief 91 * Tests whether either intersection point is an interior point of 92 * one of the input segments. 93 * 94 * @return <code>true</code> if either intersection point is in 95 * the interior of one of the input segments 96 */ 97 bool isInteriorIntersection(); 98 99 /** \brief 100 * Tests whether either intersection point is an interior point 101 * of the specified input segment. 102 * 103 * @return <code>true</code> if either intersection point is in 104 * the interior of the input segment 105 */ 106 bool isInteriorIntersection(size_t inputLineIndex); 107 108 /// Force computed intersection to be rounded to a given precision model. 109 /// 110 /// No getter is provided, because the precision model is not required 111 /// to be specified. 112 /// @param newPM the PrecisionModel to use for rounding 113 /// 114 void setPrecisionModel(const geom::PrecisionModel * newPM)115 setPrecisionModel(const geom::PrecisionModel* newPM) 116 { 117 precisionModel = newPM; 118 } 119 120 /// Compute the intersection of a point p and the line p1-p2. 121 /// 122 /// This function computes the boolean value of the hasIntersection test. 123 /// The actual value of the intersection (if there is one) 124 /// is equal to the value of <code>p</code>. 125 /// 126 void computeIntersection(const geom::Coordinate& p, const geom::Coordinate& p1, const geom::Coordinate& p2); 127 128 /// Same as above but doesn't compute intersection point. Faster. 129 static bool hasIntersection(const geom::Coordinate& p, const geom::Coordinate& p1, const geom::Coordinate& p2); 130 131 enum intersection_type : uint8_t { 132 /// Indicates that line segments do not intersect 133 NO_INTERSECTION = 0, 134 135 /// Indicates that line segments intersect in a single point 136 POINT_INTERSECTION = 1, 137 138 /// Indicates that line segments intersect in a line segment 139 COLLINEAR_INTERSECTION = 2 140 }; 141 142 /// Computes the intersection of the lines p1-p2 and p3-p4 143 void computeIntersection(const geom::Coordinate& p1, const geom::Coordinate& p2, 144 const geom::Coordinate& p3, const geom::Coordinate& p4); 145 146 std::string toString() const; 147 148 /** 149 * Tests whether the input geometries intersect. 150 * 151 * @return true if the input geometries intersect 152 */ 153 bool hasIntersection()154 hasIntersection() const 155 { 156 return result != NO_INTERSECTION; 157 } 158 159 /// Returns the number of intersection points found. 160 /// 161 /// This will be either 0, 1 or 2. 162 /// 163 size_t getIntersectionNum()164 getIntersectionNum() const 165 { 166 return result; 167 } 168 169 170 /// Returns the intIndex'th intersection point 171 /// 172 /// @param intIndex is 0 or 1 173 /// 174 /// @return the intIndex'th intersection point 175 /// 176 const geom::Coordinate& getIntersection(size_t intIndex)177 getIntersection(size_t intIndex) const 178 { 179 return intPt[intIndex]; 180 } 181 182 /// Returns false if both numbers are zero. 183 /// 184 /// @return true if both numbers are positive or if both numbers are negative. 185 /// 186 static bool isSameSignAndNonZero(double a, double b); 187 188 /** \brief 189 * Test whether a point is a intersection point of two line segments. 190 * 191 * Note that if the intersection is a line segment, this method only tests for 192 * equality with the endpoints of the intersection segment. 193 * It does <b>not</b> return true if 194 * the input point is internal to the intersection segment. 195 * 196 * @return true if the input point is one of the intersection points. 197 */ 198 bool isIntersection(const geom::Coordinate& pt) const; 199 200 /** \brief 201 * Tests whether an intersection is proper. 202 * 203 * The intersection between two line segments is considered proper if 204 * they intersect in a single point in the interior of both segments 205 * (e.g. the intersection is a single point and is not equal to any of the 206 * endpoints). 207 * 208 * The intersection between a point and a line segment is considered proper 209 * if the point lies in the interior of the segment (e.g. is not equal to 210 * either of the endpoints). 211 * 212 * @return true if the intersection is proper 213 */ 214 bool isProper()215 isProper() const 216 { 217 return hasIntersection() && isProperVar; 218 } 219 220 /** \brief 221 * Computes the intIndex'th intersection point in the direction of 222 * a specified input line segment 223 * 224 * @param segmentIndex is 0 or 1 225 * @param intIndex is 0 or 1 226 * 227 * @return the intIndex'th intersection point in the direction of the 228 * specified input line segment 229 */ 230 const geom::Coordinate& getIntersectionAlongSegment(size_t segmentIndex, size_t intIndex); 231 232 /** \brief 233 * Computes the index of the intIndex'th intersection point in the direction of 234 * a specified input line segment 235 * 236 * @param segmentIndex is 0 or 1 237 * @param intIndex is 0 or 1 238 * 239 * @return the index of the intersection point along the segment (0 or 1) 240 */ 241 size_t getIndexAlongSegment(size_t segmentIndex, size_t intIndex); 242 243 /** \brief 244 * Computes the "edge distance" of an intersection point along the specified 245 * input line segment. 246 * 247 * @param geomIndex is 0 or 1 248 * @param intIndex is 0 or 1 249 * 250 * @return the edge distance of the intersection point 251 */ 252 double getEdgeDistance(size_t geomIndex, size_t intIndex) const; 253 254 private: 255 256 /** 257 * If makePrecise is true, computed intersection coordinates 258 * will be made precise using Coordinate#makePrecise 259 */ 260 const geom::PrecisionModel* precisionModel; 261 262 size_t result; 263 264 const geom::Coordinate* inputLines[2][2]; 265 266 /** 267 * We store real Coordinates here because 268 * we must compute the Z of intersection point. 269 */ 270 geom::Coordinate intPt[2]; 271 272 /** 273 * The indexes of the endpoints of the intersection lines, in order along 274 * the corresponding line 275 */ 276 size_t intLineIndex[2][2]; 277 278 bool isProperVar; 279 //Coordinate &pa; 280 //Coordinate &pb; 281 282 bool isCollinear()283 isCollinear() const 284 { 285 return result == COLLINEAR_INTERSECTION; 286 } 287 288 uint8_t computeIntersect(const geom::Coordinate& p1, const geom::Coordinate& p2, 289 const geom::Coordinate& q1, const geom::Coordinate& q2); 290 291 bool isEndPoint()292 isEndPoint() const 293 { 294 return hasIntersection() && !isProperVar; 295 } 296 297 void computeIntLineIndex(); 298 299 void computeIntLineIndex(size_t segmentIndex); 300 301 uint8_t computeCollinearIntersection(const geom::Coordinate& p1, const geom::Coordinate& p2, 302 const geom::Coordinate& q1, const geom::Coordinate& q2); 303 304 /** \brief 305 * This method computes the actual value of the intersection point. 306 * 307 * To obtain the maximum precision from the intersection calculation, 308 * the coordinates are normalized by subtracting the minimum 309 * ordinate values (in absolute value). This has the effect of 310 * removing common significant digits from the calculation to 311 * maintain more bits of precision. 312 */ 313 geom::Coordinate intersection(const geom::Coordinate& p1, 314 const geom::Coordinate& p2, 315 const geom::Coordinate& q1, 316 const geom::Coordinate& q2) const; 317 318 /** 319 * Test whether a point lies in the envelopes of both input segments. 320 * A correctly computed intersection point should return true 321 * for this test. 322 * Since this test is for debugging purposes only, no attempt is 323 * made to optimize the envelope test. 324 * 325 * @return true if the input point lies within both 326 * input segment envelopes 327 */ 328 bool isInSegmentEnvelopes(const geom::Coordinate& intPt) const; 329 330 331 /** 332 * Computes a segment intersection. 333 * Round-off error can cause the raw computation to fail, 334 * (usually due to the segments being approximately parallel). 335 * If this happens, a reasonable approximation is computed instead. 336 * 337 * @param p1 a segment endpoint 338 * @param p2 a segment endpoint 339 * @param q1 a segment endpoint 340 * @param q2 a segment endpoint 341 * @return the computed intersection point is stored there 342 */ 343 geom::Coordinate intersectionSafe(const geom::Coordinate& p1, const geom::Coordinate& p2, 344 const geom::Coordinate& q1, const geom::Coordinate& q2) const; 345 346 /** 347 * Finds the endpoint of the segments P and Q which 348 * is closest to the other segment. 349 * This is a reasonable surrogate for the true 350 * intersection points in ill-conditioned cases 351 * (e.g. where two segments are nearly coincident, 352 * or where the endpoint of one segment lies almost on the other segment). 353 * <p> 354 * This replaces the older CentralEndpoint heuristic, 355 * which chose the wrong endpoint in some cases 356 * where the segments had very distinct slopes 357 * and one endpoint lay almost on the other segment. 358 * 359 * @param p1 an endpoint of segment P 360 * @param p2 an endpoint of segment P 361 * @param q1 an endpoint of segment Q 362 * @param q2 an endpoint of segment Q 363 * @return the nearest endpoint to the other segment 364 */ 365 static geom::Coordinate nearestEndpoint(const geom::Coordinate& p1, 366 const geom::Coordinate& p2, 367 const geom::Coordinate& q1, 368 const geom::Coordinate& q2); 369 370 static double zGet(const geom::Coordinate& p, const geom::Coordinate& q); 371 372 static double zGetOrInterpolate(const geom::Coordinate& p, 373 const geom::Coordinate& p0, 374 const geom::Coordinate& p1); 375 376 static geom::Coordinate zGetOrInterpolateCopy(const geom::Coordinate& p, 377 const geom::Coordinate& p0, 378 const geom::Coordinate& p1); 379 380 /// \brief 381 /// Return a Z value being the interpolation of Z from p0 to p1 at 382 /// the given point p 383 static double zInterpolate(const geom::Coordinate& p, 384 const geom::Coordinate& p0, 385 const geom::Coordinate& p1); 386 387 static double zInterpolate(const geom::Coordinate& p, 388 const geom::Coordinate& p1, 389 const geom::Coordinate& p2, 390 const geom::Coordinate& q1, 391 const geom::Coordinate& q2); 392 393 }; 394 395 396 } // namespace geos::algorithm 397 } // namespace geos 398 399 400 #endif // GEOS_ALGORITHM_LINEINTERSECTOR_H 401 402