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