summaryrefslogtreecommitdiff
path: root/boost/geometry/algorithms/detail/overlay/select_rings.hpp
diff options
context:
space:
mode:
authorDongHun Kwak <dh0128.kwak@samsung.com>2016-03-21 15:45:20 +0900
committerDongHun Kwak <dh0128.kwak@samsung.com>2016-03-21 15:46:37 +0900
commit733b5d5ae2c5d625211e2985ac25728ac3f54883 (patch)
treea5b214744b256f07e1dc2bd7273035a7808c659f /boost/geometry/algorithms/detail/overlay/select_rings.hpp
parent08c1e93fa36a49f49325a07fe91ff92c964c2b6c (diff)
downloadboost-733b5d5ae2c5d625211e2985ac25728ac3f54883.tar.gz
boost-733b5d5ae2c5d625211e2985ac25728ac3f54883.tar.bz2
boost-733b5d5ae2c5d625211e2985ac25728ac3f54883.zip
Imported Upstream version 1.58.0upstream/1.58.0
Change-Id: If0072143aa26874812e0db6872e1efb10a3e5e94 Signed-off-by: DongHun Kwak <dh0128.kwak@samsung.com>
Diffstat (limited to 'boost/geometry/algorithms/detail/overlay/select_rings.hpp')
-rw-r--r--boost/geometry/algorithms/detail/overlay/select_rings.hpp217
1 files changed, 120 insertions, 97 deletions
diff --git a/boost/geometry/algorithms/detail/overlay/select_rings.hpp b/boost/geometry/algorithms/detail/overlay/select_rings.hpp
index 385658a190..d18e012b2d 100644
--- a/boost/geometry/algorithms/detail/overlay/select_rings.hpp
+++ b/boost/geometry/algorithms/detail/overlay/select_rings.hpp
@@ -1,6 +1,6 @@
// Boost.Geometry (aka GGL, Generic Geometry Library)
-// Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
+// Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands.
// Copyright (c) 2014 Adam Wulkiewicz, Lodz, Poland.
// Use, modification and distribution is subject to the Boost Software License,
@@ -20,7 +20,6 @@
#include <boost/geometry/algorithms/area.hpp>
#include <boost/geometry/algorithms/within.hpp>
#include <boost/geometry/algorithms/detail/interior_iterator.hpp>
-#include <boost/geometry/algorithms/detail/point_on_border.hpp>
#include <boost/geometry/algorithms/detail/ring_identifier.hpp>
#include <boost/geometry/algorithms/detail/overlay/ring_properties.hpp>
#include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
@@ -34,6 +33,18 @@ namespace boost { namespace geometry
namespace detail { namespace overlay
{
+struct ring_turn_info
+{
+ bool has_uu_turn;
+ bool has_normal_turn;
+ bool within_other;
+
+ ring_turn_info()
+ : has_uu_turn(false)
+ , has_normal_turn(false)
+ , within_other(false)
+ {}
+};
namespace dispatch
{
@@ -45,41 +56,41 @@ namespace dispatch
template <typename Box>
struct select_rings<box_tag, Box>
{
- template <typename Geometry, typename Map>
+ template <typename Geometry, typename RingPropertyMap>
static inline void apply(Box const& box, Geometry const& ,
- ring_identifier const& id, Map& map, bool midpoint)
+ ring_identifier const& id, RingPropertyMap& ring_properties)
{
- map[id] = typename Map::mapped_type(box, midpoint);
+ ring_properties[id] = typename RingPropertyMap::mapped_type(box);
}
- template <typename Map>
+ template <typename RingPropertyMap>
static inline void apply(Box const& box,
- ring_identifier const& id, Map& map, bool midpoint)
+ ring_identifier const& id, RingPropertyMap& ring_properties)
{
- map[id] = typename Map::mapped_type(box, midpoint);
+ ring_properties[id] = typename RingPropertyMap::mapped_type(box);
}
};
template <typename Ring>
struct select_rings<ring_tag, Ring>
{
- template <typename Geometry, typename Map>
+ template <typename Geometry, typename RingPropertyMap>
static inline void apply(Ring const& ring, Geometry const& ,
- ring_identifier const& id, Map& map, bool midpoint)
+ ring_identifier const& id, RingPropertyMap& ring_properties)
{
if (boost::size(ring) > 0)
{
- map[id] = typename Map::mapped_type(ring, midpoint);
+ ring_properties[id] = typename RingPropertyMap::mapped_type(ring);
}
}
- template <typename Map>
+ template <typename RingPropertyMap>
static inline void apply(Ring const& ring,
- ring_identifier const& id, Map& map, bool midpoint)
+ ring_identifier const& id, RingPropertyMap& ring_properties)
{
if (boost::size(ring) > 0)
{
- map[id] = typename Map::mapped_type(ring, midpoint);
+ ring_properties[id] = typename RingPropertyMap::mapped_type(ring);
}
}
};
@@ -88,14 +99,14 @@ namespace dispatch
template <typename Polygon>
struct select_rings<polygon_tag, Polygon>
{
- template <typename Geometry, typename Map>
+ template <typename Geometry, typename RingPropertyMap>
static inline void apply(Polygon const& polygon, Geometry const& geometry,
- ring_identifier id, Map& map, bool midpoint)
+ ring_identifier id, RingPropertyMap& ring_properties)
{
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, midpoint);
+ per_ring::apply(exterior_ring(polygon), geometry, id, ring_properties);
typename interior_return_type<Polygon const>::type
rings = interior_rings(polygon);
@@ -103,18 +114,18 @@ namespace dispatch
it = boost::begin(rings); it != boost::end(rings); ++it)
{
id.ring_index++;
- per_ring::apply(*it, geometry, id, map, midpoint);
+ per_ring::apply(*it, geometry, id, ring_properties);
}
}
- template <typename Map>
+ template <typename RingPropertyMap>
static inline void apply(Polygon const& polygon,
- ring_identifier id, Map& map, bool midpoint)
+ ring_identifier id, RingPropertyMap& ring_properties)
{
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, midpoint);
+ per_ring::apply(exterior_ring(polygon), id, ring_properties);
typename interior_return_type<Polygon const>::type
rings = interior_rings(polygon);
@@ -122,7 +133,7 @@ namespace dispatch
it = boost::begin(rings); it != boost::end(rings); ++it)
{
id.ring_index++;
- per_ring::apply(*it, id, map, midpoint);
+ per_ring::apply(*it, id, ring_properties);
}
}
};
@@ -130,9 +141,9 @@ namespace dispatch
template <typename Multi>
struct select_rings<multi_polygon_tag, Multi>
{
- template <typename Geometry, typename Map>
+ template <typename Geometry, typename RingPropertyMap>
static inline void apply(Multi const& multi, Geometry const& geometry,
- ring_identifier id, Map& map, bool midpoint)
+ ring_identifier id, RingPropertyMap& ring_properties)
{
typedef typename boost::range_iterator
<
@@ -145,7 +156,7 @@ namespace dispatch
for (iterator_type it = boost::begin(multi); it != boost::end(multi); ++it)
{
id.ring_index = -1;
- per_polygon::apply(*it, geometry, id, map, midpoint);
+ per_polygon::apply(*it, geometry, id, ring_properties);
id.multi_index++;
}
}
@@ -161,14 +172,12 @@ struct decide
template<>
struct decide<overlay_union>
{
- template <typename Code>
- static bool include(ring_identifier const& , Code const& code)
+ static bool include(ring_identifier const& , ring_turn_info const& info)
{
- return code.within_code * -1 == 1;
+ return info.has_uu_turn || ! info.within_other;
}
- template <typename Code>
- static bool reversed(ring_identifier const& , Code const& )
+ static bool reversed(ring_identifier const& , ring_turn_info const& )
{
return false;
}
@@ -177,31 +186,43 @@ struct decide<overlay_union>
template<>
struct decide<overlay_difference>
{
- template <typename Code>
- static bool include(ring_identifier const& id, Code const& code)
+ static bool include(ring_identifier const& id, ring_turn_info const& info)
{
- bool is_first = id.source_index == 0;
- return code.within_code * -1 * (is_first ? 1 : -1) == 1;
+ // Difference: A - B
+
+ // If this is A (source_index=0) and there is only a u/u turn,
+ // then the ring is inside B
+ // If this is B (source_index=1) and there is only a u/u turn,
+ // then the ring is NOT inside A
+
+ // If this is A and the ring is within the other geometry,
+ // then we should NOT include it.
+ // If this is B then we SHOULD include it.
+
+ bool const is_first = id.source_index == 0;
+ bool const within_other = info.within_other
+ || (is_first && info.has_uu_turn);
+ return is_first ? ! within_other : within_other;
}
- template <typename Code>
- static bool reversed(ring_identifier const& id, Code const& code)
+ static bool reversed(ring_identifier const& id, ring_turn_info const& info)
{
- return include(id, code) && id.source_index == 1;
+ // Difference: A - B
+ // If this is B, and the ring is included, it should be reversed afterwards
+
+ return id.source_index == 1 && include(id, info);
}
};
template<>
struct decide<overlay_intersection>
{
- template <typename Code>
- static bool include(ring_identifier const& , Code const& code)
+ static bool include(ring_identifier const& , ring_turn_info const& info)
{
- return code.within_code * 1 == 1;
+ return ! info.has_uu_turn && info.within_other;
}
- template <typename Code>
- static bool reversed(ring_identifier const& , Code const& )
+ static bool reversed(ring_identifier const& , ring_turn_info const& )
{
return false;
}
@@ -211,61 +232,60 @@ struct decide<overlay_intersection>
template
<
overlay_type OverlayType,
- typename Geometry1, typename Geometry2,
- typename IntersectionMap, typename SelectionMap
+ typename Geometry1,
+ typename Geometry2,
+ typename TurnInfoMap,
+ typename RingPropertyMap
>
-inline void update_selection_map(Geometry1 const& geometry1,
+inline void update_ring_selection(Geometry1 const& geometry1,
Geometry2 const& geometry2,
- IntersectionMap const& intersection_map,
- SelectionMap const& map_with_all, SelectionMap& selection_map)
+ TurnInfoMap const& turn_info_map,
+ RingPropertyMap const& all_ring_properties,
+ RingPropertyMap& selected_ring_properties)
{
- selection_map.clear();
+ selected_ring_properties.clear();
- for (typename SelectionMap::const_iterator it = boost::begin(map_with_all);
- it != boost::end(map_with_all);
+ for (typename RingPropertyMap::const_iterator it = boost::begin(all_ring_properties);
+ it != boost::end(all_ring_properties);
++it)
{
- /*
- int union_code = it->second.within_code * -1;
- bool is_first = it->first.source_index == 0;
- std::cout << it->first << " " << it->second.area
- << ": " << it->second.within_code
- << " union: " << union_code
- << " intersection: " << (it->second.within_code * 1)
- << " G1-G2: " << (union_code * (is_first ? 1 : -1))
- << " G2-G1: " << (union_code * (is_first ? -1 : 1))
- << " -> " << (decide<OverlayType>::include(it->first, it->second) ? "INC" : "")
- << decide<OverlayType>::reverse(it->first, it->second)
- << std::endl;
- */
-
- bool found = intersection_map.find(it->first) != intersection_map.end();
- if (! found)
+ ring_identifier const& id = it->first;
+
+ ring_turn_info info;
+
+ typename TurnInfoMap::const_iterator tcit = turn_info_map.find(id);
+ if (tcit != turn_info_map.end())
{
- ring_identifier const id = it->first;
- typename SelectionMap::mapped_type properties = it->second; // Copy by value
+ info = tcit->second; // Copy by value
+ }
- // Calculate the "within code" (previously this was done earlier but is
- // much efficienter here - it can be even more efficient doing it all at once,
- // using partition, TODO)
- // So though this is less elegant than before, it avoids many unused point-in-poly calculations
+ if (info.has_normal_turn)
+ {
+ // There are normal turns on this ring. It should be traversed, we
+ // don't include the original ring
+ continue;
+ }
+
+ if (! info.has_uu_turn)
+ {
+ // Check if the ring is within the other geometry, by taking
+ // a point lying on the ring
switch(id.source_index)
{
case 0 :
- properties.within_code
- = geometry::within(properties.point, geometry2) ? 1 : -1;
+ info.within_other = geometry::within(it->second.point, geometry2);
break;
case 1 :
- properties.within_code
- = geometry::within(properties.point, geometry1) ? 1 : -1;
+ info.within_other = geometry::within(it->second.point, geometry1);
break;
}
+ }
- if (decide<OverlayType>::include(id, properties))
- {
- properties.reversed = decide<OverlayType>::reversed(id, properties);
- selection_map[id] = properties;
- }
+ if (decide<OverlayType>::include(id, info))
+ {
+ typename RingPropertyMap::mapped_type properties = it->second; // Copy by value
+ properties.reversed = decide<OverlayType>::reversed(id, info);
+ selected_ring_properties[id] = properties;
}
}
}
@@ -277,44 +297,47 @@ inline void update_selection_map(Geometry1 const& geometry1,
template
<
overlay_type OverlayType,
- typename Geometry1, typename Geometry2,
- typename IntersectionMap, typename SelectionMap
+ typename Geometry1,
+ typename Geometry2,
+ typename RingTurnInfoMap,
+ typename RingPropertyMap
>
inline void select_rings(Geometry1 const& geometry1, Geometry2 const& geometry2,
- IntersectionMap const& intersection_map,
- SelectionMap& selection_map, bool midpoint)
+ RingTurnInfoMap const& turn_info_per_ring,
+ RingPropertyMap& selected_ring_properties)
{
typedef typename geometry::tag<Geometry1>::type tag1;
typedef typename geometry::tag<Geometry2>::type tag2;
- SelectionMap map_with_all;
+ RingPropertyMap all_ring_properties;
dispatch::select_rings<tag1, Geometry1>::apply(geometry1, geometry2,
- ring_identifier(0, -1, -1), map_with_all, midpoint);
+ ring_identifier(0, -1, -1), all_ring_properties);
dispatch::select_rings<tag2, Geometry2>::apply(geometry2, geometry1,
- ring_identifier(1, -1, -1), map_with_all, midpoint);
+ ring_identifier(1, -1, -1), all_ring_properties);
- update_selection_map<OverlayType>(geometry1, geometry2, intersection_map,
- map_with_all, selection_map);
+ update_ring_selection<OverlayType>(geometry1, geometry2, turn_info_per_ring,
+ all_ring_properties, selected_ring_properties);
}
template
<
overlay_type OverlayType,
typename Geometry,
- typename IntersectionMap, typename SelectionMap
+ typename RingTurnInfoMap,
+ typename RingPropertyMap
>
inline void select_rings(Geometry const& geometry,
- IntersectionMap const& intersection_map,
- SelectionMap& selection_map, bool midpoint)
+ RingTurnInfoMap const& turn_info_per_ring,
+ RingPropertyMap& selected_ring_properties)
{
typedef typename geometry::tag<Geometry>::type tag;
- SelectionMap map_with_all;
+ RingPropertyMap all_ring_properties;
dispatch::select_rings<tag, Geometry>::apply(geometry,
- ring_identifier(0, -1, -1), map_with_all, midpoint);
+ ring_identifier(0, -1, -1), all_ring_properties);
- update_selection_map<OverlayType>(geometry, geometry, intersection_map,
- map_with_all, selection_map);
+ update_ring_selection<OverlayType>(geometry, geometry, turn_info_per_ring,
+ all_ring_properties, selected_ring_properties);
}