1 //
2 // Ported from JTS junit/algorithm/RobustLineIntersectionTest.java r788
3 
4 #include <tut/tut.hpp>
5 // geos
6 #include <geos/io/WKTReader.h>
7 #include <geos/algorithm/LineIntersector.h>
8 #include <geos/geom/PrecisionModel.h>
9 #include <geos/geom/GeometryFactory.h>
10 #include <geos/geom/Geometry.h> // required for use in unique_ptr
11 #include <geos/geom/LineString.h>
12 #include <geos/geom/Coordinate.h>
13 // std
14 #include <sstream>
15 #include <string>
16 #include <memory>
17 
18 namespace geos {
19 namespace geom {
20 class Geometry;
21 }
22 }
23 
24 using namespace geos::geom; //
25 
26 namespace tut {
27 //
28 // Test Group
29 //
30 
31 struct test_robustlineintersection_data {
32     typedef std::unique_ptr<Geometry> GeomPtr;
33 
34     bool
equalstut::test_robustlineintersection_data35     equals(const Coordinate& p0, const Coordinate& p1,
36            double distanceTolerance)
37     {
38         return p0.distance(p1) <= distanceTolerance;
39     }
40 
41     void
checkIntPointstut::test_robustlineintersection_data42     checkIntPoints(const Coordinate& p, const Coordinate& q,
43                    double distanceTolerance)
44     {
45         bool isEqual = equals(p, q, distanceTolerance);
46         ensure("checkIntPoints: expected: " + p.toString() + " obtained " + q.toString(), isEqual);
47     }
48 
49     /**
50      *
51      * @param pt array of 4 Coordinates
52      * @param expectedIntersectionNum
53      * @param intPt the expected intersection points
54      *              (maybe null if not tested)
55      *              must contain at least expectedIntersectionNum
56      *              elements
57      */
58     void
checkIntersectiontut::test_robustlineintersection_data59     checkIntersection(const std::vector<Coordinate>& pt,
60                       size_t expectedIntersectionNum,
61                       const std::vector<Coordinate>& intPt,
62                       double distanceTolerance)
63     {
64         geos::algorithm::LineIntersector li;
65         li.computeIntersection(pt[0], pt[1], pt[2], pt[3]);
66 
67         auto intNum = li.getIntersectionNum();
68         ensure_equals(intNum, expectedIntersectionNum);
69 
70         if(intPt.empty()) {
71             return;
72         }
73 
74         ensure_equals(intPt.size(), intNum);
75 
76         // test that both points are represented here
77         //bool isIntPointsCorrect = true;
78         if(intNum == 1) {
79             checkIntPoints(intPt[0], li.getIntersection(0),
80                            distanceTolerance);
81         }
82         else if(intNum == 2) {
83             checkIntPoints(intPt[0], li.getIntersection(0),
84                            distanceTolerance);
85             checkIntPoints(intPt[1], li.getIntersection(0),
86                            distanceTolerance);
87 
88             if(!(
89                         equals(intPt[0], li.getIntersection(0), distanceTolerance)
90                         ||
91                         equals(intPt[0], li.getIntersection(1), distanceTolerance))) {
92                 checkIntPoints(intPt[0], li.getIntersection(0),
93                                distanceTolerance);
94                 checkIntPoints(intPt[0], li.getIntersection(1),
95                                distanceTolerance);
96             }
97 
98             else if(!(
99                         equals(intPt[1], li.getIntersection(0), distanceTolerance)
100                         ||
101                         equals(intPt[1], li.getIntersection(1), distanceTolerance))) {
102                 checkIntPoints(intPt[1], li.getIntersection(0),
103                                distanceTolerance);
104                 checkIntPoints(intPt[1], li.getIntersection(1),
105                                distanceTolerance);
106             }
107         }
108         //assertTrue("Int Pts not equal", isIntPointsCorrect);
109     }
110 
111     void
checkIntersectiontut::test_robustlineintersection_data112     checkIntersection(const std::string& wkt1,
113                       const std::string& wkt2,
114                       int expectedIntersectionNum,
115                       const std::string& expectedWKT,
116                       double distanceTolerance)
117     //throws ParseException
118     {
119         GeomPtr g1(reader.read(wkt1));
120         GeomPtr g2(reader.read(wkt2));
121 
122         LineString* l1ptr = dynamic_cast<LineString*>(g1.get());
123         LineString* l2ptr = dynamic_cast<LineString*>(g2.get());
124 
125         ensure(nullptr != l1ptr);
126         ensure(nullptr != l2ptr);
127 
128         LineString& l1 = *l1ptr;
129         LineString& l2 = *l2ptr;
130 
131         std::vector<Coordinate> pt;
132         pt.push_back(l1.getCoordinateN(0));
133         pt.push_back(l1.getCoordinateN(1));
134         pt.push_back(l2.getCoordinateN(0));
135         pt.push_back(l2.getCoordinateN(1));
136 
137         GeomPtr g(reader.read(expectedWKT));
138 
139         std::unique_ptr<CoordinateSequence> cs(g->getCoordinates());
140 
141         std::vector<Coordinate> intPt;
142         for(size_t i = 0; i < cs->size(); ++i) {
143             intPt.push_back(cs->getAt(i));
144         }
145 
146         checkIntersection(pt, expectedIntersectionNum,
147                           intPt, distanceTolerance);
148     }
149 
150     void
checkIntersectiontut::test_robustlineintersection_data151     checkIntersection(const std::string& wkt1,
152                       const std::string& wkt2,
153                       int expectedIntersectionNum,
154                       const std::vector<Coordinate>& intPt,
155                       double distanceTolerance)
156     // throws ParseException
157     {
158         GeomPtr g1(reader.read(wkt1));
159         GeomPtr g2(reader.read(wkt2));
160 
161         LineString* l1ptr = dynamic_cast<LineString*>(g1.get());
162         LineString* l2ptr = dynamic_cast<LineString*>(g2.get());
163 
164         ensure(nullptr != l1ptr);
165         ensure(nullptr != l2ptr);
166 
167         LineString& l1 = *l1ptr;
168         LineString& l2 = *l2ptr;
169 
170         std::vector<Coordinate> pt;
171         pt.push_back(l1.getCoordinateN(0));
172         pt.push_back(l1.getCoordinateN(1));
173         pt.push_back(l2.getCoordinateN(0));
174         pt.push_back(l2.getCoordinateN(1));
175 
176         checkIntersection(pt, expectedIntersectionNum,
177                           intPt, distanceTolerance);
178     }
179 
180     void
checkIntersectionNonetut::test_robustlineintersection_data181     checkIntersectionNone(const std::string& wkt1,
182                           const std::string& wkt2)
183     // throws ParseException
184     {
185         GeomPtr g1(reader.read(wkt1));
186         GeomPtr g2(reader.read(wkt2));
187 
188         LineString* l1ptr = dynamic_cast<LineString*>(g1.get());
189         LineString* l2ptr = dynamic_cast<LineString*>(g2.get());
190 
191         ensure(nullptr != l1ptr);
192         ensure(nullptr != l2ptr);
193 
194         LineString& l1 = *l1ptr;
195         LineString& l2 = *l2ptr;
196 
197         std::vector<Coordinate> pt;
198         pt.push_back(l1.getCoordinateN(0));
199         pt.push_back(l1.getCoordinateN(1));
200         pt.push_back(l2.getCoordinateN(0));
201         pt.push_back(l2.getCoordinateN(1));
202 
203         std::vector<Coordinate> intPt;
204         checkIntersection(pt, 0, intPt, 0);
205     }
206 
207     void
checkInputNotAlteredtut::test_robustlineintersection_data208     checkInputNotAltered(const std::string& wkt1, const std::string& wkt2, int scaleFactor)
209     {
210         GeomPtr g1(reader.read(wkt1));
211         GeomPtr g2(reader.read(wkt2));
212 
213         LineString* l1ptr = dynamic_cast<LineString*>(g1.get());
214         LineString* l2ptr = dynamic_cast<LineString*>(g2.get());
215 
216         ensure(nullptr != l1ptr);
217         ensure(nullptr != l2ptr);
218 
219         LineString& l1 = *l1ptr;
220         LineString& l2 = *l2ptr;
221 
222         std::vector<Coordinate> pt;
223         pt.push_back(l1.getCoordinateN(0));
224         pt.push_back(l1.getCoordinateN(1));
225         pt.push_back(l2.getCoordinateN(0));
226         pt.push_back(l2.getCoordinateN(1));
227         checkInputNotAltered(pt, scaleFactor);
228     }
229 
230     void
checkInputNotAlteredtut::test_robustlineintersection_data231     checkInputNotAltered(const std::vector<Coordinate>& pt, int scaleFactor)
232     {
233         // save input points
234         std::vector<Coordinate> savePt = pt;
235 
236         geos::algorithm::LineIntersector li;
237         PrecisionModel lpm(scaleFactor);
238         li.setPrecisionModel(&lpm);
239         li.computeIntersection(pt[0], pt[1], pt[2], pt[3]);
240 
241         // check that input points are unchanged
242         for(int i = 0; i < 4; i++) {
243             ensure_equals(savePt[i], pt[i]);
244         }
245     }
246 
247 
248 
test_robustlineintersection_datatut::test_robustlineintersection_data249     test_robustlineintersection_data()
250         :
251         pm(),
252         gf(GeometryFactory::create(&pm)),
253         reader(gf.get())
254     {
255     }
256 
257     PrecisionModel pm;
258     GeometryFactory::Ptr gf;
259     geos::io::WKTReader reader;
260 
261 };
262 
263 typedef test_group<test_robustlineintersection_data> group;
264 typedef group::object object;
265 
266 group test_robustlineintersection_group(
267     "geos::algorithm::RobustLineIntersection");
268 
269 
270 //
271 // Test Cases
272 //
273 
274 // 1 - Test from strk which is bad in GEOS (2009-04-14).
275 template<>
276 template<>
test()277 void object::test<1>
278 ()
279 {
280     checkIntersection(
281         "LINESTRING (588750.7429703881 4518950.493668233, 588748.2060409798 4518933.9452804085)",
282         "LINESTRING (588745.824857241 4518940.742239175, 588748.2060437313 4518933.9452791475)",
283         1,
284         "POINT (588748.2060416829 4518933.945284994)",
285         0);
286 }
287 
288 // 2 - Test from strk which is bad in GEOS (2009-04-14).
289 template<>
290 template<>
test()291 void object::test<2>
292 ()
293 {
294     checkIntersection(
295         "LINESTRING (588743.626135934 4518924.610969561, 588732.2822865889 4518925.4314047815)",
296         "LINESTRING (588739.1191384895 4518927.235700594, 588731.7854614238 4518924.578370095)",
297         1,
298         "POINT (588733.8306132929 4518925.319423238)",
299         0);
300 }
301 
302 // 3 - DaveSkeaCase
303 //
304 // This used to be a failure case (exception),
305 // but apparently works now.
306 // Possibly normalization has fixed this?
307 //
308 #if 0 // fails: finds 1 intersection rather then two
309 template<>
310 template<>
311 void object::test<3>
312 ()
313 {
314     std::vector<Coordinate> intPt;
315     intPt.push_back(Coordinate(2089426.5233462777, 1180182.3877339689));
316     intPt.push_back(Coordinate(2085646.6891757075, 1195618.7333999649));
317 
318     checkIntersection(
319         "LINESTRING ( 2089426.5233462777 1180182.3877339689, 2085646.6891757075 1195618.7333999649 )",
320         "LINESTRING ( 1889281.8148903656 1997547.0560044837, 2259977.3672235999 483675.17050843034 )",
321         2,
322         intPt, 0);
323 }
324 #endif // fails
325 
326 #if 0 // fails: the intersection point doesn't match
327 // 4 - Outside envelope using HCoordinate method (testCmp5CaseWKT)
328 template<>
329 template<>
330 void object::test<4>
331 ()
332 {
333     std::vector<Coordinate> intPt;
334     intPt.push_back(Coordinate(4348437.0557510145, 5552597.375203926));
335 
336     checkIntersection(
337         "LINESTRING (4348433.262114629 5552595.478385733, 4348440.849387404 5552599.272022122 )",
338         "LINESTRING (4348433.26211463  5552595.47838573,  4348440.8493874   5552599.27202212  )",
339         1,
340         intPt, 0);
341 }
342 #endif // fails
343 
344 #if 0 // fails: the intersection point doesn't match
345 // 5 - Result of this test should be the same as the WKT one!
346 //     (testCmp5CaseRaw)
347 template<>
348 template<>
349 void object::test<5>
350 ()
351 {
352     std::vector<Coordinate> pt;
353     pt.push_back(Coordinate(4348433.262114629, 5552595.478385733));
354     pt.push_back(Coordinate(4348440.849387404, 5552599.272022122));
355     pt.push_back(Coordinate(4348433.26211463,  5552595.47838573));
356     pt.push_back(Coordinate(4348440.8493874,   5552599.27202212));
357 
358     std::vector<Coordinate> intPt;
359     intPt.push_back(Coordinate(4348437.0557510145, 5552597.375203926));
360 
361     checkIntersection(pt, 1, intPt, 0);
362 }
363 #endif // fails
364 
365 /**
366  * Test involving two non-almost-parallel lines.
367  * Does not seem to cause problems with basic line intersection algorithm.
368  *
369  */
370 //     (testLeduc_1)
371 template<>
372 template<>
test()373 void object::test<6>
374 ()
375 {
376     checkIntersection(
377         "LINESTRING (305690.0434123494 254176.46578338774, 305601.9999843455 254243.19999846347)",
378         "LINESTRING (305689.6153764265 254177.33102743194, 305692.4999844298 254171.4999983967)",
379         1,
380         "POINT (305690.0434123494 254176.46578338774)",
381         0);
382 }
383 
384 #if 0 // fails: finds an intersection (we don't have DD)
385 /**
386  * Test from Tomas Fa - JTS list 6/13/2012
387  *
388  * Fails using original JTS DeVillers determine orientation test.
389  * Succeeds using DD and Shewchuk orientation
390  *
391  */
392 // testTomasFa_2
393 template<>
394 template<>
395 void object::test<7>
396 ()
397 {
398     checkIntersectionNone(
399         "LINESTRING (-5.9 163.1, 76.1 250.7)",
400         "LINESTRING (14.6 185.0, 96.6 272.6)");
401 }
402 #endif // fails
403 
404 #if 0 // fails: finds an intersection (we don't have DD)
405 /**
406  * Test from Tomas Fa - JTS list 6/13/2012
407  *
408  * Fails using original JTS DeVillers determine orientation test.
409  * Succeeds using DD and Shewchuk orientation
410  *
411  */
412 // testTomasFa_1
413 template<>
414 template<>
415 void object::test<8>
416 ()
417 {
418     checkIntersectionNone(
419         "LINESTRING (-42.0 163.2, 21.2 265.2)",
420         "LINESTRING (-26.2 188.7, 37.0 290.7)");
421 }
422 #endif // fails
423 
424 /**
425  * Following cases were failures when using the CentralEndpointIntersector heuristic.
426  * This is because one segment lies at a significant angle to the other,
427  * with only one endpoint is close to the other segment.
428  * The CE heuristic chose the wrong endpoint to return.
429  * The fix is to use a new heuristic which out of the 4 endpoints
430  * chooses the one which is closest to the other segment.
431  * This works in all known failure cases.
432  *
433  */
434 // public void testCentralEndpointHeuristicFailure()
435 template<>
436 template<>
test()437 void object::test<9>
438 ()
439 {
440     checkIntersection(
441         "LINESTRING (163.81867067 -211.31840378, 165.9174252 -214.1665075)",
442         "LINESTRING (2.84139601 -57.95412726, 469.59990601 -502.63851732)",
443         1,
444         "POINT (163.81867067 -211.31840378)",
445         0);
446 }
447 
448 // public void testCentralEndpointHeuristicFailure2()
449 template<>
450 template<>
test()451 void object::test<10>
452 ()
453 {
454     checkIntersection(
455         "LINESTRING (-58.00593335955 -1.43739086465, -513.86101637525 -457.29247388035)",
456         "LINESTRING (-215.22279674875 -158.65425425385, -218.1208801283 -160.68343590235)",
457         1,
458         "POINT ( -215.22279674875 -158.65425425385 )",
459         0);
460 }
461 
462 /**
463  * Tests a case where intersection point is rounded,
464  * and it is computed as a nearest endpoint.
465  * Exposed a bug due to aliasing of endpoint.
466  *
467  * MD 8 Mar 2013
468  *
469  */
470 // testRoundedPointsNotAltered()
471 template<>
472 template<>
test()473 void object::test<11>
474 ()
475 {
476     checkInputNotAltered(
477         "LINESTRING (-58.00593335955 -1.43739086465, -513.86101637525 -457.29247388035)",
478         "LINESTRING (-215.22279674875 -158.65425425385, -218.1208801283 -160.68343590235)",
479         100000);
480 }
481 
482 
483 
484 
485 } // namespace tut
486 
487