libs/geometry/test/algorithms/intersects.cpp

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