Boost logo

Boost-Commit :

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


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