Subject: [Boost-commit] svn:boost r76978 - in trunk: boost/geometry/algorithms/detail/overlay libs/geometry/test/multi/algorithms
From: barend.gehrels_at_[hidden]
Date: 2012-02-11 12:10:18
Author: barendgehrels
Date: 2012-02-11 12:10:17 EST (Sat, 11 Feb 2012)
New Revision: 76978
URL: http://svn.boost.org/trac/boost/changeset/76978
Log:
Boost.Geometry line/poly overlay (new for 1.49), bugfix (avoid degenerate lines with only one point, and sub-sort on operation in case of duplicate intersection points). Including unit test update.
Note, this also fixes two earlier unit tests with degenerate outputs.
Text files modified:
trunk/boost/geometry/algorithms/detail/overlay/follow.hpp | 42 +++++++++++++++++++++++++++++++++++----
trunk/libs/geometry/test/multi/algorithms/multi_difference.cpp | 12 +++++++++-
2 files changed, 47 insertions(+), 7 deletions(-)
Modified: trunk/boost/geometry/algorithms/detail/overlay/follow.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/overlay/follow.hpp (original)
+++ trunk/boost/geometry/algorithms/detail/overlay/follow.hpp 2012-02-11 12:10:17 EST (Sat, 11 Feb 2012)
@@ -182,11 +182,11 @@
// and add the output piece
geometry::copy_segments<false>(linestring, segment_id, index, current_piece);
detail::overlay::append_no_duplicates(current_piece, point);
- if (! current_piece.empty())
+ if (current_piece.size() > 1)
{
*out++ = current_piece;
- current_piece.clear();
}
+ current_piece.clear();
}
static inline bool is_entered(bool entered)
@@ -277,14 +277,46 @@
template<typename Turn>
struct sort_on_segment
{
+ // In case of turn point at the same location, we want to have continue/blocked LAST
+ // because that should be followed (intersection) or skipped (difference).
+ // By chance the enumeration is ordered like that but we keep the safe way here.
+ inline int operation_order(Turn const& turn) const
+ {
+ operation_type const& operation = turn.operations[0].operation;
+ switch(operation)
+ {
+ case operation_none : return 0;
+ case operation_union : return 1;
+ case operation_intersection : return 2;
+ case operation_blocked : return 3;
+ case operation_continue : return 4;
+ }
+ return -1;
+ };
+
+ inline bool use_operation(Turn const& left, Turn const& right) const
+ {
+ // If they are the same, OK.
+ return operation_order(left) < operation_order(right);
+ }
+
+ inline bool use_distance(Turn const& left, Turn const& right) const
+ {
+ return geometry::math::equals(left.operations[0].enriched.distance, right.operations[0].enriched.distance)
+ ? use_operation(left, right)
+ : left.operations[0].enriched.distance < right.operations[0].enriched.distance
+ ;
+ }
+
inline bool operator()(Turn const& left, Turn const& right) const
{
segment_identifier const& sl = left.operations[0].seg_id;
segment_identifier const& sr = right.operations[0].seg_id;
return sl == sr
- ? left.operations[0].enriched.distance < right.operations[0].enriched.distance
- : sl < sr;
+ ? use_distance(left, right)
+ : sl < sr
+ ;
}
};
@@ -364,7 +396,7 @@
}
// Output the last one, if applicable
- if (! current_piece.empty())
+ if (current_piece.size() > 1)
{
*out++ = current_piece;
}
Modified: trunk/libs/geometry/test/multi/algorithms/multi_difference.cpp
==============================================================================
--- trunk/libs/geometry/test/multi/algorithms/multi_difference.cpp (original)
+++ trunk/libs/geometry/test/multi/algorithms/multi_difference.cpp 2012-02-11 12:10:17 EST (Sat, 11 Feb 2012)
@@ -151,10 +151,18 @@
typedef typename bg::point_type<Polygon>::type Point;
typedef bg::model::ring<Point> Ring;
- test_one_lp<LineString, LineString, MultiPolygon>("case_mp_ls_1", "LINESTRING(2 0,2 5)", case_multi_simplex[0], 3, 5, 1.30);
+ test_one_lp<LineString, LineString, MultiPolygon>("case_mp_ls_1", "LINESTRING(2 0,2 5)", case_multi_simplex[0], 2, 4, 1.30);
test_one_lp<LineString, MultiLineString, Polygon>("case_p_mls_1", "MULTILINESTRING((2 0,2 5),(3 0,3 5))", case_single_simplex, 3, 6, 2.5);
- test_one_lp<LineString, MultiLineString, MultiPolygon>("case_mp_mls_1", "MULTILINESTRING((2 0,2 5),(3 0,3 5))", case_multi_simplex[0], 6, 11, 3.1666667);
+ test_one_lp<LineString, MultiLineString, MultiPolygon>("case_mp_mls_1", "MULTILINESTRING((2 0,2 5),(3 0,3 5))", case_multi_simplex[0], 5, 10, 3.1666667);
test_one_lp<LineString, MultiLineString, Ring>("case_r_mls_1", "MULTILINESTRING((2 0,2 5),(3 0,3 5))", case_single_simplex, 3, 6, 2.5);
+
+ // Collinear cases, with multiple turn points at the same location
+ test_one_lp<LineString, LineString, MultiPolygon>("case_mp_ls_2a", "LINESTRING(1 0,1 1,2 1,2 0)", "MULTIPOLYGON(((0 0,0 1,1 1,1 0,0 0)),((1 1,1 2,2 2,2 1,1 1)))", 1, 2, 1.0);
+ test_one_lp<LineString, LineString, MultiPolygon>("case_mp_ls_2b", "LINESTRING(1 0,1 1,2 1,2 0)", "MULTIPOLYGON(((1 1,1 2,2 2,2 1,1 1)),((0 0,0 1,1 1,1 0,0 0)))", 1, 2, 1.0);
+
+ test_one_lp<LineString, LineString, MultiPolygon>("case_mp_ls_3",
+ "LINESTRING(6 6,6 7,7 7,7 6,8 6,8 7,9 7,9 6)",
+ "MULTIPOLYGON(((5 7,5 8,6 8,6 7,5 7)),((6 6,6 7,7 7,7 6,6 6)),((8 8,9 8,9 7,8 7,7 7,7 8,8 8)))", 2, 5, 3.0);
}