1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2
3 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
4 // Copyright (c) 2013-2015 Adam Wulkiewicz, Lodz, Poland.
5
6 // This file was modified by Oracle on 2013, 2015.
7 // Modifications copyright (c) 2013-2015, Oracle and/or its affiliates.
8
9 // Use, modification and distribution is subject to the Boost Software License,
10 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
11 // http://www.boost.org/LICENSE_1_0.txt)
12
13 #include "test_intersects.hpp"
14
15
16 #include <boost/geometry/geometries/geometries.hpp>
17 #include <boost/geometry/geometries/point_xy.hpp>
18
19 #include <boost/geometry/util/rational.hpp>
20
21
22 template <typename P>
test_all()23 void test_all()
24 {
25 typedef bg::model::linestring<P> linestring;
26 typedef bg::model::polygon<P> polygon;
27 typedef bg::model::ring<P> ring;
28 typedef bg::model::ring<P, true, false> ring_open;
29
30 // self-intersecting is not tested in disjoint, so that is done here.
31
32 // Just a normal polygon
33 test_self_intersects<polygon>("POLYGON((0 0,0 4,1.5 2.5,2.5 1.5,4 0,0 0))", false);
34
35 // Self intersecting
36 test_self_intersects<polygon>("POLYGON((1 2,1 1,2 1,2 2.25,3 2.25,3 0,0 0,0 3,3 3,2.75 2,1 2))", true);
37
38 // Self intersecting in last segment
39 test_self_intersects<polygon>("POLYGON((0 2,2 4,2 0,4 2,0 2))", true);
40
41 // Self tangent
42 test_self_intersects<polygon>("POLYGON((0 0,0 4,4 4,4 0,2 4,0 0))", true);
43
44 // Self tangent in corner
45 test_self_intersects<polygon>("POLYGON((0 0,0 4,4 4,4 0,0 4,2 0,0 0))", true);
46
47 // With spike
48 test_self_intersects<polygon>("POLYGON((0 0,0 4,4 4,4 2,6 2,4 2,4 0,0 0))", true);
49
50 // Non intersection, but with duplicate
51 test_self_intersects<polygon>("POLYGON((0 0,0 4,4 0,4 0,0 0))", false);
52
53 // With many duplicates
54 test_self_intersects<polygon>(
55 "POLYGON((0 0,0 1,0 1,0 1,0 2,0 2,0 3,0 3,0 3,0 3,0 4,2 4,2 4,4 4,4 0,4 0,3 0,3 0,3 0,3 0,3 0,0 0))",
56 false);
57
58 // Hole: interior tangent to exterior
59 test_self_intersects<polygon>("POLYGON((0 0,0 4,4 4,4 0,0 0),(1 2,2 4,3 2,1 2))", true);
60
61 // Hole: interior intersecting exterior
62 test_self_intersects<polygon>("POLYGON((0 0,0 4,4 4,4 0,0 0),(1 1,1 3,5 4,1 1))", true);
63
64 // Hole: two intersecting holes
65 test_self_intersects<polygon>(
66 "POLYGON((0 0,0 4,4 4,4 0,0 0),(1 1,1 3,3 3,3 1,1 1),(2 2,2 3.5,3.5 3.5,3.5 2,2 2))", true);
67
68 // Mail Akira T on [Boost-users] at 27-7-2011 3:17
69 test_self_intersects<linestring>(
70 "LINESTRING(0 0,0 4,4 4,2 2,2 5)", true);
71
72 test_self_intersects<linestring>(
73 "LINESTRING(0 4,4 4,2 2,2 5)", true);
74
75 // Test self-intersections at last segment in close/open rings:
76 test_self_intersects<ring>(
77 "POLYGON((0 0,3 3,4 1,0 0))", false);
78
79 test_self_intersects<ring_open>(
80 "POLYGON((0 0,3 3,4 1))", false);
81
82 test_self_intersects<ring>(
83 "POLYGON((0 0,3 3,4 1,0 1,0 0))", true);
84
85 test_self_intersects<ring_open>(
86 "POLYGON((0 0,3 3,4 1,0 1))", true);
87
88 // Duplicates in first or last
89 test_self_intersects<ring>(
90 "POLYGON((0 0,3 3,4 1,0 1,0 1,0 0))", true);
91 test_self_intersects<ring>(
92 "POLYGON((0 0,3 3,4 1,0 1,0 0,0 0))", true);
93 test_self_intersects<ring_open>(
94 "POLYGON((0 0,3 3,4 1,0 1,0 1))", true);
95 test_self_intersects<ring>(
96 "POLYGON((0 0,0 0,3 3,4 1,0 1,0 1,0 0))", true);
97 test_self_intersects<ring_open>(
98 "POLYGON((0 0,0 0,3 3,4 1,0 1,0 1))", true);
99 test_self_intersects<ring>(
100 "POLYGON((0 0,3 3,3 3,4 1,0 1,0 1,0 0))", true);
101 test_self_intersects<ring_open>(
102 "POLYGON((0 0,3 3,3 3,4 1,0 1,0 1))", true);
103
104 test_self_intersects<ring>(
105 "POLYGON((0 0,3 3,4 1,0 0,0 0))", false);
106 test_self_intersects<ring>(
107 "POLYGON((0 0,3 3,4 1,4 1,0 0))", false);
108 test_self_intersects<ring_open>(
109 "POLYGON((0 0,3 3,4 1,4 1))", false);
110 test_self_intersects<ring>(
111 "POLYGON((0 0,0 0,3 3,4 1,0 0))", false);
112 test_self_intersects<ring_open>(
113 "POLYGON((0 0,0 0,3 3,4 1))", false);
114 test_self_intersects<ring>(
115 "POLYGON((0 0,3 3,3 3,4 1,0 0))", false);
116 test_self_intersects<ring_open>(
117 "POLYGON((0 0,3 3,3 3,4 1))", false);
118 }
119
test_main(int,char * [])120 int test_main( int , char* [] )
121 {
122 test_all<bg::model::d2::point_xy<double> >();
123
124 #if ! defined(BOOST_GEOMETRY_RESCALE_TO_ROBUST)
125 test_all<bg::model::d2::point_xy<boost::rational<int> > >();
126 #endif
127
128 #if defined(HAVE_TTMATH)
129 test_all<bg::model::d2::point_xy<ttmath_big> >();
130 #endif
131
132 return 0;
133 }
134