1 // Boost.Geometry (aka GGL, Generic Geometry Library)
3 // Copyright (c) 2015 Barend Gehrels, Amsterdam, the Netherlands.
4 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
6 // This file was modified by Oracle on 2017, 2019.
7 // Modifications copyright (c) 2017, 2019 Oracle and/or its affiliates.
9 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
11 // Use, modification and distribution is subject to the Boost Software License,
12 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
13 // http://www.boost.org/LICENSE_1_0.txt)
15 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SORT_BY_SIDE_HPP
16 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SORT_BY_SIDE_HPP
22 #include <boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp>
23 #include <boost/geometry/algorithms/detail/overlay/get_ring.hpp>
24 #include <boost/geometry/algorithms/detail/direction_code.hpp>
25 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
27 #include <boost/geometry/util/condition.hpp>
29 namespace boost { namespace geometry
32 #ifndef DOXYGEN_NO_DETAIL
33 namespace detail { namespace overlay { namespace sort_by_side
36 enum direction_type { dir_unknown = -1, dir_from = 0, dir_to = 1 };
38 typedef signed_size_type rank_type;
41 // Point-wrapper, adding some properties
42 template <typename Point>
49 , direction(dir_unknown)
52 , operation(operation_none)
55 ranked_point(Point const& p, signed_size_type ti, int oi,
56 direction_type d, operation_type op, segment_identifier const& si)
71 signed_size_type zone; // index of closed zone, in uu turn there would be 2 zones
72 signed_size_type turn_index;
73 int operation_index; // 0,1
74 direction_type direction;
75 std::size_t count_left;
76 std::size_t count_right;
77 operation_type operation;
78 segment_identifier seg_id;
81 struct less_by_turn_index
84 inline bool operator()(const T& first, const T& second) const
86 return first.turn_index == second.turn_index
87 ? first.index < second.index
88 : first.turn_index < second.turn_index
96 inline bool operator()(const T& first, const T& second) const
98 // Length might be considered too
99 // First order by from/to
100 if (first.direction != second.direction)
102 return first.direction < second.direction;
104 // Then by turn index
105 if (first.turn_index != second.turn_index)
107 return first.turn_index < second.turn_index;
109 // This can also be the same (for example in buffer), but seg_id is
111 return first.seg_id < second.seg_id;
117 template <typename T>
118 inline bool operator()(const T&, const T& ) const
124 template <typename Point, typename SideStrategy, typename LessOnSame, typename Compare>
127 less_by_side(const Point& p1, const Point& p2, SideStrategy const& strategy)
130 , m_strategy(strategy)
133 template <typename T>
134 inline bool operator()(const T& first, const T& second) const
136 typedef typename SideStrategy::cs_tag cs_tag;
141 int const side_first = m_strategy.apply(m_origin, m_turn_point, first.point);
142 int const side_second = m_strategy.apply(m_origin, m_turn_point, second.point);
144 if (side_first == 0 && side_second == 0)
146 // Both collinear. They might point into different directions: <------*------>
147 // If so, order the one going backwards as the very first.
149 int const first_code = direction_code<cs_tag>(m_origin, m_turn_point, first.point);
150 int const second_code = direction_code<cs_tag>(m_origin, m_turn_point, second.point);
152 // Order by code, backwards first, then forward.
153 return first_code != second_code
154 ? first_code < second_code
155 : on_same(first, second)
158 else if (side_first == 0
159 && direction_code<cs_tag>(m_origin, m_turn_point, first.point) == -1)
161 // First collinear and going backwards.
162 // Order as the very first, so return always true
165 else if (side_second == 0
166 && direction_code<cs_tag>(m_origin, m_turn_point, second.point) == -1)
168 // Second is collinear and going backwards
169 // Order as very last, so return always false
173 // They are not both collinear
175 if (side_first != side_second)
177 return compare(side_first, side_second);
180 // They are both left, both right, and/or both collinear (with each other and/or with p1,p2)
182 int const side_second_wrt_first = m_strategy.apply(m_turn_point, first.point, second.point);
184 if (side_second_wrt_first == 0)
186 return on_same(first, second);
189 int const side_first_wrt_second = -side_second_wrt_first;
191 // Both are on same side, and not collinear
192 // Union: return true if second is right w.r.t. first, so -1,
193 // so other is 1. union has greater as compare functor
194 // Intersection: v.v.
195 return compare(side_first_wrt_second, side_second_wrt_first);
199 Point const& m_origin;
200 Point const& m_turn_point;
201 SideStrategy const& m_strategy;
204 // Sorts vectors in counter clockwise order (by default)
209 overlay_type OverlayType,
211 typename SideStrategy,
216 typedef ranked_point<Point> rp;
221 inline bool operator()(rp const& ranked_point) const
223 // New candidate if there are no polygons on left side,
224 // but there are on right side
225 return ranked_point.count_left == 0
226 && ranked_point.count_right > 0;
230 struct include_intersection
232 inline bool operator()(rp const& ranked_point) const
234 // New candidate if there are two polygons on right side,
235 // and less on the left side
236 return ranked_point.count_left < 2
237 && ranked_point.count_right >= 2;
242 side_sorter(SideStrategy const& strategy)
244 , m_origin_segment_distance(0)
245 , m_strategy(strategy)
248 void add_segment_from(signed_size_type turn_index, int op_index,
249 Point const& point_from,
250 operation_type op, segment_identifier const& si,
253 m_ranked_points.push_back(rp(point_from, turn_index, op_index, dir_from, op, si));
256 m_origin = point_from;
261 void add_segment_to(signed_size_type turn_index, int op_index,
262 Point const& point_to,
263 operation_type op, segment_identifier const& si)
265 m_ranked_points.push_back(rp(point_to, turn_index, op_index, dir_to, op, si));
268 void add_segment(signed_size_type turn_index, int op_index,
269 Point const& point_from, Point const& point_to,
270 operation_type op, segment_identifier const& si,
273 add_segment_from(turn_index, op_index, point_from, op, si, is_origin);
274 add_segment_to(turn_index, op_index, point_to, op, si);
277 template <typename Operation, typename Geometry1, typename Geometry2>
278 Point add(Operation const& op, signed_size_type turn_index, int op_index,
279 Geometry1 const& geometry1,
280 Geometry2 const& geometry2,
283 Point point1, point2, point3;
284 geometry::copy_segment_points<Reverse1, Reverse2>(geometry1, geometry2,
285 op.seg_id, point1, point2, point3);
286 Point const& point_to = op.fraction.is_one() ? point3 : point2;
287 add_segment(turn_index, op_index, point1, point_to, op.operation, op.seg_id, is_origin);
291 template <typename Operation, typename Geometry1, typename Geometry2>
292 void add(Operation const& op, signed_size_type turn_index, int op_index,
293 segment_identifier const& departure_seg_id,
294 Geometry1 const& geometry1,
295 Geometry2 const& geometry2,
298 Point const point1 = add(op, turn_index, op_index, geometry1, geometry2, false);
303 = op.seg_id.source_index == departure_seg_id.source_index
304 && op.seg_id.ring_index == departure_seg_id.ring_index
305 && op.seg_id.multi_index == departure_seg_id.multi_index;
309 signed_size_type const segment_distance = calculate_segment_distance(op, departure_seg_id, geometry1, geometry2);
310 if (m_origin_count == 0 ||
311 segment_distance < m_origin_segment_distance)
314 m_origin_segment_distance = segment_distance;
321 template <typename Operation, typename Geometry1, typename Geometry2>
322 static signed_size_type calculate_segment_distance(Operation const& op,
323 segment_identifier const& departure_seg_id,
324 Geometry1 const& geometry1,
325 Geometry2 const& geometry2)
327 if (op.seg_id.segment_index >= departure_seg_id.segment_index)
329 // dep.seg_id=5, op.seg_id=7, distance=2, being segments 5,6
330 return op.seg_id.segment_index - departure_seg_id.segment_index;
332 // Take wrap into account
333 // Suppose point_count=10 (10 points, 9 segments), dep.seg_id=7, op.seg_id=2,
334 // then distance=9-7+2=4, being segments 7,8,0,1
335 std::size_t const segment_count
336 = op.seg_id.source_index == 0
337 ? segment_count_on_ring(geometry1, op.seg_id)
338 : segment_count_on_ring(geometry2, op.seg_id);
339 return segment_count - departure_seg_id.segment_index + op.seg_id.segment_index;
342 void apply(Point const& turn_point)
344 // We need three compare functors:
345 // 1) to order clockwise (union) or counter clockwise (intersection)
346 // 2) to order by side, resulting in unique ranks for all points
347 // 3) to order by side, resulting in non-unique ranks
348 // to give colinear points
350 // Sort by side and assign rank
351 less_by_side<Point, SideStrategy, less_by_index, Compare> less_unique(m_origin, turn_point, m_strategy);
352 less_by_side<Point, SideStrategy, less_false, Compare> less_non_unique(m_origin, turn_point, m_strategy);
354 std::sort(m_ranked_points.begin(), m_ranked_points.end(), less_unique);
356 std::size_t colinear_rank = 0;
357 for (std::size_t i = 0; i < m_ranked_points.size(); i++)
360 && less_non_unique(m_ranked_points[i - 1], m_ranked_points[i]))
362 // It is not collinear
366 m_ranked_points[i].rank = colinear_rank;
370 template <signed_size_type segment_identifier::*Member, typename Map>
371 void find_open_generic(Map& handled, bool check)
373 for (std::size_t i = 0; i < m_ranked_points.size(); i++)
375 const rp& ranked = m_ranked_points[i];
376 if (ranked.direction != dir_from)
381 signed_size_type const& index = ranked.seg_id.*Member;
382 if (check && (index < 0 || index > 1))
387 if (! handled[index])
389 find_polygons_for_source<Member>(index, i);
390 handled[index] = true;
397 if (BOOST_GEOMETRY_CONDITION(OverlayType == overlay_buffer))
399 // For buffers, use piece index
400 std::map<signed_size_type, bool> handled;
403 &segment_identifier::piece_index
408 // For other operations, by source (there should only source 0,1)
409 bool handled[2] = {false, false};
412 &segment_identifier::source_index
419 if (m_ranked_points.empty())
424 std::size_t const last = 1 + m_ranked_points.back().rank;
426 // Move iterator after rank==0
427 bool has_first = false;
428 typename container_type::iterator it = m_ranked_points.begin() + 1;
429 for (; it != m_ranked_points.end() && it->rank == 0; ++it)
436 // Reverse first part (having rank == 0), if any,
437 // but skip the very first row
438 std::reverse(m_ranked_points.begin() + 1, it);
439 for (typename container_type::iterator fit = m_ranked_points.begin();
442 BOOST_ASSERT(fit->rank == 0);
446 // Reverse the rest (main rank > 0)
447 std::reverse(it, m_ranked_points.end());
448 for (; it != m_ranked_points.end(); ++it)
450 BOOST_ASSERT(it->rank > 0);
451 it->rank = last - it->rank;
455 bool has_origin() const
457 return m_origin_count > 0;
462 typedef std::vector<rp> container_type;
463 container_type m_ranked_points;
465 std::size_t m_origin_count;
466 signed_size_type m_origin_segment_distance;
467 SideStrategy m_strategy;
471 //! Check how many open spaces there are
472 template <typename Include>
473 inline std::size_t open_count(Include const& include_functor) const
475 std::size_t result = 0;
476 rank_type last_rank = 0;
477 for (std::size_t i = 0; i < m_ranked_points.size(); i++)
479 rp const& ranked_point = m_ranked_points[i];
481 if (ranked_point.rank > last_rank
482 && ranked_point.direction == sort_by_side::dir_to
483 && include_functor(ranked_point))
486 last_rank = ranked_point.rank;
492 std::size_t move(std::size_t index) const
494 std::size_t const result = index + 1;
495 return result >= m_ranked_points.size() ? 0 : result;
498 //! member is pointer to member (source_index or multi_index)
499 template <signed_size_type segment_identifier::*Member>
500 std::size_t move(signed_size_type member_index, std::size_t index) const
502 std::size_t result = move(index);
503 while (m_ranked_points[result].seg_id.*Member != member_index)
505 result = move(result);
510 void assign_ranks(rank_type min_rank, rank_type max_rank, int side_index)
512 for (std::size_t i = 0; i < m_ranked_points.size(); i++)
514 rp& ranked = m_ranked_points[i];
515 // Suppose there are 8 ranks, if min=4,max=6: assign 4,5,6
516 // if min=5,max=2: assign from 5,6,7,1,2
518 = max_rank >= min_rank
519 ? ranked.rank >= min_rank && ranked.rank <= max_rank
520 : ranked.rank >= min_rank || ranked.rank <= max_rank
529 else if (side_index == 2)
531 ranked.count_right++;
537 template <signed_size_type segment_identifier::*Member>
538 void find_polygons_for_source(signed_size_type the_index,
539 std::size_t start_index)
541 bool in_polygon = true; // Because start_index is "from", arrives at the turn
542 rp const& start_rp = m_ranked_points[start_index];
543 rank_type last_from_rank = start_rp.rank;
544 rank_type previous_rank = start_rp.rank;
546 for (std::size_t index = move<Member>(the_index, start_index);
548 index = move<Member>(the_index, index))
550 rp& ranked = m_ranked_points[index];
552 if (ranked.rank != previous_rank && ! in_polygon)
554 assign_ranks(last_from_rank, previous_rank - 1, 1);
555 assign_ranks(last_from_rank + 1, previous_rank, 2);
558 if (index == start_index)
563 if (ranked.direction == dir_from)
565 last_from_rank = ranked.rank;
568 else if (ranked.direction == dir_to)
573 previous_rank = ranked.rank;
577 //! Find closed zones and assign it
578 template <typename Include>
579 std::size_t assign_zones(Include const& include_functor)
581 // Find a starting point (the first rank after an outgoing rank
582 // with no polygons on the left side)
583 rank_type start_rank = m_ranked_points.size() + 1;
584 std::size_t start_index = 0;
585 rank_type max_rank = 0;
586 for (std::size_t i = 0; i < m_ranked_points.size(); i++)
588 rp const& ranked_point = m_ranked_points[i];
589 if (ranked_point.rank > max_rank)
591 max_rank = ranked_point.rank;
593 if (ranked_point.direction == sort_by_side::dir_to
594 && include_functor(ranked_point))
596 start_rank = ranked_point.rank + 1;
598 if (ranked_point.rank == start_rank && start_index == 0)
605 rank_type const undefined_rank = max_rank + 1;
606 std::size_t zone_id = 0;
607 rank_type last_rank = 0;
608 rank_type rank_at_next_zone = undefined_rank;
609 std::size_t index = start_index;
610 for (std::size_t i = 0; i < m_ranked_points.size(); i++)
612 rp& ranked_point = m_ranked_points[index];
614 // Implement cyclic behavior
616 if (index == m_ranked_points.size())
621 if (ranked_point.rank != last_rank)
623 if (ranked_point.rank == rank_at_next_zone)
626 rank_at_next_zone = undefined_rank;
629 if (ranked_point.direction == sort_by_side::dir_to
630 && include_functor(ranked_point))
632 rank_at_next_zone = ranked_point.rank + 1;
633 if (rank_at_next_zone > max_rank)
635 rank_at_next_zone = 0;
639 last_rank = ranked_point.rank;
642 ranked_point.zone = zone_id;
648 inline std::size_t open_count(operation_type for_operation) const
650 return for_operation == operation_union
651 ? open_count(include_union())
652 : open_count(include_intersection())
656 inline std::size_t assign_zones(operation_type for_operation)
658 return for_operation == operation_union
659 ? assign_zones(include_union())
660 : assign_zones(include_intersection())
667 //! Metafunction to define side_order (clockwise, ccw) by operation_type
668 template <operation_type OpType>
669 struct side_compare {};
672 struct side_compare<operation_union>
674 typedef std::greater<int> type;
678 struct side_compare<operation_intersection>
680 typedef std::less<int> type;
684 }}} // namespace detail::overlay::sort_by_side
685 #endif //DOXYGEN_NO_DETAIL
688 }} // namespace boost::geometry
690 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SORT_BY_SIDE_HPP