1 // Boost.Geometry (aka GGL, Generic Geometry Library)
3 // Copyright (c) 2014-2019, Oracle and/or its affiliates.
5 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
6 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
8 // Licensed under the Boost Software License version 1.0.
9 // http://www.boost.org/users/license.html
11 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_SIMPLE_LINEAR_HPP
12 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_SIMPLE_LINEAR_HPP
17 #include <boost/range.hpp>
19 #include <boost/geometry/core/assert.hpp>
20 #include <boost/geometry/core/closure.hpp>
21 #include <boost/geometry/core/coordinate_type.hpp>
22 #include <boost/geometry/core/point_type.hpp>
23 #include <boost/geometry/core/tag.hpp>
24 #include <boost/geometry/core/tags.hpp>
26 #include <boost/geometry/util/range.hpp>
28 #include <boost/geometry/policies/predicate_based_interrupt_policy.hpp>
29 #include <boost/geometry/policies/robustness/no_rescale_policy.hpp>
30 #include <boost/geometry/policies/robustness/segment_ratio.hpp>
32 #include <boost/geometry/algorithms/intersects.hpp>
33 #include <boost/geometry/algorithms/not_implemented.hpp>
35 #include <boost/geometry/algorithms/detail/check_iterator_range.hpp>
36 #include <boost/geometry/algorithms/detail/signed_size_type.hpp>
38 #include <boost/geometry/algorithms/detail/disjoint/linear_linear.hpp>
39 #include <boost/geometry/algorithms/detail/equals/point_point.hpp>
40 #include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp>
41 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
42 #include <boost/geometry/algorithms/detail/overlay/self_turn_points.hpp>
43 #include <boost/geometry/algorithms/detail/is_valid/has_duplicates.hpp>
44 #include <boost/geometry/algorithms/detail/is_valid/has_spikes.hpp>
46 #include <boost/geometry/algorithms/detail/is_simple/debug_print_boundary_points.hpp>
47 #include <boost/geometry/algorithms/detail/is_simple/failure_policy.hpp>
48 #include <boost/geometry/algorithms/detail/is_valid/debug_print_turns.hpp>
50 #include <boost/geometry/algorithms/dispatch/is_simple.hpp>
52 #include <boost/geometry/strategies/intersection.hpp>
55 namespace boost { namespace geometry
59 #ifndef DOXYGEN_NO_DETAIL
60 namespace detail { namespace is_simple
64 template <typename Turn>
65 inline bool check_segment_indices(Turn const& turn,
66 signed_size_type last_index)
69 (turn.operations[0].seg_id.segment_index == 0
70 && turn.operations[1].seg_id.segment_index == last_index)
72 (turn.operations[0].seg_id.segment_index == 0
73 && turn.operations[1].seg_id.segment_index == last_index);
80 typename EqPPStrategy,
81 typename Tag = typename tag<Geometry>::type
83 class is_acceptable_turn
84 : not_implemented<Geometry>
87 template <typename Linestring, typename EqPPStrategy>
88 class is_acceptable_turn<Linestring, EqPPStrategy, linestring_tag>
91 is_acceptable_turn(Linestring const& linestring)
92 : m_linestring(linestring)
93 , m_is_closed(geometry::detail::equals::equals_point_point(range::front(linestring),
94 range::back(linestring),
98 template <typename Turn>
99 inline bool apply(Turn const& turn) const
101 BOOST_GEOMETRY_ASSERT(boost::size(m_linestring) > 1);
103 && turn.method == overlay::method_none
104 && check_segment_indices(turn, boost::size(m_linestring) - 2)
105 && turn.operations[0].fraction.is_zero();
109 Linestring const& m_linestring;
110 bool const m_is_closed;
113 template <typename MultiLinestring, typename EqPPStrategy>
114 class is_acceptable_turn<MultiLinestring, EqPPStrategy, multi_linestring_tag>
117 template <typename Point1, typename Point2>
118 static inline bool equals_point_point(Point1 const& point1, Point2 const& point2)
120 return geometry::detail::equals::equals_point_point(point1, point2,
124 template <typename Point, typename Linestring>
125 static inline bool is_boundary_point_of(Point const& point,
126 Linestring const& linestring)
128 BOOST_GEOMETRY_ASSERT(boost::size(linestring) > 1);
130 !equals_point_point(range::front(linestring), range::back(linestring))
132 (equals_point_point(point, range::front(linestring))
133 || equals_point_point(point, range::back(linestring)));
136 template <typename Turn, typename Linestring>
137 static inline bool is_closing_point_of(Turn const& turn,
138 Linestring const& linestring)
140 BOOST_GEOMETRY_ASSERT(boost::size(linestring) > 1);
142 turn.method == overlay::method_none
144 check_segment_indices(turn, boost::size(linestring) - 2)
146 equals_point_point(range::front(linestring), range::back(linestring))
148 turn.operations[0].fraction.is_zero();
152 template <typename Linestring1, typename Linestring2>
153 static inline bool have_same_boundary_points(Linestring1 const& ls1,
154 Linestring2 const& ls2)
157 equals_point_point(range::front(ls1), range::front(ls2))
159 equals_point_point(range::back(ls1), range::back(ls2))
161 (equals_point_point(range::front(ls1), range::back(ls2))
163 equals_point_point(range::back(ls1), range::front(ls2)))
168 is_acceptable_turn(MultiLinestring const& multilinestring)
169 : m_multilinestring(multilinestring)
172 template <typename Turn>
173 inline bool apply(Turn const& turn) const
175 typedef typename boost::range_value<MultiLinestring>::type linestring_type;
177 linestring_type const& ls1 =
178 range::at(m_multilinestring, turn.operations[0].seg_id.multi_index);
180 linestring_type const& ls2 =
181 range::at(m_multilinestring, turn.operations[1].seg_id.multi_index);
183 if (turn.operations[0].seg_id.multi_index
184 == turn.operations[1].seg_id.multi_index)
186 return is_closing_point_of(turn, ls1);
190 is_boundary_point_of(turn.point, ls1)
191 && is_boundary_point_of(turn.point, ls2)
193 ( boost::size(ls1) != 2
194 || boost::size(ls2) != 2
195 || ! have_same_boundary_points(ls1, ls2) );
199 MultiLinestring const& m_multilinestring;
203 template <typename Linear, typename Strategy>
204 inline bool has_self_intersections(Linear const& linear, Strategy const& strategy)
206 typedef typename point_type<Linear>::type point_type;
208 // compute self turns
209 typedef detail::overlay::turn_info<point_type> turn_info;
211 std::deque<turn_info> turns;
213 typedef detail::overlay::get_turn_info
215 detail::disjoint::assign_disjoint_policy
218 typedef is_acceptable_turn
221 typename Strategy::equals_point_point_strategy_type
222 > is_acceptable_turn_type;
224 is_acceptable_turn_type predicate(linear);
225 detail::overlay::predicate_based_interrupt_policy
227 is_acceptable_turn_type
228 > interrupt_policy(predicate);
230 // TODO: skip_adjacent should be set to false
231 detail::self_get_turn_points::get_turns
236 detail::no_rescale_policy(),
238 interrupt_policy, 0, true);
240 detail::is_valid::debug_print_turns(turns.begin(), turns.end());
241 debug_print_boundary_points(linear);
243 return interrupt_policy.has_intersections;
247 template <typename Linestring, bool CheckSelfIntersections = true>
248 struct is_simple_linestring
250 template <typename Strategy>
251 static inline bool apply(Linestring const& linestring,
252 Strategy const& strategy)
254 simplicity_failure_policy policy;
255 return ! boost::empty(linestring)
256 && ! detail::is_valid::has_duplicates
258 Linestring, closed, typename Strategy::cs_tag
259 >::apply(linestring, policy)
260 && ! detail::is_valid::has_spikes
263 >::apply(linestring, policy, strategy.get_side_strategy());
267 template <typename Linestring>
268 struct is_simple_linestring<Linestring, true>
270 template <typename Strategy>
271 static inline bool apply(Linestring const& linestring,
272 Strategy const& strategy)
274 return is_simple_linestring
277 >::apply(linestring, strategy)
278 && ! has_self_intersections(linestring, strategy);
283 template <typename MultiLinestring>
284 struct is_simple_multilinestring
287 template <typename Strategy>
288 struct per_linestring
290 per_linestring(Strategy const& strategy)
291 : m_strategy(strategy)
294 template <typename Linestring>
295 inline bool apply(Linestring const& linestring) const
297 return detail::is_simple::is_simple_linestring
300 false // do not compute self-intersections
301 >::apply(linestring, m_strategy);
304 Strategy const& m_strategy;
308 template <typename Strategy>
309 static inline bool apply(MultiLinestring const& multilinestring,
310 Strategy const& strategy)
312 typedef per_linestring<Strategy> per_ls;
314 // check each of the linestrings for simplicity
315 // but do not compute self-intersections yet; these will be
316 // computed for the entire multilinestring
317 if ( ! detail::check_iterator_range
319 per_ls, // do not compute self-intersections
320 true // allow empty multilinestring
321 >::apply(boost::begin(multilinestring),
322 boost::end(multilinestring),
329 return ! has_self_intersections(multilinestring, strategy);
335 }} // namespace detail::is_simple
336 #endif // DOXYGEN_NO_DETAIL
340 #ifndef DOXYGEN_NO_DISPATCH
344 // A linestring is a curve.
345 // A curve is simple if it does not pass through the same point twice,
346 // with the possible exception of its two endpoints
348 // Reference: OGC 06-103r4 (6.1.6.1)
349 template <typename Linestring>
350 struct is_simple<Linestring, linestring_tag>
351 : detail::is_simple::is_simple_linestring<Linestring>
355 // A MultiLinestring is a MultiCurve
356 // A MultiCurve is simple if all of its elements are simple and the
357 // only intersections between any two elements occur at Points that
358 // are on the boundaries of both elements.
360 // Reference: OGC 06-103r4 (6.1.8.1; Fig. 9)
361 template <typename MultiLinestring>
362 struct is_simple<MultiLinestring, multi_linestring_tag>
363 : detail::is_simple::is_simple_multilinestring<MultiLinestring>
367 } // namespace dispatch
368 #endif // DOXYGEN_NO_DISPATCH
371 }} // namespace boost::geometry
374 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_SIMPLE_LINEAR_HPP