|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r78680 - in trunk/boost/geometry: algorithms/detail algorithms/detail/overlay extensions/algorithms/buffer
From: barend.gehrels_at_[hidden]
Date: 2012-05-27 09:17:24
Author: barendgehrels
Date: 2012-05-27 09:17:22 EDT (Sun, 27 May 2012)
New Revision: 78680
URL: http://svn.boost.org/trac/boost/changeset/78680
Log:
[geometry] pending commits for buffer
Added:
trunk/boost/geometry/algorithms/detail/get_left_turns.hpp (contents, props changed)
Text files modified:
trunk/boost/geometry/algorithms/detail/occupation_info.hpp | 171 +--------------
trunk/boost/geometry/algorithms/detail/overlay/turn_info.hpp | 9
trunk/boost/geometry/extensions/algorithms/buffer/buffer_inserter.hpp | 4
trunk/boost/geometry/extensions/algorithms/buffer/buffer_policies.hpp | 5
trunk/boost/geometry/extensions/algorithms/buffer/buffered_piece_collection.hpp | 443 ++++++++++++++++++++-------------------
5 files changed, 253 insertions(+), 379 deletions(-)
Added: trunk/boost/geometry/algorithms/detail/get_left_turns.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/geometry/algorithms/detail/get_left_turns.hpp 2012-05-27 09:17:22 EDT (Sun, 27 May 2012)
@@ -0,0 +1,367 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+
+// Copyright (c) 2012 Barend Gehrels, Amsterdam, the Netherlands.
+
+// 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_GET_LEFT_TURNS_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_GET_LEFT_TURNS_HPP
+
+#include <boost/geometry/iterators/ever_circling_iterator.hpp>
+
+namespace boost { namespace geometry
+{
+
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail
+{
+
+// TODO: move this to /util/
+template <typename T>
+static inline std::pair<T, T> ordered_pair(T const& first, T const& second)
+{
+ return first < second ? std::make_pair(first, second) : std::make_pair(second, first);
+}
+
+template <typename AngleInfo>
+inline void debug_left_turn(AngleInfo const& ai, AngleInfo const& previous)
+{
+#ifdef BOOST_GEOMETRY_DEBUG_BUFFER_OCCUPATION
+ std::cout << "Angle: " << (ai.incoming ? "i" : "o")
+ << " " << si(ai.seg_id)
+ << " " << (math::r2d * (ai.angle) )
+ << " turn: " << ai.turn_index << "[" << ai.operation_index << "]"
+ ;
+
+ if (ai.turn_index != previous.turn_index
+ || ai.operation_index != previous.operation_index)
+ {
+ std::cout << " diff: " << math::r2d * math::abs(previous.angle - ai.angle);
+ }
+ std::cout << std::endl;
+#endif
+}
+
+template <typename AngleInfo>
+inline void debug_left_turn(std::string const& caption, AngleInfo const& ai, AngleInfo const& previous,
+ int code = -99, int code2 = -99, int code3 = -99, int code4 = -99)
+{
+#ifdef BOOST_GEOMETRY_DEBUG_BUFFER_OCCUPATION
+ std::cout << " " << caption
+ << " turn: " << ai.turn_index << "[" << ai.operation_index << "]"
+ << " " << si(ai.seg_id)
+ << " " << (ai.incoming ? "i" : "o")
+ << " " << (math::r2d * (ai.angle) )
+ << " turn: " << previous.turn_index << "[" << previous.operation_index << "]"
+ << " " << si(previous.seg_id)
+ << " " << (previous.incoming ? "i" : "o")
+ << " " << (math::r2d * (previous.angle) )
+ ;
+
+ if (code != -99)
+ {
+ std::cout << " code: " << code << " , " << code2 << " , " << code3 << " , " << code4;
+ }
+ std::cout << std::endl;
+#endif
+}
+
+
+template <typename Operation>
+inline bool include_operation(Operation const& op,
+ segment_identifier const& outgoing_seg_id,
+ segment_identifier const& incoming_seg_id)
+{
+ return op.seg_id == outgoing_seg_id
+ && op.other_id == incoming_seg_id
+ && (op.operation == detail::overlay::operation_union
+ ||op.operation == detail::overlay::operation_continue)
+ ;
+}
+
+template <typename Turn>
+inline bool process_include(segment_identifier const& outgoing_seg_id, segment_identifier const& incoming_seg_id,
+ int turn_index, Turn& turn,
+ std::set<int>& keep_indices, int priority)
+{
+ bool result = false;
+ for (int i = 0; i < 2; i++)
+ {
+ if (include_operation(turn.operations[i], outgoing_seg_id, incoming_seg_id))
+ {
+ turn.operations[i].include_in_occupation_map = true;
+ if (priority > turn.priority)
+ {
+ turn.priority = priority;
+ }
+ keep_indices.insert(turn_index);
+ result = true;
+ }
+ }
+ return result;
+}
+
+template <typename AngleInfo, typename Turns, typename TurnSegmentIndices>
+inline bool include_left_turn_of_all(
+ AngleInfo const& outgoing, AngleInfo const& incoming,
+ Turns& turns, TurnSegmentIndices const& turn_segment_indices,
+ std::set<int>& keep_indices, int priority)
+{
+ segment_identifier const& outgoing_seg_id = turns[outgoing.turn_index].operations[outgoing.operation_index].seg_id;
+ segment_identifier const& incoming_seg_id = turns[incoming.turn_index].operations[incoming.operation_index].seg_id;
+
+ if (outgoing.turn_index == incoming.turn_index)
+ {
+ return process_include(outgoing_seg_id, incoming_seg_id, outgoing.turn_index, turns[outgoing.turn_index], keep_indices, priority);
+ }
+
+ bool result = false;
+ std::pair<segment_identifier, segment_identifier> pair = ordered_pair(outgoing_seg_id, incoming_seg_id);
+ auto it = turn_segment_indices.find(pair);
+ if (it != turn_segment_indices.end())
+ {
+ for (auto sit = it->second.begin(); sit != it->second.end(); ++sit)
+ {
+ if (process_include(outgoing_seg_id, incoming_seg_id, *sit, turns[*sit], keep_indices, priority))
+ {
+ result = true;
+ }
+ }
+ }
+ return result;
+}
+
+template <std::size_t Index, typename Turn>
+inline bool corresponds(Turn const& turn, segment_identifier const& seg_id)
+{
+ return turn.operations[Index].operation == detail::overlay::operation_union
+ && turn.operations[Index].seg_id == seg_id;
+}
+
+
+template <typename Turns, typename TurnSegmentIndices>
+inline bool prefer_by_other(Turns const& turns,
+ TurnSegmentIndices const& turn_segment_indices,
+ std::set<int>& indices)
+{
+ std::map<segment_identifier, int> map;
+ for (auto sit = indices.begin(); sit != indices.end(); ++sit)
+ {
+ map[turns[*sit].operations[0].seg_id]++;
+ map[turns[*sit].operations[1].seg_id]++;
+ }
+
+ std::set<segment_identifier> segment_occuring_once;
+ for (auto mit = map.begin(); mit != map.end(); ++mit)
+ {
+ if (mit->second == 1)
+ {
+ segment_occuring_once.insert(mit->first);
+ }
+#ifdef BOOST_GEOMETRY_DEBUG_BUFFER_PREFER
+ std::cout << si(mit->first) << " " << mit->second << std::endl;
+#endif
+ }
+
+ if (segment_occuring_once.size() == 2)
+ {
+ // Try to find within all turns a turn with these two segments
+
+ std::set<segment_identifier>::const_iterator soo_it = segment_occuring_once.begin();
+ segment_identifier front = *soo_it;
+ soo_it++;
+ segment_identifier back = *soo_it;
+
+ std::pair<segment_identifier, segment_identifier> pair = ordered_pair(front, back);
+ auto it = turn_segment_indices.find(pair);
+ if (it != turn_segment_indices.end())
+ {
+ // debug_turns_by_indices("Found", it->second);
+ // Check which is the union/continue
+ segment_identifier good;
+ for (auto sit = it->second.begin(); sit != it->second.end(); ++sit)
+ {
+ if (turns[*sit].operations[0].operation == detail::overlay::operation_union)
+ {
+ good = turns[*sit].operations[0].seg_id;
+ }
+ else if (turns[*sit].operations[1].operation == detail::overlay::operation_union)
+ {
+ good = turns[*sit].operations[1].seg_id;
+ }
+ }
+
+#ifdef BOOST_GEOMETRY_DEBUG_BUFFER_PREFER
+ std::cout << "Good: " << si(good) << std::endl;
+#endif
+
+ // Find in indexes-to-keep this segment with the union. Discard the other one
+ std::set<int> ok_indices;
+ for (auto sit = indices.begin(); sit != indices.end(); ++sit)
+ {
+ if (corresponds<0>(turns[*sit], good) || corresponds<1>(turns[*sit], good))
+ {
+ ok_indices.insert(*sit);
+ }
+ }
+ if (ok_indices.size() > 0 && ok_indices.size() < indices.size())
+ {
+ indices = ok_indices;
+ std::cout << "^";
+ return true;
+ }
+ }
+ }
+ return false;
+}
+
+template <typename Turns>
+inline void prefer_by_priority(Turns const& turns, std::set<int>& indices)
+{
+ // Find max prio
+ int min_prio = 1024, max_prio = 0;
+ for (auto sit = indices.begin(); sit != indices.end(); ++sit)
+ {
+ if (turns[*sit].priority > max_prio)
+ {
+ max_prio = turns[*sit].priority;
+ }
+ if (turns[*sit].priority < min_prio)
+ {
+ min_prio = turns[*sit].priority;
+ }
+ }
+
+ if (min_prio == max_prio)
+ {
+ return;
+ }
+
+ // Only keep indices with high prio
+ std::set<int> ok_indices;
+ for (auto sit = indices.begin(); sit != indices.end(); ++sit)
+ {
+ if (turns[*sit].priority >= max_prio)
+ {
+ ok_indices.insert(*sit);
+ }
+ }
+ if (ok_indices.size() > 0 && ok_indices.size() < indices.size())
+ {
+ indices = ok_indices;
+ std::cout << "%";
+ }
+}
+
+template <typename AngleInfo, typename Angles, typename Turns, typename TurnSegmentIndices>
+inline void calculate_left_turns(Angles const& angles,
+ Turns& turns, TurnSegmentIndices const& turn_segment_indices,
+ std::set<int>& keep_indices)
+{
+ bool debug_indicate_size = false;
+
+ typedef typename strategy::side::services::default_strategy
+ <
+ typename cs_tag<typename AngleInfo::point_type>::type
+ >::type side_strategy;
+
+ std::size_t i = 0;
+ std::size_t n = boost::size(angles);
+
+ typedef geometry::ever_circling_range_iterator<Angles const> circling_iterator;
+ circling_iterator cit(angles);
+
+ debug_left_turn(*cit, *cit);
+ for(circling_iterator prev = cit++; i < n; prev = cit++, i++)
+ {
+ debug_left_turn(*cit, *prev);
+
+ bool const include = ! geometry::math::equals(prev->angle, cit->angle)
+ && ! prev->incoming
+ && cit->incoming;
+
+ if (include)
+ {
+ // Go back to possibly include more same left outgoing angles:
+ // Because we check on side too we can take a large "epsilon"
+ circling_iterator back = prev - 1;
+
+ typename AngleInfo::angle_type eps = 0.00001;
+ int b = 1;
+ for(std::size_t d = 0;
+ math::abs(prev->angle - back->angle) < eps
+ && ! back->incoming
+ && d < n;
+ d++)
+ {
+ --back;
+ ++b;
+ }
+
+ // Same but forward to possibly include more incoming angles
+ int f = 1;
+ circling_iterator forward = cit + 1;
+ for(std::size_t d = 0;
+ math::abs(cit->angle - forward->angle) < eps
+ && forward->incoming
+ && d < n;
+ d++)
+ {
+ ++forward;
+ ++f;
+ }
+
+#ifdef BOOST_GEOMETRY_DEBUG_BUFFER_OCCUPATION
+ std::cout << "HANDLE " << b << "/" << f << " ANGLES" << std::endl;
+#endif
+ for(circling_iterator bit = prev; bit != back; --bit)
+ {
+ int code = side_strategy::apply(bit->direction_point, prev->intersection_point, prev->direction_point);
+ int code2 = side_strategy::apply(prev->direction_point, bit->intersection_point, bit->direction_point);
+ for(circling_iterator fit = cit; fit != forward; ++fit)
+ {
+ int code3 = side_strategy::apply(fit->direction_point, cit->intersection_point, cit->direction_point);
+ int code4 = side_strategy::apply(cit->direction_point, fit->intersection_point, fit->direction_point);
+
+ int priority = 2;
+ if (code == -1 && code2 == 1)
+ {
+ // This segment is lying right of the other one.
+ // Cannot ignore it (because of robustness, see a.o. #rt_p21 from unit test).
+ // But if we find more we can prefer later by priority
+ // (a.o. necessary for #rt_o2 from unit test)
+ priority = 1;
+ }
+
+ bool included = include_left_turn_of_all(*bit, *fit, turns, turn_segment_indices, keep_indices, priority);
+ debug_left_turn(included ? "KEEP" : "SKIP", *fit, *bit, code, code2, code3, code4);
+ }
+ }
+ }
+ }
+
+ if (debug_indicate_size)
+ {
+ std::cout << " size=" << keep_indices.size();
+ }
+
+ if (keep_indices.size() >= 2)
+ {
+ prefer_by_other(turns, turn_segment_indices, keep_indices);
+ }
+ if (keep_indices.size() >= 2)
+ {
+ prefer_by_priority(turns, keep_indices);
+ }
+}
+
+} // namespace detail
+#endif // DOXYGEN_NO_DETAIL
+
+
+}} // namespace boost::geometry
+
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_GET_LEFT_TURNS_HPP
Modified: trunk/boost/geometry/algorithms/detail/occupation_info.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/occupation_info.hpp (original)
+++ trunk/boost/geometry/algorithms/detail/occupation_info.hpp 2012-05-27 09:17:22 EDT (Sun, 27 May 2012)
@@ -9,7 +9,9 @@
#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OCCUPATION_INFO_HPP
#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OCCUPATION_INFO_HPP
- #define BOOST_GEOMETRY_DEBUG_BUFFER_OCCUPATION
+#if ! defined(NDEBUG)
+ #define BOOST_GEOMETRY_DEBUG_BUFFER_OCCUPATION
+#endif
#include <algorithm>
#include <boost/range.hpp>
@@ -19,7 +21,8 @@
#include <boost/geometry/algorithms/equals.hpp>
#include <boost/geometry/iterators/closing_iterator.hpp>
-#include <boost/geometry/iterators/ever_circling_iterator.hpp>
+
+#include <boost/geometry/algorithms/detail/get_left_turns.hpp>
namespace boost { namespace geometry
@@ -42,8 +45,7 @@
inline relaxed_less()
{
// TODO: adapt for ttmath, and maybe build the map in another way
- // (e.g. exact constellations of segment-id's, maybe adaptive.
- // for the moment take the sqrt (to consider it as comparable distances)
+ // (e.g. exact constellations of segment-id's), maybe adaptive.
epsilon = std::numeric_limits<double>::epsilon() * 100.0;
}
@@ -211,163 +213,14 @@
return m_occupied;
}
- static inline void debug_left_turn(AngleInfo const& ai, AngleInfo const& previous)
- {
-#ifdef BOOST_GEOMETRY_DEBUG_BUFFER_OCCUPATION
- std::cout << "Angle: " << (ai.incoming ? "i" : "o")
- // << " " << si(ai.seg_id)
- << " " << (math::r2d * (ai.angle) )
- << " turn: " << ai.turn_index << "[" << ai.operation_index << "]";
-
- if (ai.turn_index != previous.turn_index
- || ai.operation_index != previous.operation_index)
- {
- std::cout << " diff: " << math::r2d * math::abs(previous.angle - ai.angle);
- }
- std::cout << std::endl;
-#endif
- }
-
- static inline void debug_left_turn(std::string const& caption, AngleInfo const& ai, AngleInfo const& previous,
- int code = -99, int code2 = -99, int code3 = -99, int code4 = -99)
+ template <typename Turns, typename TurnSegmentIndices>
+ inline void get_left_turns(
+ Turns& turns, TurnSegmentIndices const& turn_segment_indices,
+ std::set<int>& keep_indices)
{
-#ifdef BOOST_GEOMETRY_DEBUG_BUFFER_OCCUPATION
- std::cout << " " << caption << ": "
- << (ai.incoming ? "i" : "o")
- << " " << (math::r2d * (ai.angle) )
- << " turn: " << ai.turn_index << "[" << ai.operation_index << "]"
- << " " << (previous.incoming ? "i" : "o")
- << " " << (math::r2d * (previous.angle) )
- << " turn: " << previous.turn_index << "[" << previous.operation_index << "]";
-
- if (code != -99)
- {
- std::cout << " code: " << code << " , " << code2 << " , " << code3 << " , " << code4;
- }
- std::cout << std::endl;
-#endif
- }
-
- template <typename Turns>
- static inline void include_left_turn(AngleInfo const& outgoing, AngleInfo const& incoming,
- Turns const& turns,
- std::set<int> const& turn_indices,
- std::set<std::pair<int, int> >& keep_indices)
- {
- // Safety check
- if (turn_indices.count(outgoing.turn_index) > 0
- && turn_indices.count(incoming.turn_index) > 0)
- {
- // Check if this is the intended turn (of the two segments making an open angle with each other)
- if (turns[outgoing.turn_index].operations[outgoing.operation_index].other_id ==
- turns[incoming.turn_index].operations[incoming.operation_index].seg_id)
- {
- //if (turns[outgoing.turn_index].operations[outgoing.operation_index].operation == detail::overlay::operation_union
- // || turns[outgoing.turn_index].operations[outgoing.operation_index].operation == detail::overlay::operation_continue)
- {
- // This is the left turn. Mark it and don't check it for other pieces
- keep_indices.insert(std::make_pair(outgoing.turn_index, outgoing.operation_index));
- //std::cout << " INC";
- }
- }
-#ifdef BOOST_GEOMETRY_DEBUG_BUFFER_OCCUPATION
- //else
- //{
- // std::cout << " SKIP " << outgoing.turn_index << "[" << outgoing.operation_index << "]" << std::endl;
- //}
-#endif
- }
+ std::sort(angles.begin(), angles.end(), angle_sort());
+ calculate_left_turns<AngleInfo>(angles, turns, turn_segment_indices, keep_indices);
}
-
-
- template <typename Turns>
- inline void get_left_turns(Turns const& turns,
- std::set<int> const& turn_indices,
- std::set<std::pair<int, int> >& keep_indices)
- {
- typedef typename strategy::side::services::default_strategy
- <
- typename cs_tag<typename AngleInfo::point_type>::type
- >::type side_strategy;
-
- std::sort(angles.begin(), angles.end(), angle_sort());
-#ifdef BOOST_GEOMETRY_DEBUG_BUFFER_OCCUPATION
- std::cout << "get_left_turns()" << std::endl;
-#endif
-
- std::size_t i = 0;
- std::size_t n = boost::size(angles);
-
- typedef geometry::ever_circling_range_iterator<collection_type const> circling_iterator;
- circling_iterator cit(angles);
-
- debug_left_turn(*cit, *cit);
- for(circling_iterator prev = cit++; i < n; prev = cit++, i++)
- {
- debug_left_turn(*cit, *prev);
-
- bool include = ! geometry::math::equals(prev->angle, cit->angle)
- && ! prev->incoming
- && cit->incoming;
-
- if (include)
- {
- // Go back to possibly include more same left outgoing angles:
- // Because we check on side too we can take a large "epsilon"
- circling_iterator back = prev - 1;
-
- typename AngleInfo::angle_type eps = 0.00001;
- int b = 1;
- for(std::size_t d = 0;
- math::abs(prev->angle - back->angle) < eps
- && ! back->incoming
- && d < n;
- d++)
- {
- --back;
- ++b;
- }
-
- // Same but forward to possibly include more incoming angles
- int f = 1;
- circling_iterator forward = cit + 1;
- for(std::size_t d = 0;
- math::abs(cit->angle - forward->angle) < eps
- && forward->incoming
- && d < n;
- d++)
- {
- ++forward;
- ++f;
- }
-
-#ifdef BOOST_GEOMETRY_DEBUG_BUFFER_OCCUPATION
- std::cout << "HANDLE " << b << "/" << f << " ANGLES" << std::endl;
-#endif
-
- for(circling_iterator bit = prev; bit != back; --bit)
- {
- int code = side_strategy::apply(bit->direction_point, prev->intersection_point, prev->direction_point);
- int code2 = side_strategy::apply(prev->direction_point, bit->intersection_point, bit->direction_point);
- for(circling_iterator fit = cit; fit != forward; ++fit)
- {
- int code3 = side_strategy::apply(fit->direction_point, cit->intersection_point, cit->direction_point);
- int code4 = side_strategy::apply(cit->direction_point, fit->intersection_point, fit->direction_point);
-
- if (! (code == -1 && code2 == 1))
- {
- include_left_turn(*bit, *fit, turns, turn_indices, keep_indices);
- debug_left_turn("ALSO", *fit, *bit, code, code2, code3, code4);
- }
- }
- }
- }
- }
-#ifdef BOOST_GEOMETRY_DEBUG_BUFFER_OCCUPATION
- std::cout << "USE " << keep_indices.size() << " OF " << turn_indices.size() << " TURNS" << std::endl;
-#endif
- }
-
};
Modified: trunk/boost/geometry/algorithms/detail/overlay/turn_info.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/overlay/turn_info.hpp (original)
+++ trunk/boost/geometry/algorithms/detail/overlay/turn_info.hpp 2012-05-27 09:17:22 EDT (Sun, 27 May 2012)
@@ -103,6 +103,12 @@
{
return has12(type, type);
}
+
+ inline bool has(operation_type type) const
+ {
+ return this->operations[0].operation == type
+ || this->operations[1].operation == type;
+ }
inline bool combination(operation_type type1, operation_type type2) const
{
@@ -121,8 +127,7 @@
}
inline bool any_blocked() const
{
- return this->operations[0].operation == operation_blocked
- || this->operations[1].operation == operation_blocked;
+ return has(operation_blocked);
}
Modified: trunk/boost/geometry/extensions/algorithms/buffer/buffer_inserter.hpp
==============================================================================
--- trunk/boost/geometry/extensions/algorithms/buffer/buffer_inserter.hpp (original)
+++ trunk/boost/geometry/extensions/algorithms/buffer/buffer_inserter.hpp 2012-05-27 09:17:22 EDT (Sun, 27 May 2012)
@@ -368,8 +368,8 @@
#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
//collection.map_offsetted(mapper);
//collection.map_offsetted_points(mapper);
- //collection.map_turns(mapper);
- collection.map_opposite_locations(mapper);
+ collection.map_turns(mapper);
+ //collection.map_opposite_locations(mapper);
#endif
collection.discard_rings();
Modified: trunk/boost/geometry/extensions/algorithms/buffer/buffer_policies.hpp
==============================================================================
--- trunk/boost/geometry/extensions/algorithms/buffer/buffer_policies.hpp (original)
+++ trunk/boost/geometry/extensions/algorithms/buffer/buffer_policies.hpp 2012-05-27 09:17:22 EDT (Sun, 27 May 2012)
@@ -101,9 +101,11 @@
struct buffer_turn_operation : public detail::overlay::traversal_turn_operation<Point>
{
int piece_index;
+ bool include_in_occupation_map;
inline buffer_turn_operation()
: piece_index(-1)
+ , include_in_occupation_map(false)
{}
};
@@ -115,12 +117,14 @@
intersection_location_type location;
+ int priority;
int count_within, count_on_helper, count_on_offsetted, count_on_corner;
int count_on_occupied;
int count_on_multi;
#if defined(BOOST_GEOMETRY_COUNT_DOUBLE_UU)
int count_on_uu;
#endif
+
std::set<int> piece_indices_to_skip;
#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
@@ -130,6 +134,7 @@
inline buffer_turn_info()
: is_opposite(false)
, location(location_ok)
+ , priority(0)
, count_within(0)
, count_on_helper(0)
, count_on_offsetted(0)
Modified: trunk/boost/geometry/extensions/algorithms/buffer/buffered_piece_collection.hpp
==============================================================================
--- trunk/boost/geometry/extensions/algorithms/buffer/buffered_piece_collection.hpp (original)
+++ trunk/boost/geometry/extensions/algorithms/buffer/buffered_piece_collection.hpp 2012-05-27 09:17:22 EDT (Sun, 27 May 2012)
@@ -15,6 +15,7 @@
#include <set>
#include <boost/range.hpp>
+
#include <boost/geometry/core/coordinate_type.hpp>
#include <boost/geometry/core/point_type.hpp>
@@ -173,6 +174,9 @@
buffered_ring_collection<Ring> traversed_rings;
segment_identifier current_segment_id;
+ std::map<std::pair<segment_identifier, segment_identifier>, std::set<int> > m_turn_indices_per_segment_pair;
+
+
typedef std::vector<buffer_turn_info<point_type> > turn_vector_type;
typedef detail::overlay::get_turn_info
<
@@ -297,6 +301,11 @@
iterator next2 = next_point(ring2, it2);
+ if (piece1.index == 5 && piece2.index == 22)
+ {
+ int kkk = 0;
+ }
+
turn_policy::apply(*prev1, *it1, *next1,
*prev2, *it2, *next2,
the_model, std::back_inserter(m_turns));
@@ -429,7 +438,7 @@
buffered_ring<Ring> const& ring = offsetted_rings[seg_id.multi_index];
- int const side_offsetted = side_on_convex_range<side_strategy >(turn.point,
+ int const side_offsetted = side_on_convex_range< /*relaxed_side<point_type> */ side_strategy >(turn.point,
boost::begin(ring) + seg_id.segment_index,
boost::begin(ring) + pc.last_segment_index,
seg_id, on_segment_seg_id);
@@ -473,7 +482,7 @@
}
}
- inline void debug_preference(std::string const& caption, std::set<int> const& indices) const
+ inline void debug_turns_by_indices(std::string const& caption, std::set<int> const& indices) const
{
#ifdef BOOST_GEOMETRY_DEBUG_BUFFER_OCCUPATION
std::cout << caption << ": " << indices.size() << std::endl;
@@ -493,21 +502,14 @@
#endif
}
- template <typename T>
- static inline std::pair<T, T> ordered_pair(T const& first, T const& second)
- {
- return first < second ? std::make_pair(first, second) : std::make_pair(second, first);
- }
-
- std::map<std::pair<segment_identifier, segment_identifier>, std::set<int> > turns_per_segment;
inline void fill_segment_map()
{
- turns_per_segment.clear();
+ m_turn_indices_per_segment_pair.clear();
int index = 0;
for (typename boost::range_iterator<turn_vector_type>::type it =
boost::begin(m_turns); it != boost::end(m_turns); ++it, ++index)
{
- turns_per_segment
+ m_turn_indices_per_segment_pair
[
ordered_pair
(
@@ -518,156 +520,17 @@
}
}
- template <std::size_t Index, typename Turn>
- static inline bool corresponds(Turn const& turn, segment_identifier const& seg_id)
- {
- return turn.operations[Index].operation == detail::overlay::operation_union
- && turn.operations[Index].seg_id == seg_id;
- }
-
- inline bool prefer_one(std::set<int>& indices) const
- {
- std::map<segment_identifier, int> map;
- for (auto sit = indices.begin(); sit != indices.end(); ++sit)
- {
- int const index = *sit;
- map[m_turns[index].operations[0].seg_id]++;
- map[m_turns[index].operations[1].seg_id]++;
- }
- std::set<segment_identifier> segment_occuring_once;
- for (auto mit = map.begin(); mit != map.end(); ++mit)
- {
- if (mit->second == 1)
- {
- segment_occuring_once.insert(mit->first);
- }
-#ifdef BOOST_GEOMETRY_DEBUG_BUFFER_PREFER
- std::cout << si(mit->first) << " " << mit->second << std::endl;
-#endif
- }
- if (segment_occuring_once.size() == 2)
- {
- // Try to find within all turns a turn with these two segments
-
- std::set<segment_identifier>::const_iterator soo_it = segment_occuring_once.begin();
- segment_identifier front = *soo_it;
- soo_it++;
- segment_identifier back = *soo_it;
-
- std::pair<segment_identifier, segment_identifier> pair = ordered_pair(front, back);
- auto it = turns_per_segment.find(pair);
- if (it != turns_per_segment.end())
- {
- debug_preference("Found", it->second);
- // Check which is the union/continue
- segment_identifier good;
- for (auto sit = it->second.begin(); sit != it->second.end(); ++sit)
- {
- if (m_turns[*sit].operations[0].operation == detail::overlay::operation_union)
- {
- good = m_turns[*sit].operations[0].seg_id;
- }
- else if (m_turns[*sit].operations[1].operation == detail::overlay::operation_union)
- {
- good = m_turns[*sit].operations[1].seg_id;
- }
- }
-
-#ifdef BOOST_GEOMETRY_DEBUG_BUFFER_PREFER
- std::cout << "Good: " << si(good) << std::endl;
-#endif
-
- // Find in indexes-to-keep this segment with the union. Discard the other one
- std::set<int> ok_indices;
- for (auto sit = indices.begin(); sit != indices.end(); ++sit)
- {
- if (corresponds<0>(m_turns[*sit], good) || corresponds<1>(m_turns[*sit], good))
- {
- ok_indices.insert(*sit);
- }
- }
- if (ok_indices.size() > 0 && ok_indices.size() < indices.size())
- {
- indices = ok_indices;
- ////std::cout << "^";
- return true;
- }
- }
- }
- return false;
- }
-
- inline void get_left_turns(buffer_occupation_info& info)
+ // Sets "count_on_multi" (if not kept) or "piece_indices_to_skip" (if kept)
+ // for to avoid within operations for these pieces
+ inline void process_left_turns(buffer_occupation_info const& info,
+ std::set<int> const& keep_indices)
{
- std::set<std::pair<int, int> > keep_indices;
- info.get_left_turns(m_turns, info.turn_indices, keep_indices);
-
- if (keep_indices.empty())
- {
- return;
- }
-
-#ifdef BOOST_GEOMETRY_DEBUG_BUFFER_OCCUPATION
- for (std::set<std::pair<int, int> >::const_iterator sit = keep_indices.begin();
- sit != keep_indices.end();
- ++sit)
- {
- std::cout << " " << sit->first << "[" << sit->second << "]";
- }
- std::cout << std::endl;
-#endif
-
- // We have to create a version of the set with only turn_indices, ki
- std::set<int> ki;
- for (std::set<std::pair<int, int> >::const_iterator sit = keep_indices.begin();
- sit != keep_indices.end();
- ++sit)
- {
- ki.insert(sit->first);
-
- if (m_turns[sit->first].both(detail::overlay::operation_union))
- {
- // Avoid both turns of a u/u turn to be included.
- if (keep_indices.count(std::make_pair(sit->first, 1 - sit->second)) == 0)
- {
- m_turns[sit->first].operations[1 - sit->second].operation = detail::overlay::operation_none;
- }
-#if defined(BOOST_GEOMETRY_COUNT_DOUBLE_UU)
- else if (m_turns[sit->first].both(detail::overlay::operation_union))
- {
- m_turns[sit->first].count_on_uu++;
- }
-#endif
- }
-
-#ifdef BOOST_GEOMETRY_DEBUG_BUFFER_OCCUPATION
- std::cout << "Keep " << sit->first << "[" << sit->second << "]"
- << " "<< si(m_turns[sit->first].operations[0].seg_id)
- << " "<< si(m_turns[sit->first].operations[1].seg_id)
- << " " << m_turns[sit->first].operations[0].piece_index
- << "/" << m_turns[sit->first].operations[1].piece_index
- << " " << method_char(m_turns[sit->first].method)
- << " " << operation_char(m_turns[sit->first].operations[0].operation)
- << "/" << operation_char(m_turns[sit->first].operations[1].operation)
-
- << std::endl;
-#endif
-
- }
-
- if (ki.size() == 2)
- {
- debug_preference("Keep", ki);
- prefer_one(ki);
- debug_preference("Kept", ki);
- }
-
for (std::set<int>::const_iterator sit1 = info.turn_indices.begin();
sit1 != info.turn_indices.end();
++sit1)
{
- if (ki.count(*sit1) == 0)
+ if (keep_indices.count(*sit1) == 0)
{
m_turns[*sit1].count_on_multi++;
}
@@ -685,6 +548,22 @@
}
}
}
+ }
+
+ inline void get_left_turns(buffer_occupation_info& info)
+ {
+ debug_turns_by_indices("Examine", info.turn_indices);
+
+ std::set<int> keep_indices;
+ info.get_left_turns(m_turns, m_turn_indices_per_segment_pair, keep_indices);
+
+ if (! keep_indices.empty())
+ {
+#ifdef BOOST_GEOMETRY_DEBUG_BUFFER_OCCUPATION
+ std::cout << "USE " << keep_indices.size() << " OF " << info.turn_indices.size() << " TURNS" << std::endl;
+#endif
+ process_left_turns(info, keep_indices);
+ }
}
inline int piece_count(buffer_occupation_info const& info)
@@ -703,20 +582,18 @@
inline void classify_occupied_locations()
{
- fill_segment_map();
-
for (typename boost::range_iterator<typename occupation_map_type::map_type>::type it =
boost::begin(m_occupation_map.map);
it != boost::end(m_occupation_map.map); ++it)
{
buffer_occupation_info& info = it->second;
- int const pc = piece_count(info);
+
#ifdef BOOST_GEOMETRY_DEBUG_BUFFER_OCCUPATION
- std::cout << std::endl << "left turns: " << pc << " "
+ std::cout << std::endl << "left turns: " << piece_count(info) << " "
//<< std::setprecision(20)
<< geometry::wkt(it->first) << std::endl;
#endif
- if (pc > 2)
+ if (piece_count(info) > 2)
{
if (info.occupied())
{
@@ -724,10 +601,9 @@
std::cout << "-> occupied" << std::endl;
// std::set<int> turn_indices;
- //std::set<std::pair<int, int> > keep_indices;
//info.get_left_turns(it->first, m_turns, turn_indices, keep_indices); // just for debug-info
-
#endif
+
for (std::set<int>::const_iterator sit = info.turn_indices.begin();
sit != info.turn_indices.end();
++sit)
@@ -739,11 +615,62 @@
{
get_left_turns(info);
}
- //std::cout << geometry::wkt(it->first) << " " << int(info.occupied()) << std::endl;
+ //std::cout << geometry::wkt(it->first) << " " << int(info.occupied()) << std::endl;
}
}
}
+ // The "get_left_turn" process indicates, if it is a u/u turn (both only applicable
+ // for union, two separate turns), which is indicated in the map. If done so, set
+ // the other to "none", it is part of an occupied situation and should not be followed.
+ inline void process_uu()
+ {
+ for (typename boost::range_iterator<turn_vector_type>::type it =
+ boost::begin(m_turns); it != boost::end(m_turns); ++it)
+ {
+ if (it->both(detail::overlay::operation_union)
+ && (it->operations[0].include_in_occupation_map
+ || it->operations[1].include_in_occupation_map))
+ {
+ bool set_to_none = false;
+
+ // Avoid both turns of a u/u turn to be included.
+ if (! it->operations[0].include_in_occupation_map)
+ {
+ it->operations[0].operation = detail::overlay::operation_none;
+ set_to_none = true;
+ }
+ if (! it->operations[1].include_in_occupation_map)
+ {
+ it->operations[1].operation = detail::overlay::operation_none;
+ set_to_none = true;
+ }
+ if (set_to_none)
+ {
+ std::cout << "-";
+ }
+#if defined(BOOST_GEOMETRY_COUNT_DOUBLE_UU)
+ else
+ {
+ it->count_on_uu++;
+ }
+#endif
+#ifdef BOOST_GEOMETRY_DEBUG_BUFFER_OCCUPATION
+ //std::cout << "Keep " << *sit
+ // << " "<< si(m_turns[*sit].operations[0].seg_id)
+ // << " "<< si(m_turns[*sit].operations[1].seg_id)
+ // << " " << m_turns[*sit].operations[0].piece_index
+ // << "/" << m_turns[*sit].operations[1].piece_index
+ // << " " << method_char(m_turns[*sit].method)
+ // << " " << operation_char(m_turns[*sit].operations[0].operation)
+ // << "/" << operation_char(m_turns[*sit].operations[1].operation)
+ //<< std::endl;
+#endif
+
+ }
+ }
+ }
+
#define BOOST_GEOMETRY_DEBUG_BUFFER_SITUATION_MAP
#ifdef BOOST_GEOMETRY_DEBUG_BUFFER_SITUATION_MAP
inline int get_side(point_type const& point, Ring const& ring, int segment_index)
@@ -833,9 +760,9 @@
struct clustered_info
{
- std::vector<cluster_info> intersecting_segments;
- std::set<segment_identifier> intersecting_ids;
int piece_index;
+ std::set<segment_identifier> intersecting_ids;
+ std::vector<cluster_info> intersecting_segments;
};
#ifdef OLD
@@ -846,7 +773,7 @@
};
#endif
- inline bool add_mutual_intersection(clustered_info const& cluster, segment_identifier const& seg_id)
+ static inline bool add_mutual_intersection(clustered_info const& cluster, segment_identifier const& seg_id)
{
bool result = false;
//if (cluster.intersecting_ids.count(seg_id) > 0)
@@ -854,14 +781,52 @@
{
if (it->operation.seg_id == seg_id)
{
- //add_angles(it->turn_index);
- //add_angles(it->turn_index, it->point, it->operation);
result = true;
}
}
return result;
}
+ inline bool mutually_interact(cluster_info const& a, cluster_info const& b, clustered_info const& other) const
+ {
+ // Either these two segments intersect, or they are perfectly collinear.
+ // First check the intersection:
+ if (add_mutual_intersection(other, b.operation.seg_id))
+ {
+ std::cout << "#";
+ return true;
+ }
+
+ // Then the collinearity
+ if (get_side(a.operation.seg_id, b.operation.seg_id) == 0)
+ {
+ std::cout << "1";
+ return true;
+
+ }
+
+ if (get_side(a.operation.seg_id, b.operation.seg_id, 0) == 0)
+ {
+ std::cout << "0";
+ return true;
+ }
+
+ if (geometry::equals(a.point, b.point))
+ {
+ std::cout << "=";
+ return true;
+ }
+
+ relaxed_less<point_type> comparator;
+ if (comparator.equals(a.point, b.point))
+ {
+ std::cout << "*";
+ return true;
+ }
+
+ return false;
+ }
+
inline void add_mutual_intersections(clustered_info const& cluster, std::map<segment_identifier, clustered_info> const& map)
{
for(auto it1 = cluster.intersecting_segments.begin(); it1 != cluster.intersecting_segments.end(); it1++)
@@ -874,41 +839,11 @@
if (! m_occupation_map.contains_turn_index(it1->turn_index)
|| ! m_occupation_map.contains_turn_index(it2->turn_index))
{
- // Either these two segments intersect, or they are perfectly collinear.
- // First check the intersection:
- if (add_mutual_intersection(other_cluster_it->second, it2->operation.seg_id))
- {
- ////std::cout << "#";
- add_angles(it1->turn_index);
- add_angles(it2->turn_index);
- }
- else
- {
- // Then the collinearity
- int const code = get_side(it1->operation.seg_id, it2->operation.seg_id);
- if (code == 0)
- {
- ////std::cout << "1";
- add_angles(it1->turn_index);
- add_angles(it2->turn_index);
- }
- else
- {
- int const code = get_side(it1->operation.seg_id, it2->operation.seg_id, 0);
- if (code == 0)
- {
- ////std::cout << "0";
- add_angles(it1->turn_index);
- add_angles(it2->turn_index);
- }
- else if (geometry::equals(it1->point, it2->point))
- {
- ////std::cout << "*";
- add_angles(it1->turn_index);
- add_angles(it2->turn_index);
- }
- }
- }
+ if (mutually_interact(*it1, *it2, other_cluster_it->second))
+ {
+ add_angles(it1->turn_index);
+ add_angles(it2->turn_index);
+ }
}
}
}
@@ -928,23 +863,19 @@
{
buffer_turn_info<point_type> const& turn = *it;
- // if (! turn.both(detail::overlay::operation_union))
- {
-
- // Take care with all the indices
- map[turn.operations[0].seg_id].piece_index = turn.operations[0].piece_index;
- map[turn.operations[0].seg_id].intersecting_segments.push_back(cluster_info(index, turn.point, turn.operations[1]));
- map[turn.operations[0].seg_id].intersecting_ids.insert(turn.operations[1].seg_id);
-
- map[turn.operations[1].seg_id].piece_index = turn.operations[1].piece_index;
- map[turn.operations[1].seg_id].intersecting_segments.push_back(cluster_info(index, turn.point, turn.operations[0]));
- map[turn.operations[1].seg_id].intersecting_ids.insert(turn.operations[0].seg_id);
- }
+ // Take care with all the indices
+ map[turn.operations[0].seg_id].piece_index = turn.operations[0].piece_index;
+ map[turn.operations[0].seg_id].intersecting_segments.push_back(cluster_info(index, turn.point, turn.operations[1]));
+ map[turn.operations[0].seg_id].intersecting_ids.insert(turn.operations[1].seg_id);
+
+ map[turn.operations[1].seg_id].piece_index = turn.operations[1].piece_index;
+ map[turn.operations[1].seg_id].intersecting_segments.push_back(cluster_info(index, turn.point, turn.operations[0]));
+ map[turn.operations[1].seg_id].intersecting_ids.insert(turn.operations[0].seg_id);
}
// Pass 2:
// Verify all segments crossing with more than one segment, and if they intersect each other,
- // at that pair
+ // add that pair
for (typename map_type::const_iterator mit = map.begin(); mit != map.end(); ++mit)
{
if (mit->second.intersecting_segments.size() > 1)
@@ -1069,6 +1000,53 @@
}
}
+ template <typename Turns>
+ static inline void split_uu_turns(Turns& turns)
+ {
+ Turns added;
+
+ for (typename boost::range_iterator<Turns>::type it = boost::begin(turns);
+ it != boost::end(turns); ++it)
+ {
+ if (it->both(detail::overlay::operation_union))
+ {
+ //std::cout << "U";
+
+ typename boost::range_value<Turns>::type turn = *it; // copy by value
+ // std::swap(turn.operations[0], turn.operations[1]);
+ turn.operations[0].operation = detail::overlay::operation_continue;
+ turn.operations[1].operation = detail::overlay::operation_continue;
+ it->operations[1].operation = detail::overlay::operation_continue;
+ it->operations[0].operation = detail::overlay::operation_continue;
+ added.push_back(turn);
+ }
+ }
+
+ for (typename boost::range_iterator<Turns>::type it = boost::begin(added);
+ it != boost::end(added); ++it)
+ {
+ turns.push_back(*it);
+ }
+
+ if (added.size() > 0)
+ {
+ for (typename boost::range_iterator<Turns>::type it = boost::begin(turns);
+ it != boost::end(turns); ++it)
+ {
+ std::cout << "Turn"
+ << " "<< si(it->operations[0].seg_id)
+ << " "<< si(it->operations[1].seg_id)
+ << " " << it->operations[0].piece_index
+ << "/" << it->operations[1].piece_index
+ << " " << method_char(it->method)
+ << " " << operation_char(it->operations[0].operation)
+ << "/" << operation_char(it->operations[1].operation)
+ << std::endl;
+ }
+ }
+
+ }
+
template <typename Geometry>
inline void get_turns(Geometry const& input_geometry, int factor)
{
@@ -1090,8 +1068,30 @@
}
}
+ //discard_uu_turns();
+ for (typename boost::range_iterator<turn_vector_type>::type it =
+ boost::begin(m_turns); it != boost::end(m_turns); ++it)
+ {
+ //if (it->both(detail::overlay::operation_union))
+ //{
+ // std::cout << "double UU" << std::endl;
+ //}
+ //std::cout << std::setprecision(16) << geometry::wkt(it->point)
+ // << " " << it->operations[0].piece_index << "/" << it->operations[1].piece_index
+ // << " " << si(it->operations[0].seg_id) << "/" << si(it->operations[1].seg_id)
+ // << " " << method_char(it->method)
+ // << ":" << operation_char(it->operations[0].operation)
+ // << "/" << operation_char(it->operations[1].operation)
+ // << std::endl;
+ }
+
+ //split_uu_turns(m_turns);
+
+
+ fill_segment_map();
get_occupation();
classify_occupied_locations();
+ process_uu();
classify_turns();
classify_inside();
@@ -1249,6 +1249,17 @@
}
+ // inline void discard_uu_turns()
+ // {
+ // m_turns.erase
+ //(
+ // std::remove_if(boost::begin(m_turns), boost::end(m_turns),
+ // uu_turn()),
+ // boost::end(m_turns)
+ //);
+
+ // }
+
inline void traverse()
{
typedef detail::overlay::traverse
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk