GEOS  3.11.0rc0
LineIntersector.h
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 #pragma once
21 
22 #include <geos/export.h>
23 #include <geos/algorithm/Intersection.h>
24 #include <geos/geom/Coordinate.h>
25 #include <geos/geom/Envelope.h>
26 
27 #include <string>
28 
29 // Forward declarations
30 namespace geos {
31 namespace geom {
32 class PrecisionModel;
33 }
34 }
35 
36 namespace geos {
37 namespace algorithm { // geos::algorithm
38 
50 class GEOS_DLL LineIntersector {
51 public:
52 
56  static double interpolateZ(const geom::Coordinate& p, const geom::Coordinate& p0, const geom::Coordinate& p1);
57 
58 
77  static double computeEdgeDistance(const geom::Coordinate& p, const geom::Coordinate& p0, const geom::Coordinate& p1);
78 
79  static double nonRobustComputeEdgeDistance(const geom::Coordinate& p, const geom::Coordinate& p1,
80  const geom::Coordinate& p2);
81 
82  explicit LineIntersector(const geom::PrecisionModel* initialPrecisionModel = nullptr)
83  :
84  precisionModel(initialPrecisionModel),
85  result(0),
86  inputLines(),
87  isProperVar(false)
88  {}
89 
90  ~LineIntersector() = default;
91 
100  {
101  if(isInteriorIntersection(0)) {
102  return true;
103  }
104  if(isInteriorIntersection(1)) {
105  return true;
106  }
107  return false;
108  };
109 
117  bool isInteriorIntersection(std::size_t inputLineIndex)
118  {
119  for(std::size_t i = 0; i < result; ++i) {
120  if(!(intPt[i].equals2D(*inputLines[inputLineIndex][0])
121  || intPt[i].equals2D(*inputLines[inputLineIndex][1]))) {
122  return true;
123  }
124  }
125  return false;
126  };
127 
134  void
136  {
137  precisionModel = newPM;
138  }
139 
147 
149  static bool hasIntersection(const geom::Coordinate& p, const geom::Coordinate& p1, const geom::Coordinate& p2);
150 
151  enum intersection_type : uint8_t {
153  NO_INTERSECTION = 0,
154 
156  POINT_INTERSECTION = 1,
157 
159  COLLINEAR_INTERSECTION = 2
160  };
161 
164  const geom::Coordinate& p3, const geom::Coordinate& p4);
165 
166  std::string toString() const;
167 
173  bool
175  {
176  return result != NO_INTERSECTION;
177  }
178 
179 
187  const geom::Coordinate*
188  getEndpoint(std::size_t segmentIndex, std::size_t ptIndex) const
189  {
190  return inputLines[segmentIndex][ptIndex];
191  }
192 
197  size_t
199  {
200  return result;
201  }
202 
203 
210  const geom::Coordinate&
211  getIntersection(std::size_t intIndex) const
212  {
213  return intPt[intIndex];
214  }
215 
220  static bool isSameSignAndNonZero(double a, double b);
221 
232  bool isIntersection(const geom::Coordinate& pt) const
233  {
234  for(std::size_t i = 0; i < result; ++i) {
235  if(intPt[i].equals2D(pt)) {
236  return true;
237  }
238  }
239  return false;
240  };
241 
256  bool
257  isProper() const
258  {
259  return hasIntersection() && isProperVar;
260  }
261 
272  const geom::Coordinate& getIntersectionAlongSegment(std::size_t segmentIndex, std::size_t intIndex);
273 
283  std::size_t getIndexAlongSegment(std::size_t segmentIndex, std::size_t intIndex);
284 
294  double getEdgeDistance(std::size_t geomIndex, std::size_t intIndex) const;
295 
296 private:
297 
302  const geom::PrecisionModel* precisionModel;
303 
304  std::size_t result;
305 
306  const geom::Coordinate* inputLines[2][2];
307 
312  geom::Coordinate intPt[2];
313 
318  std::size_t intLineIndex[2][2];
319 
320  bool isProperVar;
321  //Coordinate &pa;
322  //Coordinate &pb;
323 
324  bool
325  isCollinear() const
326  {
327  return result == COLLINEAR_INTERSECTION;
328  }
329 
330  uint8_t computeIntersect(const geom::Coordinate& p1, const geom::Coordinate& p2,
331  const geom::Coordinate& q1, const geom::Coordinate& q2);
332 
333  bool
334  isEndPoint() const
335  {
336  return hasIntersection() && !isProperVar;
337  }
338 
339  void computeIntLineIndex();
340 
341  void computeIntLineIndex(std::size_t segmentIndex);
342 
343  uint8_t computeCollinearIntersection(const geom::Coordinate& p1, const geom::Coordinate& p2,
344  const geom::Coordinate& q1, const geom::Coordinate& q2);
345 
355  geom::Coordinate intersection(const geom::Coordinate& p1,
356  const geom::Coordinate& p2,
357  const geom::Coordinate& q1,
358  const geom::Coordinate& q2) const;
359 
370  bool isInSegmentEnvelopes(const geom::Coordinate& pt) const
371  {
372  geom::Envelope env0(*inputLines[0][0], *inputLines[0][1]);
373  geom::Envelope env1(*inputLines[1][0], *inputLines[1][1]);
374  return env0.contains(pt) && env1.contains(pt);
375  };
376 
389  geom::Coordinate intersectionSafe(const geom::Coordinate& p1, const geom::Coordinate& p2,
390  const geom::Coordinate& q1, const geom::Coordinate& q2) const
391  {
392  geom::Coordinate ptInt = Intersection::intersection(p1, p2, q1, q2);
393  if (ptInt.isNull()) {
394  ptInt = nearestEndpoint(p1, p2, q1, q2);
395  }
396  return ptInt;
397  };
398 
418  static geom::Coordinate nearestEndpoint(const geom::Coordinate& p1,
419  const geom::Coordinate& p2,
420  const geom::Coordinate& q1,
421  const geom::Coordinate& q2);
422 
423  static double zGet(
424  const geom::Coordinate& p,
425  const geom::Coordinate& q)
426  {
427  double z = p.z;
428  if ( std::isnan(z) ) {
429  z = q.z; // may be NaN
430  }
431  return z;
432  };
433 
434  static double zGetOrInterpolate(
435  const geom::Coordinate& p,
436  const geom::Coordinate& p1,
437  const geom::Coordinate& p2)
438  {
439  double z = p.z;
440  if (! std::isnan(z) ) return z;
441  return zInterpolate(p, p1, p2); // may be NaN
442  };
443 
444  static geom::Coordinate zGetOrInterpolateCopy(
445  const geom::Coordinate& p,
446  const geom::Coordinate& p1,
447  const geom::Coordinate& p2)
448  {
449  geom::Coordinate pCopy = p;
450  double z = zGetOrInterpolate(p, p1, p2);
451  pCopy.z = z;
452  return pCopy;
453  };
454 
458  static double zInterpolate(const geom::Coordinate& p,
459  const geom::Coordinate& p0,
460  const geom::Coordinate& p1);
461 
462  static double zInterpolate(const geom::Coordinate& p,
463  const geom::Coordinate& p1,
464  const geom::Coordinate& p2,
465  const geom::Coordinate& q1,
466  const geom::Coordinate& q2);
467 
468 };
469 
470 
471 } // namespace geos::algorithm
472 } // namespace geos
473 
474 
475 
476 
477 
478 
479 
480 
481 
482 
483 
484 
485 
486 
487 
488 
A LineIntersector is an algorithm that can both test whether two line segments intersect and compute ...
Definition: LineIntersector.h:50
intersection_type
Definition: LineIntersector.h:151
void computeIntersection(const geom::Coordinate &p1, const geom::Coordinate &p2, const geom::Coordinate &p3, const geom::Coordinate &p4)
Computes the intersection of the lines p1-p2 and p3-p4.
const geom::Coordinate * getEndpoint(std::size_t segmentIndex, std::size_t ptIndex) const
Definition: LineIntersector.h:188
const geom::Coordinate & getIntersectionAlongSegment(std::size_t segmentIndex, std::size_t intIndex)
Computes the intIndex'th intersection point in the direction of a specified input line segment.
static bool hasIntersection(const geom::Coordinate &p, const geom::Coordinate &p1, const geom::Coordinate &p2)
Same as above but doesn't compute intersection point. Faster.
bool isInteriorIntersection(std::size_t inputLineIndex)
Tests whether either intersection point is an interior point of the specified input segment.
Definition: LineIntersector.h:117
void setPrecisionModel(const geom::PrecisionModel *newPM)
Definition: LineIntersector.h:135
bool isInteriorIntersection()
Tests whether either intersection point is an interior point of one of the input segments.
Definition: LineIntersector.h:99
const geom::Coordinate & getIntersection(std::size_t intIndex) const
Definition: LineIntersector.h:211
bool hasIntersection() const
Definition: LineIntersector.h:174
static bool isSameSignAndNonZero(double a, double b)
void computeIntersection(const geom::Coordinate &p, const geom::Coordinate &p1, const geom::Coordinate &p2)
bool isProper() const
Tests whether an intersection is proper.
Definition: LineIntersector.h:257
static double computeEdgeDistance(const geom::Coordinate &p, const geom::Coordinate &p0, const geom::Coordinate &p1)
static double interpolateZ(const geom::Coordinate &p, const geom::Coordinate &p0, const geom::Coordinate &p1)
Return a Z value being the interpolation of Z from p0 and p1 at the given point p.
size_t getIntersectionNum() const
Definition: LineIntersector.h:198
double getEdgeDistance(std::size_t geomIndex, std::size_t intIndex) const
Computes the "edge distance" of an intersection point along the specified input line segment.
std::size_t getIndexAlongSegment(std::size_t segmentIndex, std::size_t intIndex)
Computes the index of the intIndex'th intersection point in the direction of a specified input line s...
bool isIntersection(const geom::Coordinate &pt) const
Test whether a point is a intersection point of two line segments.
Definition: LineIntersector.h:232
Coordinate is the lightweight class used to store coordinates.
Definition: Coordinate.h:58
An Envelope defines a rectangulare region of the 2D coordinate plane.
Definition: Envelope.h:58
Specifies the precision model of the Coordinate in a Geometry.
Definition: PrecisionModel.h:90
Basic namespace for all GEOS functionalities.
Definition: Angle.h:25