Subject: [Boost-commit] svn:boost r83189 - in trunk/boost/geometry/extensions/algorithms: . buffer
From: barend.gehrels_at_[hidden]
Date: 2013-02-27 12:25:09
Author: barendgehrels
Date: 2013-02-27 12:25:07 EST (Wed, 27 Feb 2013)
New Revision: 83189
URL: http://svn.boost.org/trac/boost/changeset/83189
Log:
[geometry] updated offset/buffer w.r.t. changes in library
Text files modified:
trunk/boost/geometry/extensions/algorithms/buffer/buffer_inserter.hpp | 2
trunk/boost/geometry/extensions/algorithms/buffer/buffered_piece_collection.hpp | 707 ++++++++++++++++++++-------------------
trunk/boost/geometry/extensions/algorithms/buffer/buffered_ring.hpp | 17
trunk/boost/geometry/extensions/algorithms/offset.hpp | 8
4 files changed, 379 insertions(+), 355 deletions(-)
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 2013-02-27 12:25:07 EST (Wed, 27 Feb 2013)
@@ -383,7 +383,7 @@
//collection.map_traverse(mapper);
#endif
- collection.assign<GeometryOutput>(out);
+ collection.template assign<GeometryOutput>(out);
}
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 2013-02-27 12:25:07 EST (Wed, 27 Feb 2013)
@@ -33,6 +33,7 @@
#include <boost/geometry/algorithms/detail/overlay/calculate_distance_policy.hpp>
#include <boost/geometry/algorithms/detail/overlay/enrich_intersection_points.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/traversal_info.hpp>
#include <boost/geometry/algorithms/detail/overlay/traverse.hpp>
@@ -163,19 +164,19 @@
// These both form a complete clockwise ring for each piece (with one dupped point)
- // 1: half, part of offsetted_rings
+ // 1: half, part of offsetted_rings
segment_identifier first_seg_id;
int last_segment_index; // no segment-identifier - it is always the same
- // 2: half, not part (will be indexed in one vector too)
+ // 2: half, not part (will be indexed in one vector too)
std::vector<point_type> helper_segments; // 3 points for segment, 2 points for join - 0 points for flat-end
};
typedef typename strategy::side::services::default_strategy
- <
- typename cs_tag<point_type>::type
- >::type side_strategy;
+ <
+ typename cs_tag<point_type>::type
+ >::type side_strategy;
typedef std::vector<piece> piece_vector;
piece_vector m_pieces;
@@ -195,29 +196,29 @@
turn_vector_type m_turns;
- // To check clustered locations we keep track of segments being opposite somewhere
- std::set<segment_identifier> m_in_opposite_segments;
+ // To check clustered locations we keep track of segments being opposite somewhere
+ std::set<segment_identifier> m_in_opposite_segments;
- struct buffer_occupation_info : public occupation_info<angle_info<point_type, coordinate_type> >
- {
- std::set<segment_identifier> seg_ids;
- std::set<int> turn_indices;
- };
+ struct buffer_occupation_info : public occupation_info<angle_info<point_type, coordinate_type> >
+ {
+ std::set<segment_identifier> seg_ids;
+ std::set<int> turn_indices;
+ };
typedef occupation_map<point_type, buffer_occupation_info> occupation_map_type;
occupation_map_type m_occupation_map;
- struct redundant_turn
- {
- inline bool operator()(buffer_turn_info<point_type> const& turn) const
- {
- // Erase discarded turns (location not OK) and the turns
- // only used to detect oppositeness.
- return turn.location != location_ok
- || turn.opposite();
- }
- };
+ struct redundant_turn
+ {
+ inline bool operator()(buffer_turn_info<point_type> const& turn) const
+ {
+ // Erase discarded turns (location not OK) and the turns
+ // only used to detect oppositeness.
+ return turn.location != location_ok
+ || turn.opposite();
+ }
+ };
inline bool is_neighbor(piece const& piece1, piece const& piece2) const
@@ -247,43 +248,43 @@
inline void move_to_next_point(Range const& range, Iterator& next) const
{
++next;
- if (next == boost::end(range))
- {
- next = boost::begin(range) + 1;
- }
+ if (next == boost::end(range))
+ {
+ next = boost::begin(range) + 1;
+ }
}
template <typename Range, typename Iterator>
inline Iterator next_point(Range const& range, Iterator it) const
{
Iterator result = it;
- move_to_next_point(range, result);
- while(geometry::equals(*it, *result))
- {
- move_to_next_point(range, result);
- }
- return result;
+ move_to_next_point(range, result);
+ while(geometry::equals(*it, *result))
+ {
+ move_to_next_point(range, result);
+ }
+ return result;
}
inline void calculate_turns(piece const& piece1, piece const& piece2)
{
typedef typename boost::range_iterator<buffered_ring<Ring> const>::type iterator;
- segment_identifier seg_id1 = piece1.first_seg_id;
- segment_identifier seg_id2 = piece2.first_seg_id;
+ segment_identifier seg_id1 = piece1.first_seg_id;
+ segment_identifier seg_id2 = piece2.first_seg_id;
+
+ if (seg_id1.segment_index < 0 || seg_id2.segment_index < 0)
+ {
+ return;
+ }
- if (seg_id1.segment_index < 0 || seg_id2.segment_index < 0)
- {
- return;
- }
-
- buffered_ring<Ring> const& ring1 = offsetted_rings[seg_id1.multi_index];
- iterator it1_first = boost::begin(ring1) + seg_id1.segment_index;
- iterator it1_last = boost::begin(ring1) + piece1.last_segment_index;
-
- buffered_ring<Ring> const& ring2 = offsetted_rings[seg_id2.multi_index];
- iterator it2_first = boost::begin(ring2) + seg_id2.segment_index;
- iterator it2_last = boost::begin(ring2) + piece2.last_segment_index;
+ buffered_ring<Ring> const& ring1 = offsetted_rings[seg_id1.multi_index];
+ iterator it1_first = boost::begin(ring1) + seg_id1.segment_index;
+ iterator it1_last = boost::begin(ring1) + piece1.last_segment_index;
+
+ buffered_ring<Ring> const& ring2 = offsetted_rings[seg_id2.multi_index];
+ iterator it2_first = boost::begin(ring2) + seg_id2.segment_index;
+ iterator it2_last = boost::begin(ring2) + piece2.last_segment_index;
buffer_turn_info<point_type> the_model;
the_model.operations[0].piece_index = piece1.index;
@@ -297,7 +298,7 @@
the_model.operations[1].piece_index = piece2.index;
the_model.operations[1].seg_id = piece2.first_seg_id;
- iterator next1 = next_point(ring1, it1);
+ iterator next1 = next_point(ring1, it1);
iterator it2 = it2_first;
for (iterator prev2 = it2++;
@@ -308,12 +309,7 @@
the_model.operations[0].other_id = the_model.operations[1].seg_id;
the_model.operations[1].other_id = the_model.operations[0].seg_id;
- iterator next2 = next_point(ring2, it2);
-
- if (piece1.index == 5 && piece2.index == 22)
- {
- int kkk = 0;
- }
+ iterator next2 = next_point(ring2, it2);
turn_policy::apply(*prev1, *it1, *next1,
*prev2, *it2, *next2,
@@ -322,27 +318,27 @@
}
}
- inline void fill_opposite_segments()
- {
+ inline void fill_opposite_segments()
+ {
for (typename boost::range_iterator<turn_vector_type const>::type it =
boost::begin(m_turns); it != boost::end(m_turns); ++it)
{
- if (it->is_opposite)
- {
- m_in_opposite_segments.insert(it->operations[0].seg_id);
- m_in_opposite_segments.insert(it->operations[1].seg_id);
+ if (it->is_opposite)
+ {
+ m_in_opposite_segments.insert(it->operations[0].seg_id);
+ m_in_opposite_segments.insert(it->operations[1].seg_id);
//std::cout << " " << it->operations[0].seg_id.segment_index;
- }
- }
- }
+ }
+ }
+ }
- inline segment_relation_code get_segment_relation(point_type const& point,
+ inline segment_relation_code get_segment_relation(point_type const& point,
segment_identifier const& seg_id) const
- {
- typedef typename boost::range_iterator<std::vector<point_type> const>::type iterator_type;
- iterator_type it = boost::begin(offsetted_rings[seg_id.multi_index]) + seg_id.segment_index;
- iterator_type prev = it++;
- int side = side_strategy::apply(point, *prev, *it);
+ {
+ typedef typename boost::range_iterator<std::vector<point_type> const>::type iterator_type;
+ iterator_type it = boost::begin(offsetted_rings[seg_id.multi_index]) + seg_id.segment_index;
+ iterator_type prev = it++;
+ int side = side_strategy::apply(point, *prev, *it);
if (side == 0)
{
if (geometry::equals(point, *prev))
@@ -359,34 +355,34 @@
}
}
return segment_relation_disjoint;
- }
+ }
inline void add_angles(int turn_index, int operation_index, point_type const& point, buffer_turn_operation<point_type> const& operation)
{
point_type mapped_point;
buffer_occupation_info& info = m_occupation_map.find_or_insert(point, mapped_point);
- info.turn_indices.insert(turn_index);
+ info.turn_indices.insert(turn_index);
info.seg_ids.insert(operation.seg_id);
add_incoming_and_outgoing_angles(mapped_point, point,
- offsetted_rings[operation.seg_id.multi_index],
+ offsetted_rings[operation.seg_id.multi_index],
turn_index, operation_index,
- operation.seg_id,
- info);
+ operation.seg_id,
+ info);
}
inline void add_angles(int turn_index)
{
- if (! m_occupation_map.contains_turn_index(turn_index))
- {
- m_occupation_map.insert_turn_index(turn_index);
+ if (! m_occupation_map.contains_turn_index(turn_index))
+ {
+ m_occupation_map.insert_turn_index(turn_index);
- buffer_turn_info<point_type> const& turn = m_turns[turn_index];
+ buffer_turn_info<point_type> const& turn = m_turns[turn_index];
//std::cout << "Adding point " << turn_index << " " << geometry::wkt(turn.point) << std::endl;
- add_angles(turn_index, 0, turn.point, turn.operations[0]);
- add_angles(turn_index, 1, turn.point, turn.operations[1]);
- }
+ add_angles(turn_index, 0, turn.point, turn.operations[0]);
+ add_angles(turn_index, 1, turn.point, turn.operations[1]);
+ }
}
@@ -404,53 +400,45 @@
return;
}
- int flat_ends_involved = 0;
+ int flat_ends_involved = 0;
for (int i = 0; i < int(boost::size(turn.operations)); i++)
{
- // Don't check any turn against a piece of which is itself the result
- if (turn.operations[i].piece_index == pc.index)
- {
- return;
- }
+ // Don't check any turn against a piece of which is itself the result
+ if (turn.operations[i].piece_index == pc.index)
+ {
+ return;
+ }
piece const& piece_from_intersection = m_pieces[turn.operations[i].piece_index];
if (piece_from_intersection.type == buffered_flat_end)
- {
- flat_ends_involved++;
- }
- }
+ {
+ flat_ends_involved++;
+ }
+ }
int side_helper = side_on_convex_range<side_strategy>(turn.point, pc.helper_segments);
if (side_helper == 1)
{
- // Left or outside
+ // Left or outside
return;
}
- segment_identifier seg_id = pc.first_seg_id;
- if (seg_id.segment_index < 0)
- {
- // Should not occur
- std::cout << "Warning: negative segment_index" << std::endl;
- return;
- }
-
- if (turn.operations[0].piece_index == 9 && turn.operations[1].piece_index == 35
- && (pc.index == 3 || pc.index == 9 || pc.index == 35))
+ segment_identifier seg_id = pc.first_seg_id;
+ if (seg_id.segment_index < 0)
{
- double epsilon = std::numeric_limits<double>::epsilon();
- int kkk = 0;
+ // Should not occur
+ std::cout << "Warning: negative segment_index" << std::endl;
+ return;
}
+ segment_identifier on_segment_seg_id;
- segment_identifier on_segment_seg_id;
-
- buffered_ring<Ring> const& ring = offsetted_rings[seg_id.multi_index];
+ buffered_ring<Ring> const& ring = offsetted_rings[seg_id.multi_index];
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);
+ boost::begin(ring) + seg_id.segment_index,
+ boost::begin(ring) + pc.last_segment_index,
+ seg_id, on_segment_seg_id);
if (side_offsetted == 1)
{
return;
@@ -463,30 +451,30 @@
}
if (side_offsetted == 0)
{
- turn.count_on_offsetted++;
+ turn.count_on_offsetted++;
}
if (side_helper == 0)
{
- if (geometry::equals(turn.point, pc.helper_segments.back())
- || geometry::equals(turn.point, pc.helper_segments.front()))
+ if (geometry::equals(turn.point, pc.helper_segments.back())
+ || geometry::equals(turn.point, pc.helper_segments.front()))
{
turn.count_on_corner++;
}
else
{
- if (flat_ends_involved == 0)
- {
- turn.count_on_helper++;
+ if (flat_ends_involved == 0)
+ {
+ turn.count_on_helper++;
#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
- std::ostringstream out;
- out << "HLP " << pc.index;
- turn.debug_string += out.str();
+ std::ostringstream out;
+ out << "HLP " << pc.index;
+ turn.debug_string += out.str();
#endif
- }
- else
- {
- turn.count_on_corner++;
- }
+ }
+ else
+ {
+ turn.count_on_corner++;
+ }
}
}
}
@@ -506,7 +494,7 @@
<< " " << method_char(m_turns[index].method)
<< " " << operation_char(m_turns[index].operations[0].operation)
<< "/" << operation_char(m_turns[index].operations[1].operation)
- << std::endl;
+ << std::endl;
}
#endif
}
@@ -532,80 +520,80 @@
// 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,
+ inline void process_left_turns(buffer_occupation_info const& info,
std::set<int> const& keep_indices)
- {
- for (std::set<int>::const_iterator sit1 = info.turn_indices.begin();
- sit1 != info.turn_indices.end();
- ++sit1)
- {
- if (keep_indices.count(*sit1) == 0)
- {
- m_turns[*sit1].count_on_multi++;
+ {
+ for (std::set<int>::const_iterator sit1 = info.turn_indices.begin();
+ sit1 != info.turn_indices.end();
+ ++sit1)
+ {
+ if (keep_indices.count(*sit1) == 0)
+ {
+ m_turns[*sit1].count_on_multi++;
}
else
{
- for (std::set<int>::const_iterator sit2 = info.turn_indices.begin();
- sit2 != info.turn_indices.end();
- ++sit2)
- {
- if (sit2 != sit1)
- {
- m_turns[*sit1].piece_indices_to_skip.insert(m_turns[*sit2].operations[0].piece_index);
- m_turns[*sit1].piece_indices_to_skip.insert(m_turns[*sit2].operations[1].piece_index);
- }
- }
+ for (std::set<int>::const_iterator sit2 = info.turn_indices.begin();
+ sit2 != info.turn_indices.end();
+ ++sit2)
+ {
+ if (sit2 != sit1)
+ {
+ m_turns[*sit1].piece_indices_to_skip.insert(m_turns[*sit2].operations[0].piece_index);
+ m_turns[*sit1].piece_indices_to_skip.insert(m_turns[*sit2].operations[1].piece_index);
+ }
+ }
}
}
}
- inline void get_left_turns(buffer_occupation_info& info)
- {
+ 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);
+ info.get_left_turns(m_turns, m_turn_indices_per_segment_pair, keep_indices);
- if (! keep_indices.empty())
- {
+ 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)
+ {
+ std::set<int> piece_indices;
- inline int piece_count(buffer_occupation_info const& info)
- {
- std::set<int> piece_indices;
-
- for (std::set<int>::const_iterator sit = info.turn_indices.begin();
- sit != info.turn_indices.end();
- ++sit)
- {
- piece_indices.insert(m_turns[*sit].operations[0].piece_index);
- piece_indices.insert(m_turns[*sit].operations[1].piece_index);
- }
- return piece_indices.size();
- }
+ for (std::set<int>::const_iterator sit = info.turn_indices.begin();
+ sit != info.turn_indices.end();
+ ++sit)
+ {
+ piece_indices.insert(m_turns[*sit].operations[0].piece_index);
+ piece_indices.insert(m_turns[*sit].operations[1].piece_index);
+ }
+ return piece_indices.size();
+ }
- inline void classify_occupied_locations()
- {
+ inline void classify_occupied_locations()
+ {
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)
+ boost::begin(m_occupation_map.map);
+ it != boost::end(m_occupation_map.map); ++it)
{
- buffer_occupation_info& info = it->second;
+ buffer_occupation_info& info = it->second;
#ifdef BOOST_GEOMETRY_DEBUG_BUFFER_OCCUPATION
std::cout << std::endl << "left turns: " << piece_count(info) << " "
//<< std::setprecision(20)
<< geometry::wkt(it->first) << std::endl;
#endif
- if (piece_count(info) > 2)
- {
- if (info.occupied())
- {
+ if (piece_count(info) > 2)
+ {
+ if (info.occupied())
+ {
#ifdef BOOST_GEOMETRY_DEBUG_BUFFER_OCCUPATION
std::cout << "-> occupied" << std::endl;
@@ -613,21 +601,21 @@
//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)
- {
- m_turns[*sit].count_on_occupied++;
- }
- }
- else
- {
- get_left_turns(info);
- }
- //std::cout << geometry::wkt(it->first) << " " << int(info.occupied()) << std::endl;
- }
+ for (std::set<int>::const_iterator sit = info.turn_indices.begin();
+ sit != info.turn_indices.end();
+ ++sit)
+ {
+ m_turns[*sit].count_on_occupied++;
+ }
+ }
+ else
+ {
+ get_left_turns(info);
+ }
+ //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
@@ -636,7 +624,7 @@
{
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))
@@ -673,7 +661,7 @@
// << " " << method_char(m_turns[*sit].method)
// << " " << operation_char(m_turns[*sit].operations[0].operation)
// << "/" << operation_char(m_turns[*sit].operations[1].operation)
- //<< std::endl;
+ //<< std::endl;
#endif
}
@@ -682,13 +670,13 @@
#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)
- {
+ inline int get_side(point_type const& point, Ring const& ring, int segment_index)
+ {
typedef typename boost::range_iterator<Ring const> iterator_type;
- iterator_type it = boost::begin(ring) + segment_index;
- iterator_type prev = it++;
- return side_strategy::apply(point, *prev, *it);
- }
+ iterator_type it = boost::begin(ring) + segment_index;
+ iterator_type prev = it++;
+ return side_strategy::apply(point, *prev, *it);
+ }
#endif
template <typename Iterator>
@@ -698,21 +686,21 @@
}
- inline int get_side(segment_identifier const& seg_id1, segment_identifier const& seg_id2, int which = 1) const
- {
+ inline int get_side(segment_identifier const& seg_id1, segment_identifier const& seg_id2, int which = 1) const
+ {
typedef typename boost::range_iterator<Ring const>::type iterator_type;
Ring const& ring1 = offsetted_rings[seg_id1.multi_index];
Ring const& ring2 = offsetted_rings[seg_id2.multi_index];
- iterator_type it1 = boost::begin(ring1) + seg_id1.segment_index;
- iterator_type it2 = boost::begin(ring2) + seg_id2.segment_index;
+ iterator_type it1 = boost::begin(ring1) + seg_id1.segment_index;
+ iterator_type it2 = boost::begin(ring2) + seg_id2.segment_index;
- iterator_type prev1 = it1++;
- iterator_type prev2 = it2++;
+ iterator_type prev1 = it1++;
+ iterator_type prev2 = it2++;
- int code1 = side_strategy::apply(select_for_side(prev1, it1, which), *prev2, *it2);
- int code2 = side_strategy::apply(select_for_side(prev2, it2, which), *prev1, *it1);
+ int code1 = side_strategy::apply(select_for_side(prev1, it1, which), *prev2, *it2);
+ int code2 = side_strategy::apply(select_for_side(prev2, it2, which), *prev1, *it1);
if (code1 == 1 && code2 == -1) return 1;
if (code1 == -1 && code2 == 1) return -1;
@@ -724,8 +712,8 @@
// // Check if the other side gives some more info
// // (I've never seen this is the case though it might be so, if they are much longer.
- //int code1f = side_strategy::apply(*prev1, *prev2, *it2);
- //int code2f = side_strategy::apply(*prev2, *prev1, *it1);
+ //int code1f = side_strategy::apply(*prev1, *prev2, *it2);
+ //int code2f = side_strategy::apply(*prev2, *prev1, *it1);
// if (code1f != 0 || code2f != 0)
// {
@@ -739,38 +727,38 @@
//std::cout << "Collinear: " << code1 << " " << code2 << std::endl;
#endif
return 0;
- }
+ }
- inline void debug_segment(segment_identifier id)
- {
+ inline void debug_segment(segment_identifier id)
+ {
typedef typename boost::range_iterator<buffered_ring<Ring> const>::type iterator;
buffered_ring<Ring> const& ring = offsetted_rings[id.multi_index];
- iterator it = boost::begin(ring) + id.segment_index;
- iterator prev = it++;
- geometry::model::referring_segment<point_type const&> segment(*prev, *it);
+ iterator it = boost::begin(ring) + id.segment_index;
+ iterator prev = it++;
+ geometry::model::referring_segment<point_type const&> segment(*prev, *it);
//std::cout << geometry::wkt(*prev) << " " << geometry::wkt(*it) << std::endl;
- }
+ }
- struct cluster_info
- {
- inline cluster_info(int i, point_type p, buffer_turn_operation<point_type> op)
- : turn_index(i)
- , point(p)
- , operation(op)
- {}
-
- inline cluster_info()
- : turn_index(-1)
- {}
-
- int turn_index;
- point_type point;
- buffer_turn_operation<point_type> operation;
- };
+ struct cluster_info
+ {
+ inline cluster_info(int i, point_type p, buffer_turn_operation<point_type> op)
+ : turn_index(i)
+ , point(p)
+ , operation(op)
+ {}
+
+ inline cluster_info()
+ : turn_index(-1)
+ {}
+
+ int turn_index;
+ point_type point;
+ buffer_turn_operation<point_type> operation;
+ };
struct clustered_info
{
@@ -787,139 +775,139 @@
};
#endif
- static inline bool add_mutual_intersection(clustered_info const& cluster, segment_identifier const& seg_id)
- {
- bool result = false;
+ 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)
typedef typename boost::range_iterator<std::vector<cluster_info> const>::type iterator_type;
- for(iterator_type it = cluster.intersecting_segments.begin(); it != cluster.intersecting_segments.end(); it++)
- {
- if (it->operation.seg_id == seg_id)
- {
- result = true;
- }
- }
- return result;
- }
+ for(iterator_type it = cluster.intersecting_segments.begin(); it != cluster.intersecting_segments.end(); it++)
+ {
+ if (it->operation.seg_id == seg_id)
+ {
+ 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 << "#";
+ // 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";
+ // 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";
+ 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 << "=";
+ std::cout << "=";
return true;
}
relaxed_less<point_type> comparator;
if (comparator.equals(a.point, b.point))
- {
- std::cout << "*";
+ {
+ std::cout << "*";
return true;
- }
+ }
return false;
}
- inline void add_mutual_intersections(clustered_info const& cluster, std::map<segment_identifier, clustered_info> const& map)
- {
+ inline void add_mutual_intersections(clustered_info const& cluster, std::map<segment_identifier, clustered_info> const& map)
+ {
typedef std::map<segment_identifier, clustered_info> map_type;
typedef typename boost::range_iterator<map_type const>::type map_it;
typedef typename boost::range_iterator<std::vector<cluster_info> const>::type cluster_it;
for(cluster_it it1 = cluster.intersecting_segments.begin(); it1 != cluster.intersecting_segments.end(); it1++)
- {
- map_it const& other_cluster_it = map.find(it1->operation.seg_id);
- if (other_cluster_it != map.end())
- {
- for(cluster_it it2 = it1 + 1; it2 != cluster.intersecting_segments.end(); it2++)
- {
- if (! m_occupation_map.contains_turn_index(it1->turn_index)
- || ! m_occupation_map.contains_turn_index(it2->turn_index))
- {
+ {
+ map_it const& other_cluster_it = map.find(it1->operation.seg_id);
+ if (other_cluster_it != map.end())
+ {
+ for(cluster_it it2 = it1 + 1; it2 != cluster.intersecting_segments.end(); it2++)
+ {
+ if (! m_occupation_map.contains_turn_index(it1->turn_index)
+ || ! m_occupation_map.contains_turn_index(it2->turn_index))
+ {
if (mutually_interact(*it1, *it2, other_cluster_it->second))
{
- add_angles(it1->turn_index);
- add_angles(it2->turn_index);
+ add_angles(it1->turn_index);
+ add_angles(it2->turn_index);
}
- }
- }
- }
- }
- }
+ }
+ }
+ }
+ }
+ }
inline void add_multi_intersections_to_occupation_map()
- {
+ {
// Pass 1: create map of all segments
- typedef std::map<segment_identifier, clustered_info> map_type;
- map_type map;
+ typedef std::map<segment_identifier, clustered_info> map_type;
+ map_type map;
- int index = 0;
+ int index = 0;
for (typename boost::range_iterator<turn_vector_type>::type it =
boost::begin(m_turns); it != boost::end(m_turns); ++it, ++index)
{
- buffer_turn_info<point_type> const& turn = *it;
+ buffer_turn_info<point_type> const& turn = *it;
- // 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,
// add that pair
- for (typename map_type::const_iterator mit = map.begin(); mit != map.end(); ++mit)
- {
- if (mit->second.intersecting_segments.size() > 1)
- {
- add_mutual_intersections(mit->second, map);
- }
- }
+ for (typename map_type::const_iterator mit = map.begin(); mit != map.end(); ++mit)
+ {
+ if (mit->second.intersecting_segments.size() > 1)
+ {
+ add_mutual_intersections(mit->second, map);
+ }
+ }
}
- inline void get_occupation()
+ inline void get_occupation()
{
- fill_opposite_segments();
+ fill_opposite_segments();
// Pass 1: fill all segments part of opposite segments
int index = 0;
for (typename boost::range_iterator<turn_vector_type>::type it =
boost::begin(m_turns); it != boost::end(m_turns); ++it, ++index)
{
- buffer_turn_info<point_type>& turn = *it;
+ buffer_turn_info<point_type>& turn = *it;
//std::cout << "Referring to point " << geometry::wkt(turn.point) << std::endl;
- if (m_in_opposite_segments.count(turn.operations[0].seg_id) > 0
- || m_in_opposite_segments.count(turn.operations[1].seg_id) > 0)
- {
- add_angles(index);
- }
- }
+ if (m_in_opposite_segments.count(turn.operations[0].seg_id) > 0
+ || m_in_opposite_segments.count(turn.operations[1].seg_id) > 0)
+ {
+ add_angles(index);
+ }
+ }
// Pass 2: add multi intersection
add_multi_intersections_to_occupation_map();
@@ -929,18 +917,18 @@
for (typename boost::range_iterator<turn_vector_type>::type it =
boost::begin(m_turns); it != boost::end(m_turns); ++it, ++index)
{
- buffer_turn_info<point_type>& turn = *it;
- if (m_in_opposite_segments.count(turn.operations[0].seg_id) == 0
- && m_in_opposite_segments.count(turn.operations[1].seg_id) == 0)
- {
+ buffer_turn_info<point_type>& turn = *it;
+ if (m_in_opposite_segments.count(turn.operations[0].seg_id) == 0
+ && m_in_opposite_segments.count(turn.operations[1].seg_id) == 0)
+ {
// See if it is in the map
if (m_occupation_map.contains(turn.point))
{
- add_angles(index);
+ add_angles(index);
}
- }
- }
- }
+ }
+ }
+ }
inline void classify_turns()
{
@@ -950,7 +938,7 @@
// TODO: in partition.
for (typename boost::range_iterator<turn_vector_type>::type it =
boost::begin(m_turns); it != boost::end(m_turns); ++it)
- {
+ {
//if (it->count_on_occupied == 0)
{
typename std::vector<piece>::const_iterator pit;
@@ -970,13 +958,13 @@
return turn.count_within > 0
|| turn.count_on_multi > 0
|| turn.count_on_helper > 0
- || turn.count_on_occupied > 0
+ || turn.count_on_occupied > 0
;
}
inline void classify_inside()
{
- // Set results:
+ // Set results:
for (typename boost::range_iterator<turn_vector_type>::type it =
boost::begin(m_turns); it != boost::end(m_turns); ++it)
{
@@ -1005,16 +993,16 @@
boost::begin(m_turns); it != boost::end(m_turns); ++it)
{
if (it->location == location_ok)
- {
- int code = check_original
+ {
+ int code = check_original
<
typename geometry::tag<Geometry>::type
>::apply(it->point, input_geometry);
- if (code * factor == 1)
- {
- it->location = inside_original;
- }
- }
+ if (code * factor == 1)
+ {
+ it->location = inside_original;
+ }
+ }
}
}
@@ -1025,7 +1013,7 @@
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";
@@ -1042,7 +1030,7 @@
for (typename boost::range_iterator<Turns>::type it = boost::begin(added);
it != boost::end(added); ++it)
- {
+ {
turns.push_back(*it);
}
@@ -1050,7 +1038,7 @@
{
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)
@@ -1059,7 +1047,7 @@
<< " " << method_char(it->method)
<< " " << operation_char(it->operations[0].operation)
<< "/" << operation_char(it->operations[1].operation)
- << std::endl;
+ << std::endl;
}
}
@@ -1068,7 +1056,7 @@
template <typename Geometry>
inline void get_turns(Geometry const& input_geometry, int factor)
{
- // Now: quadratic
+ // Now: quadratic
// TODO use partition
for(typename piece_vector::const_iterator it1 = boost::begin(m_pieces);
@@ -1086,20 +1074,20 @@
}
}
- //discard_uu_turns();
+ //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)
+ //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)
+ // << " " << method_char(it->method)
+ // << ":" << operation_char(it->operations[0].operation)
+ // << "/" << operation_char(it->operations[1].operation)
// << std::endl;
}
@@ -1107,7 +1095,7 @@
fill_segment_map();
- get_occupation();
+ get_occupation();
classify_occupied_locations();
process_uu();
classify_turns();
@@ -1139,7 +1127,7 @@
current_segment_id.segment_index++;
offsetted_rings.back().push_back(p);
- return offsetted_rings.back().size();
+ return offsetted_rings.back().size();
}
inline piece& add_piece(piece_type type, bool decrease_by_one)
@@ -1160,7 +1148,7 @@
point_type const& b1, point_type const& b2)
{
bool const last_type_join = ! m_pieces.empty()
- && m_pieces.back().first_seg_id.multi_index == current_segment_id.multi_index
+ && m_pieces.back().first_seg_id.multi_index == current_segment_id.multi_index
&& m_pieces.back().type == buffered_join;
piece& pc = add_piece(type, last_type_join);
@@ -1186,7 +1174,7 @@
piece& pc = add_piece(type, true);
bool first = true;
- int last = offsetted_rings.back().size() + 1;
+ int last = offsetted_rings.back().size() + 1;
for (typename Range::const_iterator it = boost::begin(range);
it != boost::end(range);
++it)
@@ -1259,22 +1247,22 @@
inline void discard_turns()
{
m_turns.erase
- (
- std::remove_if(boost::begin(m_turns), boost::end(m_turns),
- redundant_turn()),
- boost::end(m_turns)
- );
+ (
+ std::remove_if(boost::begin(m_turns), boost::end(m_turns),
+ redundant_turn()),
+ boost::end(m_turns)
+ );
}
// 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)
- //);
+ //(
+ // std::remove_if(boost::begin(m_turns), boost::end(m_turns),
+ // uu_turn()),
+ // boost::end(m_turns)
+ //);
// }
@@ -1322,14 +1310,31 @@
it != boost::end(traversed_rings);
++it, ++index)
{
- ring_identifier id(2, index, -1);
- selected[id] = properties(*it, true);
+ ring_identifier id(2, index, -1);
+ selected[id] = properties(*it, true);
}
detail::overlay::assign_parents(offsetted_rings, traversed_rings, selected, false);
return detail::overlay::add_rings<GeometryOutput>(selected, offsetted_rings, traversed_rings, out);
}
+ template <typename GeometryOutput>
+ inline void assign_offsetted_rings(GeometryOutput& out)
+ {
+ typedef typename boost::range_iterator<buffered_ring<Ring> const>::type iterator;
+
+ for(typename buffered_ring_collection<buffered_ring<Ring> >::const_iterator it = boost::begin(offsetted_rings);
+ it != boost::end(offsetted_rings);
+ ++it)
+ {
+ for (iterator pit = boost::begin(*it); pit != boost::end(*it); ++pit)
+ {
+ out.push_back(*pit);
+ }
+ }
+ }
+
+
};
Modified: trunk/boost/geometry/extensions/algorithms/buffer/buffered_ring.hpp
==============================================================================
--- trunk/boost/geometry/extensions/algorithms/buffer/buffered_ring.hpp (original)
+++ trunk/boost/geometry/extensions/algorithms/buffer/buffered_ring.hpp 2013-02-27 12:25:07 EST (Wed, 27 Feb 2013)
@@ -68,6 +68,19 @@
};
}} // namespace detail::buffer
+
+
+// Turn of concept checking (for now)
+namespace dispatch
+{
+template <typename Geometry, bool IsConst>
+struct check<Geometry, detail::buffer::buffered_ring_collection_tag, IsConst>
+{
+};
+
+}
+
+
#endif // DOXYGEN_NO_DETAIL
@@ -113,6 +126,10 @@
} // namespace traits
+
+
+
+
namespace core_dispatch
{
Modified: trunk/boost/geometry/extensions/algorithms/offset.hpp
==============================================================================
--- trunk/boost/geometry/extensions/algorithms/offset.hpp (original)
+++ trunk/boost/geometry/extensions/algorithms/offset.hpp 2013-02-27 12:25:07 EST (Wed, 27 Feb 2013)
@@ -50,7 +50,7 @@
DistanceStrategy const& distance,
JoinStrategy const& join)
{
- collection.add_input();
+ collection.start_new_ring();
iterate(collection, boost::begin(range), boost::end(range),
buffer_side_left,
distance, join);
@@ -123,8 +123,6 @@
detail::buffer::buffered_piece_collection
<
- //typename geometry::ring_type<GeometryOut>::type
- // TODO the piece collection will not require a polygonal argument
model::ring<typename point_type<Geometry>::type>
> collection;
@@ -135,6 +133,10 @@
Geometry,
GeometryOut
>::apply(collection, geometry, distance_strategy, join);
+
+
+ collection.assign_offsetted_rings(out);
+
}