12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661 |
- // Boost.Geometry (aka GGL, Generic Geometry Library)
- // Copyright (c) 2012-2014 Barend Gehrels, Amsterdam, the Netherlands.
- // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
- // This file was modified by Oracle on 2016-2019.
- // Modifications copyright (c) 2016-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_BUFFER_BUFFERED_PIECE_COLLECTION_HPP
- #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_BUFFERED_PIECE_COLLECTION_HPP
- #include <algorithm>
- #include <cstddef>
- #include <set>
- #include <boost/core/ignore_unused.hpp>
- #include <boost/range.hpp>
- #include <boost/geometry/core/assert.hpp>
- #include <boost/geometry/core/coordinate_type.hpp>
- #include <boost/geometry/core/point_type.hpp>
- #include <boost/geometry/algorithms/comparable_distance.hpp>
- #include <boost/geometry/algorithms/covered_by.hpp>
- #include <boost/geometry/algorithms/envelope.hpp>
- #include <boost/geometry/algorithms/is_convex.hpp>
- #include <boost/geometry/strategies/buffer.hpp>
- #include <boost/geometry/geometries/ring.hpp>
- #include <boost/geometry/algorithms/detail/buffer/buffered_ring.hpp>
- #include <boost/geometry/algorithms/detail/buffer/buffer_policies.hpp>
- #include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp>
- #include <boost/geometry/algorithms/detail/buffer/get_piece_turns.hpp>
- #include <boost/geometry/algorithms/detail/buffer/turn_in_piece_visitor.hpp>
- #include <boost/geometry/algorithms/detail/buffer/turn_in_original_visitor.hpp>
- #include <boost/geometry/algorithms/detail/disjoint/point_box.hpp>
- #include <boost/geometry/algorithms/detail/overlay/add_rings.hpp>
- #include <boost/geometry/algorithms/detail/overlay/assign_parents.hpp>
- #include <boost/geometry/algorithms/detail/overlay/enrichment_info.hpp>
- #include <boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp>
- #include <boost/geometry/algorithms/detail/overlay/ring_properties.hpp>
- #include <boost/geometry/algorithms/detail/overlay/select_rings.hpp>
- #include <boost/geometry/algorithms/detail/overlay/traversal_info.hpp>
- #include <boost/geometry/algorithms/detail/overlay/traverse.hpp>
- #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
- #include <boost/geometry/algorithms/detail/occupation_info.hpp>
- #include <boost/geometry/algorithms/detail/partition.hpp>
- #include <boost/geometry/algorithms/detail/sections/sectionalize.hpp>
- #include <boost/geometry/algorithms/detail/sections/section_box_policies.hpp>
- #include <boost/geometry/util/range.hpp>
- namespace boost { namespace geometry
- {
- #ifndef DOXYGEN_NO_DETAIL
- namespace detail { namespace buffer
- {
- enum segment_relation_code
- {
- segment_relation_on_left,
- segment_relation_on_right,
- segment_relation_within,
- segment_relation_disjoint
- };
- /*
- * Terminology
- *
- * Suppose we make a buffer (using blocked corners) of this rectangle:
- *
- * +-------+
- * | |
- * | rect |
- * | |
- * +-------+
- *
- * For the sides we get these four buffered side-pieces (marked with s)
- * and four buffered corner pieces (marked with c)
- *
- * c---+---s---+---c
- * | | piece | | <- see below for details of the middle top-side-piece
- * +---+-------+---+
- * | | | |
- * s | rect | s <- two side pieces left/right of rect
- * | | | |
- * +---+-------+---+
- * | | piece | | <- one side-piece below, and two corner pieces
- * c---+---s---+---c
- *
- * The outer part of the picture above, using all pieces,
- * form together the offsetted ring (marked with o below)
- * The 8 pieces are part of the piece collection and use for inside-checks
- * The inner parts form (using 1 or 2 points per piece, often co-located)
- * form together the robust_polygons (marked with r below)
- * The remaining piece-segments are helper-segments (marked with h)
- *
- * ooooooooooooooooo
- * o h h o
- * ohhhrrrrrrrrrhhho
- * o r r o
- * o r r o
- * o r r o
- * ohhhrrrrrrrrrhhho
- * o h h o
- * ooooooooooooooooo
- *
- */
- template <typename Ring, typename IntersectionStrategy, typename RobustPolicy>
- struct buffered_piece_collection
- {
- typedef buffered_piece_collection
- <
- Ring, IntersectionStrategy, RobustPolicy
- > this_type;
- typedef typename geometry::point_type<Ring>::type point_type;
- typedef typename geometry::coordinate_type<Ring>::type coordinate_type;
- typedef typename geometry::robust_point_type
- <
- point_type,
- RobustPolicy
- >::type robust_point_type;
- // Robust ring/polygon type, always clockwise
- typedef geometry::model::ring<robust_point_type> robust_ring_type;
- typedef geometry::model::box<robust_point_type> robust_box_type;
- typedef typename default_comparable_distance_result
- <
- robust_point_type
- >::type robust_comparable_radius_type;
- typedef typename IntersectionStrategy::side_strategy_type side_strategy_type;
- typedef typename IntersectionStrategy::envelope_strategy_type envelope_strategy_type;
- typedef typename IntersectionStrategy::expand_strategy_type expand_strategy_type;
- typedef typename IntersectionStrategy::template area_strategy
- <
- point_type
- >::type area_strategy_type;
- typedef typename IntersectionStrategy::template area_strategy
- <
- robust_point_type
- >::type robust_area_strategy_type;
- typedef typename area_strategy_type::template result_type
- <
- point_type
- >::type area_result_type;
- typedef typename robust_area_strategy_type::template result_type
- <
- robust_point_type
- >::type robust_area_result_type;
- typedef typename IntersectionStrategy::template point_in_geometry_strategy
- <
- robust_point_type,
- robust_ring_type
- >::type point_in_geometry_strategy_type;
- typedef typename geometry::rescale_policy_type
- <
- typename geometry::point_type<Ring>::type,
- typename IntersectionStrategy::cs_tag
- >::type rescale_policy_type;
- typedef geometry::segment_ratio
- <
- typename geometry::coordinate_type<robust_point_type>::type
- > ratio_type;
- typedef buffer_turn_info
- <
- point_type,
- robust_point_type,
- ratio_type
- > buffer_turn_info_type;
- typedef buffer_turn_operation
- <
- point_type,
- ratio_type
- > buffer_turn_operation_type;
- typedef std::vector<buffer_turn_info_type> turn_vector_type;
- struct robust_turn
- {
- std::size_t turn_index;
- int operation_index;
- robust_point_type point;
- segment_identifier seg_id;
- ratio_type fraction;
- };
- struct piece
- {
- typedef robust_ring_type piece_robust_ring_type;
- typedef geometry::section<robust_box_type, 1> section_type;
- strategy::buffer::piece_type type;
- signed_size_type index;
- signed_size_type left_index; // points to previous piece of same ring
- signed_size_type right_index; // points to next piece of same ring
- // The next two members (1, 2) form together a complete clockwise ring
- // for each piece (with one dupped point)
- // The complete clockwise ring is also included as a robust ring (3)
- // 1: half, part of offsetted_rings
- segment_identifier first_seg_id;
- signed_size_type last_segment_index; // no segment-identifier - it is the same as first_seg_id
- signed_size_type offsetted_count; // part in robust_ring which is part of offsetted ring
- #if defined(BOOST_GEOMETRY_BUFFER_USE_HELPER_POINTS)
- // 2: half, not part of offsetted rings - part of robust ring
- std::vector<point_type> helper_points; // 4 points for side, 3 points for join - 0 points for flat-end
- #endif
- bool is_flat_start;
- bool is_flat_end;
- bool is_deflated;
- bool is_convex;
- bool is_monotonic_increasing[2]; // 0=x, 1=y
- bool is_monotonic_decreasing[2]; // 0=x, 1=y
- // Monotonic sections of pieces around points
- std::vector<section_type> sections;
- // Robust representations
- // 3: complete ring
- robust_ring_type robust_ring;
- robust_box_type robust_envelope;
- robust_box_type robust_offsetted_envelope;
- std::vector<robust_turn> robust_turns; // Used only in insert_rescaled_piece_turns - we might use a map instead
- robust_point_type robust_center;
- robust_comparable_radius_type robust_min_comparable_radius;
- robust_comparable_radius_type robust_max_comparable_radius;
- piece()
- : type(strategy::buffer::piece_type_unknown)
- , index(-1)
- , left_index(-1)
- , right_index(-1)
- , last_segment_index(-1)
- , offsetted_count(-1)
- , is_flat_start(false)
- , is_flat_end(false)
- , is_deflated(false)
- , is_convex(false)
- , robust_min_comparable_radius(0)
- , robust_max_comparable_radius(0)
- {
- is_monotonic_increasing[0] = false;
- is_monotonic_increasing[1] = false;
- is_monotonic_decreasing[0] = false;
- is_monotonic_decreasing[1] = false;
- }
- };
- struct robust_original
- {
- typedef robust_ring_type original_robust_ring_type;
- typedef geometry::sections<robust_box_type, 1> sections_type;
- inline robust_original()
- : m_is_interior(false)
- , m_has_interiors(true)
- {}
- inline robust_original(robust_ring_type const& ring,
- bool is_interior, bool has_interiors,
- envelope_strategy_type const& envelope_strategy,
- expand_strategy_type const& expand_strategy)
- : m_ring(ring)
- , m_is_interior(is_interior)
- , m_has_interiors(has_interiors)
- {
- geometry::envelope(m_ring, m_box, envelope_strategy);
- // create monotonic sections in x-dimension
- // The dimension is critical because the direction is later used
- // in the optimization for within checks using winding strategy
- // and this strategy is scanning in x direction.
- typedef boost::mpl::vector_c<std::size_t, 0> dimensions;
- geometry::sectionalize<false, dimensions>(m_ring,
- detail::no_rescale_policy(), m_sections,
- envelope_strategy, expand_strategy);
- }
- robust_ring_type m_ring;
- robust_box_type m_box;
- sections_type m_sections;
- bool m_is_interior;
- bool m_has_interiors;
- };
- typedef std::vector<piece> piece_vector_type;
- piece_vector_type m_pieces;
- turn_vector_type m_turns;
- signed_size_type m_first_piece_index;
- bool m_deflate;
- bool m_has_deflated;
- buffered_ring_collection<buffered_ring<Ring> > offsetted_rings; // indexed by multi_index
- std::vector<robust_original> robust_originals; // robust representation of the original(s)
- robust_ring_type current_robust_ring;
- buffered_ring_collection<Ring> traversed_rings;
- segment_identifier current_segment_id;
- // Specificly for offsetted rings around points
- // but also for large joins with many points
- typedef geometry::sections<robust_box_type, 2> sections_type;
- sections_type monotonic_sections;
- // Define the clusters, mapping cluster_id -> turns
- typedef std::map
- <
- signed_size_type,
- detail::overlay::cluster_info
- > cluster_type;
- cluster_type m_clusters;
- IntersectionStrategy m_intersection_strategy;
- side_strategy_type m_side_strategy;
- area_strategy_type m_area_strategy;
- envelope_strategy_type m_envelope_strategy;
- expand_strategy_type m_expand_strategy;
- point_in_geometry_strategy_type m_point_in_geometry_strategy;
- robust_area_strategy_type m_robust_area_strategy;
- RobustPolicy const& m_robust_policy;
- struct redundant_turn
- {
- inline bool operator()(buffer_turn_info_type const& turn) const
- {
- return turn.remove_on_multi;
- }
- };
- buffered_piece_collection(IntersectionStrategy const& intersection_strategy,
- RobustPolicy const& robust_policy)
- : m_first_piece_index(-1)
- , m_deflate(false)
- , m_has_deflated(false)
- , m_intersection_strategy(intersection_strategy)
- , m_side_strategy(intersection_strategy.get_side_strategy())
- , m_area_strategy(intersection_strategy
- .template get_area_strategy<point_type>())
- , m_envelope_strategy(intersection_strategy.get_envelope_strategy())
- , m_expand_strategy(intersection_strategy.get_expand_strategy())
- , m_point_in_geometry_strategy(intersection_strategy
- .template get_point_in_geometry_strategy<robust_point_type,
- robust_ring_type>())
- , m_robust_area_strategy(intersection_strategy
- .template get_area_strategy<robust_point_type>())
- , m_robust_policy(robust_policy)
- {}
- #if defined(BOOST_GEOMETRY_BUFFER_ENLARGED_CLUSTERS)
- // Will (most probably) be removed later
- template <typename OccupationMap>
- inline void adapt_mapped_robust_point(OccupationMap const& map,
- buffer_turn_info_type& turn, int distance) const
- {
- for (int x = -distance; x <= distance; x++)
- {
- for (int y = -distance; y <= distance; y++)
- {
- robust_point_type rp = turn.robust_point;
- geometry::set<0>(rp, geometry::get<0>(rp) + x);
- geometry::set<1>(rp, geometry::get<1>(rp) + y);
- if (map.find(rp) != map.end())
- {
- turn.mapped_robust_point = rp;
- return;
- }
- }
- }
- }
- #endif
- inline void get_occupation(
- #if defined(BOOST_GEOMETRY_BUFFER_ENLARGED_CLUSTERS)
- int distance = 0
- #endif
- )
- {
- typedef occupation_info<angle_info<robust_point_type, coordinate_type> >
- buffer_occupation_info;
- typedef std::map
- <
- robust_point_type,
- buffer_occupation_info,
- geometry::less<robust_point_type>
- > occupation_map_type;
- occupation_map_type occupation_map;
- // 1: Add all intersection points to occupation map
- typedef typename boost::range_iterator<turn_vector_type>::type
- iterator_type;
- for (iterator_type it = boost::begin(m_turns);
- it != boost::end(m_turns);
- ++it)
- {
- if (it->location == location_ok)
- {
- #if defined(BOOST_GEOMETRY_BUFFER_ENLARGED_CLUSTERS)
- if (distance > 0 && ! occupation_map.empty())
- {
- adapt_mapped_robust_point(occupation_map, *it, distance);
- }
- #endif
- occupation_map[it->get_robust_point()].count++;
- }
- }
- // Remove all points with one or more u/u points from the map
- // (Alternatively, we could NOT do this here and change all u/u
- // behaviour in overlay. Currently nothing is done: each polygon is
- // just followed there. We could also always switch polygons there. For
- // buffer behaviour, where 3 pieces might meet of which 2 (or more) form
- // a u/u turn, this last option would have been better, probably).
- for (iterator_type it = boost::begin(m_turns);
- it != boost::end(m_turns);
- ++it)
- {
- if (it->both(detail::overlay::operation_union))
- {
- typename occupation_map_type::iterator mit =
- occupation_map.find(it->get_robust_point());
- if (mit != occupation_map.end())
- {
- occupation_map.erase(mit);
- }
- }
- }
- // 2: Remove all points from map which has only one
- typename occupation_map_type::iterator it = occupation_map.begin();
- while (it != occupation_map.end())
- {
- if (it->second.count <= 1)
- {
- typename occupation_map_type::iterator to_erase = it;
- ++it;
- occupation_map.erase(to_erase);
- }
- else
- {
- ++it;
- }
- }
- if (occupation_map.empty())
- {
- return;
- }
- // 3: Add vectors (incoming->intersection-point,
- // intersection-point -> outgoing)
- // for all (co-located) points still present in the map
- for (iterator_type tit = boost::begin(m_turns);
- tit != boost::end(m_turns);
- ++tit)
- {
- typename occupation_map_type::iterator mit =
- occupation_map.find(tit->get_robust_point());
- if (mit != occupation_map.end())
- {
- buffer_occupation_info& info = mit->second;
- for (int i = 0; i < 2; i++)
- {
- add_incoming_and_outgoing_angles(tit->get_robust_point(), *tit,
- m_pieces,
- i, tit->operations[i].seg_id,
- info);
- }
- tit->count_on_multi++;
- }
- }
- #if defined(BOOST_GEOMETRY_BUFFER_ENLARGED_CLUSTERS)
- // X: Check rounding issues
- if (distance == 0)
- {
- for (typename occupation_map_type::const_iterator it = occupation_map.begin();
- it != occupation_map.end(); ++it)
- {
- if (it->second.has_rounding_issues(it->first))
- {
- if(distance == 0)
- {
- get_occupation(distance + 1);
- return;
- }
- }
- }
- }
- #endif
- // Get left turns from all clusters
- for (typename occupation_map_type::iterator mit = occupation_map.begin();
- mit != occupation_map.end(); ++mit)
- {
- mit->second.get_left_turns(mit->first, m_turns, m_side_strategy);
- }
- }
- inline void classify_turns()
- {
- for (typename boost::range_iterator<turn_vector_type>::type it =
- boost::begin(m_turns); it != boost::end(m_turns); ++it)
- {
- if (it->count_within > 0)
- {
- it->location = inside_buffer;
- }
- if (it->count_within_near_offsetted > 0)
- {
- // Within can have in rare cases a rounding issue. We don't discard this
- // point, so it can be used to continue started rings in traversal. But
- // will never start a new ring from this type of points.
- it->operations[0].enriched.startable = false;
- it->operations[1].enriched.startable = false;
- }
- }
- }
- struct deflate_properties
- {
- bool has_inflated;
- std::size_t count;
- inline deflate_properties()
- : has_inflated(false)
- , count(0u)
- {}
- };
- inline void discard_turns_for_deflate()
- {
- // Deflate cases should have at least 3 points PER deflated original
- // to form a correct triangle
- // But if there are intersections between a deflated ring and another
- // ring, it is all accepted
- // In deflate most turns are i/u by nature, but u/u is also possible
- std::map<signed_size_type, deflate_properties> properties;
- for (typename boost::range_iterator<turn_vector_type const>::type it =
- boost::begin(m_turns); it != boost::end(m_turns); ++it)
- {
- const buffer_turn_info_type& turn = *it;
- if (turn.location == location_ok)
- {
- const buffer_turn_operation_type& op0 = turn.operations[0];
- const buffer_turn_operation_type& op1 = turn.operations[1];
- if (! m_pieces[op0.seg_id.piece_index].is_deflated
- || ! m_pieces[op1.seg_id.piece_index].is_deflated)
- {
- properties[op0.seg_id.multi_index].has_inflated = true;
- properties[op1.seg_id.multi_index].has_inflated = true;
- continue;
- }
- // It is deflated, update counts
- for (int i = 0; i < 2; i++)
- {
- const buffer_turn_operation_type& op = turn.operations[i];
- if (op.operation == detail::overlay::operation_union
- || op.operation == detail::overlay::operation_continue)
- {
- properties[op.seg_id.multi_index].count++;
- }
- }
- }
- }
- for (typename boost::range_iterator<turn_vector_type>::type it =
- boost::begin(m_turns); it != boost::end(m_turns); ++it)
- {
- buffer_turn_info_type& turn = *it;
- if (turn.location == location_ok)
- {
- const buffer_turn_operation_type& op0 = turn.operations[0];
- const buffer_turn_operation_type& op1 = turn.operations[1];
- signed_size_type const multi0 = op0.seg_id.multi_index;
- signed_size_type const multi1 = op1.seg_id.multi_index;
- if (multi0 == multi1)
- {
- const deflate_properties& prop = properties[multi0];
- // NOTE: Keep brackets around prop.count
- // avoid gcc-bug "parse error in template argument list"
- // GCC versions 5.4 and 5.5 (and probably more)
- if (! prop.has_inflated && (prop.count) < 3)
- {
- // Property is not inflated
- // Not enough points, this might be caused by <float> where
- // detection turn-in-original failed because of numeric errors
- turn.location = location_discard;
- }
- }
- else
- {
- // Two different (possibly deflated) rings
- }
- }
- }
- }
- template <typename DistanceStrategy>
- inline void check_remaining_points(DistanceStrategy const& distance_strategy)
- {
- // Check if a turn is inside any of the originals
- typedef turn_in_original_ovelaps_box
- <
- typename IntersectionStrategy::disjoint_point_box_strategy_type
- > turn_in_original_ovelaps_box_type;
- typedef original_ovelaps_box
- <
- typename IntersectionStrategy::disjoint_box_box_strategy_type
- > original_ovelaps_box_type;
- turn_in_original_visitor
- <
- turn_vector_type,
- point_in_geometry_strategy_type
- > visitor(m_turns, m_point_in_geometry_strategy);
- geometry::partition
- <
- robust_box_type,
- include_turn_policy,
- detail::partition::include_all_policy
- >::apply(m_turns, robust_originals, visitor,
- turn_get_box(), turn_in_original_ovelaps_box_type(),
- original_get_box(), original_ovelaps_box_type());
- bool const deflate = distance_strategy.negative();
- for (typename boost::range_iterator<turn_vector_type>::type it =
- boost::begin(m_turns); it != boost::end(m_turns); ++it)
- {
- buffer_turn_info_type& turn = *it;
- if (turn.location == location_ok)
- {
- if (deflate && turn.count_in_original <= 0)
- {
- // For deflate/negative buffers: it is not in original, discard
- turn.location = location_discard;
- }
- else if (! deflate && turn.count_in_original > 0)
- {
- // For inflate: it is in original, discard
- turn.location = location_discard;
- }
- }
- }
- if (m_has_deflated)
- {
- // Either strategy was negative, or there were interior rings
- discard_turns_for_deflate();
- }
- }
- inline bool assert_indices_in_robust_rings() const
- {
- geometry::equal_to<robust_point_type> comparator;
- for (typename boost::range_iterator<turn_vector_type const>::type it =
- boost::begin(m_turns); it != boost::end(m_turns); ++it)
- {
- for (int i = 0; i < 2; i++)
- {
- robust_point_type const &p1
- = m_pieces[it->operations[i].piece_index].robust_ring
- [it->operations[i].index_in_robust_ring];
- robust_point_type const &p2 = it->robust_point;
- if (! comparator(p1, p2))
- {
- return false;
- }
- }
- }
- return true;
- }
- inline void insert_rescaled_piece_turns()
- {
- // Add rescaled turn points to corresponding pieces
- // (after this, each turn occurs twice)
- std::size_t index = 0;
- for (typename boost::range_iterator<turn_vector_type>::type it =
- boost::begin(m_turns); it != boost::end(m_turns); ++it, ++index)
- {
- geometry::recalculate(it->robust_point, it->point, m_robust_policy);
- #if defined(BOOST_GEOMETRY_BUFFER_ENLARGED_CLUSTERS)
- it->mapped_robust_point = it->robust_point;
- #endif
- robust_turn turn;
- it->turn_index = index;
- turn.turn_index = index;
- turn.point = it->robust_point;
- for (int i = 0; i < 2; i++)
- {
- turn.operation_index = i;
- turn.seg_id = it->operations[i].seg_id;
- turn.fraction = it->operations[i].fraction;
- piece& pc = m_pieces[it->operations[i].piece_index];
- pc.robust_turns.push_back(turn);
- // Take into account for the box (intersection points should fall inside,
- // but in theory they can be one off because of rounding
- geometry::expand(pc.robust_envelope, it->robust_point);
- geometry::expand(pc.robust_offsetted_envelope, it->robust_point);
- }
- }
- if (! use_side_of_intersection<typename geometry::cs_tag<point_type>::type>::value)
- {
- // Insert all rescaled turn-points into these rings, to form a
- // reliable integer-based ring. All turns can be compared (inside) to this
- // rings to see if they are inside.
- for (typename boost::range_iterator<piece_vector_type>::type
- it = boost::begin(m_pieces); it != boost::end(m_pieces); ++it)
- {
- piece& pc = *it;
- signed_size_type piece_segment_index = pc.first_seg_id.segment_index;
- if (! pc.robust_turns.empty())
- {
- if (pc.robust_turns.size() > 1u)
- {
- std::sort(pc.robust_turns.begin(), pc.robust_turns.end(), buffer_operation_less());
- }
- // Walk through them, in reverse to insert at right index
- signed_size_type index_offset = static_cast<signed_size_type>(pc.robust_turns.size()) - 1;
- for (typename boost::range_reverse_iterator<const std::vector<robust_turn> >::type
- rit = boost::const_rbegin(pc.robust_turns);
- rit != boost::const_rend(pc.robust_turns);
- ++rit, --index_offset)
- {
- signed_size_type const index_in_vector = 1 + rit->seg_id.segment_index - piece_segment_index;
- BOOST_GEOMETRY_ASSERT
- (
- index_in_vector > 0
- && index_in_vector < pc.offsetted_count
- );
- pc.robust_ring.insert(boost::begin(pc.robust_ring) + index_in_vector, rit->point);
- pc.offsetted_count++;
- m_turns[rit->turn_index].operations[rit->operation_index].index_in_robust_ring = index_in_vector + index_offset;
- }
- }
- }
- BOOST_GEOMETRY_ASSERT(assert_indices_in_robust_rings());
- }
- }
- template <std::size_t Dimension>
- static inline void determine_monotonicity(piece& pc,
- robust_point_type const& current,
- robust_point_type const& next)
- {
- if (geometry::get<Dimension>(current) >= geometry::get<Dimension>(next))
- {
- pc.is_monotonic_increasing[Dimension] = false;
- }
- if (geometry::get<Dimension>(current) <= geometry::get<Dimension>(next))
- {
- pc.is_monotonic_decreasing[Dimension] = false;
- }
- }
- inline void determine_properties(piece& pc) const
- {
- pc.is_monotonic_increasing[0] = true;
- pc.is_monotonic_increasing[1] = true;
- pc.is_monotonic_decreasing[0] = true;
- pc.is_monotonic_decreasing[1] = true;
- pc.is_convex = geometry::is_convex(pc.robust_ring, m_side_strategy);
- if (pc.offsetted_count < 2)
- {
- return;
- }
- typename robust_ring_type::const_iterator current = pc.robust_ring.begin();
- typename robust_ring_type::const_iterator next = current + 1;
- for (signed_size_type i = 1; i < pc.offsetted_count; i++)
- {
- determine_monotonicity<0>(pc, *current, *next);
- determine_monotonicity<1>(pc, *current, *next);
- current = next;
- ++next;
- }
- }
- void determine_properties()
- {
- for (typename piece_vector_type::iterator it = boost::begin(m_pieces);
- it != boost::end(m_pieces);
- ++it)
- {
- determine_properties(*it);
- }
- }
- inline void reverse_negative_robust_rings()
- {
- for (typename piece_vector_type::iterator it = boost::begin(m_pieces);
- it != boost::end(m_pieces);
- ++it)
- {
- piece& pc = *it;
- if (geometry::area(pc.robust_ring, m_robust_area_strategy) < 0)
- {
- // Rings can be ccw:
- // - in a concave piece
- // - in a line-buffer with a negative buffer-distance
- std::reverse(pc.robust_ring.begin(), pc.robust_ring.end());
- }
- }
- }
- inline void prepare_buffered_point_piece(piece& pc)
- {
- // create monotonic sections in y-dimension
- typedef boost::mpl::vector_c<std::size_t, 1> dimensions;
- geometry::sectionalize<false, dimensions>(pc.robust_ring,
- detail::no_rescale_policy(), pc.sections,
- m_envelope_strategy, m_expand_strategy);
- // Determine min/max radius
- typedef geometry::model::referring_segment<robust_point_type const>
- robust_segment_type;
- typename robust_ring_type::const_iterator current = pc.robust_ring.begin();
- typename robust_ring_type::const_iterator next = current + 1;
- for (signed_size_type i = 1; i < pc.offsetted_count; i++)
- {
- robust_segment_type s(*current, *next);
- robust_comparable_radius_type const d
- = geometry::comparable_distance(pc.robust_center, s);
- if (i == 1 || d < pc.robust_min_comparable_radius)
- {
- pc.robust_min_comparable_radius = d;
- }
- if (i == 1 || d > pc.robust_max_comparable_radius)
- {
- pc.robust_max_comparable_radius = d;
- }
- current = next;
- ++next;
- }
- }
- inline void prepare_buffered_point_pieces()
- {
- for (typename piece_vector_type::iterator it = boost::begin(m_pieces);
- it != boost::end(m_pieces);
- ++it)
- {
- if (it->type == geometry::strategy::buffer::buffered_point)
- {
- prepare_buffered_point_piece(*it);
- }
- }
- }
- template <typename DistanceStrategy>
- inline void get_turns(DistanceStrategy const& distance_strategy)
- {
- for(typename boost::range_iterator<sections_type>::type it
- = boost::begin(monotonic_sections);
- it != boost::end(monotonic_sections);
- ++it)
- {
- enlarge_box(it->bounding_box, 1);
- }
- {
- // Calculate the turns
- piece_turn_visitor
- <
- piece_vector_type,
- buffered_ring_collection<buffered_ring<Ring> >,
- turn_vector_type,
- IntersectionStrategy,
- RobustPolicy
- > visitor(m_pieces, offsetted_rings, m_turns,
- m_intersection_strategy, m_robust_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
- <
- robust_box_type
- >::apply(monotonic_sections, visitor,
- get_section_box_type(),
- overlaps_section_box_type());
- }
- insert_rescaled_piece_turns();
- reverse_negative_robust_rings();
- determine_properties();
- prepare_buffered_point_pieces();
- {
- // Check if it is inside any of the pieces
- turn_in_piece_visitor
- <
- typename geometry::cs_tag<point_type>::type,
- turn_vector_type, piece_vector_type,
- DistanceStrategy,
- point_in_geometry_strategy_type,
- side_strategy_type
- > visitor(m_turns, m_pieces,
- distance_strategy,
- m_point_in_geometry_strategy,
- m_side_strategy);
- typedef turn_ovelaps_box
- <
- typename IntersectionStrategy::disjoint_point_box_strategy_type
- > turn_ovelaps_box_type;
- typedef piece_ovelaps_box
- <
- typename IntersectionStrategy::disjoint_box_box_strategy_type
- > piece_ovelaps_box_type;
- geometry::partition
- <
- robust_box_type
- >::apply(m_turns, m_pieces, visitor,
- turn_get_box(), turn_ovelaps_box_type(),
- piece_get_box(), piece_ovelaps_box_type());
- }
- }
- inline void start_new_ring(bool deflate)
- {
- signed_size_type const n = static_cast<signed_size_type>(offsetted_rings.size());
- current_segment_id.source_index = 0;
- current_segment_id.multi_index = n;
- current_segment_id.ring_index = -1;
- current_segment_id.segment_index = 0;
- offsetted_rings.resize(n + 1);
- current_robust_ring.clear();
- m_first_piece_index = static_cast<signed_size_type>(boost::size(m_pieces));
- m_deflate = deflate;
- if (deflate)
- {
- // Pieces contain either deflated exterior rings, or inflated
- // interior rings which are effectively deflated too
- m_has_deflated = true;
- }
- }
- inline void abort_ring()
- {
- // Remove all created pieces for this ring, sections, last offsetted
- while (! m_pieces.empty()
- && m_pieces.back().first_seg_id.multi_index
- == current_segment_id.multi_index)
- {
- m_pieces.erase(m_pieces.end() - 1);
- }
- while (! monotonic_sections.empty()
- && monotonic_sections.back().ring_id.multi_index
- == current_segment_id.multi_index)
- {
- monotonic_sections.erase(monotonic_sections.end() - 1);
- }
- offsetted_rings.erase(offsetted_rings.end() - 1);
- current_robust_ring.clear();
- m_first_piece_index = -1;
- }
- inline void update_closing_point()
- {
- BOOST_GEOMETRY_ASSERT(! offsetted_rings.empty());
- buffered_ring<Ring>& added = offsetted_rings.back();
- if (! boost::empty(added))
- {
- range::back(added) = range::front(added);
- }
- }
- inline void update_last_point(point_type const& p,
- buffered_ring<Ring>& ring)
- {
- // For the first point of a new piece, and there were already
- // points in the offsetted ring, for some piece types the first point
- // is a duplicate of the last point of the previous piece.
- // TODO: disable that, that point should not be added
- // For now, it is made equal because due to numerical instability,
- // it can be a tiny bit off, possibly causing a self-intersection
- BOOST_GEOMETRY_ASSERT(boost::size(m_pieces) > 0);
- if (! ring.empty()
- && current_segment_id.segment_index
- == m_pieces.back().first_seg_id.segment_index)
- {
- ring.back() = p;
- }
- }
- inline void set_piece_center(point_type const& center)
- {
- BOOST_GEOMETRY_ASSERT(! m_pieces.empty());
- geometry::recalculate(m_pieces.back().robust_center, center,
- m_robust_policy);
- }
- inline void finish_ring(strategy::buffer::result_code code,
- bool is_interior = false, bool has_interiors = false)
- {
- if (code == strategy::buffer::result_error_numerical)
- {
- abort_ring();
- return;
- }
- if (m_first_piece_index == -1)
- {
- return;
- }
- if (m_first_piece_index < static_cast<signed_size_type>(boost::size(m_pieces)))
- {
- // If piece was added
- // Reassign left-of-first and right-of-last
- geometry::range::at(m_pieces, m_first_piece_index).left_index
- = static_cast<signed_size_type>(boost::size(m_pieces)) - 1;
- geometry::range::back(m_pieces).right_index = m_first_piece_index;
- }
- m_first_piece_index = -1;
- update_closing_point();
- if (! current_robust_ring.empty())
- {
- BOOST_GEOMETRY_ASSERT
- (
- geometry::equals(current_robust_ring.front(),
- current_robust_ring.back())
- );
- robust_originals.push_back(
- robust_original(current_robust_ring,
- is_interior, has_interiors, m_envelope_strategy, m_expand_strategy));
- }
- }
- inline void set_current_ring_concave()
- {
- BOOST_GEOMETRY_ASSERT(boost::size(offsetted_rings) > 0);
- offsetted_rings.back().has_concave = true;
- }
- inline signed_size_type add_point(point_type const& p)
- {
- BOOST_GEOMETRY_ASSERT(boost::size(offsetted_rings) > 0);
- buffered_ring<Ring>& current_ring = offsetted_rings.back();
- update_last_point(p, current_ring);
- current_segment_id.segment_index++;
- current_ring.push_back(p);
- return static_cast<signed_size_type>(current_ring.size());
- }
- //-------------------------------------------------------------------------
- inline piece& create_piece(strategy::buffer::piece_type type,
- bool decrease_segment_index_by_one)
- {
- if (type == strategy::buffer::buffered_concave)
- {
- offsetted_rings.back().has_concave = true;
- }
- piece pc;
- pc.type = type;
- pc.index = static_cast<signed_size_type>(boost::size(m_pieces));
- pc.is_deflated = m_deflate;
- current_segment_id.piece_index = pc.index;
- pc.first_seg_id = current_segment_id;
- // Assign left/right (for first/last piece per ring they will be re-assigned later)
- pc.left_index = pc.index - 1;
- pc.right_index = pc.index + 1;
- std::size_t const n = boost::size(offsetted_rings.back());
- pc.first_seg_id.segment_index = decrease_segment_index_by_one ? n - 1 : n;
- pc.last_segment_index = pc.first_seg_id.segment_index;
- m_pieces.push_back(pc);
- return m_pieces.back();
- }
- inline void init_rescale_piece(piece& pc, std::size_t helper_points_size)
- {
- if (pc.first_seg_id.segment_index < 0)
- {
- // This indicates an error situation: an earlier piece was empty
- // It currently does not happen
- // std::cout << "EMPTY " << pc.type << " " << pc.index << " " << pc.first_seg_id.multi_index << std::endl;
- pc.offsetted_count = 0;
- return;
- }
- BOOST_GEOMETRY_ASSERT(pc.first_seg_id.multi_index >= 0);
- BOOST_GEOMETRY_ASSERT(pc.last_segment_index >= 0);
- pc.offsetted_count = pc.last_segment_index - pc.first_seg_id.segment_index;
- BOOST_GEOMETRY_ASSERT(pc.offsetted_count >= 0);
- pc.robust_ring.reserve(pc.offsetted_count + helper_points_size);
- // Add rescaled offsetted segments
- {
- buffered_ring<Ring> const& ring = offsetted_rings[pc.first_seg_id.multi_index];
- typedef typename boost::range_iterator<const buffered_ring<Ring> >::type it_type;
- for (it_type it = boost::begin(ring) + pc.first_seg_id.segment_index;
- it != boost::begin(ring) + pc.last_segment_index;
- ++it)
- {
- robust_point_type point;
- geometry::recalculate(point, *it, m_robust_policy);
- pc.robust_ring.push_back(point);
- }
- }
- }
- inline robust_point_type add_helper_point(piece& pc, const point_type& point)
- {
- #if defined(BOOST_GEOMETRY_BUFFER_USE_HELPER_POINTS)
- pc.helper_points.push_back(point);
- #endif
- robust_point_type rob_point;
- geometry::recalculate(rob_point, point, m_robust_policy);
- pc.robust_ring.push_back(rob_point);
- return rob_point;
- }
- // TODO: this is shared with sectionalize, move to somewhere else (assign?)
- template <typename Box, typename Value>
- inline void enlarge_box(Box& box, Value value)
- {
- geometry::set<0, 0>(box, geometry::get<0, 0>(box) - value);
- geometry::set<0, 1>(box, geometry::get<0, 1>(box) - value);
- geometry::set<1, 0>(box, geometry::get<1, 0>(box) + value);
- geometry::set<1, 1>(box, geometry::get<1, 1>(box) + value);
- }
- inline void calculate_robust_envelope(piece& pc)
- {
- if (pc.offsetted_count == 0)
- {
- return;
- }
- geometry::envelope(pc.robust_ring, pc.robust_envelope, m_envelope_strategy);
- geometry::assign_inverse(pc.robust_offsetted_envelope);
- for (signed_size_type i = 0; i < pc.offsetted_count; i++)
- {
- geometry::expand(pc.robust_offsetted_envelope, pc.robust_ring[i]);
- }
- // Take roundings into account, enlarge boxes with 1 integer
- enlarge_box(pc.robust_envelope, 1);
- enlarge_box(pc.robust_offsetted_envelope, 1);
- }
- inline void sectionalize(piece& pc)
- {
- buffered_ring<Ring> const& ring = offsetted_rings.back();
- typedef geometry::detail::sectionalize::sectionalize_part
- <
- point_type,
- boost::mpl::vector_c<std::size_t, 0, 1> // x,y dimension
- > sectionalizer;
- // Create a ring-identifier. The source-index is the piece index
- // The multi_index is as in this collection (the ring), but not used here
- // The ring_index is not used
- ring_identifier ring_id(pc.index, pc.first_seg_id.multi_index, -1);
- sectionalizer::apply(monotonic_sections,
- boost::begin(ring) + pc.first_seg_id.segment_index,
- boost::begin(ring) + pc.last_segment_index,
- m_robust_policy,
- ring_id, 10);
- }
- inline void finish_piece(piece& pc)
- {
- init_rescale_piece(pc, 0u);
- calculate_robust_envelope(pc);
- sectionalize(pc);
- }
- inline void finish_piece(piece& pc,
- const point_type& point1,
- const point_type& point2,
- const point_type& point3)
- {
- init_rescale_piece(pc, 3u);
- if (pc.offsetted_count == 0)
- {
- return;
- }
- add_helper_point(pc, point1);
- robust_point_type mid_point = add_helper_point(pc, point2);
- add_helper_point(pc, point3);
- calculate_robust_envelope(pc);
- sectionalize(pc);
- current_robust_ring.push_back(mid_point);
- }
- inline void finish_piece(piece& pc,
- const point_type& point1,
- const point_type& point2,
- const point_type& point3,
- const point_type& point4)
- {
- init_rescale_piece(pc, 4u);
- add_helper_point(pc, point1);
- robust_point_type mid_point2 = add_helper_point(pc, point2);
- robust_point_type mid_point1 = add_helper_point(pc, point3);
- add_helper_point(pc, point4);
- sectionalize(pc);
- calculate_robust_envelope(pc);
- // Add mid-points in other order to current helper_ring
- current_robust_ring.push_back(mid_point1);
- current_robust_ring.push_back(mid_point2);
- }
- inline void add_piece(strategy::buffer::piece_type type, point_type const& p,
- point_type const& b1, point_type const& b2)
- {
- piece& pc = create_piece(type, false);
- add_point(b1);
- pc.last_segment_index = add_point(b2);
- finish_piece(pc, b2, p, b1);
- }
- template <typename Range>
- inline void add_range_to_piece(piece& pc, Range const& range, bool add_front)
- {
- BOOST_GEOMETRY_ASSERT(boost::size(range) != 0u);
- typename Range::const_iterator it = boost::begin(range);
- // If it follows a non-join (so basically the same piece-type) point b1 should be added.
- // There should be two intersections later and it should be discarded.
- // But for now we need it to calculate intersections
- if (add_front)
- {
- add_point(*it);
- }
- for (++it; it != boost::end(range); ++it)
- {
- pc.last_segment_index = add_point(*it);
- }
- }
- template <typename Range>
- inline void add_piece(strategy::buffer::piece_type type, Range const& range,
- bool decrease_segment_index_by_one)
- {
- piece& pc = create_piece(type, decrease_segment_index_by_one);
- if (boost::size(range) > 0u)
- {
- add_range_to_piece(pc, range, offsetted_rings.back().empty());
- }
- finish_piece(pc);
- }
- template <typename Range>
- inline void add_side_piece(point_type const& p1, point_type const& p2,
- Range const& range, bool first)
- {
- BOOST_GEOMETRY_ASSERT(boost::size(range) >= 2u);
- piece& pc = create_piece(strategy::buffer::buffered_segment, ! first);
- add_range_to_piece(pc, range, first);
- finish_piece(pc, range.back(), p2, p1, range.front());
- }
- template <typename Range>
- inline void add_piece(strategy::buffer::piece_type type,
- point_type const& p, Range const& range)
- {
- piece& pc = create_piece(type, true);
- if (boost::size(range) > 0u)
- {
- add_range_to_piece(pc, range, offsetted_rings.back().empty());
- finish_piece(pc, range.back(), p, range.front());
- }
- else
- {
- finish_piece(pc);
- }
- }
- template <typename EndcapStrategy, typename Range>
- inline void add_endcap(EndcapStrategy const& strategy, Range const& range,
- point_type const& end_point)
- {
- boost::ignore_unused(strategy);
- if (range.empty())
- {
- return;
- }
- strategy::buffer::piece_type pt = strategy.get_piece_type();
- if (pt == strategy::buffer::buffered_flat_end)
- {
- // It is flat, should just be added, without helper segments
- add_piece(pt, range, true);
- }
- else
- {
- // Normal case, it has an "inside", helper segments should be added
- add_piece(pt, end_point, range);
- }
- }
- inline void mark_flat_start()
- {
- if (! m_pieces.empty())
- {
- piece& back = m_pieces.back();
- back.is_flat_start = true;
- }
- }
- inline void mark_flat_end()
- {
- if (! m_pieces.empty())
- {
- piece& back = m_pieces.back();
- back.is_flat_end = true;
- }
- }
- //-------------------------------------------------------------------------
- inline void enrich()
- {
- enrich_intersection_points<false, false, overlay_buffer>(m_turns,
- m_clusters, offsetted_rings, offsetted_rings,
- m_robust_policy,
- m_intersection_strategy);
- }
- // Discards all rings which do have not-OK intersection points only.
- // Those can never be traversed and should not be part of the output.
- inline void discard_rings()
- {
- for (typename boost::range_iterator<turn_vector_type const>::type it =
- boost::begin(m_turns); it != boost::end(m_turns); ++it)
- {
- if (it->location != location_ok)
- {
- offsetted_rings[it->operations[0].seg_id.multi_index].has_discarded_intersections = true;
- offsetted_rings[it->operations[1].seg_id.multi_index].has_discarded_intersections = true;
- }
- else
- {
- offsetted_rings[it->operations[0].seg_id.multi_index].has_accepted_intersections = true;
- offsetted_rings[it->operations[1].seg_id.multi_index].has_accepted_intersections = true;
- }
- }
- }
- inline bool point_coveredby_original(point_type const& point)
- {
- typedef typename IntersectionStrategy::disjoint_point_box_strategy_type d_pb_strategy_type;
- robust_point_type any_point;
- geometry::recalculate(any_point, point, m_robust_policy);
- signed_size_type count_in_original = 0;
- // Check of the robust point of this outputted ring is in
- // any of the robust original rings
- // This can go quadratic if the input has many rings, and there
- // are many untouched deflated rings around
- for (typename std::vector<robust_original>::const_iterator it
- = robust_originals.begin();
- it != robust_originals.end();
- ++it)
- {
- robust_original const& original = *it;
- if (detail::disjoint::disjoint_point_box(any_point,
- original.m_box,
- d_pb_strategy_type()))
- {
- continue;
- }
- int const geometry_code
- = detail::within::point_in_geometry(any_point,
- original.m_ring, m_point_in_geometry_strategy);
- if (geometry_code == -1)
- {
- // Outside, continue
- continue;
- }
- // Apply for possibly nested interior rings
- if (original.m_is_interior)
- {
- count_in_original--;
- }
- else if (original.m_has_interiors)
- {
- count_in_original++;
- }
- else
- {
- // Exterior ring without interior rings
- return true;
- }
- }
- return count_in_original > 0;
- }
- // For a deflate, all rings around inner rings which are untouched
- // (no intersections/turns) and which are OUTSIDE the original should
- // be discarded
- inline void discard_nonintersecting_deflated_rings()
- {
- for(typename buffered_ring_collection<buffered_ring<Ring> >::iterator it
- = boost::begin(offsetted_rings);
- it != boost::end(offsetted_rings);
- ++it)
- {
- buffered_ring<Ring>& ring = *it;
- if (! ring.has_intersections()
- && boost::size(ring) > 0u
- && geometry::area(ring, m_area_strategy) < 0)
- {
- if (! point_coveredby_original(geometry::range::front(ring)))
- {
- ring.is_untouched_outside_original = true;
- }
- }
- }
- }
- inline void block_turns()
- {
- // To fix left-turn issues like #rt_u13
- // But currently it causes more other issues than it fixes
- // m_turns.erase
- // (
- // std::remove_if(boost::begin(m_turns), boost::end(m_turns),
- // redundant_turn()),
- // boost::end(m_turns)
- // );
- for (typename boost::range_iterator<turn_vector_type>::type it =
- boost::begin(m_turns); it != boost::end(m_turns); ++it)
- {
- buffer_turn_info_type& turn = *it;
- if (turn.location != location_ok)
- {
- // Discard this turn (don't set it to blocked to avoid colocated
- // clusters being discarded afterwards
- turn.discarded = true;
- }
- }
- }
- inline void traverse()
- {
- typedef detail::overlay::traverse
- <
- false, false,
- buffered_ring_collection<buffered_ring<Ring> >,
- buffered_ring_collection<buffered_ring<Ring > >,
- overlay_buffer,
- backtrack_for_buffer
- > traverser;
- std::map<ring_identifier, overlay::ring_turn_info> turn_info_per_ring;
- traversed_rings.clear();
- buffer_overlay_visitor visitor;
- traverser::apply(offsetted_rings, offsetted_rings,
- m_intersection_strategy, m_robust_policy,
- m_turns, traversed_rings,
- turn_info_per_ring,
- m_clusters, visitor);
- }
- inline void reverse()
- {
- for(typename buffered_ring_collection<buffered_ring<Ring> >::iterator it = boost::begin(offsetted_rings);
- it != boost::end(offsetted_rings);
- ++it)
- {
- if (! it->has_intersections())
- {
- std::reverse(it->begin(), it->end());
- }
- }
- for (typename boost::range_iterator<buffered_ring_collection<Ring> >::type
- it = boost::begin(traversed_rings);
- it != boost::end(traversed_rings);
- ++it)
- {
- std::reverse(it->begin(), it->end());
- }
- }
- template <typename GeometryOutput, typename OutputIterator>
- inline OutputIterator assign(OutputIterator out) const
- {
- typedef detail::overlay::ring_properties<point_type, area_result_type> properties;
- std::map<ring_identifier, properties> selected;
- // Select all rings which do not have any self-intersection
- // Inner rings, for deflate, which do not have intersections, and
- // which are outside originals, are skipped
- // (other ones should be traversed)
- signed_size_type index = 0;
- for(typename buffered_ring_collection<buffered_ring<Ring> >::const_iterator it = boost::begin(offsetted_rings);
- it != boost::end(offsetted_rings);
- ++it, ++index)
- {
- if (! it->has_intersections()
- && ! it->is_untouched_outside_original)
- {
- properties p = properties(*it, m_area_strategy);
- if (p.valid)
- {
- ring_identifier id(0, index, -1);
- selected[id] = p;
- }
- }
- }
- // Select all created rings
- index = 0;
- for (typename boost::range_iterator<buffered_ring_collection<Ring> const>::type
- it = boost::begin(traversed_rings);
- it != boost::end(traversed_rings);
- ++it, ++index)
- {
- properties p = properties(*it, m_area_strategy);
- if (p.valid)
- {
- ring_identifier id(2, index, -1);
- selected[id] = p;
- }
- }
- detail::overlay::assign_parents<overlay_buffer>(offsetted_rings, traversed_rings,
- selected, m_intersection_strategy);
- return detail::overlay::add_rings<GeometryOutput>(selected, offsetted_rings, traversed_rings, out,
- m_area_strategy);
- }
- };
- }} // namespace detail::buffer
- #endif // DOXYGEN_NO_DETAIL
- }} // namespace boost::geometry
- #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_BUFFERED_PIECE_COLLECTION_HPP
|