ceph/src/boost/libs/geometry/test/algorithms/intersects/intersects_self.cpp

   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>
  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
 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 }