12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211 |
- // Boost.Geometry (aka GGL, Generic Geometry Library)
- // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
- // Copyright (c) 2014-2017 Adam Wulkiewicz, Lodz, Poland.
- // This file was modified by Oracle on 2014, 2016, 2017, 2018.
- // Modifications copyright (c) 2014-2018 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_GET_TURNS_HPP
- #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURNS_HPP
- #include <cstddef>
- #include <map>
- #include <boost/array.hpp>
- #include <boost/concept_check.hpp>
- #include <boost/core/ignore_unused.hpp>
- #include <boost/mpl/if.hpp>
- #include <boost/mpl/vector_c.hpp>
- #include <boost/range.hpp>
- #include <boost/geometry/core/access.hpp>
- #include <boost/geometry/core/assert.hpp>
- #include <boost/geometry/core/coordinate_dimension.hpp>
- #include <boost/geometry/core/exterior_ring.hpp>
- #include <boost/geometry/core/interior_rings.hpp>
- #include <boost/geometry/core/reverse_dispatch.hpp>
- #include <boost/geometry/core/ring_type.hpp>
- #include <boost/geometry/core/tags.hpp>
- #include <boost/geometry/geometries/concepts/check.hpp>
- #include <boost/geometry/util/math.hpp>
- #include <boost/geometry/views/closeable_view.hpp>
- #include <boost/geometry/views/reversible_view.hpp>
- #include <boost/geometry/views/detail/range_type.hpp>
- #include <boost/geometry/geometries/box.hpp>
- #include <boost/geometry/geometries/segment.hpp>
- #include <boost/geometry/iterators/ever_circling_iterator.hpp>
- #include <boost/geometry/strategies/intersection_strategies.hpp>
- #include <boost/geometry/strategies/intersection_result.hpp>
- #include <boost/geometry/algorithms/detail/disjoint/box_box.hpp>
- #include <boost/geometry/algorithms/detail/disjoint/point_point.hpp>
- #include <boost/geometry/algorithms/detail/interior_iterator.hpp>
- #include <boost/geometry/algorithms/detail/partition.hpp>
- #include <boost/geometry/algorithms/detail/recalculate.hpp>
- #include <boost/geometry/algorithms/detail/sections/section_box_policies.hpp>
- #include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp>
- #include <boost/geometry/algorithms/detail/overlay/get_turn_info_ll.hpp>
- #include <boost/geometry/algorithms/detail/overlay/get_turn_info_la.hpp>
- #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp>
- #include <boost/geometry/algorithms/detail/sections/range_by_section.hpp>
- #include <boost/geometry/algorithms/detail/sections/sectionalize.hpp>
- #include <boost/geometry/algorithms/detail/sections/section_functions.hpp>
- #ifdef BOOST_GEOMETRY_DEBUG_INTERSECTION
- # include <sstream>
- # include <boost/geometry/io/dsv/write.hpp>
- #endif
- namespace boost { namespace geometry
- {
- // Silence warning C4127: conditional expression is constant
- #if defined(_MSC_VER)
- #pragma warning(push)
- #pragma warning(disable : 4127)
- #endif
- #ifndef DOXYGEN_NO_DETAIL
- namespace detail { namespace get_turns
- {
- struct no_interrupt_policy
- {
- static bool const enabled = false;
- // variable required by self_get_turn_points::get_turns
- static bool const has_intersections = false;
- template <typename Range>
- static inline bool apply(Range const&)
- {
- return false;
- }
- };
- template
- <
- bool IsAreal,
- typename Section,
- typename Point,
- typename CircularIterator,
- typename IntersectionStrategy,
- typename RobustPolicy
- >
- struct unique_sub_range_from_section
- {
- typedef Point point_type;
- unique_sub_range_from_section(Section const& section, signed_size_type index,
- CircularIterator circular_iterator,
- Point const& previous, Point const& current,
- RobustPolicy const& robust_policy)
- : m_section(section)
- , m_index(index)
- , m_previous_point(previous)
- , m_current_point(current)
- , m_circular_iterator(circular_iterator)
- , m_point_retrieved(false)
- , m_robust_policy(robust_policy)
- {
- }
- inline bool is_first_segment() const
- {
- return !IsAreal && m_section.is_non_duplicate_first && m_index == m_section.begin_index;
- }
- inline bool is_last_segment() const
- {
- return size() == 2u;
- }
- inline std::size_t size() const
- {
- return IsAreal ? 3
- : m_section.is_non_duplicate_last && m_index + 1 >= m_section.end_index ? 2 : 3;
- }
- inline Point const& at(std::size_t index) const
- {
- BOOST_GEOMETRY_ASSERT(index < size());
- switch (index)
- {
- case 0 : return m_previous_point;
- case 1 : return m_current_point;
- case 2 : return get_next_point();
- default : return m_previous_point;
- }
- }
- private :
- inline Point const& get_next_point() const
- {
- if (! m_point_retrieved)
- {
- advance_to_non_duplicate_next(m_current_point, m_circular_iterator);
- m_point = *m_circular_iterator;
- m_point_retrieved = true;
- }
- return m_point;
- }
- inline void advance_to_non_duplicate_next(Point const& current, CircularIterator& circular_iterator) const
- {
- typedef typename IntersectionStrategy::point_in_point_strategy_type disjoint_strategy_type;
- typedef typename robust_point_type<Point, RobustPolicy>::type robust_point_type;
- robust_point_type current_robust_point;
- robust_point_type next_robust_point;
- geometry::recalculate(current_robust_point, current, m_robust_policy);
- geometry::recalculate(next_robust_point, *circular_iterator, m_robust_policy);
- // To see where the next segments bend to, in case of touch/intersections
- // on end points, we need (in case of degenerate/duplicate points) an extra
- // iterator which moves to the REAL next point, so non duplicate.
- // This needs an extra comparison (disjoint).
- // (Note that within sections, non duplicate points are already asserted,
- // by the sectionalize process).
- // So advance to the "non duplicate next"
- // (the check is defensive, to avoid endless loops)
- std::size_t check = 0;
- while(! detail::disjoint::disjoint_point_point
- (
- current_robust_point, next_robust_point,
- disjoint_strategy_type()
- )
- && check++ < m_section.range_count)
- {
- circular_iterator++;
- geometry::recalculate(next_robust_point, *circular_iterator, m_robust_policy);
- }
- }
- Section const& m_section;
- signed_size_type m_index;
- Point const& m_previous_point;
- Point const& m_current_point;
- mutable CircularIterator m_circular_iterator;
- mutable Point m_point;
- mutable bool m_point_retrieved;
- RobustPolicy m_robust_policy;
- };
- template
- <
- typename Geometry1, typename Geometry2,
- bool Reverse1, bool Reverse2,
- typename Section1, typename Section2,
- typename TurnPolicy
- >
- class get_turns_in_sections
- {
- typedef typename closeable_view
- <
- typename range_type<Geometry1>::type const,
- closure<Geometry1>::value
- >::type cview_type1;
- typedef typename closeable_view
- <
- typename range_type<Geometry2>::type const,
- closure<Geometry2>::value
- >::type cview_type2;
- typedef typename reversible_view
- <
- cview_type1 const,
- Reverse1 ? iterate_reverse : iterate_forward
- >::type view_type1;
- typedef typename reversible_view
- <
- cview_type2 const,
- Reverse2 ? iterate_reverse : iterate_forward
- >::type view_type2;
- typedef typename boost::range_iterator
- <
- view_type1 const
- >::type range1_iterator;
- typedef typename boost::range_iterator
- <
- view_type2 const
- >::type range2_iterator;
- typedef ever_circling_iterator<range1_iterator> circular1_iterator;
- typedef ever_circling_iterator<range2_iterator> circular2_iterator;
- template <typename Geometry, typename Section>
- static inline bool adjacent(Section const& section,
- signed_size_type index1, signed_size_type index2)
- {
- // About n-2:
- // (square: range_count=5, indices 0,1,2,3
- // -> 0-3 are adjacent, don't check on intersections)
- // Also tested for open polygons, and/or duplicates
- // About first condition: will be optimized by compiler (static)
- // It checks if it is areal (box, ring, (multi)polygon)
- signed_size_type const n = static_cast<signed_size_type>(section.range_count);
- boost::ignore_unused(n, index1, index2);
- return boost::is_same
- <
- typename tag_cast
- <
- typename geometry::tag<Geometry>::type,
- areal_tag
- >::type,
- areal_tag
- >::value
- && index1 == 0
- && index2 >= n - 2
- ;
- }
- public :
- // Returns true if terminated, false if interrupted
- template <typename IntersectionStrategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
- static inline bool apply(
- int source_id1, Geometry1 const& geometry1, Section1 const& sec1,
- int source_id2, Geometry2 const& geometry2, Section2 const& sec2,
- bool skip_larger, bool skip_adjacent,
- IntersectionStrategy const& intersection_strategy,
- RobustPolicy const& robust_policy,
- Turns& turns,
- InterruptPolicy& interrupt_policy)
- {
- boost::ignore_unused(interrupt_policy);
- static bool const areal1 = boost::is_same
- <
- typename tag_cast<typename tag<Geometry1>::type, areal_tag>::type,
- areal_tag
- >::type::value;
- static bool const areal2 = boost::is_same
- <
- typename tag_cast<typename tag<Geometry2>::type, areal_tag>::type,
- areal_tag
- >::type::value;
- if ((sec1.duplicate && (sec1.count + 1) < sec1.range_count)
- || (sec2.duplicate && (sec2.count + 1) < sec2.range_count))
- {
- // Skip sections containig only duplicates.
- // They are still important (can indicate non-disjointness)
- // but they will be found processing adjacent sections.
- // Do NOT skip if they are the ONLY section
- return true;
- }
- cview_type1 cview1(range_by_section(geometry1, sec1));
- cview_type2 cview2(range_by_section(geometry2, sec2));
- view_type1 view1(cview1);
- view_type2 view2(cview2);
- range1_iterator begin_range_1 = boost::begin(view1);
- range1_iterator end_range_1 = boost::end(view1);
- range2_iterator begin_range_2 = boost::begin(view2);
- range2_iterator end_range_2 = boost::end(view2);
- int const dir1 = sec1.directions[0];
- int const dir2 = sec2.directions[0];
- signed_size_type index1 = sec1.begin_index;
- signed_size_type ndi1 = sec1.non_duplicate_index;
- range1_iterator prev1, it1, end1;
- get_start_point_iterator(sec1, view1, prev1, it1, end1,
- index1, ndi1, dir1, sec2.bounding_box, robust_policy);
- // We need a circular iterator because it might run through the closing point.
- // One circle is actually enough but this one is just convenient.
- ever_circling_iterator<range1_iterator> next1(begin_range_1, end_range_1, it1, true);
- next1++;
- // Walk through section and stop if we exceed the other box
- // section 2: [--------------]
- // section 1: |----|---|---|---|---|
- for (prev1 = it1++, next1++;
- it1 != end1 && ! detail::section::exceeding<0>(dir1, *prev1, sec1.bounding_box, sec2.bounding_box, robust_policy);
- ++prev1, ++it1, ++index1, ++next1, ++ndi1)
- {
- unique_sub_range_from_section
- <
- areal1, Section1, point1_type, circular1_iterator,
- IntersectionStrategy, RobustPolicy
- > unique_sub_range1(sec1, index1,
- circular1_iterator(begin_range_1, end_range_1, next1, true),
- *prev1, *it1,
- robust_policy);
- signed_size_type index2 = sec2.begin_index;
- signed_size_type ndi2 = sec2.non_duplicate_index;
- range2_iterator prev2, it2, end2;
- get_start_point_iterator(sec2, view2, prev2, it2, end2,
- index2, ndi2, dir2, sec1.bounding_box, robust_policy);
- ever_circling_iterator<range2_iterator> next2(begin_range_2, end_range_2, it2, true);
- next2++;
- for (prev2 = it2++, next2++;
- it2 != end2 && ! detail::section::exceeding<0>(dir2, *prev2, sec2.bounding_box, sec1.bounding_box, robust_policy);
- ++prev2, ++it2, ++index2, ++next2, ++ndi2)
- {
- bool skip = false;
- if (source_id1 == source_id2
- && sec1.ring_id.multi_index == sec2.ring_id.multi_index
- && sec1.ring_id.ring_index == sec2.ring_id.ring_index)
- {
- // Sources and rings are the same
- if (skip_larger && index1 >= index2)
- {
- // Skip to avoid getting all intersections twice
- skip = true;
- }
- else if (skip_adjacent)
- {
- // In some cases (dissolve, has_self_intersections)
- // neighbouring segments should be checked
- // (for example to detect spikes properly)
- // skip if it is a neighbouring segment.
- // (including, for areas, first-last segment
- // and two segments with one or more degenerate/duplicate
- // (zero-length) segments in between)
- skip = ndi2 == ndi1 + 1
- || adjacent<Geometry1>(sec1, index1, index2);
- }
- }
- if (! skip)
- {
- unique_sub_range_from_section
- <
- areal2, Section2, point2_type, circular2_iterator,
- IntersectionStrategy, RobustPolicy
- > unique_sub_range2(sec2, index2,
- circular2_iterator(begin_range_2, end_range_2, next2),
- *prev2, *it2,
- robust_policy);
- typedef typename boost::range_value<Turns>::type turn_info;
- turn_info ti;
- ti.operations[0].seg_id
- = segment_identifier(source_id1, sec1.ring_id.multi_index,
- sec1.ring_id.ring_index, index1);
- ti.operations[1].seg_id
- = segment_identifier(source_id2, sec2.ring_id.multi_index,
- sec2.ring_id.ring_index, index2);
- std::size_t const size_before = boost::size(turns);
- TurnPolicy::apply(unique_sub_range1, unique_sub_range2,
- ti, intersection_strategy, robust_policy,
- std::back_inserter(turns));
- if (InterruptPolicy::enabled)
- {
- if (interrupt_policy.apply(
- std::make_pair(range::pos(turns, size_before),
- boost::end(turns))))
- {
- return false;
- }
- }
- }
- }
- }
- return true;
- }
- private :
- typedef typename geometry::point_type<Geometry1>::type point1_type;
- typedef typename geometry::point_type<Geometry2>::type point2_type;
- typedef typename model::referring_segment<point1_type const> segment1_type;
- typedef typename model::referring_segment<point2_type const> segment2_type;
- // It is NOT possible to have section-iterators here
- // because of the logistics of "index" (the section-iterator automatically
- // skips to the begin-point, we loose the index or have to recalculate it)
- // So we mimic it here
- template <typename Range, typename Section, typename Box, typename RobustPolicy>
- static inline void get_start_point_iterator(Section const& section,
- Range const& range,
- typename boost::range_iterator<Range const>::type& it,
- typename boost::range_iterator<Range const>::type& prev,
- typename boost::range_iterator<Range const>::type& end,
- signed_size_type& index, signed_size_type& ndi,
- int dir, Box const& other_bounding_box, RobustPolicy const& robust_policy)
- {
- it = boost::begin(range) + section.begin_index;
- end = boost::begin(range) + section.end_index + 1;
- // Mimic section-iterator:
- // Skip to point such that section interects other box
- prev = it++;
- for(; it != end && detail::section::preceding<0>(dir, *it, section.bounding_box, other_bounding_box, robust_policy);
- prev = it++, index++, ndi++)
- {}
- // Go back one step because we want to start completely preceding
- it = prev;
- }
- };
- template
- <
- typename Geometry1, typename Geometry2,
- bool Reverse1, bool Reverse2,
- typename TurnPolicy,
- typename IntersectionStrategy,
- typename RobustPolicy,
- typename Turns,
- typename InterruptPolicy
- >
- struct section_visitor
- {
- int m_source_id1;
- Geometry1 const& m_geometry1;
- int m_source_id2;
- Geometry2 const& m_geometry2;
- IntersectionStrategy const& m_intersection_strategy;
- RobustPolicy const& m_rescale_policy;
- Turns& m_turns;
- InterruptPolicy& m_interrupt_policy;
- section_visitor(int id1, Geometry1 const& g1,
- int id2, Geometry2 const& g2,
- IntersectionStrategy const& intersection_strategy,
- RobustPolicy const& robust_policy,
- Turns& turns,
- InterruptPolicy& ip)
- : m_source_id1(id1), m_geometry1(g1)
- , m_source_id2(id2), m_geometry2(g2)
- , m_intersection_strategy(intersection_strategy)
- , m_rescale_policy(robust_policy)
- , m_turns(turns)
- , m_interrupt_policy(ip)
- {}
- template <typename Section>
- inline bool apply(Section const& sec1, Section const& sec2)
- {
- if (! detail::disjoint::disjoint_box_box(sec1.bounding_box,
- sec2.bounding_box,
- m_intersection_strategy.get_disjoint_box_box_strategy()))
- {
- // false if interrupted
- return get_turns_in_sections
- <
- Geometry1,
- Geometry2,
- Reverse1, Reverse2,
- Section, Section,
- TurnPolicy
- >::apply(m_source_id1, m_geometry1, sec1,
- m_source_id2, m_geometry2, sec2,
- false, false,
- m_intersection_strategy,
- m_rescale_policy,
- m_turns, m_interrupt_policy);
- }
- return true;
- }
- };
- template
- <
- typename Geometry1, typename Geometry2,
- bool Reverse1, bool Reverse2,
- typename TurnPolicy
- >
- class get_turns_generic
- {
- public:
- template <typename IntersectionStrategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
- static inline void apply(
- int source_id1, Geometry1 const& geometry1,
- int source_id2, Geometry2 const& geometry2,
- IntersectionStrategy const& intersection_strategy,
- RobustPolicy const& robust_policy,
- Turns& turns,
- InterruptPolicy& interrupt_policy)
- {
- // First create monotonic sections...
- typedef typename boost::range_value<Turns>::type ip_type;
- typedef typename ip_type::point_type point_type;
- typedef model::box
- <
- typename geometry::robust_point_type
- <
- point_type, RobustPolicy
- >::type
- > box_type;
- typedef geometry::sections<box_type, 2> sections_type;
- sections_type sec1, sec2;
- typedef boost::mpl::vector_c<std::size_t, 0, 1> dimensions;
- typename IntersectionStrategy::envelope_strategy_type const
- envelope_strategy = intersection_strategy.get_envelope_strategy();
- typename IntersectionStrategy::expand_strategy_type const
- expand_strategy = intersection_strategy.get_expand_strategy();
- geometry::sectionalize<Reverse1, dimensions>(geometry1, robust_policy,
- sec1, envelope_strategy, expand_strategy, 0);
- geometry::sectionalize<Reverse2, dimensions>(geometry2, robust_policy,
- sec2, envelope_strategy, expand_strategy, 1);
- // ... and then partition them, intersecting overlapping sections in visitor method
- section_visitor
- <
- Geometry1, Geometry2,
- Reverse1, Reverse2,
- TurnPolicy,
- IntersectionStrategy, RobustPolicy,
- Turns, InterruptPolicy
- > visitor(source_id1, geometry1, source_id2, geometry2,
- intersection_strategy, robust_policy,
- turns, interrupt_policy);
- typedef detail::section::get_section_box
- <
- typename IntersectionStrategy::expand_box_strategy_type
- > get_section_box_type;
- typedef detail::section::overlaps_section_box
- <
- typename IntersectionStrategy::disjoint_box_box_strategy_type
- > overlaps_section_box_type;
- geometry::partition
- <
- box_type
- >::apply(sec1, sec2, visitor,
- get_section_box_type(),
- overlaps_section_box_type());
- }
- };
- // Get turns for a range with a box, following Cohen-Sutherland (cs) approach
- template
- <
- typename Range, typename Box,
- bool ReverseRange, bool ReverseBox,
- typename TurnPolicy
- >
- struct get_turns_cs
- {
- typedef typename geometry::point_type<Range>::type range_point_type;
- typedef typename geometry::point_type<Box>::type box_point_type;
- typedef boost::array<box_point_type, 4> box_array;
- typedef typename closeable_view
- <
- Range const,
- closure<Range>::value
- >::type cview_type;
- typedef typename reversible_view
- <
- cview_type const,
- ReverseRange ? iterate_reverse : iterate_forward
- >::type view_type;
- typedef typename boost::range_iterator
- <
- view_type const
- >::type iterator_type;
- struct unique_sub_range_from_box_policy
- {
- typedef box_point_type point_type;
- unique_sub_range_from_box_policy(box_array const& box)
- : m_box(box)
- , m_index(0)
- {}
- static inline bool is_first_segment() { return false; }
- static inline bool is_last_segment() { return false; }
- static inline std::size_t size() { return 4; }
- inline box_point_type const& at(std::size_t index) const
- {
- BOOST_GEOMETRY_ASSERT(index < size());
- return m_box[(m_index + index) % 4];
- }
- inline void next()
- {
- m_index++;
- }
- private :
- box_array const& m_box;
- std::size_t m_index;
- };
- struct unique_sub_range_from_view_policy
- {
- typedef range_point_type point_type;
- unique_sub_range_from_view_policy(view_type const& view, point_type const& pi, point_type const& pj, iterator_type it)
- : m_view(view)
- , m_pi(pi)
- , m_pj(pj)
- , m_circular_iterator(boost::begin(view), boost::end(view), it, true)
- {
- ++m_circular_iterator;
- }
- static inline bool is_first_segment() { return false; }
- static inline bool is_last_segment() { return false; }
- static inline std::size_t size() { return 3; }
- inline point_type const& at(std::size_t index) const
- {
- BOOST_GEOMETRY_ASSERT(index < size());
- switch (index)
- {
- case 0 : return m_pi;
- case 1 : return m_pj;
- case 2 : return *m_circular_iterator;
- default : return m_pi;
- }
- }
- private :
- view_type const& m_view;
- point_type const& m_pi;
- point_type const& m_pj;
- ever_circling_iterator<iterator_type> m_circular_iterator;
- };
- template <typename IntersectionStrategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
- static inline void apply(
- int source_id1, Range const& range,
- int source_id2, Box const& box,
- IntersectionStrategy const& intersection_strategy,
- RobustPolicy const& robust_policy,
- Turns& turns,
- InterruptPolicy& interrupt_policy,
- signed_size_type multi_index = -1,
- signed_size_type ring_index = -1)
- {
- if ( boost::size(range) <= 1)
- {
- return;
- }
- box_array box_points;
- assign_box_corners_oriented<ReverseBox>(box, box_points);
- cview_type cview(range);
- view_type view(cview);
- // TODO: in this code, possible duplicate points are not yet taken
- // into account (not in the iterator, nor in the retrieve policy)
- iterator_type it = boost::begin(view);
- //bool first = true;
- //char previous_side[2] = {0, 0};
- signed_size_type index = 0;
- for (iterator_type prev = it++;
- it != boost::end(view);
- prev = it++, index++)
- {
- segment_identifier seg_id(source_id1,
- multi_index, ring_index, index);
- unique_sub_range_from_view_policy view_unique_sub_range(view, *prev, *it, it);
- /*if (first)
- {
- previous_side[0] = get_side<0>(box, *prev);
- previous_side[1] = get_side<1>(box, *prev);
- }
- char current_side[2];
- current_side[0] = get_side<0>(box, *it);
- current_side[1] = get_side<1>(box, *it);
- // There can NOT be intersections if
- // 1) EITHER the two points are lying on one side of the box (! 0 && the same)
- // 2) OR same in Y-direction
- // 3) OR all points are inside the box (0)
- if (! (
- (current_side[0] != 0 && current_side[0] == previous_side[0])
- || (current_side[1] != 0 && current_side[1] == previous_side[1])
- || (current_side[0] == 0
- && current_side[1] == 0
- && previous_side[0] == 0
- && previous_side[1] == 0)
- )
- )*/
- if (true)
- {
- get_turns_with_box(seg_id, source_id2,
- view_unique_sub_range,
- box_points,
- intersection_strategy,
- robust_policy,
- turns,
- interrupt_policy);
- // Future performance enhancement:
- // return if told by the interrupt policy
- }
- }
- }
- private:
- template<std::size_t Index, typename Point>
- static inline int get_side(Box const& box, Point const& point)
- {
- // Inside -> 0
- // Outside -> -1 (left/below) or 1 (right/above)
- // On border -> -2 (left/lower) or 2 (right/upper)
- // The only purpose of the value is to not be the same,
- // and to denote if it is inside (0)
- typename coordinate_type<Point>::type const& c = get<Index>(point);
- typename coordinate_type<Box>::type const& left = get<min_corner, Index>(box);
- typename coordinate_type<Box>::type const& right = get<max_corner, Index>(box);
- if (geometry::math::equals(c, left)) return -2;
- else if (geometry::math::equals(c, right)) return 2;
- else if (c < left) return -1;
- else if (c > right) return 1;
- else return 0;
- }
- template
- <
- typename IntersectionStrategy,
- typename Turns,
- typename InterruptPolicy,
- typename RobustPolicy
- >
- static inline void get_turns_with_box(segment_identifier const& seg_id, int source_id2,
- unique_sub_range_from_view_policy const& range_unique_sub_range,
- box_array const& box,
- IntersectionStrategy const& intersection_strategy,
- RobustPolicy const& robust_policy,
- // Output
- Turns& turns,
- InterruptPolicy& interrupt_policy)
- {
- boost::ignore_unused(interrupt_policy);
- // Depending on code some relations can be left out
- typedef typename boost::range_value<Turns>::type turn_info;
- turn_info ti;
- ti.operations[0].seg_id = seg_id;
- unique_sub_range_from_box_policy box_unique_sub_range(box);
- ti.operations[1].seg_id = segment_identifier(source_id2, -1, -1, 0);
- TurnPolicy::apply(range_unique_sub_range, box_unique_sub_range,
- ti, intersection_strategy, robust_policy,
- std::back_inserter(turns));
- ti.operations[1].seg_id = segment_identifier(source_id2, -1, -1, 1);
- box_unique_sub_range.next();
- TurnPolicy::apply(range_unique_sub_range, box_unique_sub_range,
- ti, intersection_strategy, robust_policy,
- std::back_inserter(turns));
- ti.operations[1].seg_id = segment_identifier(source_id2, -1, -1, 2);
- box_unique_sub_range.next();
- TurnPolicy::apply(range_unique_sub_range, box_unique_sub_range,
- ti, intersection_strategy, robust_policy,
- std::back_inserter(turns));
- ti.operations[1].seg_id = segment_identifier(source_id2, -1, -1, 3);
- box_unique_sub_range.next();
- TurnPolicy::apply(range_unique_sub_range, box_unique_sub_range,
- ti, intersection_strategy, robust_policy,
- std::back_inserter(turns));
- if (InterruptPolicy::enabled)
- {
- interrupt_policy.apply(turns);
- }
- }
- };
- template
- <
- typename Polygon, typename Box,
- bool Reverse, bool ReverseBox,
- typename TurnPolicy
- >
- struct get_turns_polygon_cs
- {
- template <typename IntersectionStrategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
- static inline void apply(
- int source_id1, Polygon const& polygon,
- int source_id2, Box const& box,
- IntersectionStrategy const& intersection_strategy,
- RobustPolicy const& robust_policy,
- Turns& turns,
- InterruptPolicy& interrupt_policy,
- signed_size_type multi_index = -1)
- {
- typedef typename geometry::ring_type<Polygon>::type ring_type;
- typedef detail::get_turns::get_turns_cs
- <
- ring_type, Box,
- Reverse, ReverseBox,
- TurnPolicy
- > intersector_type;
- intersector_type::apply(
- source_id1, geometry::exterior_ring(polygon),
- source_id2, box,
- intersection_strategy,
- robust_policy,
- turns,
- interrupt_policy,
- multi_index, -1);
- signed_size_type i = 0;
- typename interior_return_type<Polygon const>::type
- rings = interior_rings(polygon);
- for (typename detail::interior_iterator<Polygon const>::type
- it = boost::begin(rings); it != boost::end(rings); ++it, ++i)
- {
- intersector_type::apply(
- source_id1, *it,
- source_id2, box,
- intersection_strategy,
- robust_policy,
- turns, interrupt_policy,
- multi_index, i);
- }
- }
- };
- template
- <
- typename Multi, typename Box,
- bool Reverse, bool ReverseBox,
- typename TurnPolicy
- >
- struct get_turns_multi_polygon_cs
- {
- template <typename IntersectionStrategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
- static inline void apply(
- int source_id1, Multi const& multi,
- int source_id2, Box const& box,
- IntersectionStrategy const& intersection_strategy,
- RobustPolicy const& robust_policy,
- Turns& turns,
- InterruptPolicy& interrupt_policy)
- {
- typedef typename boost::range_iterator
- <
- Multi const
- >::type iterator_type;
- signed_size_type i = 0;
- for (iterator_type it = boost::begin(multi);
- it != boost::end(multi);
- ++it, ++i)
- {
- // Call its single version
- get_turns_polygon_cs
- <
- typename boost::range_value<Multi>::type, Box,
- Reverse, ReverseBox,
- TurnPolicy
- >::apply(source_id1, *it, source_id2, box,
- intersection_strategy, robust_policy,
- turns, interrupt_policy, i);
- }
- }
- };
- // GET_TURN_INFO_TYPE
- template <typename Geometry>
- struct topological_tag_base
- {
- typedef typename tag_cast<typename tag<Geometry>::type, pointlike_tag, linear_tag, areal_tag>::type type;
- };
- template <typename Geometry1, typename Geometry2, typename AssignPolicy,
- typename Tag1 = typename tag<Geometry1>::type, typename Tag2 = typename tag<Geometry2>::type,
- typename TagBase1 = typename topological_tag_base<Geometry1>::type, typename TagBase2 = typename topological_tag_base<Geometry2>::type>
- struct get_turn_info_type
- : overlay::get_turn_info<AssignPolicy>
- {};
- template <typename Geometry1, typename Geometry2, typename AssignPolicy, typename Tag1, typename Tag2>
- struct get_turn_info_type<Geometry1, Geometry2, AssignPolicy, Tag1, Tag2, linear_tag, linear_tag>
- : overlay::get_turn_info_linear_linear<AssignPolicy>
- {};
- template <typename Geometry1, typename Geometry2, typename AssignPolicy, typename Tag1, typename Tag2>
- struct get_turn_info_type<Geometry1, Geometry2, AssignPolicy, Tag1, Tag2, linear_tag, areal_tag>
- : overlay::get_turn_info_linear_areal<AssignPolicy>
- {};
- template <typename Geometry1, typename Geometry2, typename SegmentRatio,
- typename Tag1 = typename tag<Geometry1>::type, typename Tag2 = typename tag<Geometry2>::type,
- typename TagBase1 = typename topological_tag_base<Geometry1>::type, typename TagBase2 = typename topological_tag_base<Geometry2>::type>
- struct turn_operation_type
- {
- typedef overlay::turn_operation<typename point_type<Geometry1>::type, SegmentRatio> type;
- };
- template <typename Geometry1, typename Geometry2, typename SegmentRatio, typename Tag1, typename Tag2>
- struct turn_operation_type<Geometry1, Geometry2, SegmentRatio, Tag1, Tag2, linear_tag, linear_tag>
- {
- typedef overlay::turn_operation_linear<typename point_type<Geometry1>::type, SegmentRatio> type;
- };
- template <typename Geometry1, typename Geometry2, typename SegmentRatio, typename Tag1, typename Tag2>
- struct turn_operation_type<Geometry1, Geometry2, SegmentRatio, Tag1, Tag2, linear_tag, areal_tag>
- {
- typedef overlay::turn_operation_linear<typename point_type<Geometry1>::type, SegmentRatio> type;
- };
- }} // namespace detail::get_turns
- #endif // DOXYGEN_NO_DETAIL
- #ifndef DOXYGEN_NO_DISPATCH
- namespace dispatch
- {
- // Because this is "detail" method, and most implementations will use "generic",
- // we take the freedom to derive it from "generic".
- template
- <
- typename GeometryTag1, typename GeometryTag2,
- typename Geometry1, typename Geometry2,
- bool Reverse1, bool Reverse2,
- typename TurnPolicy
- >
- struct get_turns
- : detail::get_turns::get_turns_generic
- <
- Geometry1, Geometry2,
- Reverse1, Reverse2,
- TurnPolicy
- >
- {};
- template
- <
- typename Polygon, typename Box,
- bool ReversePolygon, bool ReverseBox,
- typename TurnPolicy
- >
- struct get_turns
- <
- polygon_tag, box_tag,
- Polygon, Box,
- ReversePolygon, ReverseBox,
- TurnPolicy
- > : detail::get_turns::get_turns_polygon_cs
- <
- Polygon, Box,
- ReversePolygon, ReverseBox,
- TurnPolicy
- >
- {};
- template
- <
- typename Ring, typename Box,
- bool ReverseRing, bool ReverseBox,
- typename TurnPolicy
- >
- struct get_turns
- <
- ring_tag, box_tag,
- Ring, Box,
- ReverseRing, ReverseBox,
- TurnPolicy
- > : detail::get_turns::get_turns_cs
- <
- Ring, Box, ReverseRing, ReverseBox,
- TurnPolicy
- >
- {};
- template
- <
- typename MultiPolygon,
- typename Box,
- bool ReverseMultiPolygon, bool ReverseBox,
- typename TurnPolicy
- >
- struct get_turns
- <
- multi_polygon_tag, box_tag,
- MultiPolygon, Box,
- ReverseMultiPolygon, ReverseBox,
- TurnPolicy
- >
- : detail::get_turns::get_turns_multi_polygon_cs
- <
- MultiPolygon, Box,
- ReverseMultiPolygon, ReverseBox,
- TurnPolicy
- >
- {};
- template
- <
- typename GeometryTag1, typename GeometryTag2,
- typename Geometry1, typename Geometry2,
- bool Reverse1, bool Reverse2,
- typename TurnPolicy
- >
- struct get_turns_reversed
- {
- template <typename IntersectionStrategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
- static inline void apply(int source_id1, Geometry1 const& g1,
- int source_id2, Geometry2 const& g2,
- IntersectionStrategy const& intersection_strategy,
- RobustPolicy const& robust_policy,
- Turns& turns,
- InterruptPolicy& interrupt_policy)
- {
- get_turns
- <
- GeometryTag2, GeometryTag1,
- Geometry2, Geometry1,
- Reverse2, Reverse1,
- TurnPolicy
- >::apply(source_id2, g2, source_id1, g1,
- intersection_strategy, robust_policy,
- turns, interrupt_policy);
- }
- };
- } // namespace dispatch
- #endif // DOXYGEN_NO_DISPATCH
- /*!
- \brief \brief_calc2{turn points}
- \ingroup overlay
- \tparam Geometry1 \tparam_geometry
- \tparam Geometry2 \tparam_geometry
- \tparam Turns type of turn-container (e.g. vector of "intersection/turn point"'s)
- \param geometry1 \param_geometry
- \param geometry2 \param_geometry
- \param intersection_strategy segments intersection strategy
- \param robust_policy policy to handle robustness issues
- \param turns container which will contain turn points
- \param interrupt_policy policy determining if process is stopped
- when intersection is found
- */
- template
- <
- bool Reverse1, bool Reverse2,
- typename AssignPolicy,
- typename Geometry1,
- typename Geometry2,
- typename IntersectionStrategy,
- typename RobustPolicy,
- typename Turns,
- typename InterruptPolicy
- >
- inline void get_turns(Geometry1 const& geometry1,
- Geometry2 const& geometry2,
- IntersectionStrategy const& intersection_strategy,
- RobustPolicy const& robust_policy,
- Turns& turns,
- InterruptPolicy& interrupt_policy)
- {
- concepts::check_concepts_and_equal_dimensions<Geometry1 const, Geometry2 const>();
- typedef detail::overlay::get_turn_info<AssignPolicy> TurnPolicy;
- //typedef detail::get_turns::get_turn_info_type<Geometry1, Geometry2, AssignPolicy> TurnPolicy;
- boost::mpl::if_c
- <
- reverse_dispatch<Geometry1, Geometry2>::type::value,
- dispatch::get_turns_reversed
- <
- typename tag<Geometry1>::type,
- typename tag<Geometry2>::type,
- Geometry1, Geometry2,
- Reverse1, Reverse2,
- TurnPolicy
- >,
- dispatch::get_turns
- <
- typename tag<Geometry1>::type,
- typename tag<Geometry2>::type,
- Geometry1, Geometry2,
- Reverse1, Reverse2,
- TurnPolicy
- >
- >::type::apply(0, geometry1,
- 1, geometry2,
- intersection_strategy,
- robust_policy,
- turns, interrupt_policy);
- }
- #if defined(_MSC_VER)
- #pragma warning(pop)
- #endif
- }} // namespace boost::geometry
- #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURNS_HPP
|