[Boost-commit] svn:boost r77304 - trunk/boost/geometry/algorithms/detail/overlay

Subject: [Boost-commit] svn:boost r77304 - trunk/boost/geometry/algorithms/detail/overlay
From: barend.gehrels_at_[hidden]
Date: 2012-03-11 13:46:24

Author: barendgehrels
Date: 2012-03-11 13:46:23 EDT (Sun, 11 Mar 2012)
New Revision: 77304
URL: http://svn.boost.org/trac/boost/changeset/77304

Log:
[geometry] fixed robustness issue with non-consistent side-info in collinear case
Text files modified: 
   trunk/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp |    50 +++++++++++++++++++++++++++++++++++++-- 
   1 files changed, 47 insertions(+), 3 deletions(-)

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-03-11 13:46:23 EDT (Sun, 11 Mar 2012)
@@ -533,6 +533,13 @@
          - if P arrives and P turns right: intersection for P
          - if Q arrives and Q turns left: union for Q (=intersection for P)
          - if Q arrives and Q turns right: intersection for Q (=union for P)
+
+         ROBUSTNESS: p and q are collinear, so you would expect
+         that side qk//p1 == pk//q1. But that is not always the case
+         in near-epsilon ranges. Then decision logic is different.
+         If p arrives, q is further, so the angle qk//p1 is (normally) 
+         more precise than pk//p1
+
     */
     template
     <
@@ -555,10 +562,13 @@
         // Should not be 0, this is checked before
         BOOST_ASSERT(arrival != 0);
 
+        int const side_p = SideStrategy::apply(pi, pj, pk);
+        int const side_q = SideStrategy::apply(qi, qj, qk);
+
         // If p arrives, use p, else use q
         int const side_p_or_q = arrival == 1
-            ? SideStrategy::apply(pi, pj, pk)
-            : SideStrategy::apply(qi, qj, qk)
+            ? side_p
+            : side_q
             ;
 
         // See comments above,
@@ -574,9 +584,43 @@
         }
         else
         {
-            ui_else_iu(product == 1, ti);
+            int const side_pk = SideStrategy::apply(qi, qj, pk);
+            int const side_qk = SideStrategy::apply(pi, pj, qk);
+
+            if (side_pk != side_p || side_qk != side_q)
+            {
+                std::cout << " -> Collinear " 
+                    << " arr: " << arrival
+                    << " prod: " << product
+                    << " dir: " << side_p << " " << side_q
+                    << " rev: " << side_pk << " " << side_qk
+                    << std::endl;
+
+                handle_robustness(ti, product, side_p, side_q, side_pk, side_qk);
+            }
+            else
+            {
+                // The normal case
+                ui_else_iu(product == 1, ti);
+            }
         }
     }
+
+    static inline void handle_robustness(TurnInfo& ti,
+                    int product, 
+                    int side_p, int side_q,
+                    int side_pk, int side_qk)
+    {
+        bool take_ui = product == 1;
+        if (product == 1 && side_p == 1 && side_pk != 1
+            || product == -1 && side_q == 1 && side_qk != 1)
+        {
+            std::cout << " -> Reverse" << std::endl;
+            take_ui = ! take_ui;
+        }
+
+        ui_else_iu(take_ui, ti);
+    }
 };
 
 template