summaryrefslogtreecommitdiff log msg author committer range
blob: 8feb48db6a592410d568c5f9040592af755f6076 (plain)
 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 ``` ``````// Boost.Geometry (aka GGL, Generic Geometry Library) // Copyright (c) 2015 Barend Gehrels, Amsterdam, the Netherlands. // Use, modification and distribution is subject to the Boost Software License, // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) #ifndef BOOST_GEOMETRY_ALGORITHMS_IS_CONVEX_HPP #define BOOST_GEOMETRY_ALGORITHMS_IS_CONVEX_HPP #include #include #include #include #include #include #include #include #include #include namespace boost { namespace geometry { #ifndef DOXYGEN_NO_DETAIL namespace detail { namespace is_convex { struct ring_is_convex { template static inline bool apply(Ring const& ring) { typedef typename geometry::point_type::type point_type; typedef typename strategy::side::services::default_strategy < typename cs_tag::type >::type side_strategy_type; std::size_t n = boost::size(ring); if (boost::size(ring) < core_detail::closure::minimum_ring_size < geometry::closure::value >::value) { // (Too) small rings are considered as non-concave, is convex return true; } // Walk in clockwise direction, consider ring as closed // (though closure is not important in this algorithm - any dupped // point is skipped) typedef detail::normalized_view view_type; view_type view(ring); typedef geometry::ever_circling_range_iterator it_type; it_type previous(view); it_type current(view); current++; std::size_t index = 1; while (equals::equals_point_point(*current, *previous) && index < n) { current++; index++; } if (index == n) { // All points are apparently equal return true; } it_type next = current; next++; while (equals::equals_point_point(*current, *next)) { next++; } // We have now three different points on the ring // Walk through all points, use a counter because of the ever-circling // iterator for (std::size_t i = 0; i < n; i++) { int const side = side_strategy_type::apply(*previous, *current, *next); if (side == 1) { // Next is on the left side of clockwise ring: // the piece is not convex return false; } previous = current; current = next; // Advance next to next different point // (because there are non-equal points, this loop is not infinite) next++; while (equals::equals_point_point(*current, *next)) { next++; } } return true; } }; }} // namespace detail::is_convex #endif // DOXYGEN_NO_DETAIL #ifndef DOXYGEN_NO_DISPATCH namespace dispatch { template < typename Geometry, typename Tag = typename tag::type > struct is_convex : not_implemented {}; template struct is_convex { static inline bool apply(Box const& ) { // Any box is convex (TODO: consider spherical boxes) return true; } }; template struct is_convex : detail::is_convex::ring_is_convex {}; } // namespace dispatch #endif // DOXYGEN_NO_DISPATCH // TODO: variants // TODO: documentation / qbk template inline bool is_convex(Geometry const& geometry) { return dispatch::is_convex::apply(geometry); } }} // namespace boost::geometry #endif // BOOST_GEOMETRY_ALGORITHMS_IS_CONVEX_HPP ``````