[Boost-commit] svn:boost r66587 - in sandbox/geometry: boost/geometry/algorithms boost/geometry/algorithms/detail/overlay libs/geometry/doc/testcases libs/geometry/test/multi/algorithms/overlay

Subject: [Boost-commit] svn:boost r66587 - in sandbox/geometry: boost/geometry/algorithms boost/geometry/algorithms/detail/overlay libs/geometry/doc/testcases libs/geometry/test/multi/algorithms/overlay
From: barend.gehrels_at_[hidden]
Date: 2010-11-15 04:38:38

Author: barendgehrels
Date: 2010-11-15 04:38:32 EST (Mon, 15 Nov 2010)
New Revision: 66587
URL: http://svn.boost.org/trac/boost/changeset/66587

Log:
Fixed last pie case (as multi-polygon)
Binary files modified: 
   sandbox/geometry/libs/geometry/doc/testcases/get_turn_info.ppt
   sandbox/geometry/libs/geometry/doc/testcases/overlay_cases.ppt
   sandbox/geometry/libs/geometry/doc/testcases/relate.ppt
Text files modified: 
   sandbox/geometry/boost/geometry/algorithms/correct.hpp                          |    17 +++                                     
   sandbox/geometry/boost/geometry/algorithms/detail/overlay/handle_tangencies.hpp |   181 ++++++++++++++++++++------------------- 
   sandbox/geometry/libs/geometry/test/multi/algorithms/overlay/multi_traverse.cpp |     4                                         
   3 files changed, 106 insertions(+), 96 deletions(-)

Modified: sandbox/geometry/boost/geometry/algorithms/correct.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/correct.hpp	(original)
+++ sandbox/geometry/boost/geometry/algorithms/correct.hpp	2010-11-15 04:38:32 EST (Mon, 15 Nov 2010)
@@ -101,6 +101,7 @@
 struct correct_ring
 {
     typedef typename point_type<Ring>::type point_type;
+    typedef typename coordinate_type<Ring>::type coordinate_type;
 
     typedef typename strategy::area::services::default_strategy
         <
@@ -138,7 +139,8 @@
         }
         // Check area
         Predicate predicate;
-        if (predicate(ring_area_type::apply(r, strategy_type()), 0))
+        coordinate_type const zero = 0;
+        if (predicate(ring_area_type::apply(r, strategy_type()), zero))
         {
             std::reverse(boost::begin(r), boost::end(r));
         }
@@ -151,10 +153,15 @@
 struct correct_polygon
 {
     typedef typename ring_type<Polygon>::type ring_type;
+    typedef typename coordinate_type<Polygon>::type coordinate_type;
 
     static inline void apply(Polygon& poly)
     {
-        correct_ring<ring_type, std::less<double> >::apply(exterior_ring(poly));
+        correct_ring
+            <
+                ring_type, 
+                std::less<coordinate_type> 
+            >::apply(exterior_ring(poly));
 
         typedef typename boost::range_iterator
             <
@@ -164,7 +171,11 @@
         for (iterator_type it = boost::begin(interior_rings(poly));
              it != boost::end(interior_rings(poly)); ++it)
         {
-            correct_ring<ring_type, std::greater<double> >::apply(*it);
+            correct_ring
+                <
+                    ring_type, 
+                    std::greater<coordinate_type> 
+                >::apply(*it);
         }
     }
 };

Modified: sandbox/geometry/boost/geometry/algorithms/detail/overlay/handle_tangencies.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/detail/overlay/handle_tangencies.hpp	(original)
+++ sandbox/geometry/boost/geometry/algorithms/detail/overlay/handle_tangencies.hpp	2010-11-15 04:38:32 EST (Mon, 15 Nov 2010)
@@ -51,7 +51,43 @@
     Strategy const& m_strategy;
 
     typedef typename Indexed::type turn_operation_type;
-    typedef typename geometry::point_type<Geometry1> point_type;
+    typedef typename geometry::point_type<Geometry1>::type point_type;
+    typedef geometry::segment<point_type const> segment_type;
+
+    // Determine how p/r and p/s are located.
+    template <typename P>
+    static inline void overlap_info(P const& pi, P const& pj,
+        P const& ri, P const& rj,
+        P const& si, P const& sj,
+        bool& pr_overlap, bool& ps_overlap, bool& rs_overlap)
+    {
+        // Determine how p/r and p/s are located.
+        // One of them is coming from opposite direction.
+
+        typedef strategy::intersection::relate_cartesian_segments
+            <
+                policies::relate::segments_intersection_points
+                    <
+                        segment_type,
+                        segment_type,
+                        segment_intersection_points<point_type>
+                    >
+            > policy;
+
+        segment_type p(pi, pj);
+        segment_type r(ri, rj);
+        segment_type s(si, sj);
+
+        // Get the intersection point (or two points)
+        segment_intersection_points<point_type> pr = policy::apply(p, r);
+        segment_intersection_points<point_type> ps = policy::apply(p, s);
+        segment_intersection_points<point_type> rs = policy::apply(r, s);
+
+        // Check on overlap
+        pr_overlap = pr.count == 2;
+        ps_overlap = ps.count == 2;
+        rs_overlap = rs.count == 2;
+    }
 
 
     inline void debug_consider(int order, Indexed const& left,
@@ -60,9 +96,8 @@
             std::string const& extra = "", bool ret = false
         ) const
     {
-        //if (skip) return;
+        if (skip) return;
 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
-        typedef typename geometry::point_type<Geometry1>::type point_type;
         point_type pi, pj, ri, rj, si, sj;
         geometry::copy_segment_points(m_geometry1, m_geometry2,
             left.subject.seg_id,
@@ -74,6 +109,8 @@
             right.subject.other_id,
             si, sj);
 
+        bool prc = false, psc = false, rsc = false;
+        overlap_info(pi, pj, ri, rj, si, sj, prc, psc, rsc);
         
         int const side_ri_p = m_strategy.apply(pi, pj, ri);
         int const side_rj_p = m_strategy.apply(pi, pj, rj);
@@ -100,7 +137,9 @@
                 << " ri//p: " << side_ri_p
                 << " si//p: " << side_si_p
                 << " si//r: " << side_si_r
-                << " idx: " << left.index << "/" << right.index;
+                << " cnts: " << int(prc) << ","  << int(psc) << "," << int(rsc)
+                //<< " idx: " << left.index << "/" << right.index
+                ;
 
         if (! extra.empty())
         {
@@ -207,7 +246,18 @@
     {
         debug_consider(0, left, right, header);
 
-        typedef typename geometry::point_type<Geometry1>::type point_type;
+        // In general, order it like "union, intersection".
+        if (left.subject.operation == operation_intersection
+            && right.subject.operation == operation_union)
+        {
+            return false;
+        }
+        else if (left.subject.operation == operation_union
+            && right.subject.operation == operation_intersection)
+        {
+            return true;
+        }
+
         point_type pi, pj, ri, rj, si, sj;
         geometry::copy_segment_points(m_geometry1, m_geometry2,
             left.subject.seg_id,
@@ -223,33 +273,17 @@
         int const side_si_p = m_strategy.apply(pi, pj, si);
         int const side_si_r = m_strategy.apply(ri, rj, si);
 
-        // TODO: harmonize the similar cases below now.
-
         // Both located at same side (#58, pie_21_7_21_0_3)
         if (side_ri_p * side_si_p == 1 && side_si_r != 0)
         {
             // Take the most left one
-            bool ret = false;
-
-            if (left.subject.operation == operation_intersection
-                && right.subject.operation == operation_union)
-            {
-                ret = false;
-            }
-            else if (left.subject.operation == operation_union
-                && right.subject.operation == operation_intersection)
-            {
-                ret = true;
-            }
-            else if (left.subject.operation == operation_union
+            if (left.subject.operation == operation_union
                 && right.subject.operation == operation_union)
             {
-                ret = side_si_r == 1;
+                bool ret = side_si_r == 1;
+                //debug_consider(0, left, right, header, false, "same side", ret);
+                return ret;
             }
-
-
-            //debug_consider(0, left, right, header, false, "same side", ret);
-            return ret;
         }
 
 
@@ -258,35 +292,19 @@
         {
             bool ret = false;
 
-            if (left.subject.operation == operation_intersection
-                && right.subject.operation == operation_union)
-            {
-                // #55_iet_iet: reverse this
-                ret = false;
-            }
-            else if (left.subject.operation == operation_union
-                && right.subject.operation == operation_intersection)
-            {
-                // #55_iet_iet: also.
-                ret = true;
-            }
-            else if (left.subject.operation == operation_union
-                && right.subject.operation == operation_union)
             {
                 ret = side_ri_p == 1; // #100
+                //debug_consider(0, left, right, header, false, "coming from opposite", ret);
+                return ret;
             }
-            else
-            {
 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
-                std::cout << " iu/iu coming from opposite unhandled" << std::endl;
+            std::cout << " iu/iu coming from opposite unhandled" << std::endl;
 #endif
-                ret = left.index < right.index;
-            }
-
-            //debug_consider(0, left, right, header, false, "coming from opposite", ret);
-            return ret;
         }
 
+        // We need EXTRA information here: are p/r/s overlapping?
+        bool pr_ov = false, ps_ov = false, rs_ov = false;
+        overlap_info(pi, pj, ri, rj, si, sj, pr_ov, ps_ov, rs_ov);
 
         // One coming from right (#83,#90)
         // One coming from left (#90, #94, #95)
@@ -294,66 +312,50 @@
         {
             bool ret = false;
 
-            if (left.subject.operation == operation_intersection
-                && right.subject.operation == operation_union)
+            if (pr_ov || ps_ov)
             {
-                ret = false;
-            }
-            else if (left.subject.operation == operation_union
-                && right.subject.operation == operation_intersection)
-            {
-                ret = true;
+                int r = side_ri_p != 0 ? side_ri_p : side_si_p;
+                ret = r * side_si_r == 1;
             }
-
             else
             {
-                // We need EXTRA information here.                
-                int r = side_ri_p != 0 ? side_ri_p : side_si_p;
-                ret = r * side_si_r == 1;
+                ret = side_si_r == 1;
             }
 
-            debug_consider(0, left, right, header, false, "other", ret);
+            //debug_consider(0, left, right, header, false, "other", ret);
             return ret;
         }
 
         // All aligned (#92, #96)
         if (side_ri_p == 0 && side_si_p == 0 && side_si_r == 0)
         {
-            // Determine how p/r and p/s are located.
             // One of them is coming from opposite direction.
-            typedef geometry::segment<const point_type> segment_type;
 
-            typedef strategy::intersection::relate_cartesian_segments
-                <
-                    policies::relate::segments_intersection_points
-                        <
-                            segment_type,
-                            segment_type,
-                            segment_intersection_points<point_type>
-                        >
-                > policy;
-
-            segment_type p(pi, pj);
-            segment_type r(ri, rj);
-            segment_type s(si, sj);
-
-            // Get the intersection point (or two points)
-            segment_intersection_points<point_type> pr = policy::apply(p, r);
-            segment_intersection_points<point_type> ps = policy::apply(p, s);
-
-            // Take the one NOT being collinear
-            if (pr.count == 2 && ps.count == 1) return true;
-            if (pr.count == 1 && ps.count == 2) return false;
-
-#ifdef BOOST_GEOMETRY_DEBUG_ENRICH
-            std::cout << "iu/iu all collinear unhandled" << std::endl;
-#endif
+            // Take the one NOT overlapping
+            bool ret = false;
+            bool found = false;
+            if (pr_ov && ! ps_ov) 
+            {
+                ret = true;
+                found = true;
+            }
+            else if (!pr_ov && ps_ov) 
+            {
+                ret = false;
+                found = true;
+            }
 
+            //debug_consider(0, left, right, header, false, "aligned", ret);
+            if (found)
+            {
+                return ret;
+            }
         }
 
-#ifdef BOOST_GEOMETRY_DEBUG_ENRICH
+//#ifdef BOOST_GEOMETRY_DEBUG_ENRICH
         std::cout << " iu/iu unhandled" << std::endl;
-#endif
+        debug_consider(0, left, right, header, false, "unhandled", left.index < right.index);
+//#endif
         return left.index < right.index;
     }
 
@@ -362,7 +364,6 @@
     {
         debug_consider(0, left, right, header);
 
-        typedef typename geometry::point_type<Geometry1>::type point_type;
         point_type pi, pj, ri, rj, si, sj;
         geometry::copy_segment_points(m_geometry1, m_geometry2,
             left.subject.seg_id,

Modified: sandbox/geometry/libs/geometry/doc/testcases/get_turn_info.ppt
==============================================================================
Binary files. No diff available.

Modified: sandbox/geometry/libs/geometry/doc/testcases/overlay_cases.ppt
==============================================================================
Binary files. No diff available.

Modified: sandbox/geometry/libs/geometry/doc/testcases/relate.ppt
==============================================================================
Binary files. No diff available.

Modified: sandbox/geometry/libs/geometry/test/multi/algorithms/overlay/multi_traverse.cpp
==============================================================================
--- sandbox/geometry/libs/geometry/test/multi/algorithms/overlay/multi_traverse.cpp	(original)
+++ sandbox/geometry/libs/geometry/test/multi/algorithms/overlay/multi_traverse.cpp	2010-11-15 04:38:32 EST (Mon, 15 Nov 2010)
@@ -467,12 +467,10 @@
             "pie_16_16_9_0_2", boost::make_tuple(2, 1146795),
             pie_16_16_9_0_2[0], pie_16_16_9_0_2[1]
         );
-return;
-wrong:
     test_overlay<multi_polygon, multi_polygon,
         test_traverse<ov::operation_intersection>,  Tuple>
         (
-            "pie_7_2_1_0_15", boost::make_tuple(2, 1146795),
+            "pie_7_2_1_0_15", boost::make_tuple(2, 490585.5),
             pie_7_2_1_0_15[0], pie_7_2_1_0_15[1]
         );