summaryrefslogtreecommitdiff
path: root/boost/geometry/algorithms/detail/is_valid
diff options
context:
space:
mode:
Diffstat (limited to 'boost/geometry/algorithms/detail/is_valid')
-rw-r--r--boost/geometry/algorithms/detail/is_valid/has_spikes.hpp15
-rw-r--r--boost/geometry/algorithms/detail/is_valid/has_valid_self_turns.hpp2
-rw-r--r--boost/geometry/algorithms/detail/is_valid/is_acceptable_turn.hpp13
-rw-r--r--boost/geometry/algorithms/detail/is_valid/linear.hpp36
-rw-r--r--boost/geometry/algorithms/detail/is_valid/multipolygon.hpp75
-rw-r--r--boost/geometry/algorithms/detail/is_valid/polygon.hpp155
-rw-r--r--boost/geometry/algorithms/detail/is_valid/ring.hpp7
7 files changed, 223 insertions, 80 deletions
diff --git a/boost/geometry/algorithms/detail/is_valid/has_spikes.hpp b/boost/geometry/algorithms/detail/is_valid/has_spikes.hpp
index aa90e52db6..96efec79cd 100644
--- a/boost/geometry/algorithms/detail/is_valid/has_spikes.hpp
+++ b/boost/geometry/algorithms/detail/is_valid/has_spikes.hpp
@@ -1,8 +1,9 @@
// Boost.Geometry (aka GGL, Generic Geometry Library)
-// Copyright (c) 2014-2015, Oracle and/or its affiliates.
+// Copyright (c) 2014-2017, Oracle and/or its affiliates.
// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
+// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
// Licensed under the Boost Software License version 1.0.
// http://www.boost.org/users/license.html
@@ -91,8 +92,9 @@ struct has_spikes
return std::find_if(second, last, not_equal(*first));
}
- template <typename VisitPolicy>
- static inline bool apply(Range const& range, VisitPolicy& visitor)
+ template <typename VisitPolicy, typename SideStrategy>
+ static inline bool apply(Range const& range, VisitPolicy& visitor,
+ SideStrategy const& strategy)
{
boost::ignore_unused(visitor);
@@ -124,9 +126,8 @@ struct has_spikes
while (next != boost::end(view))
{
- if ( geometry::detail::point_is_spike_or_equal(*prev,
- *next,
- *cur) )
+ if ( geometry::detail::point_is_spike_or_equal(*prev, *next, *cur,
+ strategy) )
{
return
! visitor.template apply<failure_spikes>(is_linear, *cur);
@@ -146,7 +147,7 @@ struct has_spikes
boost::rend(view));
iterator next = find_different_from_first(cur, boost::end(view));
- if (detail::point_is_spike_or_equal(*prev, *next, *cur))
+ if (detail::point_is_spike_or_equal(*prev, *next, *cur, strategy))
{
return
! visitor.template apply<failure_spikes>(is_linear, *cur);
diff --git a/boost/geometry/algorithms/detail/is_valid/has_valid_self_turns.hpp b/boost/geometry/algorithms/detail/is_valid/has_valid_self_turns.hpp
index b91dc6a697..b36e9f38b7 100644
--- a/boost/geometry/algorithms/detail/is_valid/has_valid_self_turns.hpp
+++ b/boost/geometry/algorithms/detail/is_valid/has_valid_self_turns.hpp
@@ -86,7 +86,7 @@ public:
IsAcceptableTurn
> interrupt_policy;
- geometry::self_turns<turn_policy>(geometry,
+ detail::self_get_turn_points::self_turns<false, turn_policy>(geometry,
strategy,
robust_policy,
turns,
diff --git a/boost/geometry/algorithms/detail/is_valid/is_acceptable_turn.hpp b/boost/geometry/algorithms/detail/is_valid/is_acceptable_turn.hpp
index 0d80d6f6c0..fccc0ffdb7 100644
--- a/boost/geometry/algorithms/detail/is_valid/is_acceptable_turn.hpp
+++ b/boost/geometry/algorithms/detail/is_valid/is_acceptable_turn.hpp
@@ -138,10 +138,17 @@ public:
}
operation_type const op = acceptable_operation<MultiPolygon>::value;
+ if ( base::check_turn(turn, method_touch_interior, op)
+ || base::check_turn(turn, method_touch, op))
+ {
+ return true;
+ }
- return base::check_turn(turn, method_touch_interior, op)
- || base::check_turn(turn, method_touch, op)
- ;
+ // Turn is acceptable only in case of a touch(interior) and both lines
+ // (polygons) do not cross
+ return (turn.method == method_touch
+ || turn.method == method_touch_interior)
+ && turn.touch_only;
}
};
diff --git a/boost/geometry/algorithms/detail/is_valid/linear.hpp b/boost/geometry/algorithms/detail/is_valid/linear.hpp
index 6bc6b86cf8..39cb36ef5b 100644
--- a/boost/geometry/algorithms/detail/is_valid/linear.hpp
+++ b/boost/geometry/algorithms/detail/is_valid/linear.hpp
@@ -43,9 +43,10 @@ namespace detail { namespace is_valid
template <typename Linestring>
struct is_valid_linestring
{
- template <typename VisitPolicy>
+ template <typename VisitPolicy, typename Strategy>
static inline bool apply(Linestring const& linestring,
- VisitPolicy& visitor)
+ VisitPolicy& visitor,
+ Strategy const& strategy)
{
if (has_invalid_coordinate<Linestring>::apply(linestring, visitor))
{
@@ -75,15 +76,12 @@ struct is_valid_linestring
{
return visitor.template apply<no_failure>();
}
- return ! has_spikes<Linestring, closed>::apply(linestring, visitor);
- }
- template <typename VisitPolicy, typename Strategy>
- static inline bool apply(Linestring const& linestring,
- VisitPolicy& visitor,
- Strategy const&)
- {
- return apply(linestring, visitor);
+ return ! has_spikes
+ <
+ Linestring, closed
+ >::apply(linestring, visitor,
+ strategy.get_side_strategy());
}
};
@@ -132,10 +130,13 @@ class is_valid
>
{
private:
- template <typename VisitPolicy>
+ template <typename VisitPolicy, typename Strategy>
struct per_linestring
{
- per_linestring(VisitPolicy& policy) : m_policy(policy) {}
+ per_linestring(VisitPolicy& policy, Strategy const& strategy)
+ : m_policy(policy)
+ , m_strategy(strategy)
+ {}
template <typename Linestring>
inline bool apply(Linestring const& linestring) const
@@ -143,17 +144,18 @@ private:
return detail::is_valid::is_valid_linestring
<
Linestring
- >::apply(linestring, m_policy);
+ >::apply(linestring, m_policy, m_strategy);
}
VisitPolicy& m_policy;
+ Strategy const& m_strategy;
};
public:
template <typename VisitPolicy, typename Strategy>
static inline bool apply(MultiLinestring const& multilinestring,
VisitPolicy& visitor,
- Strategy const&)
+ Strategy const& strategy)
{
if (BOOST_GEOMETRY_CONDITION(
AllowEmptyMultiGeometries && boost::empty(multilinestring)))
@@ -161,13 +163,15 @@ public:
return visitor.template apply<no_failure>();
}
+ typedef per_linestring<VisitPolicy, Strategy> per_ls;
+
return detail::check_iterator_range
<
- per_linestring<VisitPolicy>,
+ per_ls,
false // do not check for empty multilinestring (done above)
>::apply(boost::begin(multilinestring),
boost::end(multilinestring),
- per_linestring<VisitPolicy>(visitor));
+ per_ls(visitor, strategy));
}
};
diff --git a/boost/geometry/algorithms/detail/is_valid/multipolygon.hpp b/boost/geometry/algorithms/detail/is_valid/multipolygon.hpp
index 84dacc57f1..ed24b13810 100644
--- a/boost/geometry/algorithms/detail/is_valid/multipolygon.hpp
+++ b/boost/geometry/algorithms/detail/is_valid/multipolygon.hpp
@@ -76,45 +76,66 @@ private:
<
typename PolygonIterator,
typename TurnIterator,
- typename VisitPolicy
+ typename VisitPolicy,
+ typename Strategy
>
static inline
bool are_polygon_interiors_disjoint(PolygonIterator polygons_first,
PolygonIterator polygons_beyond,
TurnIterator turns_first,
TurnIterator turns_beyond,
- VisitPolicy& visitor)
+ VisitPolicy& visitor,
+ Strategy const& strategy)
{
boost::ignore_unused(visitor);
- // collect all polygons that have turns
+ // collect all polygons that have crossing turns
std::set<signed_size_type> multi_indices;
for (TurnIterator tit = turns_first; tit != turns_beyond; ++tit)
{
- multi_indices.insert(tit->operations[0].seg_id.multi_index);
- multi_indices.insert(tit->operations[1].seg_id.multi_index);
+ if (! tit->touch_only)
+ {
+ multi_indices.insert(tit->operations[0].seg_id.multi_index);
+ multi_indices.insert(tit->operations[1].seg_id.multi_index);
+ }
}
+ typedef geometry::model::box<typename point_type<MultiPolygon>::type> box_type;
+ typedef typename base::template partition_item<PolygonIterator, box_type> item_type;
+
// put polygon iterators without turns in a vector
- std::vector<PolygonIterator> polygon_iterators;
+ std::vector<item_type> polygon_iterators;
signed_size_type multi_index = 0;
for (PolygonIterator it = polygons_first; it != polygons_beyond;
++it, ++multi_index)
{
if (multi_indices.find(multi_index) == multi_indices.end())
{
- polygon_iterators.push_back(it);
+ polygon_iterators.push_back(item_type(it));
}
}
- typename base::item_visitor_type item_visitor;
+ // prepare strategies
+ typedef typename std::iterator_traits<PolygonIterator>::value_type polygon_type;
+ typedef typename Strategy::template point_in_geometry_strategy
+ <
+ polygon_type, polygon_type
+ >::type within_strategy_type;
+ within_strategy_type const within_strategy
+ = strategy.template get_point_in_geometry_strategy<polygon_type, polygon_type>();
+ typedef typename Strategy::envelope_strategy_type envelope_strategy_type;
+ envelope_strategy_type const envelope_strategy
+ = strategy.get_envelope_strategy();
+
+ // call partition to check if polygons are disjoint from each other
+ typename base::template item_visitor_type<within_strategy_type> item_visitor(within_strategy);
geometry::partition
<
geometry::model::box<typename point_type<MultiPolygon>::type>
>::apply(polygon_iterators, item_visitor,
- typename base::expand_box(),
- typename base::overlaps_box());
+ typename base::template expand_box<envelope_strategy_type>(envelope_strategy),
+ typename base::template overlaps_box<envelope_strategy_type>(envelope_strategy));
if (item_visitor.items_overlap)
{
@@ -155,13 +176,15 @@ private:
<
typename PolygonIterator,
typename TurnIterator,
- typename VisitPolicy
+ typename VisitPolicy,
+ typename Strategy
>
static inline bool apply(PolygonIterator polygons_first,
PolygonIterator polygons_beyond,
TurnIterator turns_first,
TurnIterator turns_beyond,
- VisitPolicy& visitor)
+ VisitPolicy& visitor,
+ Strategy const& strategy)
{
signed_size_type multi_index = 0;
for (PolygonIterator it = polygons_first; it != polygons_beyond;
@@ -185,7 +208,8 @@ private:
if (! Predicate::apply(*it,
filtered_turns_first,
filtered_turns_beyond,
- visitor))
+ visitor,
+ strategy))
{
return false;
}
@@ -200,19 +224,21 @@ private:
<
typename PolygonIterator,
typename TurnIterator,
- typename VisitPolicy
+ typename VisitPolicy,
+ typename Strategy
>
static inline bool have_holes_inside(PolygonIterator polygons_first,
PolygonIterator polygons_beyond,
TurnIterator turns_first,
TurnIterator turns_beyond,
- VisitPolicy& visitor)
+ VisitPolicy& visitor,
+ Strategy const& strategy)
{
return has_property_per_polygon
<
typename base::has_holes_inside
>::apply(polygons_first, polygons_beyond,
- turns_first, turns_beyond, visitor);
+ turns_first, turns_beyond, visitor, strategy);
}
@@ -221,19 +247,21 @@ private:
<
typename PolygonIterator,
typename TurnIterator,
- typename VisitPolicy
+ typename VisitPolicy,
+ typename Strategy
>
static inline bool have_connected_interior(PolygonIterator polygons_first,
PolygonIterator polygons_beyond,
TurnIterator turns_first,
TurnIterator turns_beyond,
- VisitPolicy& visitor)
+ VisitPolicy& visitor,
+ Strategy const& strategy)
{
return has_property_per_polygon
<
typename base::has_connected_interior
>::apply(polygons_first, polygons_beyond,
- turns_first, turns_beyond, visitor);
+ turns_first, turns_beyond, visitor, strategy);
}
@@ -307,7 +335,8 @@ public:
boost::end(multipolygon),
turns.begin(),
turns.end(),
- visitor))
+ visitor,
+ strategy))
{
return false;
}
@@ -320,7 +349,8 @@ public:
boost::end(multipolygon),
turns.begin(),
turns.end(),
- visitor))
+ visitor,
+ strategy))
{
return false;
}
@@ -332,7 +362,8 @@ public:
boost::end(multipolygon),
turns.begin(),
turns.end(),
- visitor);
+ visitor,
+ strategy);
}
};
diff --git a/boost/geometry/algorithms/detail/is_valid/polygon.hpp b/boost/geometry/algorithms/detail/is_valid/polygon.hpp
index f7e22fb8d2..5c6229b793 100644
--- a/boost/geometry/algorithms/detail/is_valid/polygon.hpp
+++ b/boost/geometry/algorithms/detail/is_valid/polygon.hpp
@@ -1,5 +1,7 @@
// Boost.Geometry (aka GGL, Generic Geometry Library)
+// Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
+
// Copyright (c) 2014-2017, Oracle and/or its affiliates.
// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
@@ -43,6 +45,7 @@
#include <boost/geometry/algorithms/expand.hpp>
#include <boost/geometry/algorithms/num_interior_rings.hpp>
#include <boost/geometry/algorithms/validity_failure_type.hpp>
+#include <boost/geometry/algorithms/detail/point_on_border.hpp>
#include <boost/geometry/algorithms/within.hpp>
#include <boost/geometry/algorithms/detail/check_iterator_range.hpp>
@@ -142,43 +145,103 @@ protected:
};
+ // Iterator value_type is a Ring or Polygon
+ template <typename Iterator, typename Box>
+ struct partition_item
+ {
+ explicit partition_item(Iterator it)
+ : m_it(it)
+ , m_is_initialized(false)
+ {}
+
+ Iterator get() const
+ {
+ return m_it;
+ }
+
+ template <typename EnvelopeStrategy>
+ Box const& get_envelope(EnvelopeStrategy const& strategy) const
+ {
+ if (! m_is_initialized)
+ {
+ m_box = geometry::return_envelope<Box>(*m_it, strategy);
+ m_is_initialized = true;
+ }
+ return m_box;
+ }
+
+ private:
+ Iterator m_it;
+ mutable Box m_box;
+ mutable bool m_is_initialized;
+ };
+
// structs for partition -- start
+ template <typename EnvelopeStrategy>
struct expand_box
{
+ explicit expand_box(EnvelopeStrategy const& strategy) : m_strategy(strategy) {}
+
template <typename Box, typename Iterator>
- static inline void apply(Box& total, Iterator const& it)
+ inline void apply(Box& total, partition_item<Iterator, Box> const& item) const
{
- geometry::expand(total, geometry::return_envelope<Box>(*it));
+ geometry::expand(total, item.get_envelope(m_strategy));
}
+ EnvelopeStrategy const& m_strategy;
};
+ template <typename EnvelopeStrategy>
struct overlaps_box
{
+ explicit overlaps_box(EnvelopeStrategy const& strategy) : m_strategy(strategy) {}
+
template <typename Box, typename Iterator>
- static inline bool apply(Box const& box, Iterator const& it)
+ inline bool apply(Box const& box, partition_item<Iterator, Box> const& item) const
{
- return ! geometry::disjoint(*it, box);
+ return ! geometry::disjoint(item.get_envelope(m_strategy), box);
}
+
+ EnvelopeStrategy const& m_strategy;
};
+ template <typename WithinStrategy>
struct item_visitor_type
{
bool items_overlap;
+ WithinStrategy const& m_strategy;
+
+ explicit item_visitor_type(WithinStrategy const& strategy)
+ : items_overlap(false)
+ , m_strategy(strategy)
+ {}
- item_visitor_type() : items_overlap(false) {}
+ template <typename Item>
+ inline bool is_within(Item const& first, Item const& second)
+ {
+ typename point_type<Polygon>::type point;
+ typedef detail::point_on_border::point_on_range<true> pob;
+
+ // TODO: this should check for a point on the interior, instead
+ // of on border. Or it should check using the overlap function.
+
+ return pob::apply(point, points_begin(first), points_end(first))
+ && geometry::within(point, second, m_strategy);
+ }
- template <typename Item1, typename Item2>
- inline void apply(Item1 const& item1, Item2 const& item2)
+ template <typename Iterator, typename Box>
+ inline bool apply(partition_item<Iterator, Box> const& item1,
+ partition_item<Iterator, Box> const& item2)
{
if (! items_overlap
- && (geometry::within(*points_begin(*item1), *item2)
- || geometry::within(*points_begin(*item2), *item1))
- )
+ && (is_within(*item1.get(), *item2.get())
+ || is_within(*item2.get(), *item1.get())))
{
items_overlap = true;
+ return false; // interrupt
}
+ return true;
}
};
// structs for partition -- end
@@ -189,14 +252,16 @@ protected:
typename RingIterator,
typename ExteriorRing,
typename TurnIterator,
- typename VisitPolicy
+ typename VisitPolicy,
+ typename Strategy
>
static inline bool are_holes_inside(RingIterator rings_first,
RingIterator rings_beyond,
ExteriorRing const& exterior_ring,
TurnIterator turns_first,
TurnIterator turns_beyond,
- VisitPolicy& visitor)
+ VisitPolicy& visitor,
+ Strategy const& strategy)
{
boost::ignore_unused(visitor);
@@ -217,6 +282,14 @@ protected:
}
}
+ // prepare strategy
+ typedef typename std::iterator_traits<RingIterator>::value_type inter_ring_type;
+ typename Strategy::template point_in_geometry_strategy
+ <
+ inter_ring_type, ExteriorRing
+ >::type const in_exterior_strategy
+ = strategy.template get_point_in_geometry_strategy<inter_ring_type, ExteriorRing>();
+
signed_size_type ring_index = 0;
for (RingIterator it = rings_first; it != rings_beyond;
++it, ++ring_index)
@@ -224,7 +297,7 @@ protected:
// do not examine interior rings that have turns with the
// exterior ring
if (ring_indices.find(ring_index) == ring_indices.end()
- && ! geometry::covered_by(range::front(*it), exterior_ring))
+ && ! geometry::covered_by(range::front(*it), exterior_ring, in_exterior_strategy))
{
return visitor.template apply<failure_interior_rings_outside>();
}
@@ -237,26 +310,42 @@ protected:
ring_indices.insert(tit->operations[1].seg_id.ring_index);
}
+ typedef geometry::model::box<typename point_type<Polygon>::type> box_type;
+ typedef partition_item<RingIterator, box_type> item_type;
+
// put iterators for interior rings without turns in a vector
- std::vector<RingIterator> ring_iterators;
+ std::vector<item_type> ring_iterators;
ring_index = 0;
for (RingIterator it = rings_first; it != rings_beyond;
++it, ++ring_index)
{
if (ring_indices.find(ring_index) == ring_indices.end())
{
- ring_iterators.push_back(it);
+ ring_iterators.push_back(item_type(it));
}
}
- // call partition to check is interior rings are disjoint from
+ // prepare strategies
+ typedef typename Strategy::template point_in_geometry_strategy
+ <
+ inter_ring_type, inter_ring_type
+ >::type in_interior_strategy_type;
+ in_interior_strategy_type const in_interior_strategy
+ = strategy.template get_point_in_geometry_strategy<inter_ring_type, inter_ring_type>();
+ typedef typename Strategy::envelope_strategy_type envelope_strategy_type;
+ envelope_strategy_type const envelope_strategy
+ = strategy.get_envelope_strategy();
+
+ // call partition to check if interior rings are disjoint from
// each other
- item_visitor_type item_visitor;
+ item_visitor_type<in_interior_strategy_type> item_visitor(in_interior_strategy);
geometry::partition
<
- geometry::model::box<typename point_type<Polygon>::type>
- >::apply(ring_iterators, item_visitor, expand_box(), overlaps_box());
+ box_type
+ >::apply(ring_iterators, item_visitor,
+ expand_box<envelope_strategy_type>(envelope_strategy),
+ overlaps_box<envelope_strategy_type>(envelope_strategy));
if (item_visitor.items_overlap)
{
@@ -273,35 +362,40 @@ protected:
typename InteriorRings,
typename ExteriorRing,
typename TurnIterator,
- typename VisitPolicy
+ typename VisitPolicy,
+ typename Strategy
>
static inline bool are_holes_inside(InteriorRings const& interior_rings,
ExteriorRing const& exterior_ring,
TurnIterator first,
TurnIterator beyond,
- VisitPolicy& visitor)
+ VisitPolicy& visitor,
+ Strategy const& strategy)
{
return are_holes_inside(boost::begin(interior_rings),
boost::end(interior_rings),
exterior_ring,
first,
beyond,
- visitor);
+ visitor,
+ strategy);
}
struct has_holes_inside
{
- template <typename TurnIterator, typename VisitPolicy>
+ template <typename TurnIterator, typename VisitPolicy, typename Strategy>
static inline bool apply(Polygon const& polygon,
TurnIterator first,
TurnIterator beyond,
- VisitPolicy& visitor)
+ VisitPolicy& visitor,
+ Strategy const& strategy)
{
return are_holes_inside(geometry::interior_rings(polygon),
geometry::exterior_ring(polygon),
first,
beyond,
- visitor);
+ visitor,
+ strategy);
}
};
@@ -310,11 +404,12 @@ protected:
struct has_connected_interior
{
- template <typename TurnIterator, typename VisitPolicy>
+ template <typename TurnIterator, typename VisitPolicy, typename Strategy>
static inline bool apply(Polygon const& polygon,
TurnIterator first,
TurnIterator beyond,
- VisitPolicy& visitor)
+ VisitPolicy& visitor,
+ Strategy const& )
{
boost::ignore_unused(visitor);
@@ -388,7 +483,8 @@ public:
if (! has_holes_inside::apply(polygon,
turns.begin(), turns.end(),
- visitor))
+ visitor,
+ strategy))
{
return false;
}
@@ -399,7 +495,8 @@ public:
return has_connected_interior::apply(polygon,
turns.begin(),
turns.end(),
- visitor);
+ visitor,
+ strategy);
}
};
diff --git a/boost/geometry/algorithms/detail/is_valid/ring.hpp b/boost/geometry/algorithms/detail/is_valid/ring.hpp
index 9ab68fdc48..0b95950430 100644
--- a/boost/geometry/algorithms/detail/is_valid/ring.hpp
+++ b/boost/geometry/algorithms/detail/is_valid/ring.hpp
@@ -115,7 +115,10 @@ struct is_properly_oriented
geometry::closure<Ring>::value
> ring_area_type;
- typedef typename default_area_result<Ring>::type area_result_type;
+ typedef typename Strategy::template area_strategy
+ <
+ point_type
+ >::type::return_type area_result_type;
typename ring_area_predicate
<
@@ -195,7 +198,7 @@ struct is_valid_ring
return
is_topologically_closed<Ring, closure>::apply(ring, visitor)
&& ! has_duplicates<Ring, closure>::apply(ring, visitor)
- && ! has_spikes<Ring, closure>::apply(ring, visitor)
+ && ! has_spikes<Ring, closure>::apply(ring, visitor, strategy.get_side_strategy())
&& (! CheckSelfIntersections
|| has_valid_self_turns<Ring>::apply(ring, visitor, strategy))
&& is_properly_oriented<Ring, IsInteriorRing>::apply(ring, visitor, strategy);