123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558 |
- // Boost.Geometry (aka GGL, Generic Geometry Library)
- // Copyright (c) 2007-2012 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_ENRICH_HPP
- #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ENRICH_HPP
- #include <cstddef>
- #include <algorithm>
- #include <map>
- #include <set>
- #include <vector>
- #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
- # include <iostream>
- # include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
- # include <boost/geometry/io/wkt/wkt.hpp>
- # if ! defined(BOOST_GEOMETRY_DEBUG_IDENTIFIER)
- # define BOOST_GEOMETRY_DEBUG_IDENTIFIER
- #endif
- #endif
- #include <boost/range.hpp>
- #include <boost/geometry/algorithms/detail/ring_identifier.hpp>
- #include <boost/geometry/algorithms/detail/overlay/handle_colocations.hpp>
- #include <boost/geometry/algorithms/detail/overlay/handle_self_turns.hpp>
- #include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp>
- #include <boost/geometry/algorithms/detail/overlay/less_by_segment_ratio.hpp>
- #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
- #include <boost/geometry/policies/robustness/robust_type.hpp>
- #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
- # include <boost/geometry/algorithms/detail/overlay/check_enrich.hpp>
- #endif
- namespace boost { namespace geometry
- {
- #ifndef DOXYGEN_NO_DETAIL
- namespace detail { namespace overlay
- {
- template <typename Turns>
- struct discarded_indexed_turn
- {
- discarded_indexed_turn(Turns const& turns)
- : m_turns(turns)
- {}
- template <typename IndexedTurn>
- inline bool operator()(IndexedTurn const& indexed) const
- {
- return m_turns[indexed.turn_index].discarded;
- }
- Turns const& m_turns;
- };
- // Sorts IP-s of this ring on segment-identifier, and if on same segment,
- // on distance.
- // Then assigns for each IP which is the next IP on this segment,
- // plus the vertex-index to travel to, plus the next IP
- // (might be on another segment)
- template
- <
- bool Reverse1, bool Reverse2,
- typename Operations,
- typename Turns,
- typename Geometry1, typename Geometry2,
- typename RobustPolicy,
- typename SideStrategy
- >
- inline void enrich_sort(Operations& operations,
- Turns const& turns,
- Geometry1 const& geometry1,
- Geometry2 const& geometry2,
- RobustPolicy const& robust_policy,
- SideStrategy const& strategy)
- {
- std::sort(boost::begin(operations),
- boost::end(operations),
- less_by_segment_ratio
- <
- Turns,
- typename boost::range_value<Operations>::type,
- Geometry1, Geometry2,
- RobustPolicy,
- SideStrategy,
- Reverse1, Reverse2
- >(turns, geometry1, geometry2, robust_policy, strategy));
- }
- template <typename Operations, typename Turns>
- inline void enrich_assign(Operations& operations, Turns& turns,
- bool check_turns)
- {
- typedef typename boost::range_value<Turns>::type turn_type;
- typedef typename turn_type::turn_operation_type op_type;
- typedef typename boost::range_iterator<Operations>::type iterator_type;
- if (operations.size() > 0)
- {
- // Assign travel-to-vertex/ip index for each turning point.
- // Iterator "next" is circular
- geometry::ever_circling_range_iterator<Operations const> next(operations);
- ++next;
- for (iterator_type it = boost::begin(operations);
- it != boost::end(operations); ++it)
- {
- turn_type& turn = turns[it->turn_index];
- op_type& op = turn.operations[it->operation_index];
- if (check_turns && it->turn_index == next->turn_index)
- {
- // Normal behaviour: next points at next turn, increase next.
- // For dissolve this should not be done, turn_index is often
- // the same for two consecutive operations
- ++next;
- }
- // Cluster behaviour: next should point after cluster, unless
- // their seg_ids are not the same
- // (For dissolve, this is still to be examined - TODO)
- while (turn.is_clustered()
- && it->turn_index != next->turn_index
- && turn.cluster_id == turns[next->turn_index].cluster_id
- && op.seg_id == turns[next->turn_index].operations[next->operation_index].seg_id)
- {
- ++next;
- }
- turn_type const& next_turn = turns[next->turn_index];
- op_type const& next_op = next_turn.operations[next->operation_index];
- op.enriched.travels_to_ip_index
- = static_cast<signed_size_type>(next->turn_index);
- op.enriched.travels_to_vertex_index
- = next->subject->seg_id.segment_index;
- if (op.seg_id.segment_index == next_op.seg_id.segment_index
- && op.fraction < next_op.fraction)
- {
- // Next turn is located further on same segment
- // assign next_ip_index
- // (this is one not circular therefore fraction is considered)
- op.enriched.next_ip_index = static_cast<signed_size_type>(next->turn_index);
- }
- if (! check_turns)
- {
- ++next;
- }
- }
- }
- // DEBUG
- #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
- {
- for (iterator_type it = boost::begin(operations);
- it != boost::end(operations);
- ++it)
- {
- op_type const& op = turns[it->turn_index]
- .operations[it->operation_index];
- std::cout << it->turn_index
- << " cl=" << turns[it->turn_index].cluster_id
- << " meth=" << method_char(turns[it->turn_index].method)
- << " seg=" << op.seg_id
- << " dst=" << op.fraction // needs define
- << " op=" << operation_char(turns[it->turn_index].operations[0].operation)
- << operation_char(turns[it->turn_index].operations[1].operation)
- << " (" << operation_char(op.operation) << ")"
- << " nxt=" << op.enriched.next_ip_index
- << " / " << op.enriched.travels_to_ip_index
- << " [vx " << op.enriched.travels_to_vertex_index << "]"
- << std::boolalpha << turns[it->turn_index].discarded
- << std::endl;
- ;
- }
- }
- #endif
- // END DEBUG
- }
- template <typename Operations, typename Turns>
- inline void enrich_adapt(Operations& operations, Turns& turns)
- {
- typedef typename boost::range_value<Turns>::type turn_type;
- typedef typename turn_type::turn_operation_type op_type;
- typedef typename boost::range_value<Operations>::type indexed_turn_type;
- if (operations.size() < 3)
- {
- // If it is empty, or contains one or two turns, it makes no sense
- return;
- }
- // Operations is a vector of indexed_turn_operation<>
- // Last index:
- std::size_t const x = operations.size() - 1;
- bool next_phase = false;
- for (std::size_t i = 0; i < operations.size(); i++)
- {
- indexed_turn_type const& indexed = operations[i];
- turn_type& turn = turns[indexed.turn_index];
- op_type& op = turn.operations[indexed.operation_index];
- // Previous/next index
- std::size_t const p = i > 0 ? i - 1 : x;
- std::size_t const n = i < x ? i + 1 : 0;
- turn_type const& next_turn = turns[operations[n].turn_index];
- op_type const& next_op = next_turn.operations[operations[n].operation_index];
- if (op.seg_id.segment_index == next_op.seg_id.segment_index)
- {
- turn_type const& prev_turn = turns[operations[p].turn_index];
- op_type const& prev_op = prev_turn.operations[operations[p].operation_index];
- if (op.seg_id.segment_index == prev_op.seg_id.segment_index)
- {
- op.enriched.startable = false;
- next_phase = true;
- }
- }
- }
- if (! next_phase)
- {
- return;
- }
- // Discard turns which are both non-startable
- next_phase = false;
- for (typename boost::range_iterator<Turns>::type
- it = boost::begin(turns);
- it != boost::end(turns);
- ++it)
- {
- turn_type& turn = *it;
- if (! turn.operations[0].enriched.startable
- && ! turn.operations[1].enriched.startable)
- {
- turn.discarded = true;
- next_phase = true;
- }
- }
- if (! next_phase)
- {
- return;
- }
- // Remove discarded turns from operations to avoid having them as next turn
- discarded_indexed_turn<Turns> const predicate(turns);
- operations.erase(std::remove_if(boost::begin(operations),
- boost::end(operations), predicate), boost::end(operations));
- }
- template <typename Turns, typename MappedVector>
- inline void create_map(Turns const& turns, MappedVector& mapped_vector)
- {
- typedef typename boost::range_value<Turns>::type turn_type;
- typedef typename turn_type::container_type container_type;
- typedef typename MappedVector::mapped_type mapped_type;
- typedef typename boost::range_value<mapped_type>::type indexed_type;
- std::size_t index = 0;
- for (typename boost::range_iterator<Turns const>::type
- it = boost::begin(turns);
- it != boost::end(turns);
- ++it, ++index)
- {
- // Add all (non discarded) operations on this ring
- // Blocked operations or uu on clusters (for intersection)
- // should be included, to block potential paths in clusters
- turn_type const& turn = *it;
- if (turn.discarded)
- {
- continue;
- }
- std::size_t op_index = 0;
- for (typename boost::range_iterator<container_type const>::type
- op_it = boost::begin(turn.operations);
- op_it != boost::end(turn.operations);
- ++op_it, ++op_index)
- {
- ring_identifier const ring_id
- (
- op_it->seg_id.source_index,
- op_it->seg_id.multi_index,
- op_it->seg_id.ring_index
- );
- mapped_vector[ring_id].push_back
- (
- indexed_type(index, op_index, *op_it,
- it->operations[1 - op_index].seg_id)
- );
- }
- }
- }
- template <typename Point1, typename Point2>
- inline typename geometry::coordinate_type<Point1>::type
- distance_measure(Point1 const& a, Point2 const& b)
- {
- // TODO: use comparable distance for point-point instead - but that
- // causes currently cycling include problems
- typedef typename geometry::coordinate_type<Point1>::type ctype;
- ctype const dx = get<0>(a) - get<0>(b);
- ctype const dy = get<1>(a) - get<1>(b);
- return dx * dx + dy * dy;
- }
- template <typename Turns>
- inline void calculate_remaining_distance(Turns& turns)
- {
- typedef typename boost::range_value<Turns>::type turn_type;
- typedef typename turn_type::turn_operation_type op_type;
- for (typename boost::range_iterator<Turns>::type
- it = boost::begin(turns);
- it != boost::end(turns);
- ++it)
- {
- turn_type& turn = *it;
- op_type& op0 = turn.operations[0];
- op_type& op1 = turn.operations[1];
- if (op0.remaining_distance != 0
- || op1.remaining_distance != 0)
- {
- continue;
- }
- signed_size_type const to_index0 = op0.enriched.get_next_turn_index();
- signed_size_type const to_index1 = op1.enriched.get_next_turn_index();
- if (to_index0 >= 0
- && to_index1 >= 0
- && to_index0 != to_index1)
- {
- op0.remaining_distance = distance_measure(turn.point, turns[to_index0].point);
- op1.remaining_distance = distance_measure(turn.point, turns[to_index1].point);
- }
- }
- }
- }} // namespace detail::overlay
- #endif //DOXYGEN_NO_DETAIL
- /*!
- \brief All intersection points are enriched with successor information
- \ingroup overlay
- \tparam Turns type of intersection container
- (e.g. vector of "intersection/turn point"'s)
- \tparam Clusters type of cluster container
- \tparam Geometry1 \tparam_geometry
- \tparam Geometry2 \tparam_geometry
- \tparam PointInGeometryStrategy point in geometry strategy type
- \param turns container containing intersection points
- \param clusters container containing clusters
- \param geometry1 \param_geometry
- \param geometry2 \param_geometry
- \param robust_policy policy to handle robustness issues
- \param strategy point in geometry strategy
- */
- template
- <
- bool Reverse1, bool Reverse2,
- overlay_type OverlayType,
- typename Turns,
- typename Clusters,
- typename Geometry1, typename Geometry2,
- typename RobustPolicy,
- typename IntersectionStrategy
- >
- inline void enrich_intersection_points(Turns& turns,
- Clusters& clusters,
- Geometry1 const& geometry1, Geometry2 const& geometry2,
- RobustPolicy const& robust_policy,
- IntersectionStrategy const& strategy)
- {
- static const detail::overlay::operation_type target_operation
- = detail::overlay::operation_from_overlay<OverlayType>::value;
- static const detail::overlay::operation_type opposite_operation
- = target_operation == detail::overlay::operation_union
- ? detail::overlay::operation_intersection
- : detail::overlay::operation_union;
- static const bool is_dissolve = OverlayType == overlay_dissolve;
- typedef typename boost::range_value<Turns>::type turn_type;
- typedef typename turn_type::turn_operation_type op_type;
- typedef detail::overlay::indexed_turn_operation
- <
- op_type
- > indexed_turn_operation;
- typedef std::map
- <
- ring_identifier,
- std::vector<indexed_turn_operation>
- > mapped_vector_type;
- // From here on, turn indexes are used (in clusters, next_index, etc)
- // and may only be flagged as discarded
- bool has_cc = false;
- bool const has_colocations
- = detail::overlay::handle_colocations<Reverse1, Reverse2, OverlayType>(turns,
- clusters, geometry1, geometry2);
- // Discard turns not part of target overlay
- for (typename boost::range_iterator<Turns>::type
- it = boost::begin(turns);
- it != boost::end(turns);
- ++it)
- {
- turn_type& turn = *it;
- if (turn.both(detail::overlay::operation_none)
- || turn.both(opposite_operation)
- || turn.both(detail::overlay::operation_blocked)
- || (detail::overlay::is_self_turn<OverlayType>(turn)
- && ! turn.is_clustered()
- && ! turn.both(target_operation)))
- {
- // For all operations, discard xx and none/none
- // For intersections, remove uu to avoid the need to travel
- // a union (during intersection) in uu/cc clusters (e.g. #31,#32,#33)
- // The ux is necessary to indicate impossible paths
- // (especially if rescaling is removed)
- // Similarly, for union, discard ii and ix
- // For self-turns, only keep uu / ii
- turn.discarded = true;
- turn.cluster_id = -1;
- continue;
- }
- if (! turn.discarded
- && turn.both(detail::overlay::operation_continue))
- {
- has_cc = true;
- }
- }
- if (! is_dissolve)
- {
- detail::overlay::discard_closed_turns
- <
- OverlayType,
- target_operation
- >::apply(turns, clusters, geometry1, geometry2,
- strategy);
- detail::overlay::discard_open_turns
- <
- OverlayType,
- target_operation
- >::apply(turns, clusters, geometry1, geometry2,
- strategy);
- }
- // Create a map of vectors of indexed operation-types to be able
- // to sort intersection points PER RING
- mapped_vector_type mapped_vector;
- detail::overlay::create_map(turns, mapped_vector);
- // No const-iterator; contents of mapped copy is temporary,
- // and changed by enrich
- for (typename mapped_vector_type::iterator mit
- = mapped_vector.begin();
- mit != mapped_vector.end();
- ++mit)
- {
- #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
- std::cout << "ENRICH-sort Ring "
- << mit->first << std::endl;
- #endif
- detail::overlay::enrich_sort<Reverse1, Reverse2>(
- mit->second, turns,
- geometry1, geometry2,
- robust_policy, strategy.get_side_strategy());
- }
- for (typename mapped_vector_type::iterator mit
- = mapped_vector.begin();
- mit != mapped_vector.end();
- ++mit)
- {
- #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
- std::cout << "ENRICH-assign Ring "
- << mit->first << std::endl;
- #endif
- if (is_dissolve)
- {
- detail::overlay::enrich_adapt(mit->second, turns);
- }
- detail::overlay::enrich_assign(mit->second, turns, ! is_dissolve);
- }
- if (has_colocations)
- {
- // First gather cluster properties (using even clusters with
- // discarded turns - for open turns), then clean up clusters
- detail::overlay::gather_cluster_properties
- <
- Reverse1,
- Reverse2,
- OverlayType
- >(clusters, turns, target_operation,
- geometry1, geometry2, strategy.get_side_strategy());
- detail::overlay::cleanup_clusters(turns, clusters);
- }
- if (has_cc)
- {
- detail::overlay::calculate_remaining_distance(turns);
- }
- #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
- //detail::overlay::check_graph(turns, for_operation);
- #endif
- }
- }} // namespace boost::geometry
- #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ENRICH_HPP
|