1 // Boost.Geometry (aka GGL, Generic Geometry Library)
3 // Copyright (c) 2015 Barend Gehrels, Amsterdam, the Netherlands.
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)
9 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SORT_BY_SIDE_HPP
10 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SORT_BY_SIDE_HPP
15 #include <boost/geometry/algorithms/detail/direction_code.hpp>
16 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
17 #include <boost/geometry/strategies/side.hpp>
19 namespace boost { namespace geometry
22 #ifndef DOXYGEN_NO_DETAIL
23 namespace detail { namespace overlay { namespace sort_by_side
26 enum direction_type { dir_unknown = -1, dir_from = 0, dir_to = 1 };
28 // Point-wrapper, adding some properties
29 template <typename Point>
36 , direction(dir_unknown)
39 , operation(operation_none)
42 ranked_point(const Point& p, signed_size_type ti, signed_size_type oi,
43 direction_type d, operation_type op, segment_identifier sid)
58 signed_size_type zone; // index of closed zone, in uu turn there would be 2 zones
59 signed_size_type turn_index;
60 signed_size_type operation_index;
61 direction_type direction;
62 std::size_t count_left;
63 std::size_t count_right;
64 operation_type operation;
65 segment_identifier seg_id;
68 struct less_by_turn_index
71 inline bool operator()(const T& first, const T& second) const
73 return first.turn_index == second.turn_index
74 ? first.index < second.index
75 : first.turn_index < second.turn_index
83 inline bool operator()(const T& first, const T& second) const
85 // First order by from/to
86 if (first.direction != second.direction)
88 return first.direction < second.direction;
90 // All the same, order by turn index (we might consider length too)
91 return first.turn_index < second.turn_index;
98 inline bool operator()(const T&, const T& ) const
104 template <typename Point, typename LessOnSame, typename Compare>
107 typedef typename strategy::side::services::default_strategy
109 typename cs_tag<Point>::type
112 less_by_side(const Point& p1, const Point& p2)
117 template <typename T>
118 inline bool operator()(const T& first, const T& second) const
123 int const side_first = side::apply(m_p1, m_p2, first.point);
124 int const side_second = side::apply(m_p1, m_p2, second.point);
126 if (side_first == 0 && side_second == 0)
128 // Both collinear. They might point into different directions: <------*------>
129 // If so, order the one going backwards as the very first.
131 int const first_code = direction_code(m_p1, m_p2, first.point);
132 int const second_code = direction_code(m_p1, m_p2, second.point);
134 // Order by code, backwards first, then forward.
135 return first_code != second_code
136 ? first_code < second_code
137 : on_same(first, second)
140 else if (side_first == 0
141 && direction_code(m_p1, m_p2, first.point) == -1)
143 // First collinear and going backwards.
144 // Order as the very first, so return always true
147 else if (side_second == 0
148 && direction_code(m_p1, m_p2, second.point) == -1)
150 // Second is collinear and going backwards
151 // Order as very last, so return always false
155 // They are not both collinear
157 if (side_first != side_second)
159 return compare(side_first, side_second);
162 // They are both left, both right, and/or both collinear (with each other and/or with p1,p2)
164 int const side_second_wrt_first = side::apply(m_p2, first.point, second.point);
166 if (side_second_wrt_first == 0)
168 return on_same(first, second);
171 int const side_first_wrt_second = -side_second_wrt_first;
173 // Both are on same side, and not collinear
174 // Union: return true if second is right w.r.t. first, so -1,
175 // so other is 1. union has greater as compare functor
176 // Intersection: v.v.
177 return compare(side_first_wrt_second, side_second_wrt_first);
184 template <bool Reverse1, bool Reverse2, typename Point, typename Compare>
187 typedef ranked_point<Point> rp;
189 inline void set_origin(Point const& origin)
194 template <typename Operation, typename Geometry1, typename Geometry2>
195 void add(Operation const& op, signed_size_type turn_index, signed_size_type op_index,
196 Geometry1 const& geometry1,
197 Geometry2 const& geometry2,
200 Point point1, point2, point3;
201 geometry::copy_segment_points<Reverse1, Reverse2>(geometry1, geometry2,
202 op.seg_id, point1, point2, point3);
203 Point const& point_to = op.fraction.is_one() ? point3 : point2;
205 m_ranked_points.push_back(rp(point1, turn_index, op_index, dir_from, op.operation, op.seg_id));
206 m_ranked_points.push_back(rp(point_to, turn_index, op_index, dir_to, op.operation, op.seg_id));
214 void apply(Point const& turn_point)
216 // We need three compare functors:
217 // 1) to order clockwise (union) or counter clockwise (intersection)
218 // 2) to order by side, resulting in unique ranks for all points
219 // 3) to order by side, resulting in non-unique ranks
220 // to give colinear points
222 // Sort by side and assign rank
223 less_by_side<Point, less_by_index, Compare> less_unique(m_origin, turn_point);
224 less_by_side<Point, less_false, Compare> less_non_unique(m_origin, turn_point);
226 std::sort(m_ranked_points.begin(), m_ranked_points.end(), less_unique);
228 std::size_t colinear_rank = 0;
229 for (std::size_t i = 0; i < m_ranked_points.size(); i++)
232 && less_non_unique(m_ranked_points[i - 1], m_ranked_points[i]))
234 // It is not collinear
238 m_ranked_points[i].rank = colinear_rank;
242 template <signed_size_type segment_identifier::*Member, typename Map>
243 void find_open_generic(Map& handled)
245 for (std::size_t i = 0; i < m_ranked_points.size(); i++)
247 const rp& ranked = m_ranked_points[i];
248 if (ranked.direction != dir_from)
253 signed_size_type const& index = ranked.seg_id.*Member;
254 if (! handled[index])
256 find_polygons_for_source<Member>(index, i);
257 handled[index] = true;
264 // TODO: we might pass Buffer as overlay_type, instead on the fly below
265 bool one_source = true;
266 for (std::size_t i = 0; i < m_ranked_points.size(); i++)
268 const rp& ranked = m_ranked_points[i];
269 signed_size_type const& src = ranked.seg_id.source_index;
280 std::map<signed_size_type, bool> handled;
283 &segment_identifier::piece_index
288 // by source (there should only source 0,1) TODO assert this
289 bool handled[2] = {false, false};
292 &segment_identifier::source_index
301 if (m_ranked_points.empty())
306 int const last = 1 + m_ranked_points.back().rank;
308 // Move iterator after rank==0
309 bool has_first = false;
310 typename container_type::iterator it = m_ranked_points.begin() + 1;
311 for (; it != m_ranked_points.end() && it->rank == 0; ++it)
318 // Reverse first part (having rank == 0), if any,
319 // but skip the very first row
320 std::reverse(m_ranked_points.begin() + 1, it);
321 for (typename container_type::iterator fit = m_ranked_points.begin();
324 BOOST_ASSERT(fit->rank == 0);
328 // Reverse the rest (main rank > 0)
329 std::reverse(it, m_ranked_points.end());
330 for (; it != m_ranked_points.end(); ++it)
332 BOOST_ASSERT(it->rank > 0);
333 it->rank = last - it->rank;
337 //! Check how many open spaces there are
338 template <typename Turns>
339 std::size_t open_count(Turns const& turns) const
341 typedef typename boost::range_value<Turns>::type turn_type;
342 typedef typename turn_type::turn_operation_type turn_operation_type;
344 std::size_t result = 0;
345 std::size_t last_rank = 0;
346 for (std::size_t i = 0; i < m_ranked_points.size(); i++)
348 rp const& ranked_point = m_ranked_points[i];
350 if (ranked_point.rank > last_rank
351 && ranked_point.direction == sort_by_side::dir_to)
353 // TODO: take count-left / count_right from rank itself
354 turn_type const& ranked_turn = turns[ranked_point.turn_index];
355 turn_operation_type const& ranked_op = ranked_turn.operations[ranked_point.operation_index];
356 if (ranked_op.enriched.count_left == 0
357 && ranked_op.enriched.count_right > 0)
360 last_rank = ranked_point.rank;
369 typedef std::vector<rp> container_type;
370 container_type m_ranked_points;
376 std::size_t move(std::size_t index) const
378 std::size_t const result = index + 1;
379 return result >= m_ranked_points.size() ? 0 : result;
382 //! member is pointer to member (source_index or multi_index)
383 template <signed_size_type segment_identifier::*Member>
384 std::size_t move(signed_size_type member_index, std::size_t index) const
386 std::size_t result = move(index);
387 while (m_ranked_points[result].seg_id.*Member != member_index)
389 result = move(result);
394 void assign_ranks(std::size_t min_rank, std::size_t max_rank, int side_index)
396 for (std::size_t i = 0; i < m_ranked_points.size(); i++)
398 rp& ranked = m_ranked_points[i];
399 // Suppose there are 8 ranks, if min=4,max=6: assign 4,5,6
400 // if min=5,max=2: assign from 5,6,7,1,2
402 = max_rank >= min_rank
403 ? ranked.rank >= min_rank && ranked.rank <= max_rank
404 : ranked.rank >= min_rank || ranked.rank <= max_rank
413 else if (side_index == 2)
415 ranked.count_right++;
421 template <signed_size_type segment_identifier::*Member>
422 void find_polygons_for_source(signed_size_type the_index,
423 std::size_t start_index)
425 int state = 1; // 'closed', because start_index is "from", arrives at the turn
426 std::size_t last_from_rank = m_ranked_points[start_index].rank;
427 std::size_t previous_rank = m_ranked_points[start_index].rank;
429 for (std::size_t index = move<Member>(the_index, start_index);
431 index = move<Member>(the_index, index))
433 rp& ranked = m_ranked_points[index];
435 if (ranked.rank != previous_rank && state == 0)
437 assign_ranks(last_from_rank, previous_rank - 1, 1);
438 assign_ranks(last_from_rank + 1, previous_rank, 2);
441 if (index == start_index)
446 if (ranked.direction == dir_from)
448 last_from_rank = ranked.rank;
451 else if (ranked.direction == dir_to)
456 previous_rank = ranked.rank;
460 //! Find closed zones and assign it
463 // Find a starting point (the first rank after an outgoing rank
464 // with no polygons on the left side)
465 std::size_t start_rank = m_ranked_points.size() + 1;
466 std::size_t start_index = 0;
467 std::size_t max_rank = 0;
468 for (std::size_t i = 0; i < m_ranked_points.size(); i++)
470 rp const& ranked_point = m_ranked_points[i];
471 if (ranked_point.rank > max_rank)
473 max_rank = ranked_point.rank;
475 if (ranked_point.direction == sort_by_side::dir_to
476 && ranked_point.count_left == 0
477 && ranked_point.count_right > 0)
479 start_rank = ranked_point.rank + 1;
481 if (ranked_point.rank == start_rank && start_index == 0)
488 std::size_t const undefined_rank = max_rank + 1;
489 std::size_t zone_id = 0;
490 std::size_t last_rank = 0;
491 std::size_t rank_at_next_zone = undefined_rank;
492 std::size_t index = start_index;
493 for (std::size_t i = 0; i < m_ranked_points.size(); i++)
495 rp& ranked_point = m_ranked_points[index];
497 // Implement cyclic behavior
499 if (index == m_ranked_points.size())
504 if (ranked_point.rank != last_rank)
506 if (ranked_point.rank == rank_at_next_zone)
509 rank_at_next_zone = undefined_rank;
512 if (ranked_point.direction == sort_by_side::dir_to
513 && ranked_point.count_left == 0
514 && ranked_point.count_right > 0)
516 rank_at_next_zone = ranked_point.rank + 1;
517 if (rank_at_next_zone > max_rank)
519 rank_at_next_zone = 0;
523 last_rank = ranked_point.rank;
526 ranked_point.zone = zone_id;
534 }}} // namespace detail::overlay::sort_by_side
535 #endif //DOXYGEN_NO_DETAIL
538 }} // namespace boost::geometry
540 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SORT_BY_SIDE_HPP