File Coverage

/usr/local/lib/perl5/site_perl/5.26.1/x86_64-linux/CPP/geos.x/i/geos/algorithm/LineIntersector.h
Criterion Covered Total %
statement 11 11 100.0
branch 4 6 66.6
condition n/a
subroutine n/a
pod n/a
total 15 17 88.2


line stmt bran cond sub pod time code
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
24             #include
25              
26             #include
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 not 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 rounding points which lie on the line,
74             /// but not safe to use for truncated 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,const geom::Coordinate& p2);
79              
80 18           LineIntersector(const geom::PrecisionModel* initialPrecisionModel=nullptr)
81             :
82             precisionModel(initialPrecisionModel),
83             result(0),
84 54 100         isProperVar(false)
85 18           {}
86              
87 16           ~LineIntersector() {}
88              
89             /** \brief
90             * Tests whether either intersection point is an interior point of
91             * one of the input segments.
92             *
93             * @return true if either intersection point is in
94             * the interior of one of the input segments
95             */
96             bool isInteriorIntersection();
97              
98             /** \brief
99             * Tests whether either intersection point is an interior point
100             * of the specified input segment.
101             *
102             * @return true if either intersection point is in
103             * the interior of the input segment
104             */
105             bool isInteriorIntersection(int inputLineIndex);
106              
107             /// Force computed intersection to be rounded to a given precision model.
108             //
109             /// No getter is provided, because the precision model is not required
110             /// to be specified.
111             /// @param precisionModel the PrecisionModel to use for rounding
112             ///
113 3           void setPrecisionModel(const geom::PrecisionModel *newPM) {
114 3           precisionModel=newPM;
115 3           }
116              
117             /// Compute the intersection of a point p and the line p1-p2.
118             //
119             /// This function computes the boolean value of the hasIntersection test.
120             /// The actual value of the intersection (if there is one)
121             /// is equal to the value of p.
122             ///
123             void computeIntersection(const geom::Coordinate& p, const geom::Coordinate& p1, const geom::Coordinate& p2);
124              
125             /// Same as above but doen's compute intersection point. Faster.
126             static bool hasIntersection(const geom::Coordinate& p,const geom::Coordinate& p1,const geom::Coordinate& p2);
127              
128             // These are deprecated, due to ambiguous naming
129             enum {
130             DONT_INTERSECT=0,
131             DO_INTERSECT=1,
132             COLLINEAR=2
133             };
134              
135             enum {
136             /// Indicates that line segments do not intersect
137             NO_INTERSECTION=0,
138              
139             /// Indicates that line segments intersect in a single point
140             POINT_INTERSECTION=1,
141              
142             /// Indicates that line segments intersect in a line segment
143             COLLINEAR_INTERSECTION=2
144             };
145              
146             /// Computes the intersection of the lines p1-p2 and p3-p4
147             void computeIntersection(const geom::Coordinate& p1, const geom::Coordinate& p2,
148             const geom::Coordinate& p3, const geom::Coordinate& p4);
149              
150             std::string toString() const;
151              
152             /**
153             * Tests whether the input geometries intersect.
154             *
155             * @return true if the input geometries intersect
156             */
157 12           bool hasIntersection() const { return result!=NO_INTERSECTION; }
158              
159             /// Returns the number of intersection points found.
160             //
161             /// This will be either 0, 1 or 2.
162             ///
163 2           int getIntersectionNum() const { return result; }
164              
165              
166             /// Returns the intIndex'th intersection point
167             //
168             /// @param intIndex is 0 or 1
169             ///
170             /// @return the intIndex'th intersection point
171             ///
172             const geom::Coordinate& getIntersection(int intIndex) const {
173             return intPt[intIndex];
174             }
175              
176             /// Returns false if both numbers are zero.
177             //
178             /// @return true if both numbers are positive or if both numbers are negative.
179             ///
180             static bool isSameSignAndNonZero(double a,double b);
181              
182             /** \brief
183             * Test whether a point is a intersection point of two line segments.
184             *
185             * Note that if the intersection is a line segment, this method only tests for
186             * equality with the endpoints of the intersection segment.
187             * It does not return true if
188             * the input point is internal to the intersection segment.
189             *
190             * @return true if the input point is one of the intersection points.
191             */
192             bool isIntersection(const geom::Coordinate& pt) const;
193              
194             /** \brief
195             * Tests whether an intersection is proper.
196             *
197             * The intersection between two line segments is considered proper if
198             * they intersect in a single point in the interior of both segments
199             * (e.g. the intersection is a single point and is not equal to any of the
200             * endpoints).
201             *
202             * The intersection between a point and a line segment is considered proper
203             * if the point lies in the interior of the segment (e.g. is not equal to
204             * either of the endpoints).
205             *
206             * @return true if the intersection is proper
207             */
208 1           bool isProper() const {
209 1 50         return hasIntersection()&&isProperVar;
    50          
210             }
211              
212             /** \brief
213             * Computes the intIndex'th intersection point in the direction of
214             * a specified input line segment
215             *
216             * @param segmentIndex is 0 or 1
217             * @param intIndex is 0 or 1
218             *
219             * @return the intIndex'th intersection point in the direction of the
220             * specified input line segment
221             */
222             const geom::Coordinate& getIntersectionAlongSegment(int segmentIndex,int intIndex);
223              
224             /** \brief
225             * Computes the index of the intIndex'th intersection point in the direction of
226             * a specified input line segment
227             *
228             * @param segmentIndex is 0 or 1
229             * @param intIndex is 0 or 1
230             *
231             * @return the index of the intersection point along the segment (0 or 1)
232             */
233             int getIndexAlongSegment(int segmentIndex,int intIndex);
234              
235             /** \brief
236             * Computes the "edge distance" of an intersection point along the specified
237             * input line segment.
238             *
239             * @param segmentIndex is 0 or 1
240             * @param intIndex is 0 or 1
241             *
242             * @return the edge distance of the intersection point
243             */
244             double getEdgeDistance(int geomIndex,int intIndex) const;
245              
246             private:
247              
248             void intersectionWithNormalization(const geom::Coordinate& p1,
249             const geom::Coordinate& p2,
250             const geom::Coordinate& q1,
251             const geom::Coordinate& q2,
252             geom::Coordinate &ret) const;
253              
254             /**
255             * If makePrecise is true, computed intersection coordinates
256             * will be made precise using Coordinate#makePrecise
257             */
258             const geom::PrecisionModel *precisionModel;
259              
260             int result;
261              
262             const geom::Coordinate *inputLines[2][2];
263              
264             /**
265             * We store real Coordinates here because
266             * we must compute the Z of intersection point.
267             */
268             geom::Coordinate intPt[2];
269              
270             /**
271             * The indexes of the endpoints of the intersection lines, in order along
272             * the corresponding line
273             */
274             int intLineIndex[2][2];
275              
276             bool isProperVar;
277             //Coordinate &pa;
278             //Coordinate &pb;
279              
280             bool isCollinear() const { return result==COLLINEAR_INTERSECTION; }
281              
282             int computeIntersect(const geom::Coordinate& p1,const geom::Coordinate& p2,const geom::Coordinate& q1,const geom::Coordinate& q2);
283              
284             bool isEndPoint() const {
285             return hasIntersection()&&!isProperVar;
286             }
287              
288             void computeIntLineIndex();
289              
290             void computeIntLineIndex(int segmentIndex);
291              
292             int computeCollinearIntersection(const geom::Coordinate& p1,
293             const geom::Coordinate& p2, const geom::Coordinate& q1,
294             const geom::Coordinate& q2);
295              
296             /** \brief
297             * This method computes the actual value of the intersection point.
298             *
299             * To obtain the maximum precision from the intersection calculation,
300             * the coordinates are normalized by subtracting the minimum
301             * ordinate values (in absolute value). This has the effect of
302             * removing common significant digits from the calculation to
303             * maintain more bits of precision.
304             */
305             void intersection(const geom::Coordinate& p1,
306             const geom::Coordinate& p2,
307             const geom::Coordinate& q1,
308             const geom::Coordinate& q2,
309             geom::Coordinate &ret) const;
310              
311             double smallestInAbsValue(double x1, double x2,
312             double x3, double x4) const;
313              
314             /**
315             * Test whether a point lies in the envelopes of both input segments.
316             * A correctly computed intersection point should return true
317             * for this test.
318             * Since this test is for debugging purposes only, no attempt is
319             * made to optimize the envelope test.
320             *
321             * @return true if the input point lies within both
322             * input segment envelopes
323             */
324             bool isInSegmentEnvelopes(const geom::Coordinate& intPt) const;
325              
326             /** \brief
327             * Normalize the supplied coordinates to
328             * so that the midpoint of their intersection envelope
329             * lies at the origin.
330             *
331             * @param n00
332             * @param n01
333             * @param n10
334             * @param n11
335             * @param normPt
336             */
337             void normalizeToEnvCentre(geom::Coordinate &n00, geom::Coordinate &n01,
338             geom::Coordinate &n10, geom::Coordinate &n11,
339             geom::Coordinate &normPt) const;
340              
341             /**
342             * Computes a segment intersection using homogeneous coordinates.
343             * Round-off error can cause the raw computation to fail,
344             * (usually due to the segments being approximately parallel).
345             * If this happens, a reasonable approximation is computed instead.
346             *
347             * @param p1 a segment endpoint
348             * @param p2 a segment endpoint
349             * @param q1 a segment endpoint
350             * @param q2 a segment endpoint
351             * @param intPt the computed intersection point is stored there
352             */
353             void safeHCoordinateIntersection(const geom::Coordinate& p1,
354             const geom::Coordinate& p2,
355             const geom::Coordinate& q1,
356             const geom::Coordinate& q2,
357             geom::Coordinate& intPt) const;
358              
359             };
360              
361             } // namespace geos::algorithm
362             } // namespace geos
363              
364              
365             #endif // GEOS_ALGORITHM_LINEINTERSECTOR_H
366