summaryrefslogtreecommitdiff
path: root/boost/geometry/algorithms/detail/overlay/assign_parents.hpp
diff options
context:
space:
mode:
authorDongHun Kwak <dh0128.kwak@samsung.com>2017-09-13 11:24:46 +0900
committerDongHun Kwak <dh0128.kwak@samsung.com>2017-09-13 11:25:39 +0900
commit4fadd968fa12130524c8380f33fcfe25d4de79e5 (patch)
treefd26a490cd15388d42fc6652b3c5c13012e7f93e /boost/geometry/algorithms/detail/overlay/assign_parents.hpp
parentb5c87084afaef42b2d058f68091be31988a6a874 (diff)
downloadboost-4fadd968fa12130524c8380f33fcfe25d4de79e5.tar.gz
boost-4fadd968fa12130524c8380f33fcfe25d4de79e5.tar.bz2
boost-4fadd968fa12130524c8380f33fcfe25d4de79e5.zip
Imported Upstream version 1.65.0upstream/1.65.0
Change-Id: Icf8400b375482cb11bcf77440a6934ba360d6ba4 Signed-off-by: DongHun Kwak <dh0128.kwak@samsung.com>
Diffstat (limited to 'boost/geometry/algorithms/detail/overlay/assign_parents.hpp')
-rw-r--r--boost/geometry/algorithms/detail/overlay/assign_parents.hpp136
1 files changed, 100 insertions, 36 deletions
diff --git a/boost/geometry/algorithms/detail/overlay/assign_parents.hpp b/boost/geometry/algorithms/detail/overlay/assign_parents.hpp
index 2408b4b68e..78160f5204 100644
--- a/boost/geometry/algorithms/detail/overlay/assign_parents.hpp
+++ b/boost/geometry/algorithms/detail/overlay/assign_parents.hpp
@@ -20,7 +20,8 @@
#include <boost/geometry/algorithms/expand.hpp>
#include <boost/geometry/algorithms/detail/partition.hpp>
#include <boost/geometry/algorithms/detail/overlay/get_ring.hpp>
-#include <boost/geometry/algorithms/within.hpp>
+#include <boost/geometry/algorithms/detail/overlay/range_in_geometry.hpp>
+#include <boost/geometry/algorithms/covered_by.hpp>
#include <boost/geometry/geometries/box.hpp>
@@ -37,50 +38,88 @@ namespace detail { namespace overlay
template
<
typename Item,
+ typename InnerGeometry,
typename Geometry1, typename Geometry2,
- typename RingCollection
+ typename RingCollection,
+ typename Strategy
+>
+static inline bool within_selected_input(Item const& item2,
+ InnerGeometry const& inner_geometry,
+ ring_identifier const& outer_id,
+ Geometry1 const& geometry1, Geometry2 const& geometry2,
+ RingCollection const& collection,
+ Strategy const& strategy)
+{
+ typedef typename geometry::tag<Geometry1>::type tag1;
+ typedef typename geometry::tag<Geometry2>::type tag2;
+
+ // NOTE: range_in_geometry first checks the item2.point and then
+ // if this point is on boundary it checks points of inner_geometry
+ // ring until a point inside/outside other geometry ring is found
+ switch (outer_id.source_index)
+ {
+ // covered_by
+ case 0 :
+ return range_in_geometry(item2.point, inner_geometry,
+ get_ring<tag1>::apply(outer_id, geometry1), strategy) >= 0;
+ case 1 :
+ return range_in_geometry(item2.point, inner_geometry,
+ get_ring<tag2>::apply(outer_id, geometry2), strategy) >= 0;
+ case 2 :
+ return range_in_geometry(item2.point, inner_geometry,
+ get_ring<void>::apply(outer_id, collection), strategy) >= 0;
+ }
+ return false;
+}
+
+template
+<
+ typename Item,
+ typename Geometry1, typename Geometry2,
+ typename RingCollection,
+ typename Strategy
>
-static inline bool within_selected_input(Item const& item2, ring_identifier const& ring_id,
+static inline bool within_selected_input(Item const& item2,
+ ring_identifier const& inner_id, ring_identifier const& outer_id,
Geometry1 const& geometry1, Geometry2 const& geometry2,
- RingCollection const& collection)
+ RingCollection const& collection,
+ Strategy const& strategy)
{
typedef typename geometry::tag<Geometry1>::type tag1;
typedef typename geometry::tag<Geometry2>::type tag2;
- switch (ring_id.source_index)
+ switch (inner_id.source_index)
{
case 0 :
- return geometry::within(item2.point,
- get_ring<tag1>::apply(ring_id, geometry1));
- break;
+ return within_selected_input(item2,
+ get_ring<tag1>::apply(inner_id, geometry1),
+ outer_id, geometry1, geometry2, collection, strategy);
case 1 :
- return geometry::within(item2.point,
- get_ring<tag2>::apply(ring_id, geometry2));
- break;
+ return within_selected_input(item2,
+ get_ring<tag2>::apply(inner_id, geometry2),
+ outer_id, geometry1, geometry2, collection, strategy);
case 2 :
- return geometry::within(item2.point,
- get_ring<void>::apply(ring_id, collection));
- break;
+ return within_selected_input(item2,
+ get_ring<void>::apply(inner_id, collection),
+ outer_id, geometry1, geometry2, collection, strategy);
}
return false;
}
-template <typename Point>
+template <typename Point, typename AreaType>
struct ring_info_helper
{
- typedef typename geometry::default_area_result<Point>::type area_type;
-
ring_identifier id;
- area_type real_area;
- area_type abs_area;
+ AreaType real_area;
+ AreaType abs_area;
model::box<Point> envelope;
inline ring_info_helper()
: real_area(0), abs_area(0)
{}
- inline ring_info_helper(ring_identifier i, area_type a)
+ inline ring_info_helper(ring_identifier i, AreaType const& a)
: id(i), real_area(a), abs_area(geometry::math::abs(a))
{}
};
@@ -104,7 +143,14 @@ struct ring_info_helper_ovelaps_box
}
};
-template <typename Geometry1, typename Geometry2, typename Collection, typename RingMap>
+template
+<
+ typename Geometry1,
+ typename Geometry2,
+ typename Collection,
+ typename RingMap,
+ typename Strategy
+>
struct assign_visitor
{
typedef typename RingMap::mapped_type ring_info_type;
@@ -113,26 +159,27 @@ struct assign_visitor
Geometry2 const& m_geometry2;
Collection const& m_collection;
RingMap& m_ring_map;
+ Strategy const& m_strategy;
bool m_check_for_orientation;
-
inline assign_visitor(Geometry1 const& g1, Geometry2 const& g2, Collection const& c,
- RingMap& map, bool check)
+ RingMap& map, Strategy const& strategy, bool check)
: m_geometry1(g1)
, m_geometry2(g2)
, m_collection(c)
, m_ring_map(map)
+ , m_strategy(strategy)
, m_check_for_orientation(check)
{}
template <typename Item>
- inline void apply(Item const& outer, Item const& inner, bool first = true)
+ inline bool apply(Item const& outer, Item const& inner, bool first = true)
{
if (first && outer.abs_area < inner.abs_area)
{
// Apply with reversed arguments
apply(inner, outer, false);
- return;
+ return true;
}
if (m_check_for_orientation
@@ -141,8 +188,10 @@ struct assign_visitor
{
ring_info_type& inner_in_map = m_ring_map[inner.id];
- if (geometry::within(inner_in_map.point, outer.envelope)
- && within_selected_input(inner_in_map, outer.id, m_geometry1, m_geometry2, m_collection)
+ if (geometry::covered_by(inner_in_map.point, outer.envelope)
+ && within_selected_input(inner_in_map, inner.id, outer.id,
+ m_geometry1, m_geometry2, m_collection,
+ m_strategy)
)
{
// Assign a parent if there was no earlier parent, or the newly
@@ -155,6 +204,8 @@ struct assign_visitor
}
}
}
+
+ return true;
}
};
@@ -165,12 +216,14 @@ template
<
typename Geometry1, typename Geometry2,
typename RingCollection,
- typename RingMap
+ typename RingMap,
+ typename Strategy
>
inline void assign_parents(Geometry1 const& geometry1,
Geometry2 const& geometry2,
RingCollection const& collection,
RingMap& ring_map,
+ Strategy const& strategy,
bool check_for_orientation = false)
{
typedef typename geometry::tag<Geometry1>::type tag1;
@@ -179,11 +232,15 @@ inline void assign_parents(Geometry1 const& geometry1,
typedef typename RingMap::mapped_type ring_info_type;
typedef typename ring_info_type::point_type point_type;
typedef model::box<point_type> box_type;
+ typedef typename Strategy::template area_strategy
+ <
+ point_type
+ >::type::return_type area_result_type;
typedef typename RingMap::iterator map_iterator_type;
{
- typedef ring_info_helper<point_type> helper;
+ typedef ring_info_helper<point_type, area_result_type> helper;
typedef std::vector<helper> vector_type;
typedef typename boost::range_iterator<vector_type const>::type vector_iterator_type;
@@ -204,17 +261,21 @@ inline void assign_parents(Geometry1 const& geometry1,
{
case 0 :
geometry::envelope(get_ring<tag1>::apply(it->first, geometry1),
- item.envelope);
+ item.envelope, strategy.get_envelope_strategy());
break;
case 1 :
geometry::envelope(get_ring<tag2>::apply(it->first, geometry2),
- item.envelope);
+ item.envelope, strategy.get_envelope_strategy());
break;
case 2 :
geometry::envelope(get_ring<void>::apply(it->first, collection),
- item.envelope);
+ item.envelope, strategy.get_envelope_strategy());
break;
}
+
+ // Expand envelope slightly
+ expand_by_epsilon(item.envelope);
+
if (item.real_area > 0)
{
count_positive++;
@@ -257,8 +318,9 @@ inline void assign_parents(Geometry1 const& geometry1,
assign_visitor
<
Geometry1, Geometry2,
- RingCollection, RingMap
- > visitor(geometry1, geometry2, collection, ring_map, check_for_orientation);
+ RingCollection, RingMap,
+ Strategy
+ > visitor(geometry1, geometry2, collection, ring_map, strategy, check_for_orientation);
geometry::partition
<
@@ -315,18 +377,20 @@ template
<
typename Geometry,
typename RingCollection,
- typename RingMap
+ typename RingMap,
+ typename Strategy
>
inline void assign_parents(Geometry const& geometry,
RingCollection const& collection,
RingMap& ring_map,
+ Strategy const& strategy,
bool check_for_orientation)
{
// Call it with an empty geometry as second geometry (source_id == 1)
// (ring_map should be empty for source_id==1)
Geometry empty;
- assign_parents(geometry, empty, collection, ring_map, check_for_orientation);
+ assign_parents(geometry, empty, collection, ring_map, strategy, check_for_orientation);
}