Subject: [Boost-commit] svn:boost r61507 - in sandbox/geometry/boost/geometry: algorithms/detail/buffer algorithms/detail/overlay algorithms/overlay extensions/algorithms strategies util
From: barend.gehrels_at_[hidden]
Date: 2010-04-23 11:45:19
Author: barendgehrels
Date: 2010-04-23 11:45:17 EDT (Fri, 23 Apr 2010)
New Revision: 61507
URL: http://svn.boost.org/trac/boost/changeset/61507
Log:
Last changes in buffer before moving it to extensions
Changes in dissolver/split rings
Added extensions/offset
Added const behaviour for for_each_coordinate
Aded reverse test for intersection
Added:
sandbox/geometry/boost/geometry/extensions/algorithms/offset.hpp (contents, props changed)
Text files modified:
sandbox/geometry/boost/geometry/algorithms/detail/buffer/linestring_buffer.hpp | 5
sandbox/geometry/boost/geometry/algorithms/detail/buffer/segmenting_buffer.hpp | 18 +-
sandbox/geometry/boost/geometry/algorithms/detail/overlay/dissolver.hpp | 220 ++++++++++++++++++++++++++++++++-------
sandbox/geometry/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp | 11 +
sandbox/geometry/boost/geometry/algorithms/detail/overlay/split_rings.hpp | 67 ++++++-----
sandbox/geometry/boost/geometry/algorithms/overlay/get_turns.hpp | 6
sandbox/geometry/boost/geometry/strategies/buffer.hpp | 92 +++++++++++-----
sandbox/geometry/boost/geometry/strategies/buffer_join_round.hpp | 13 +-
sandbox/geometry/boost/geometry/util/for_each_coordinate.hpp | 43 ++++++-
9 files changed, 346 insertions(+), 129 deletions(-)
Modified: sandbox/geometry/boost/geometry/algorithms/detail/buffer/linestring_buffer.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/detail/buffer/linestring_buffer.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/buffer/linestring_buffer.hpp 2010-04-23 11:45:17 EDT (Fri, 23 Apr 2010)
@@ -44,9 +44,12 @@
{
typedef typename coordinate_type<Polygon>::type coordinate_type;
typedef typename point_type<Polygon>::type output_point_type;
- typedef typename ring_type<Polygon>::type ring_type;
typedef segment<output_point_type const> segment_type;
+#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
+ typedef typename ring_type<Polygon>::type ring_type;
+#endif
+
template
<
typename Inserter,
Modified: sandbox/geometry/boost/geometry/algorithms/detail/buffer/segmenting_buffer.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/detail/buffer/segmenting_buffer.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/buffer/segmenting_buffer.hpp 2010-04-23 11:45:17 EDT (Fri, 23 Apr 2010)
@@ -107,17 +107,17 @@
coordinate_type ext_y = get<1>(head) - get<1>(tail);
distance_type segment_length = sqrt(ext_x * ext_x + ext_y * ext_y);
- if (buffered_length < distance_left)
+ if (buffered_length < std::abs(distance_left))
{
- distance_left = buffered_length;
+ distance_left = buffered_length * distance_left < 0 ? -1.0 : 1.0;
}
- if (buffered_length < distance_right)
+ if (buffered_length < std::abs(distance_right))
{
- distance_right = buffered_length;
+ distance_right = buffered_length * distance_right < 0 ? -1.0 : 1.0;
}
- distance_type prop_left = distance_left / segment_length;
- distance_type prop_right = distance_right / segment_length;
+ distance_type prop_left = std::abs(distance_left) / segment_length;
+ distance_type prop_right = std::abs(distance_right) / segment_length;
set<0>(tail_left, get<0>(tail) - ext_x * prop_left);
set<1>(tail_left, get<1>(tail) - ext_y * prop_left);
@@ -265,9 +265,9 @@
}
}
- // TEMP
- buffered.swap(buffered_pieces);
- return;
+ // TEMP, uncomment to see what was actually generated
+ //buffered.swap(buffered_pieces);
+ //return;
// END TEMP
Modified: sandbox/geometry/boost/geometry/algorithms/detail/overlay/dissolver.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/detail/overlay/dissolver.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/overlay/dissolver.hpp 2010-04-23 11:45:17 EDT (Fri, 23 Apr 2010)
@@ -229,13 +229,15 @@
template <typename CombinePolicy>
struct dissolver_generic
{
+
+
// Small structure to access elements by index;
// this avoids copying or accessing elements by address (pointer)
template <typename Box>
- struct dissolve_helper
+ struct dissolve_helper
{
int source; // 0,1
- int index;
+ int index; // index in the original array
bool dissolved;
Box box;
double area;
@@ -269,107 +271,183 @@
typename HelperVector
>
static inline void init_helper(Vector const& v, HelperVector& helper,
- int begin_index = 0, int source = 0)
+ int index = 0, int source = 0)
{
typedef typename boost::range_value<Vector>::type value_type;
typedef typename geometry::point_type<value_type>::type point_type;
typedef geometry::box<point_type> box_type;
- int index = begin_index;
- for(typename boost::range_iterator<Vector const>::type it
- = boost::begin(v);
+ for(typename boost::range_iterator<Vector const>::type
+ it = boost::begin(v);
it != boost::end(v);
++it, ++index)
{
- box_type box = geometry::make_envelope<box_type>(*it);
- helper.push_back(dissolve_helper<box_type>(index, box, geometry::area(*it), source));
+ helper.push_back(dissolve_helper<box_type>(index,
+ geometry::make_envelope<box_type>(*it),
+ geometry::area(*it),
+ source));
}
}
template
<
+ typename Element,
typename Geometry1, typename Geometry2,
typename OutputCollection
>
- static inline bool call_policy(Geometry1 const& geometry1, Geometry2 const& geometry2
+ static inline bool call_policy(
+ Element const& element1, Element const& element2,
+ Geometry1 const& geometry1, Geometry2 const& geometry2
, OutputCollection& output_collection)
{
- return
- ! geometry::disjoint(geometry1, geometry2)
- && CombinePolicy::apply(geometry1, geometry2,
- output_collection);
+ if (! geometry::disjoint(geometry1, geometry2))
+ {
+ /*std::cout << "Process " << element1.source << "/" << element1.index
+ << " and " << element2.source << "/" << element2.index
+ << " (" << element2.dissolved << "," << element2.dissolved << ")"
+ << std::endl;
+ */
+ return CombinePolicy::apply(geometry1, geometry2,
+ output_collection);
+ }
+ return false;
}
template
<
+ int Dimension,
typename HelperVector,
+ typename IndexVector,
typename InputRange,
- typename OutputCollection
+ typename OutputCollection,
+ typename Box
>
- static inline bool process(HelperVector& helper_vector
+ static inline bool divide_and_conquer(HelperVector& helper_vector
+ , IndexVector& index_vector
, InputRange const& input_range
, OutputCollection& output_collection
+ , Box const& total_box
+ , bool& changed
+ , int iteration = 0
)
{
- typedef typename boost::range_value<OutputCollection>::type output_type;
+ //std::cout << "divide_and_conquer " << iteration << std::endl;
+ typedef geometry::coordinate_type<Box>::type coordinate_type;
+ typedef typename boost::range_value<HelperVector>::type helper_type;
+ typedef typename boost::range_iterator<IndexVector const>::type iterator_type;
+
+ //if (boost::size(index_vector) >= 16 && iteration < 100)
+ // Not yet using divide and conquer
+ if (false)
+ {
+ // 1: separate box into 2 (either horizontally or vertically)
+ Box lower_box = total_box, upper_box = total_box;
+ coordinate_type two = 2.0;
+ coordinate_type mid
+ = (geometry::get<min_corner, Dimension>(total_box)
+ + geometry::get<max_corner, Dimension>(total_box)) / two;
+
+ geometry::set<max_corner, Dimension>(lower_box, mid);
+ geometry::set<min_corner, Dimension>(upper_box, mid);
+
+ // 2: divide indices into two sublists
+ IndexVector lower_list, upper_list;
+ for(iterator_type it = boost::begin(index_vector);
+ it != boost::end(index_vector);
+ ++it)
+ {
+ helper_type const& element = helper_vector[*it];
+ if (! geometry::disjoint(lower_box, element.box))
+ {
+ lower_list.push_back(*it);
+ }
+ if (! geometry::disjoint(upper_box, element.box))
+ {
+ upper_list.push_back(*it);
+ }
+ }
+
+ //std::cout << lower_list.size() << ", " << upper_list.size()<< std::endl;
+
+ // 3: recursively call function (possibly divide in other dimension)
+ divide_and_conquer<1 - Dimension>(helper_vector,
+ lower_list, input_range, output_collection, lower_box, changed, iteration + 1);
+ divide_and_conquer<1 - Dimension>(helper_vector,
+ upper_list, input_range, output_collection, upper_box, changed, iteration + 1);
+ return changed;
+ }
+
+ // There are less then 16 elements, handle them quadraticly
int n = boost::size(output_collection);
- bool changed = false;
- typedef typename boost::range_iterator<HelperVector>::type iterator_type;
- for(iterator_type it1 = boost::begin(helper_vector);
- it1 != boost::end(helper_vector);
+ for(iterator_type it1 = boost::begin(index_vector);
+ it1 != boost::end(index_vector);
++it1)
{
+ helper_type& element1 = helper_vector[*it1];
+
bool unioned = false;
- for(iterator_type it2 = boost::begin(helper_vector);
+ for(iterator_type it2 = boost::begin(index_vector);
! unioned && it2 != it1;
++it2)
{
+ helper_type& element2 = helper_vector[*it2];
+
// If they are NOT disjoint, union them
- if (! it1->dissolved
- && ! it2->dissolved
- && ! geometry::disjoint(it1->box, it2->box))
+ if (! element1.dissolved
+ && ! element2.dissolved
+ && ! geometry::disjoint(element1.box, element2.box))
{
// Runtime type check here...
- if ((it1->source == 0 && it2->source == 0
+ if ((element1.source == 0 && element2.source == 0
&& call_policy
(
- get_geometry::apply(input_range, it1->index),
- get_geometry::apply(input_range, it2->index),
+ element1, element2,
+ get_geometry::apply(input_range, element1.index),
+ get_geometry::apply(input_range, element2.index),
output_collection
)
)
- || (it1->source == 0 && it2->source == 1
+ || (element1.source == 0 && element2.source == 1
&& call_policy
(
- get_geometry::apply(input_range, it1->index),
- get_geometry::apply(output_collection, it2->index),
+ element1, element2,
+ get_geometry::apply(input_range, element1.index),
+ get_geometry::apply(output_collection, element2.index),
output_collection
)
)
- || (it1->source == 1 && it2->source == 0
+ || (element1.source == 1 && element2.source == 0
&& call_policy
(
- get_geometry::apply(output_collection, it1->index),
- get_geometry::apply(input_range, it2->index),
+ element1, element2,
+ get_geometry::apply(output_collection, element1.index),
+ get_geometry::apply(input_range, element2.index),
output_collection
)
)
- || (it1->source == 1 && it2->source == 1
+ || (element1.source == 1 && element2.source == 1
&& call_policy
(
- get_geometry::apply(output_collection, it1->index),
- get_geometry::apply(output_collection, it2->index),
+ element1, element2,
+ get_geometry::apply(output_collection, element1.index),
+ get_geometry::apply(output_collection, element2.index),
output_collection
)
)
)
{
changed = true;
- it1->dissolved = true;
- it2->dissolved = true;
+ element1.dissolved = true;
+ element2.dissolved = true;
+
unioned = true;
+/*std::cout << "Assign " << element1.source << "/" << element1.index
+<< " and " << element2.source << "/" << element2.index
+<< " (" << element2.dissolved << "," << element2.dissolved << ")"
+<< std::endl;
+*/
}
}
}
@@ -382,6 +460,12 @@
return changed;
}
+ template <typename T>
+ static inline bool helper_dissolved(T const& t)
+ {
+ return t.dissolved;
+ }
+
template
@@ -397,14 +481,70 @@
typedef typename geometry::point_type<output_type>::type point_type;
typedef geometry::box<point_type> box_type;
- typedef std::vector<dissolve_helper<box_type> > helper_vector_type;
+ typedef dissolve_helper<box_type> dissolve_helper_type;
+ typedef std::vector<dissolve_helper_type> helper_vector_type;
+
+ // Vector with indices to both input_range (source 0) and output_collection (source 1)
helper_vector_type helper_vector;
+
+ // Vector with indices to helper-vector, for divide and conquer
+ std::vector<int> index_vector;
+
+
init_helper(input_range, helper_vector);
+ // Fill intrusive list with copies, and determine bounding box
+ box_type total_box;
+ geometry::assign_inverse(total_box);
+ int index = 0;
+ for(typename boost::range_iterator<helper_vector_type const>::type
+ it = boost::begin(helper_vector);
+ it != boost::end(helper_vector);
+ ++it, ++index)
+ {
+ index_vector.push_back(index);
+ geometry::combine(total_box, it->box);
+ }
+
std::vector<output_type> unioned_collection;
- while(process(helper_vector, input_range, unioned_collection))
+ int size = 0, previous_size = 0;
+ int n = 0;
+
+ bool changed = false;
+ while(divide_and_conquer<1>
+ (helper_vector, index_vector, input_range, unioned_collection, total_box, changed) && n < 5)
{
+ // Remove everything which is already dissolved.
+ helper_vector.erase
+ (
+ std::remove_if
+ (
+ helper_vector.begin(),
+ helper_vector.end(),
+ helper_dissolved<dissolve_helper_type>
+ ),
+ helper_vector.end()
+ );
+
+ previous_size = size;
+ size = helper_vector.size();
+ n = previous_size == size ? n + 1 : 0;
+
+ // Re-initialize the list
+ index_vector.clear();
+ int index = 0;
+ for(typename boost::range_iterator<helper_vector_type const>::type
+ it = boost::begin(helper_vector);
+ it != boost::end(helper_vector);
+ ++it, ++index)
+ {
+ index_vector.push_back(index);
+ }
+
+ changed = false;
+
+ //std::cout << " " << size;
}
// Add input+output to real output
Modified: sandbox/geometry/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp 2010-04-23 11:45:17 EDT (Fri, 23 Apr 2010)
@@ -372,7 +372,16 @@
return;
}
- std::cout << "Not yet handled" << std::endl;
+ // Normally a robustness issue.
+ std::cout << "Not yet handled" << std::endl
+ << "pi " << get<0>(pi) << " , " << get<1>(pi)
+ << " pj " << get<0>(pj) << " , " << get<1>(pj)
+ << " pk " << get<0>(pk) << " , " << get<1>(pk)
+ << std::endl
+ << "qi " << get<0>(qi) << " , " << get<1>(qi)
+ << " qj " << get<0>(qj) << " , " << get<1>(qj)
+ << " qk " << get<0>(qk) << " , " << get<1>(qk)
+ << std::endl;
}
};
Modified: sandbox/geometry/boost/geometry/algorithms/detail/overlay/split_rings.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/detail/overlay/split_rings.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/overlay/split_rings.hpp 2010-04-23 11:45:17 EDT (Fri, 23 Apr 2010)
@@ -8,7 +8,9 @@
#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SPLIT_RINGS_HPP
#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SPLIT_RINGS_HPP
+#define BOOST_GEOMETRY_CHECK_SPLIT_RINGS
+//#include <boost/foreach.hpp>
#include <deque>
#include <boost/geometry/algorithms/overlay/get_turns.hpp>
@@ -26,6 +28,11 @@
#include <boost/geometry/geometries/concepts/check.hpp>
+#if defined(BOOST_GEOMETRY_DEBUG_SPLIT_RINGS) || defined(BOOST_GEOMETRY_CHECK_SPLIT_RINGS)
+# include <boost/geometry/extensions/gis/io/wkt/wkt.hpp>
+#endif
+
+
namespace boost { namespace geometry
{
@@ -62,7 +69,7 @@
--> we use id1+1
- After that, we need to update all indices AFTER IP.
+ After that, we need to update all indices AFTER IP.
We removed two vertices here (4-2), and added one (the IP)
*/
@@ -209,7 +216,7 @@
return left.count_between < right.count_between;
}
- if (left.operations[0].seg_id.segment_index
+ if (left.operations[0].seg_id.segment_index
== right.operations[0].seg_id.segment_index)
{
return left.operations[0].distance < right.operations[0].distance;
@@ -238,7 +245,7 @@
struct split_turn_info : detail::overlay::turn_info
<
P, split_turn_operation<P>
- >
+ >
{
//std::string history;
int count_between; // counts number of segments between ring in intersection
@@ -285,7 +292,7 @@
- /*
+#ifdef BOOST_GEOMETRY_DEBUG_SPLIT_RINGS
template <typename Turns>
static void report(Turns const& turns, std::string const& header)
{
@@ -296,8 +303,8 @@
std::cout << header << std::endl;
BOOST_FOREACH(typename boost::range_value<Turns>::type const& turn, turns)
{
- std::cout
- << "I at " << turn.operations[0].seg_id.segment_index
+ std::cout
+ << "I at " << turn.operations[0].seg_id.segment_index
<< "/" << turn.operations[1].seg_id.segment_index
<< " (" << turn.count_between
<< ") " << turn.operations[0].distance
@@ -305,7 +312,7 @@
<< " " << geometry::wkt(turn.point) << std::endl;
}
}
- */
+#endif
template <typename Operation>
static bool adapt(Operation& op, Operation const& first, Operation const& second)
@@ -315,14 +322,13 @@
return adapt(op, second, first);
}
if (op.seg_id.segment_index > first.seg_id.segment_index
- ||
- (op.seg_id.segment_index == first.seg_id.segment_index
- && op.distance > first.distance
- )
+ || (op.seg_id.segment_index == first.seg_id.segment_index
+ && op.distance > first.distance)
)
{
if (op.seg_id.segment_index < second.seg_id.segment_index
- //|| segment.segment_index == second &&
+ || (op.seg_id.segment_index == second.seg_id.segment_index
+ && op.distance < second.distance)
)
{
// mark for deletion
@@ -358,9 +364,9 @@
// Make operations[0].seg_id always the smallest, to sort properly
// Also calculate the number of segments in between
- for (typename boost::range_iterator<turns_type>::type
+ for (typename boost::range_iterator<turns_type>::type
it = boost::begin(turns);
- it != boost::end(turns);
+ it != boost::end(turns);
++it)
{
turn_info& turn = *it;
@@ -380,13 +386,13 @@
turn.count_between = (std::min)(between1, between2);
*/
- turn.count_between = between1;
+ turn.count_between = between1;
}
//report(turns, "swapped");
std::sort(turns.begin(), turns.end(), sorter<turn_info>());
//report(turns, "sorted");
-
+
while(turns.size() > 0)
{
@@ -395,38 +401,39 @@
split_turn_operation<point_type> const& first_op = turn.operations[0];
split_turn_operation<point_type> const& second_op = turn.operations[1];
- bool do_split = first_op.seg_id.segment_index >= 0
+ bool do_split = first_op.seg_id.segment_index >= 0
&& second_op.seg_id.segment_index >= 0;
if (do_split)
{
-
+#ifdef BOOST_GEOMETRY_CHECK_SPLIT_RINGS
ring_type copy = range; // TEMP, for check
- ring_type splitted;
- split<ring_tag, Range>::apply(range, splitted,
+#endif
+ ring_collection.resize(ring_collection.size() + 1);
+ split<ring_tag, Range>::apply(range, ring_collection.back(),
turn.operations[0].seg_id, turn.operations[1].seg_id,
turn.point);
- ring_collection.push_back(splitted);
- // BEGIN TEMP CHECK
+#ifdef BOOST_GEOMETRY_CHECK_SPLIT_RINGS
{
std::deque<turn_info> splitted_turns;
geometry::get_turns
<
split_calculate_distance_policy
- >(splitted, splitted_turns, detail::get_turns::no_interrupt_policy());
-
+ >(ring_collection.back(),
+ splitted_turns,
+ detail::get_turns::no_interrupt_policy());
if (splitted_turns.size() > 0)
{
- std::cout << "not OK! " << splitted_turns.size() << std::endl;
+ std::cout << "TODO Still intersecting! " << splitted_turns.size() << std::endl;
//std::cout << " " << geometry::wkt(copy) << std::endl;
//std::cout << " " << geometry::wkt(splitted) << std::endl;
//report(splitted_turns, "NOT OK");
//std::cout << std::endl;
}
}
- // END TEMP
+#endif
}
@@ -435,9 +442,9 @@
if (do_split)
{
- for (typename boost::range_iterator<turns_type>::type
+ for (typename boost::range_iterator<turns_type>::type
rest = boost::begin(turns);
- rest != boost::end(turns);
+ rest != boost::end(turns);
++rest)
{
//turn_info copy = turn;
@@ -445,7 +452,7 @@
|| adapt(rest->operations[1], first_op, second_op))
{
/**
- std::cout << " ADAPTED "
+ std::cout << " ADAPTED "
<< copy.operations[0].seg_id.segment_index << "/" << copy.operations[1].seg_id.segment_index
<< " "
<< geometry::wkt(copy.point) << std::endl;
@@ -453,7 +460,7 @@
}
}
}
- while(turns.size() > 0
+ while(turns.size() > 0
&& (turns.front().operations[0].seg_id.segment_index < 0
|| turns.front().operations[1].seg_id.segment_index < 0))
{
Modified: sandbox/geometry/boost/geometry/algorithms/overlay/get_turns.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/overlay/get_turns.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/overlay/get_turns.hpp 2010-04-23 11:45:17 EDT (Fri, 23 Apr 2010)
@@ -96,10 +96,8 @@
public :
// Returns true if terminated, false if interrupted
static inline bool apply(
- int source_id1, Geometry1 const& geometry1,
- Section1 const& sec1,
- int source_id2, Geometry2 const& geometry2,
- Section2 const& sec2,
+ int source_id1, Geometry1 const& geometry1, Section1 const& sec1,
+ int source_id2, Geometry2 const& geometry2, Section2 const& sec2,
Turns& turns,
InterruptPolicy& interrupt_policy)
{
Added: sandbox/geometry/boost/geometry/extensions/algorithms/offset.hpp
==============================================================================
--- (empty file)
+++ sandbox/geometry/boost/geometry/extensions/algorithms/offset.hpp 2010-04-23 11:45:17 EDT (Fri, 23 Apr 2010)
@@ -0,0 +1,202 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Copyright Barend Gehrels 2010, Geodan, 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_EXTENSIONS_ALGORITHMS_OFFSET_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_ALGORITHMS_OFFSET_HPP
+
+
+#include <boost/range/functions.hpp>
+#include <boost/range/metafunctions.hpp>
+
+#include <boost/geometry/core/point_type.hpp>
+#include <boost/geometry/algorithms/detail/buffer/line_line_intersection.hpp>
+#include <boost/geometry/algorithms/detail/disjoint.hpp>
+#include <boost/geometry/geometries/concepts/check.hpp>
+
+
+namespace boost { namespace geometry
+{
+
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace offset
+{
+
+
+template
+<
+ typename Range,
+ typename RangeOut,
+ typename JoinStrategy,
+ typename Distance
+>
+struct offset_range
+{
+ typedef typename coordinate_type<RangeOut>::type coordinate_type;
+ typedef typename point_type<RangeOut>::type output_point_type;
+ typedef segment<output_point_type const> segment_type;
+ typedef typename boost::range_iterator<Range const>::type iterator_type;
+
+ static inline void apply(Range const& range,
+ RangeOut& out,
+ JoinStrategy const& join,
+ Distance const& distance)
+ {
+ output_point_type previous_p1, previous_p2;
+ output_point_type first_p1, first_p2;
+
+ bool first = true;
+
+ iterator_type it = boost::begin(range);
+ for (iterator_type prev = it++; it != boost::end(range); ++it)
+ {
+ if (! detail::equals::equals_point_point(*prev, *it))
+ {
+ bool skip = false;
+
+ // Simulate a vector d (dx,dy)
+ coordinate_type dx = get<0>(*it) - get<0>(*prev);
+ coordinate_type dy = get<1>(*it) - get<1>(*prev);
+
+ // For normalization [0,1] (=dot product d.d, sqrt)
+ coordinate_type length = sqrt(dx * dx + dy * dy);
+
+ // Because coordinates are not equal, length should not be zero
+ BOOST_ASSERT((! geometry::math::equals(length, 0)));
+
+ // Generate the normalized perpendicular p, to the left (ccw)
+ coordinate_type px = -dy / length;
+ coordinate_type py = dx / length;
+
+ output_point_type p1, p2;
+
+ set<0>(p2, get<0>(*it) + px * distance);
+ set<1>(p2, get<1>(*it) + py * distance);
+
+ set<0>(p1, get<0>(*prev) + px * distance);
+ set<1>(p1, get<1>(*prev) + py * distance);
+
+ if (! first)
+ {
+ output_point_type p;
+ segment_type s1(p1, p2);
+ segment_type s2(previous_p1, previous_p2);
+ if (detail::buffer::line_line_intersection<output_point_type, segment_type>::apply(s1, s2, p))
+ {
+ join.apply(p, *prev, previous_p2, p1, distance, out);
+ }
+ else
+ {
+ skip = false;
+ }
+ }
+ else
+ {
+ first = false;
+ first_p1 = p1;
+ first_p2 = p2;
+
+ out.push_back(p1);
+ }
+
+ if (! skip)
+ {
+ previous_p1 = p1;
+ previous_p2 = p2;
+ prev = it;
+ }
+ }
+ }
+
+ // Last one
+ out.push_back(previous_p2);
+
+ }
+};
+
+}} // namespace detail::offset
+#endif
+
+
+
+#ifndef DOXYGEN_NO_DISPATCH
+namespace dispatch
+{
+
+template
+<
+ typename GeometryTag,
+ typename GeometryOutTag,
+ typename Geometry,
+ typename GeometryOut,
+ typename JoinStrategy,
+ typename Distance
+>
+struct offset
+{};
+
+
+template
+<
+ typename Geometry,
+ typename GeometryOut,
+ typename JoinStrategy,
+ typename Distance
+>
+struct offset
+ <
+ linestring_tag,
+ linestring_tag,
+ Geometry,
+ GeometryOut,
+ JoinStrategy,
+ Distance
+ >
+ : detail::offset::offset_range
+ <
+ Geometry,
+ GeometryOut,
+ JoinStrategy,
+ Distance
+ >
+{};
+
+
+} // namespace dispatch
+#endif // DOXYGEN_NO_DISPATCH
+
+
+template
+<
+ typename Geometry,
+ typename GeometryOut,
+ typename JoinStrategy,
+ typename Distance
+>
+inline void offset(Geometry const& geometry, GeometryOut& out,
+ JoinStrategy const& join,
+ Distance const& distance)
+{
+ concept::check<Geometry const>();
+ concept::check<GeometryOut>();
+
+ dispatch::offset
+ <
+ typename tag<Geometry>::type,
+ typename tag<GeometryOut>::type,
+ Geometry,
+ GeometryOut,
+ JoinStrategy,
+ Distance
+ >::apply(geometry, out, join, distance);
+}
+
+
+}} // namespace boost::geometry
+
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_ALGORITHMS_OFFSET_HPP
Modified: sandbox/geometry/boost/geometry/strategies/buffer.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/strategies/buffer.hpp (original)
+++ sandbox/geometry/boost/geometry/strategies/buffer.hpp 2010-04-23 11:45:17 EDT (Fri, 23 Apr 2010)
@@ -18,6 +18,9 @@
#include <boost/geometry/strategies/buffer_side.hpp>
+#define BOOST_GEOMETRY_BUFFER_NO_HELPER_POINTS
+
+
namespace boost { namespace geometry
{
@@ -113,23 +116,32 @@
template <typename Ring>
inline void apply(PointIn const& ip, PointIn const& vertex,
PointIn const& perp1, PointIn const& perp2,
- double buffer_distance,
+ coordinate_type const& buffer_distance,
Ring& buffered) const
{
- int signum = buffer_distance > 0 ? 1 : buffer_distance < 0 ? -1 : 0;
+ coordinate_type zero = 0;
+ int signum = buffer_distance > zero
+ ? 1
+ : buffer_distance < zero
+ ? -1
+ : 0;
if (side::apply(perp1, ip, perp2) == signum)
{
- // If it is concave (corner to left), add helper-line
+
+#ifdef BOOST_GEOMETRY_BUFFER_NO_HELPER_POINTS
+ // Because perp1 crosses perp2 at IP, it is not necessary to
+ // include IP
+ buffered.push_back(ip);
+#else
+ // If it is concave (corner to left), add helperline
// The helper-line IS essential for buffering holes. Without,
// holes might be generated, while they should NOT be there.
// DOES NOT WORK ALWAYS buffered.push_back(ip);
// We might consider to make it optional (because more efficient)
- //buffered.push_back(ip);
buffered.push_back(perp1);
buffered.push_back(perp2);
- // Because perp1 crosses perp2 at IP, it is not necessary to
- // include IP
+#endif
}
else
{
@@ -140,11 +152,17 @@
coordinate_type dy = get<1>(ip) - get<1>(vertex);
coordinate_type length = sqrt(dx * dx + dy * dy);
- coordinate_type max = 10.0 * std::abs(buffer_distance);
+
+ // TODO: make max-mitre-limit flexible
+ coordinate_type ten = 10.0;
+ coordinate_type zero_seven = 0.7;
+
+ coordinate_type max = ten * std::abs(buffer_distance);
if (length > max)
{
- coordinate_type prop = 0.7 * buffer_distance;
+
+ coordinate_type prop = zero_seven * buffer_distance;
prop /= length;
set<0>(p, get<0>(vertex) + dx * prop);
set<1>(p, get<1>(vertex) + dy * prop);
@@ -188,7 +206,7 @@
template <typename Ring>
inline void apply(PointIn const& ip, PointIn const& vertex,
PointIn const& perp1, PointIn const& perp2,
- double buffer_distance,
+ coordinate_type const& buffer_distance,
Ring& buffered) const
{
buffered.push_back(perp1);
@@ -226,31 +244,32 @@
#endif
typedef typename strategy_side<typename cs_tag<PointIn>::type>::type side;
+ typedef typename coordinate_type<PointOut>::type coordinate_type;
int m_max_level;
template <typename Ring>
inline void mid_points(PointIn const& vertex,
PointIn const& p1, PointIn const& p2,
- double buffer_distance,
+ coordinate_type const& buffer_distance,
Ring& buffered,
int level = 1) const
{
// Generate 'vectors'
- double vp1_x = get<0>(p1) - get<0>(vertex);
- double vp1_y = get<1>(p1) - get<1>(vertex);
+ coordinate_type vp1_x = get<0>(p1) - get<0>(vertex);
+ coordinate_type vp1_y = get<1>(p1) - get<1>(vertex);
- double vp2_x = (get<0>(p2) - get<0>(vertex));
- double vp2_y = (get<1>(p2) - get<1>(vertex));
+ coordinate_type vp2_x = (get<0>(p2) - get<0>(vertex));
+ coordinate_type vp2_y = (get<1>(p2) - get<1>(vertex));
// Average them to generate vector in between
- double two = 2;
- double v_x = (vp1_x + vp2_x) / two;
- double v_y = (vp1_y + vp2_y) / two;
+ coordinate_type two = 2;
+ coordinate_type v_x = (vp1_x + vp2_x) / two;
+ coordinate_type v_y = (vp1_y + vp2_y) / two;
- double length2 = sqrt(v_x * v_x + v_y * v_y);
+ coordinate_type length2 = sqrt(v_x * v_x + v_y * v_y);
- double prop = buffer_distance / length2;
+ coordinate_type prop = buffer_distance / length2;
PointIn mid_point;
set<0>(mid_point, get<0>(vertex) + v_x * prop);
@@ -259,36 +278,50 @@
if (level < m_max_level)
{
mid_points(vertex, p1, mid_point, buffer_distance, buffered, level + 1);
+ }
+ buffered.push_back(mid_point);
+ if (level < m_max_level)
+ {
mid_points(vertex, mid_point, p2, buffer_distance, buffered, level + 1);
}
- buffered.push_back(p2);
}
template <typename Ring>
inline void apply(PointIn const& ip, PointIn const& vertex,
PointIn const& perp1, PointIn const& perp2,
- double buffer_distance,
+ coordinate_type const& buffer_distance,
Ring& buffered) const
{
- int signum = buffer_distance > 0 ? 1 : buffer_distance < 0 ? -1 : 0;
+ coordinate_type zero = 0;
+ int signum = buffer_distance > zero
+ ? 1
+ : buffer_distance < zero
+ ? -1
+ : 0;
if (side::apply(perp1, ip, perp2) == signum)
{
- // If it is concave (corner to left), add helper-line
+#ifdef BOOST_GEOMETRY_BUFFER_NO_HELPER_POINTS
+ buffered.push_back(ip);
+#else
+ // If it is concave (corner to left), add helperline
buffered.push_back(perp1);
buffered.push_back(perp2);
+#endif
}
else
{
// Generate 'vectors'
- double vix = (get<0>(ip) - get<0>(vertex));
- double viy = (get<1>(ip) - get<1>(vertex));
+ coordinate_type vix = (get<0>(ip) - get<0>(vertex));
+ coordinate_type viy = (get<1>(ip) - get<1>(vertex));
- double length_i = sqrt(vix * vix + viy * viy);
+ coordinate_type length_i = sqrt(vix * vix + viy * viy);
- double prop = buffer_distance / length_i;
+
+ coordinate_type const bd = std::abs(buffer_distance);
+ coordinate_type prop = bd / length_i;
PointIn bp;
set<0>(bp, get<0>(vertex) + vix * prop);
@@ -306,8 +339,9 @@
else
{
buffered.push_back(perp1);
- mid_points(vertex, perp1, bp, buffer_distance, buffered);
- mid_points(vertex, bp, perp2, buffer_distance, buffered);
+ mid_points(vertex, perp1, bp, bd, buffered);
+ mid_points(vertex, bp, perp2, bd, buffered);
+ buffered.push_back(perp2);
}
#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
Modified: sandbox/geometry/boost/geometry/strategies/buffer_join_round.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/strategies/buffer_join_round.hpp (original)
+++ sandbox/geometry/boost/geometry/strategies/buffer_join_round.hpp 2010-04-23 11:45:17 EDT (Fri, 23 Apr 2010)
@@ -78,7 +78,8 @@
coordinate_type between_length = sqrt(v_x * v_x + v_y * v_y);
- coordinate_type prop = buffer_distance / between_length;
+ coordinate_type const positive_buffer_distance = std::abs(buffer_distance);
+ coordinate_type prop = positive_buffer_distance / between_length;
PointOut mid_point;
set<0>(mid_point, get<0>(vertex) + v_x * prop);
@@ -90,7 +91,7 @@
// using vector maths
vector_type v = create_vector<vector_type>(perpendicular, vertex);
vector_type w = create_vector<vector_type>(mid_point, vertex);
-
+
coordinate_type c1 = dot_product(w, v);
if (c1 > 0)
{
@@ -99,7 +100,7 @@
{
coordinate_type b = c1 / c2;
- PointOut projected_point;
+ PointOut projected_point;
multiply_value(v, b);
copy_coordinates(vertex, projected_point);
@@ -118,12 +119,12 @@
if (level < m_max_level)
{
- mid_points(vertex, perpendicular, p1, mid_point, buffer_distance, max_distance, out, level + 1);
+ mid_points(vertex, perpendicular, p1, mid_point, positive_buffer_distance, max_distance, out, level + 1);
}
*out++ = mid_point;
if (level < m_max_level)
{
- mid_points(vertex, perpendicular, mid_point, p2, buffer_distance, max_distance, out, level + 1);
+ mid_points(vertex, perpendicular, mid_point, p2, positive_buffer_distance, max_distance, out, level + 1);
}
}
@@ -145,7 +146,7 @@
template<typename PointOut>
struct join_none
{
- template <typename OutputIterator, typename Point, typename Point2,
+ template <typename OutputIterator, typename Point, typename Point2,
typename DistanceType>
inline OutputIterator apply(Point const& ,
Point2 const& ,
Modified: sandbox/geometry/boost/geometry/util/for_each_coordinate.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/util/for_each_coordinate.hpp (original)
+++ sandbox/geometry/boost/geometry/util/for_each_coordinate.hpp 2010-04-23 11:45:17 EDT (Fri, 23 Apr 2010)
@@ -11,6 +11,7 @@
#include <boost/concept/requires.hpp>
#include <boost/geometry/geometries/concepts/point_concept.hpp>
+#include <boost/geometry/util/add_const_if_c.hpp>
namespace boost { namespace geometry
{
@@ -19,28 +20,39 @@
namespace detail
{
-template <typename Point, int Dimension, int DimensionCount>
+template <typename Point, int Dimension, int DimensionCount, bool IsConst>
struct coordinates_scanner
{
template <typename Op>
- static inline void apply(Point& point, Op operation)
+ static inline Op apply(typename add_const_if_c
+ <
+ IsConst,
+ Point
+ >::type& point, Op operation)
{
operation.template apply<Point, Dimension>(point);
- coordinates_scanner
+ return coordinates_scanner
<
Point,
Dimension+1,
- DimensionCount
+ DimensionCount,
+ IsConst
>::apply(point, operation);
}
};
-template <typename Point, int DimensionCount>
-struct coordinates_scanner<Point, DimensionCount, DimensionCount>
+template <typename Point, int DimensionCount, bool IsConst>
+struct coordinates_scanner<Point, DimensionCount, DimensionCount, IsConst>
{
template <typename Op>
- static inline void apply(Point&, Op)
- {}
+ static inline Op apply(typename add_const_if_c
+ <
+ IsConst,
+ Point
+ >::type& point, Op operation)
+ {
+ return operation;
+ }
};
} // namespace detail
@@ -53,12 +65,25 @@
typedef typename detail::coordinates_scanner
<
- Point, 0, dimension<Point>::type::value
+ Point, 0, dimension<Point>::type::value, false
> scanner;
scanner::apply(point, operation);
}
+template <typename Point, typename Op>
+inline Op for_each_coordinate(Point const& point, Op operation)
+{
+ BOOST_CONCEPT_ASSERT( (concept::ConstPoint<Point>) );
+
+ typedef typename detail::coordinates_scanner
+ <
+ Point, 0, dimension<Point>::type::value, true
+ > scanner;
+
+ return scanner::apply(point, operation);
+}
+
}} // namespace boost::geometry
#endif // BOOST_GEOMETRY_UTIL_FOR_EACH_COORDINATE_HPP