[Boost-commit] svn:boost r72852 - in trunk/boost/geometry: algorithms/detail/overlay multi/algorithms/detail/overlay strategies/cartesian

Subject: [Boost-commit] svn:boost r72852 - in trunk/boost/geometry: algorithms/detail/overlay multi/algorithms/detail/overlay strategies/cartesian
From: barend.gehrels_at_[hidden]
Date: 2011-07-02 10:30:54

Author: barendgehrels
Date: 2011-07-02 10:30:53 EDT (Sat, 02 Jul 2011)
New Revision: 72852
URL: http://svn.boost.org/trac/boost/changeset/72852

Log:
Bugfix of case sent to list on 2011-06-27 by Phillip. To detect if geometry is within another, we use "point_on_border". We used a mid-point there (necessary for intersections), but, from now on, if there are no intersections, we should not use the mid-point because of robustness issues.
In other words, we should use the same point for both intersection-->side and within-->side.
Text files modified: 
   trunk/boost/geometry/algorithms/detail/overlay/overlay.hpp            |     6 ++--                                    
   trunk/boost/geometry/algorithms/detail/overlay/ring_properties.hpp    |     6 ++--                                    
   trunk/boost/geometry/algorithms/detail/overlay/select_rings.hpp       |    54 ++++++++++++++++++++++++--------------- 
   trunk/boost/geometry/multi/algorithms/detail/overlay/select_rings.hpp |     5 ++-                                     
   trunk/boost/geometry/strategies/cartesian/side_by_triangle.hpp        |     2                                         
   5 files changed, 43 insertions(+), 30 deletions(-)

Modified: trunk/boost/geometry/algorithms/detail/overlay/overlay.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/overlay/overlay.hpp	(original)
+++ trunk/boost/geometry/algorithms/detail/overlay/overlay.hpp	2011-07-02 10:30:53 EDT (Sat, 02 Jul 2011)
@@ -124,7 +124,7 @@
     std::map<ring_identifier, int> empty;
     std::map<ring_identifier, properties> all_of_one_of_them;
 
-    select_rings<Direction>(geometry1, geometry2, empty, all_of_one_of_them);
+    select_rings<Direction>(geometry1, geometry2, empty, all_of_one_of_them, false);
     ring_container_type rings;
     assign_parents(geometry1, geometry2, rings, all_of_one_of_them);
     return add_rings<GeometryOut>(all_of_one_of_them, geometry1, geometry2, rings, out);
@@ -236,7 +236,7 @@
         typedef ring_properties<typename geometry::point_type<Geometry1>::type> properties;
 
         std::map<ring_identifier, properties> selected;
-        select_rings<Direction>(geometry1, geometry2, map, selected);
+        select_rings<Direction>(geometry1, geometry2, map, selected, ! turn_points.empty());
 
 #ifdef BOOST_GEOMETRY_TIME_OVERLAY
         std::cout << "select_rings: " << timer.elapsed() << std::endl;
@@ -251,7 +251,7 @@
                     it != boost::end(rings);
                     ++it)
             {
-                selected[id] = properties(*it);
+                selected[id] = properties(*it, true);
                 selected[id].reversed = ReverseOut;
                 id.multi_index++;
             }

Modified: trunk/boost/geometry/algorithms/detail/overlay/ring_properties.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/overlay/ring_properties.hpp	(original)
+++ trunk/boost/geometry/algorithms/detail/overlay/ring_properties.hpp	2011-07-02 10:30:53 EDT (Sat, 02 Jul 2011)
@@ -52,17 +52,17 @@
     {}
 
     template <typename RingOrBox>
-    inline ring_properties(RingOrBox const& ring_or_box)
+    inline ring_properties(RingOrBox const& ring_or_box, bool midpoint)
         : within_code(-1)
         , reversed(false)
         , discarded(false)
         , parent_area(-1)
     {
         this->area = geometry::area(ring_or_box);
-        geometry::point_on_border(this->point, ring_or_box, true);
+        geometry::point_on_border(this->point, ring_or_box, midpoint);
     }
 
-    area_type get_area() const
+    inline area_type get_area() const
     {
         return reversed ? -area : area;
     }

Modified: trunk/boost/geometry/algorithms/detail/overlay/select_rings.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/overlay/select_rings.hpp	(original)
+++ trunk/boost/geometry/algorithms/detail/overlay/select_rings.hpp	2011-07-02 10:30:53 EDT (Sat, 02 Jul 2011)
@@ -40,15 +40,17 @@
     struct select_rings<box_tag, Box>
     {
         template <typename Geometry, typename Map>
-        static inline void apply(Box const& box, Geometry const& geometry, ring_identifier const& id, Map& map)
+        static inline void apply(Box const& box, Geometry const& geometry, 
+                ring_identifier const& id, Map& map, bool midpoint)
         {
-            map[id] = typename Map::mapped_type(box);
+            map[id] = typename Map::mapped_type(box, midpoint);
         }
 
         template <typename Map>
-        static inline void apply(Box const& box, ring_identifier const& id, Map& map)
+        static inline void apply(Box const& box, 
+                ring_identifier const& id, Map& map, bool midpoint)
         {
-            map[id] = typename Map::mapped_type(box);
+            map[id] = typename Map::mapped_type(box, midpoint);
         }
     };
 
@@ -56,20 +58,22 @@
     struct select_rings<ring_tag, Ring>
     {
         template <typename Geometry, typename Map>
-        static inline void apply(Ring const& ring, Geometry const& geometry, ring_identifier const& id, Map& map)
+        static inline void apply(Ring const& ring, Geometry const& geometry,
+                    ring_identifier const& id, Map& map, bool midpoint)
         {
             if (boost::size(ring) > 0)
             {
-                map[id] = typename Map::mapped_type(ring);
+                map[id] = typename Map::mapped_type(ring, midpoint);
             }
         }
 
         template <typename Map>
-        static inline void apply(Ring const& ring, ring_identifier const& id, Map& map)
+        static inline void apply(Ring const& ring, 
+                    ring_identifier const& id, Map& map, bool midpoint)
         {
             if (boost::size(ring) > 0)
             {
-                map[id] = typename Map::mapped_type(ring);
+                map[id] = typename Map::mapped_type(ring, midpoint);
             }
         }
     };
@@ -79,36 +83,38 @@
     struct select_rings<polygon_tag, Polygon>
     {
         template <typename Geometry, typename Map>
-        static inline void apply(Polygon const& polygon, Geometry const& geometry, ring_identifier id, Map& map)
+        static inline void apply(Polygon const& polygon, Geometry const& geometry,
+                    ring_identifier id, Map& map, bool midpoint)
         {
             typedef typename geometry::ring_type<Polygon>::type ring_type;
             typedef select_rings<ring_tag, ring_type> per_ring;
 
-            per_ring::apply(exterior_ring(polygon), geometry, id, map);
+            per_ring::apply(exterior_ring(polygon), geometry, id, map, midpoint);
 
             typename interior_return_type<Polygon const>::type rings
                         = interior_rings(polygon);
             for (BOOST_AUTO_TPL(it, boost::begin(rings)); it != boost::end(rings); ++it)
             {
                 id.ring_index++;
-                per_ring::apply(*it, geometry, id, map);
+                per_ring::apply(*it, geometry, id, map, midpoint);
             }
         }
 
         template <typename Map>
-        static inline void apply(Polygon const& polygon, ring_identifier id, Map& map)
+        static inline void apply(Polygon const& polygon,
+                ring_identifier id, Map& map, bool midpoint)
         {
             typedef typename geometry::ring_type<Polygon>::type ring_type;
             typedef select_rings<ring_tag, ring_type> per_ring;
 
-            per_ring::apply(exterior_ring(polygon), id, map);
+            per_ring::apply(exterior_ring(polygon), id, map, midpoint);
 
             typename interior_return_type<Polygon const>::type rings
                         = interior_rings(polygon);
             for (BOOST_AUTO_TPL(it, boost::begin(rings)); it != boost::end(rings); ++it)
             {
                 id.ring_index++;
-                per_ring::apply(*it, id, map);
+                per_ring::apply(*it, id, map, midpoint);
             }
         }
     };
@@ -203,7 +209,7 @@
         bool found = intersection_map.find(it->first) != intersection_map.end();
         if (! found)
         {
-            ring_identifier id = it->first;
+            ring_identifier const id = it->first;
             typename SelectionMap::mapped_type properties = it->second; // Copy by value
 
             // Calculate the "within code" (previously this was done earlier but is
@@ -242,16 +248,20 @@
     typename IntersectionMap, typename SelectionMap
 >
 inline void select_rings(Geometry1 const& geometry1, Geometry2 const& geometry2,
-            IntersectionMap const& intersection_map, SelectionMap& selection_map)
+            IntersectionMap const& intersection_map, 
+            SelectionMap& selection_map, bool midpoint)
 {
     typedef typename geometry::tag<Geometry1>::type tag1;
     typedef typename geometry::tag<Geometry2>::type tag2;
 
     SelectionMap map_with_all;
-    dispatch::select_rings<tag1, Geometry1>::apply(geometry1, geometry2, ring_identifier(0, -1, -1), map_with_all);
-    dispatch::select_rings<tag2, Geometry2>::apply(geometry2, geometry1, ring_identifier(1, -1, -1), map_with_all);
+    dispatch::select_rings<tag1, Geometry1>::apply(geometry1, geometry2,
+                ring_identifier(0, -1, -1), map_with_all, midpoint);
+    dispatch::select_rings<tag2, Geometry2>::apply(geometry2, geometry1,
+                ring_identifier(1, -1, -1), map_with_all, midpoint);
 
-    update_selection_map<OverlayType>(geometry1, geometry2, intersection_map, map_with_all, selection_map);
+    update_selection_map<OverlayType>(geometry1, geometry2, intersection_map,
+                map_with_all, selection_map);
 }
 
 template
@@ -266,9 +276,11 @@
     typedef typename geometry::tag<Geometry>::type tag;
 
     SelectionMap map_with_all;
-    dispatch::select_rings<tag, Geometry>::apply(geometry, ring_identifier(0, -1, -1), map_with_all);
+    dispatch::select_rings<tag, Geometry>::apply(geometry, 
+                ring_identifier(0, -1, -1), map_with_all);
 
-    update_selection_map<OverlayType>(intersection_map, map_with_all, selection_map);
+    update_selection_map<OverlayType>(intersection_map, map_with_all, 
+                selection_map);
 }
 
 

Modified: trunk/boost/geometry/multi/algorithms/detail/overlay/select_rings.hpp
==============================================================================
--- trunk/boost/geometry/multi/algorithms/detail/overlay/select_rings.hpp	(original)
+++ trunk/boost/geometry/multi/algorithms/detail/overlay/select_rings.hpp	2011-07-02 10:30:53 EDT (Sat, 02 Jul 2011)
@@ -30,7 +30,8 @@
     struct select_rings<multi_polygon_tag, Multi>
     {
         template <typename Geometry, typename Map>
-        static inline void apply(Multi const& multi, Geometry const& geometry, ring_identifier id, Map& map)
+        static inline void apply(Multi const& multi, Geometry const& geometry,
+                    ring_identifier id, Map& map, bool midpoint)
         {
             typedef typename boost::range_iterator
                 <
@@ -43,7 +44,7 @@
             for (iterator_type it = boost::begin(multi); it != boost::end(multi); ++it)
             {
                 id.ring_index = -1;
-                per_polygon::apply(*it, geometry, id, map);
+                per_polygon::apply(*it, geometry, id, map, midpoint);
                 id.multi_index++;
             }
         }

Modified: trunk/boost/geometry/strategies/cartesian/side_by_triangle.hpp
==============================================================================
--- trunk/boost/geometry/strategies/cartesian/side_by_triangle.hpp	(original)
+++ trunk/boost/geometry/strategies/cartesian/side_by_triangle.hpp	2011-07-02 10:30:53 EDT (Sat, 02 Jul 2011)
@@ -89,7 +89,7 @@
 
         promoted_type const s = dx * dpy - dy * dpx;
 
-        promoted_type zero = promoted_type();
+        promoted_type const zero = promoted_type();
         return math::equals(s, zero) ? 0 
             : s > zero ? 1 
             : -1;