Subject: [Boost-commit] svn:boost r77121 - in trunk: boost/geometry/algorithms boost/geometry/algorithms/detail/overlay libs/geometry/test/algorithms
From: barend.gehrels_at_[hidden]
Date: 2012-02-26 15:00:06
Author: barendgehrels
Date: 2012-02-26 15:00:05 EST (Sun, 26 Feb 2012)
New Revision: 77121
URL: http://svn.boost.org/trac/boost/changeset/77121
Log:
Boost.Geometry bugfix for disjoint of opposite-equal or or opposite-collinear segments
plus prepares extra parameters for buffer
Text files modified:
trunk/boost/geometry/algorithms/detail/overlay/calculate_distance_policy.hpp | 13 +++
trunk/boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp | 2
trunk/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp | 125 ++++++++++++++++++++++++++++++++++-----
trunk/boost/geometry/algorithms/detail/overlay/turn_info.hpp | 7 +
trunk/boost/geometry/algorithms/disjoint.hpp | 13 +++
trunk/libs/geometry/test/algorithms/disjoint.cpp | 6 +
6 files changed, 145 insertions(+), 21 deletions(-)
Modified: trunk/boost/geometry/algorithms/detail/overlay/calculate_distance_policy.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/overlay/calculate_distance_policy.hpp (original)
+++ trunk/boost/geometry/algorithms/detail/overlay/calculate_distance_policy.hpp 2012-02-26 15:00:05 EST (Sun, 26 Feb 2012)
@@ -32,9 +32,18 @@
{
static bool const include_no_turn = false;
static bool const include_degenerate = false;
+ static bool const include_opposite = false;
- template <typename Point1, typename Point2, typename Info>
- static inline void apply(Info& info, Point1 const& p1, Point2 const& p2)
+ template
+ <
+ typename Info,
+ typename Point1,
+ typename Point2,
+ typename IntersectionInfo,
+ typename DirInfo
+ >
+ static inline void apply(Info& info, Point1 const& p1, Point2 const& p2,
+ IntersectionInfo const&, DirInfo const&)
{
info.operations[0].enriched.distance
= geometry::comparable_distance(info.point, p1);
Modified: trunk/boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp (original)
+++ trunk/boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp 2012-02-26 15:00:05 EST (Sun, 26 Feb 2012)
@@ -28,6 +28,7 @@
case method_touch_interior : return 'm';
case method_collinear : return 'c';
case method_equal : return 'e';
+ case method_error : return '!';
default : return '?';
}
}
@@ -42,6 +43,7 @@
case operation_intersection : return 'i';
case operation_blocked : return 'x';
case operation_continue : return 'c';
+ case operation_opposite : return 'o';
default : return '?';
}
}
Modified: trunk/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp (original)
+++ trunk/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp 2012-02-26 15:00:05 EST (Sun, 26 Feb 2012)
@@ -466,6 +466,45 @@
template
<
typename TurnInfo,
+ typename AssignPolicy
+>
+struct equal_opposite : public base_turn_handler
+{
+ template
+ <
+ typename Point1,
+ typename Point2,
+ typename OutputIterator,
+ typename IntersectionInfo,
+ typename DirInfo
+ >
+ static inline void apply(Point1 const& pi, Point2 const& qi,
+ /* by value: */ TurnInfo tp,
+ OutputIterator& out,
+ IntersectionInfo const& intersection_info,
+ DirInfo const& dir_info)
+ {
+ // For equal-opposite segments, normally don't do anything.
+ if (AssignPolicy::include_opposite)
+ {
+ tp.method = method_equal;
+ for (int i = 0; i < 2; i++)
+ {
+ tp.operations[i].operation = operation_opposite;
+ }
+ for (unsigned int i = 0; i < intersection_info.count; i++)
+ {
+ geometry::convert(intersection_info.intersections[i], tp.point);
+ AssignPolicy::apply(tp, pi, qi, intersection_info, dir_info);
+ *out++ = tp;
+ }
+ }
+ }
+};
+
+template
+<
+ typename TurnInfo,
typename SideStrategy
>
struct collinear : public base_turn_handler
@@ -583,6 +622,7 @@
TurnInfo& tp, IntersectionInfo const& intersection_info)
{
int const side_rk_r = SideStrategy::apply(ri, rj, rk);
+ operation_type blocked = operation_blocked;
switch(side_rk_r)
{
@@ -596,15 +636,24 @@
break;
case 0 :
// No turn on opposite collinear: block, do not traverse
- // But this "xx" is ignored here, it is useless to include
- // two operation blocked, so the whole point does not need
+ // But this "xx" is usually ignored, it is useless to include
+ // two operations blocked, so the whole point does not need
// to be generated.
// So return false to indicate nothing is to be done.
- return false;
+ if (AssignPolicy::include_opposite)
+ {
+ tp.operations[Index].operation = operation_opposite;
+ blocked = operation_opposite;
+ }
+ else
+ {
+ return false;
+ }
+ break;
}
// The other direction is always blocked when collinear opposite
- tp.operations[1 - Index].operation = operation_blocked;
+ tp.operations[1 - Index].operation = blocked;
// If P arrives within Q, set info on P (which is done above, index=0),
// this turn-info belongs to the second intersection point, index=1
@@ -648,7 +697,7 @@
if (dir_info.arrival[0] == 1
&& set_tp<0>(pi, pj, pk, tp, intersection_info))
{
- AssignPolicy::apply(tp, pi, qi);
+ AssignPolicy::apply(tp, pi, qi, intersection_info, dir_info);
*out++ = tp;
}
@@ -656,9 +705,37 @@
if (dir_info.arrival[1] == 1
&& set_tp<1>(qi, qj, qk, tp, intersection_info))
{
- AssignPolicy::apply(tp, pi, qi);
+ AssignPolicy::apply(tp, pi, qi, intersection_info, dir_info);
*out++ = tp;
}
+
+ // If P arrives within Q, there is a turn dependant on P
+ if (dir_info.arrival[0] == 1
+ && set_tp<0>(pi, pj, pk, tp, intersection_info))
+ {
+ AssignPolicy::apply(tp, pi, qi, intersection_info, dir_info);
+ *out++ = tp;
+ }
+
+ if (AssignPolicy::include_opposite)
+ {
+ // Handle cases not yet handled above
+ if ((dir_info.arrival[1] == -1 && dir_info.arrival[0] == 0)
+ || (dir_info.arrival[0] == -1 && dir_info.arrival[1] == 0))
+ {
+ for (int i = 0; i < 2; i++)
+ {
+ tp.operations[i].operation = operation_opposite;
+ }
+ for (unsigned int i = 0; i < intersection_info.count; i++)
+ {
+ geometry::convert(intersection_info.intersections[i], tp.point);
+ AssignPolicy::apply(tp, pi, qi, intersection_info, dir_info);
+ *out++ = tp;
+ }
+ }
+ }
+
}
};
@@ -722,9 +799,17 @@
{
static bool const include_no_turn = false;
static bool const include_degenerate = false;
+ static bool const include_opposite = false;
- template <typename Point1, typename Point2, typename Info>
- static inline void apply(Info& , Point1 const& , Point2 const& )
+ template
+ <
+ typename Info,
+ typename Point1,
+ typename Point2,
+ typename IntersectionInfo,
+ typename DirInfo
+ >
+ static inline void apply(Info& , Point1 const& , Point2 const&, IntersectionInfo const&, DirInfo const&)
{}
};
@@ -797,7 +882,7 @@
{
only_convert<TurnInfo>::apply(tp,
result.template get<0>());
- AssignPolicy::apply(tp, pi, qi);
+ AssignPolicy::apply(tp, pi, qi, result.template get<0>(), result.template get<1>());
*out++ = tp;
}
break;
@@ -825,7 +910,7 @@
policy::template apply<1>(qi, qj, qk, pi, pj, pk,
tp, result.template get<0>(), result.template get<1>());
}
- AssignPolicy::apply(tp, pi, qi);
+ AssignPolicy::apply(tp, pi, qi, result.template get<0>(), result.template get<1>());
*out++ = tp;
}
break;
@@ -839,7 +924,7 @@
policy::apply(pi, pj, pk, qi, qj, qk,
tp, result.template get<0>(), result.template get<1>());
- AssignPolicy::apply(tp, pi, qi);
+ AssignPolicy::apply(tp, pi, qi, result.template get<0>(), result.template get<1>());
*out++ = tp;
}
break;
@@ -854,7 +939,7 @@
policy::apply(pi, pj, pk, qi, qj, qk,
tp, result.template get<0>(), result.template get<1>());
- AssignPolicy::apply(tp, pi, qi);
+ AssignPolicy::apply(tp, pi, qi, result.template get<0>(), result.template get<1>());
*out++ = tp;
}
break;
@@ -872,10 +957,18 @@
policy::apply(pi, pj, pk, qi, qj, qk,
tp, result.template get<0>(), result.template get<1>());
- AssignPolicy::apply(tp, pi, qi);
+ AssignPolicy::apply(tp, pi, qi, result.template get<0>(), result.template get<1>());
*out++ = tp;
}
- // If they ARE opposite, don't do anything.
+ else
+ {
+ equal_opposite
+ <
+ TurnInfo,
+ AssignPolicy
+ >::apply(pi, qi,
+ tp, out, result.template get<0>(), result.template get<1>());
+ }
}
break;
case 'c' :
@@ -907,7 +1000,7 @@
tp, result.template get<0>(), result.template get<1>());
}
- AssignPolicy::apply(tp, pi, qi);
+ AssignPolicy::apply(tp, pi, qi, result.template get<0>(), result.template get<1>());
*out++ = tp;
}
else
@@ -928,7 +1021,7 @@
if (AssignPolicy::include_degenerate)
{
only_convert<TurnInfo>::apply(tp, result.template get<0>());
- AssignPolicy::apply(tp, pi, qi);
+ AssignPolicy::apply(tp, pi, qi, result.template get<0>(), result.template get<1>());
*out++ = tp;
}
}
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-02-26 15:00:05 EST (Sun, 26 Feb 2012)
@@ -28,7 +28,8 @@
operation_union,
operation_intersection,
operation_blocked,
- operation_continue
+ operation_continue,
+ operation_opposite
};
@@ -114,6 +115,10 @@
{
return both(operation_blocked);
}
+ inline bool opposite() const
+ {
+ return both(operation_opposite);
+ }
inline bool any_blocked() const
{
return this->operations[0].operation == operation_blocked
Modified: trunk/boost/geometry/algorithms/disjoint.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/disjoint.hpp (original)
+++ trunk/boost/geometry/algorithms/disjoint.hpp 2012-02-26 15:00:05 EST (Sun, 26 Feb 2012)
@@ -49,10 +49,19 @@
// We want to include all points:
static bool const include_no_turn = true;
static bool const include_degenerate = true;
+ static bool const include_opposite = true;
// We don't assign extra info:
- template <typename Point1, typename Point2, typename Info>
- static inline void apply(Info& , Point1 const& , Point2 const& )
+ template
+ <
+ typename Info,
+ typename Point1,
+ typename Point2,
+ typename IntersectionInfo,
+ typename DirInfo
+ >
+ static inline void apply(Info& , Point1 const& , Point2 const&,
+ IntersectionInfo const&, DirInfo const&)
{}
};
Modified: trunk/libs/geometry/test/algorithms/disjoint.cpp
==============================================================================
--- trunk/libs/geometry/test/algorithms/disjoint.cpp (original)
+++ trunk/libs/geometry/test/algorithms/disjoint.cpp 2012-02-26 15:00:05 EST (Sun, 26 Feb 2012)
@@ -113,6 +113,12 @@
test_disjoint<segment, segment>("s/s 1", "linestring(0 0,1 1)", "linestring(1 0,0 1)", false);
test_disjoint<segment, segment>("s/s 2", "linestring(0 0,1 1)", "linestring(1 0,2 1)", true);
+ // Collinear opposite
+ test_disjoint<ls, ls>("ls/ls co", "linestring(0 0,2 2)", "linestring(1 1,0 0)", false);
+ // Collinear opposite and equal
+ test_disjoint<ls, ls>("ls/ls co-e", "linestring(0 0,1 1)", "linestring(1 1,0 0)", false);
+
+
// Degenerate linestrings
{
// Submitted by Zachary on the Boost.Geometry Mailing List, on 2012-01-29