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