123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690 |
- // Boost.Geometry (aka GGL, Generic Geometry Library)
- // Copyright (c) 2015 Barend Gehrels, Amsterdam, the Netherlands.
- // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
- // This file was modified by Oracle on 2017, 2019.
- // Modifications copyright (c) 2017, 2019 Oracle and/or its affiliates.
- // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
- // 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_DETAIL_OVERLAY_SORT_BY_SIDE_HPP
- #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SORT_BY_SIDE_HPP
- #include <algorithm>
- #include <map>
- #include <vector>
- #include <boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp>
- #include <boost/geometry/algorithms/detail/overlay/get_ring.hpp>
- #include <boost/geometry/algorithms/detail/direction_code.hpp>
- #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
- #include <boost/geometry/util/condition.hpp>
- namespace boost { namespace geometry
- {
- #ifndef DOXYGEN_NO_DETAIL
- namespace detail { namespace overlay { namespace sort_by_side
- {
- enum direction_type { dir_unknown = -1, dir_from = 0, dir_to = 1 };
- typedef signed_size_type rank_type;
- // Point-wrapper, adding some properties
- template <typename Point>
- struct ranked_point
- {
- ranked_point()
- : rank(0)
- , turn_index(-1)
- , operation_index(-1)
- , direction(dir_unknown)
- , count_left(0)
- , count_right(0)
- , operation(operation_none)
- {}
- ranked_point(Point const& p, signed_size_type ti, int oi,
- direction_type d, operation_type op, segment_identifier const& si)
- : point(p)
- , rank(0)
- , zone(-1)
- , turn_index(ti)
- , operation_index(oi)
- , direction(d)
- , count_left(0)
- , count_right(0)
- , operation(op)
- , seg_id(si)
- {}
- Point point;
- rank_type rank;
- signed_size_type zone; // index of closed zone, in uu turn there would be 2 zones
- signed_size_type turn_index;
- int operation_index; // 0,1
- direction_type direction;
- std::size_t count_left;
- std::size_t count_right;
- operation_type operation;
- segment_identifier seg_id;
- };
- struct less_by_turn_index
- {
- template <typename T>
- inline bool operator()(const T& first, const T& second) const
- {
- return first.turn_index == second.turn_index
- ? first.index < second.index
- : first.turn_index < second.turn_index
- ;
- }
- };
- struct less_by_index
- {
- template <typename T>
- inline bool operator()(const T& first, const T& second) const
- {
- // Length might be considered too
- // First order by from/to
- if (first.direction != second.direction)
- {
- return first.direction < second.direction;
- }
- // Then by turn index
- if (first.turn_index != second.turn_index)
- {
- return first.turn_index < second.turn_index;
- }
- // This can also be the same (for example in buffer), but seg_id is
- // never the same
- return first.seg_id < second.seg_id;
- }
- };
- struct less_false
- {
- template <typename T>
- inline bool operator()(const T&, const T& ) const
- {
- return false;
- }
- };
- template <typename Point, typename SideStrategy, typename LessOnSame, typename Compare>
- struct less_by_side
- {
- less_by_side(const Point& p1, const Point& p2, SideStrategy const& strategy)
- : m_origin(p1)
- , m_turn_point(p2)
- , m_strategy(strategy)
- {}
- template <typename T>
- inline bool operator()(const T& first, const T& second) const
- {
- typedef typename SideStrategy::cs_tag cs_tag;
- LessOnSame on_same;
- Compare compare;
- int const side_first = m_strategy.apply(m_origin, m_turn_point, first.point);
- int const side_second = m_strategy.apply(m_origin, m_turn_point, second.point);
- if (side_first == 0 && side_second == 0)
- {
- // Both collinear. They might point into different directions: <------*------>
- // If so, order the one going backwards as the very first.
- int const first_code = direction_code<cs_tag>(m_origin, m_turn_point, first.point);
- int const second_code = direction_code<cs_tag>(m_origin, m_turn_point, second.point);
- // Order by code, backwards first, then forward.
- return first_code != second_code
- ? first_code < second_code
- : on_same(first, second)
- ;
- }
- else if (side_first == 0
- && direction_code<cs_tag>(m_origin, m_turn_point, first.point) == -1)
- {
- // First collinear and going backwards.
- // Order as the very first, so return always true
- return true;
- }
- else if (side_second == 0
- && direction_code<cs_tag>(m_origin, m_turn_point, second.point) == -1)
- {
- // Second is collinear and going backwards
- // Order as very last, so return always false
- return false;
- }
- // They are not both collinear
- if (side_first != side_second)
- {
- return compare(side_first, side_second);
- }
- // They are both left, both right, and/or both collinear (with each other and/or with p1,p2)
- // Check mutual side
- int const side_second_wrt_first = m_strategy.apply(m_turn_point, first.point, second.point);
- if (side_second_wrt_first == 0)
- {
- return on_same(first, second);
- }
- int const side_first_wrt_second = -side_second_wrt_first;
- // Both are on same side, and not collinear
- // Union: return true if second is right w.r.t. first, so -1,
- // so other is 1. union has greater as compare functor
- // Intersection: v.v.
- return compare(side_first_wrt_second, side_second_wrt_first);
- }
- private :
- Point const& m_origin;
- Point const& m_turn_point;
- SideStrategy const& m_strategy;
- };
- // Sorts vectors in counter clockwise order (by default)
- template
- <
- bool Reverse1,
- bool Reverse2,
- overlay_type OverlayType,
- typename Point,
- typename SideStrategy,
- typename Compare
- >
- struct side_sorter
- {
- typedef ranked_point<Point> rp;
- private :
- struct include_union
- {
- inline bool operator()(rp const& ranked_point) const
- {
- // New candidate if there are no polygons on left side,
- // but there are on right side
- return ranked_point.count_left == 0
- && ranked_point.count_right > 0;
- }
- };
- struct include_intersection
- {
- inline bool operator()(rp const& ranked_point) const
- {
- // New candidate if there are two polygons on right side,
- // and less on the left side
- return ranked_point.count_left < 2
- && ranked_point.count_right >= 2;
- }
- };
- public :
- side_sorter(SideStrategy const& strategy)
- : m_origin_count(0)
- , m_origin_segment_distance(0)
- , m_strategy(strategy)
- {}
- void add_segment_from(signed_size_type turn_index, int op_index,
- Point const& point_from,
- operation_type op, segment_identifier const& si,
- bool is_origin)
- {
- m_ranked_points.push_back(rp(point_from, turn_index, op_index, dir_from, op, si));
- if (is_origin)
- {
- m_origin = point_from;
- m_origin_count++;
- }
- }
- void add_segment_to(signed_size_type turn_index, int op_index,
- Point const& point_to,
- operation_type op, segment_identifier const& si)
- {
- m_ranked_points.push_back(rp(point_to, turn_index, op_index, dir_to, op, si));
- }
- void add_segment(signed_size_type turn_index, int op_index,
- Point const& point_from, Point const& point_to,
- operation_type op, segment_identifier const& si,
- bool is_origin)
- {
- add_segment_from(turn_index, op_index, point_from, op, si, is_origin);
- add_segment_to(turn_index, op_index, point_to, op, si);
- }
- template <typename Operation, typename Geometry1, typename Geometry2>
- Point add(Operation const& op, signed_size_type turn_index, int op_index,
- Geometry1 const& geometry1,
- Geometry2 const& geometry2,
- bool is_origin)
- {
- Point point1, point2, point3;
- geometry::copy_segment_points<Reverse1, Reverse2>(geometry1, geometry2,
- op.seg_id, point1, point2, point3);
- Point const& point_to = op.fraction.is_one() ? point3 : point2;
- add_segment(turn_index, op_index, point1, point_to, op.operation, op.seg_id, is_origin);
- return point1;
- }
- template <typename Operation, typename Geometry1, typename Geometry2>
- void add(Operation const& op, signed_size_type turn_index, int op_index,
- segment_identifier const& departure_seg_id,
- Geometry1 const& geometry1,
- Geometry2 const& geometry2,
- bool check_origin)
- {
- Point const point1 = add(op, turn_index, op_index, geometry1, geometry2, false);
- if (check_origin)
- {
- bool const is_origin
- = op.seg_id.source_index == departure_seg_id.source_index
- && op.seg_id.ring_index == departure_seg_id.ring_index
- && op.seg_id.multi_index == departure_seg_id.multi_index;
- if (is_origin)
- {
- signed_size_type const segment_distance = calculate_segment_distance(op, departure_seg_id, geometry1, geometry2);
- if (m_origin_count == 0 ||
- segment_distance < m_origin_segment_distance)
- {
- m_origin = point1;
- m_origin_segment_distance = segment_distance;
- }
- m_origin_count++;
- }
- }
- }
- template <typename Operation, typename Geometry1, typename Geometry2>
- static signed_size_type calculate_segment_distance(Operation const& op,
- segment_identifier const& departure_seg_id,
- Geometry1 const& geometry1,
- Geometry2 const& geometry2)
- {
- if (op.seg_id.segment_index >= departure_seg_id.segment_index)
- {
- // dep.seg_id=5, op.seg_id=7, distance=2, being segments 5,6
- return op.seg_id.segment_index - departure_seg_id.segment_index;
- }
- // Take wrap into account
- // Suppose point_count=10 (10 points, 9 segments), dep.seg_id=7, op.seg_id=2,
- // then distance=9-7+2=4, being segments 7,8,0,1
- std::size_t const segment_count
- = op.seg_id.source_index == 0
- ? segment_count_on_ring(geometry1, op.seg_id)
- : segment_count_on_ring(geometry2, op.seg_id);
- return segment_count - departure_seg_id.segment_index + op.seg_id.segment_index;
- }
- void apply(Point const& turn_point)
- {
- // We need three compare functors:
- // 1) to order clockwise (union) or counter clockwise (intersection)
- // 2) to order by side, resulting in unique ranks for all points
- // 3) to order by side, resulting in non-unique ranks
- // to give colinear points
- // Sort by side and assign rank
- less_by_side<Point, SideStrategy, less_by_index, Compare> less_unique(m_origin, turn_point, m_strategy);
- less_by_side<Point, SideStrategy, less_false, Compare> less_non_unique(m_origin, turn_point, m_strategy);
- std::sort(m_ranked_points.begin(), m_ranked_points.end(), less_unique);
- std::size_t colinear_rank = 0;
- for (std::size_t i = 0; i < m_ranked_points.size(); i++)
- {
- if (i > 0
- && less_non_unique(m_ranked_points[i - 1], m_ranked_points[i]))
- {
- // It is not collinear
- colinear_rank++;
- }
- m_ranked_points[i].rank = colinear_rank;
- }
- }
- template <signed_size_type segment_identifier::*Member, typename Map>
- void find_open_generic(Map& handled, bool check)
- {
- for (std::size_t i = 0; i < m_ranked_points.size(); i++)
- {
- const rp& ranked = m_ranked_points[i];
- if (ranked.direction != dir_from)
- {
- continue;
- }
- signed_size_type const& index = ranked.seg_id.*Member;
- if (check && (index < 0 || index > 1))
- {
- // Should not occur
- continue;
- }
- if (! handled[index])
- {
- find_polygons_for_source<Member>(index, i);
- handled[index] = true;
- }
- }
- }
- void find_open()
- {
- if (BOOST_GEOMETRY_CONDITION(OverlayType == overlay_buffer))
- {
- // For buffers, use piece index
- std::map<signed_size_type, bool> handled;
- find_open_generic
- <
- &segment_identifier::piece_index
- >(handled, false);
- }
- else
- {
- // For other operations, by source (there should only source 0,1)
- bool handled[2] = {false, false};
- find_open_generic
- <
- &segment_identifier::source_index
- >(handled, true);
- }
- }
- void reverse()
- {
- if (m_ranked_points.empty())
- {
- return;
- }
- std::size_t const last = 1 + m_ranked_points.back().rank;
- // Move iterator after rank==0
- bool has_first = false;
- typename container_type::iterator it = m_ranked_points.begin() + 1;
- for (; it != m_ranked_points.end() && it->rank == 0; ++it)
- {
- has_first = true;
- }
- if (has_first)
- {
- // Reverse first part (having rank == 0), if any,
- // but skip the very first row
- std::reverse(m_ranked_points.begin() + 1, it);
- for (typename container_type::iterator fit = m_ranked_points.begin();
- fit != it; ++fit)
- {
- BOOST_ASSERT(fit->rank == 0);
- }
- }
- // Reverse the rest (main rank > 0)
- std::reverse(it, m_ranked_points.end());
- for (; it != m_ranked_points.end(); ++it)
- {
- BOOST_ASSERT(it->rank > 0);
- it->rank = last - it->rank;
- }
- }
- bool has_origin() const
- {
- return m_origin_count > 0;
- }
- //private :
- typedef std::vector<rp> container_type;
- container_type m_ranked_points;
- Point m_origin;
- std::size_t m_origin_count;
- signed_size_type m_origin_segment_distance;
- SideStrategy m_strategy;
- private :
- //! Check how many open spaces there are
- template <typename Include>
- inline std::size_t open_count(Include const& include_functor) const
- {
- std::size_t result = 0;
- rank_type last_rank = 0;
- for (std::size_t i = 0; i < m_ranked_points.size(); i++)
- {
- rp const& ranked_point = m_ranked_points[i];
- if (ranked_point.rank > last_rank
- && ranked_point.direction == sort_by_side::dir_to
- && include_functor(ranked_point))
- {
- result++;
- last_rank = ranked_point.rank;
- }
- }
- return result;
- }
- std::size_t move(std::size_t index) const
- {
- std::size_t const result = index + 1;
- return result >= m_ranked_points.size() ? 0 : result;
- }
- //! member is pointer to member (source_index or multi_index)
- template <signed_size_type segment_identifier::*Member>
- std::size_t move(signed_size_type member_index, std::size_t index) const
- {
- std::size_t result = move(index);
- while (m_ranked_points[result].seg_id.*Member != member_index)
- {
- result = move(result);
- }
- return result;
- }
- void assign_ranks(rank_type min_rank, rank_type max_rank, int side_index)
- {
- for (std::size_t i = 0; i < m_ranked_points.size(); i++)
- {
- rp& ranked = m_ranked_points[i];
- // Suppose there are 8 ranks, if min=4,max=6: assign 4,5,6
- // if min=5,max=2: assign from 5,6,7,1,2
- bool const in_range
- = max_rank >= min_rank
- ? ranked.rank >= min_rank && ranked.rank <= max_rank
- : ranked.rank >= min_rank || ranked.rank <= max_rank
- ;
- if (in_range)
- {
- if (side_index == 1)
- {
- ranked.count_left++;
- }
- else if (side_index == 2)
- {
- ranked.count_right++;
- }
- }
- }
- }
- template <signed_size_type segment_identifier::*Member>
- void find_polygons_for_source(signed_size_type the_index,
- std::size_t start_index)
- {
- bool in_polygon = true; // Because start_index is "from", arrives at the turn
- rp const& start_rp = m_ranked_points[start_index];
- rank_type last_from_rank = start_rp.rank;
- rank_type previous_rank = start_rp.rank;
- for (std::size_t index = move<Member>(the_index, start_index);
- ;
- index = move<Member>(the_index, index))
- {
- rp& ranked = m_ranked_points[index];
- if (ranked.rank != previous_rank && ! in_polygon)
- {
- assign_ranks(last_from_rank, previous_rank - 1, 1);
- assign_ranks(last_from_rank + 1, previous_rank, 2);
- }
- if (index == start_index)
- {
- return;
- }
- if (ranked.direction == dir_from)
- {
- last_from_rank = ranked.rank;
- in_polygon = true;
- }
- else if (ranked.direction == dir_to)
- {
- in_polygon = false;
- }
- previous_rank = ranked.rank;
- }
- }
- //! Find closed zones and assign it
- template <typename Include>
- std::size_t assign_zones(Include const& include_functor)
- {
- // Find a starting point (the first rank after an outgoing rank
- // with no polygons on the left side)
- rank_type start_rank = m_ranked_points.size() + 1;
- std::size_t start_index = 0;
- rank_type max_rank = 0;
- for (std::size_t i = 0; i < m_ranked_points.size(); i++)
- {
- rp const& ranked_point = m_ranked_points[i];
- if (ranked_point.rank > max_rank)
- {
- max_rank = ranked_point.rank;
- }
- if (ranked_point.direction == sort_by_side::dir_to
- && include_functor(ranked_point))
- {
- start_rank = ranked_point.rank + 1;
- }
- if (ranked_point.rank == start_rank && start_index == 0)
- {
- start_index = i;
- }
- }
- // Assign the zones
- rank_type const undefined_rank = max_rank + 1;
- std::size_t zone_id = 0;
- rank_type last_rank = 0;
- rank_type rank_at_next_zone = undefined_rank;
- std::size_t index = start_index;
- for (std::size_t i = 0; i < m_ranked_points.size(); i++)
- {
- rp& ranked_point = m_ranked_points[index];
- // Implement cyclic behavior
- index++;
- if (index == m_ranked_points.size())
- {
- index = 0;
- }
- if (ranked_point.rank != last_rank)
- {
- if (ranked_point.rank == rank_at_next_zone)
- {
- zone_id++;
- rank_at_next_zone = undefined_rank;
- }
- if (ranked_point.direction == sort_by_side::dir_to
- && include_functor(ranked_point))
- {
- rank_at_next_zone = ranked_point.rank + 1;
- if (rank_at_next_zone > max_rank)
- {
- rank_at_next_zone = 0;
- }
- }
- last_rank = ranked_point.rank;
- }
- ranked_point.zone = zone_id;
- }
- return zone_id;
- }
- public :
- inline std::size_t open_count(operation_type for_operation) const
- {
- return for_operation == operation_union
- ? open_count(include_union())
- : open_count(include_intersection())
- ;
- }
- inline std::size_t assign_zones(operation_type for_operation)
- {
- return for_operation == operation_union
- ? assign_zones(include_union())
- : assign_zones(include_intersection())
- ;
- }
- };
- //! Metafunction to define side_order (clockwise, ccw) by operation_type
- template <operation_type OpType>
- struct side_compare {};
- template <>
- struct side_compare<operation_union>
- {
- typedef std::greater<int> type;
- };
- template <>
- struct side_compare<operation_intersection>
- {
- typedef std::less<int> type;
- };
- }}} // namespace detail::overlay::sort_by_side
- #endif //DOXYGEN_NO_DETAIL
- }} // namespace boost::geometry
- #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SORT_BY_SIDE_HPP
|