Server : Apache/2.4.41 (Ubuntu) System : Linux absol.cf 5.4.0-198-generic #218-Ubuntu SMP Fri Sep 27 20:18:53 UTC 2024 x86_64 User : www-data ( 33) PHP Version : 7.4.33 Disable Function : pcntl_alarm,pcntl_fork,pcntl_waitpid,pcntl_wait,pcntl_wifexited,pcntl_wifstopped,pcntl_wifsignaled,pcntl_wifcontinued,pcntl_wexitstatus,pcntl_wtermsig,pcntl_wstopsig,pcntl_signal,pcntl_signal_get_handler,pcntl_signal_dispatch,pcntl_get_last_error,pcntl_strerror,pcntl_sigprocmask,pcntl_sigwaitinfo,pcntl_sigtimedwait,pcntl_exec,pcntl_getpriority,pcntl_setpriority,pcntl_async_signals,pcntl_unshare, Directory : /usr/include/boost/geometry/algorithms/detail/is_valid/
Upload File :
Current File : //usr/include/boost/geometry/algorithms/detail/is_valid/multipolygon.hpp
// Boost.Geometry (aka GGL, Generic Geometry Library)
// Copyright (c) 2014-2019, 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
#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_MULTIPOLYGON_HPP
#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_MULTIPOLYGON_HPP
#include <deque>
#include <vector>
#include <boost/core/ignore_unused.hpp>
#include <boost/iterator/filter_iterator.hpp>
#include <boost/range.hpp>
#include <boost/geometry/core/exterior_ring.hpp>
#include <boost/geometry/core/interior_rings.hpp>
#include <boost/geometry/core/ring_type.hpp>
#include <boost/geometry/core/tags.hpp>
#include <boost/geometry/util/condition.hpp>
#include <boost/geometry/util/range.hpp>
#include <boost/geometry/geometries/box.hpp>
#include <boost/geometry/algorithms/validity_failure_type.hpp>
#include <boost/geometry/algorithms/within.hpp>
#include <boost/geometry/algorithms/detail/check_iterator_range.hpp>
#include <boost/geometry/algorithms/detail/partition.hpp>
#include <boost/geometry/algorithms/detail/is_valid/has_valid_self_turns.hpp>
#include <boost/geometry/algorithms/detail/is_valid/is_acceptable_turn.hpp>
#include <boost/geometry/algorithms/detail/is_valid/polygon.hpp>
#include <boost/geometry/algorithms/detail/is_valid/debug_print_turns.hpp>
#include <boost/geometry/algorithms/detail/is_valid/debug_validity_phase.hpp>
#include <boost/geometry/algorithms/dispatch/is_valid.hpp>
#include <boost/geometry/strategies/intersection.hpp>
namespace boost { namespace geometry
{
#ifndef DOXYGEN_NO_DETAIL
namespace detail { namespace is_valid
{
template <typename MultiPolygon, bool AllowEmptyMultiGeometries>
class is_valid_multipolygon
: is_valid_polygon
<
typename boost::range_value<MultiPolygon>::type,
true // check only the validity of rings
>
{
private:
typedef is_valid_polygon
<
typename boost::range_value<MultiPolygon>::type,
true
> base;
template
<
typename PolygonIterator,
typename TurnIterator,
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,
Strategy const& strategy)
{
boost::ignore_unused(visitor);
// collect all polygons that have crossing turns
std::set<signed_size_type> multi_indices;
for (TurnIterator tit = turns_first; tit != turns_beyond; ++tit)
{
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<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(item_type(it));
}
}
// prepare strategies
typedef typename Strategy::envelope_strategy_type envelope_strategy_type;
envelope_strategy_type const envelope_strategy
= strategy.get_envelope_strategy();
typedef typename Strategy::disjoint_box_box_strategy_type disjoint_box_box_strategy_type;
disjoint_box_box_strategy_type const disjoint_strategy
= strategy.get_disjoint_box_box_strategy();
// call partition to check if polygons are disjoint from each other
typename base::template item_visitor_type<Strategy> item_visitor(strategy);
geometry::partition
<
geometry::model::box<typename point_type<MultiPolygon>::type>
>::apply(polygon_iterators, item_visitor,
typename base::template expand_box
<
envelope_strategy_type
>(envelope_strategy),
typename base::template overlaps_box
<
envelope_strategy_type,
disjoint_box_box_strategy_type
>(envelope_strategy, disjoint_strategy));
if (item_visitor.items_overlap)
{
return visitor.template apply<failure_intersecting_interiors>();
}
else
{
return visitor.template apply<no_failure>();
}
}
class has_multi_index
{
public:
has_multi_index(signed_size_type multi_index)
: m_multi_index(multi_index)
{}
template <typename Turn>
inline bool operator()(Turn const& turn) const
{
return turn.operations[0].seg_id.multi_index == m_multi_index
&& turn.operations[1].seg_id.multi_index == m_multi_index;
}
private:
signed_size_type const m_multi_index;
};
template <typename Predicate>
struct has_property_per_polygon
{
template
<
typename PolygonIterator,
typename TurnIterator,
typename VisitPolicy,
typename Strategy
>
static inline bool apply(PolygonIterator polygons_first,
PolygonIterator polygons_beyond,
TurnIterator turns_first,
TurnIterator turns_beyond,
VisitPolicy& visitor,
Strategy const& strategy)
{
signed_size_type multi_index = 0;
for (PolygonIterator it = polygons_first; it != polygons_beyond;
++it, ++multi_index)
{
has_multi_index index_predicate(multi_index);
typedef boost::filter_iterator
<
has_multi_index, TurnIterator
> filtered_turn_iterator;
filtered_turn_iterator filtered_turns_first(index_predicate,
turns_first,
turns_beyond);
filtered_turn_iterator filtered_turns_beyond(index_predicate,
turns_beyond,
turns_beyond);
if (! Predicate::apply(*it,
filtered_turns_first,
filtered_turns_beyond,
visitor,
strategy))
{
return false;
}
}
return true;
}
};
template
<
typename PolygonIterator,
typename TurnIterator,
typename VisitPolicy,
typename Strategy
>
static inline bool have_holes_inside(PolygonIterator polygons_first,
PolygonIterator polygons_beyond,
TurnIterator turns_first,
TurnIterator turns_beyond,
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, strategy);
}
template
<
typename PolygonIterator,
typename TurnIterator,
typename VisitPolicy,
typename Strategy
>
static inline bool have_connected_interior(PolygonIterator polygons_first,
PolygonIterator polygons_beyond,
TurnIterator turns_first,
TurnIterator turns_beyond,
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, strategy);
}
template <typename VisitPolicy, typename Strategy>
struct per_polygon
{
per_polygon(VisitPolicy& policy, Strategy const& strategy)
: m_policy(policy)
, m_strategy(strategy)
{}
template <typename Polygon>
inline bool apply(Polygon const& polygon) const
{
return base::apply(polygon, m_policy, m_strategy);
}
VisitPolicy& m_policy;
Strategy const& m_strategy;
};
public:
template <typename VisitPolicy, typename Strategy>
static inline bool apply(MultiPolygon const& multipolygon,
VisitPolicy& visitor,
Strategy const& strategy)
{
typedef debug_validity_phase<MultiPolygon> debug_phase;
if (BOOST_GEOMETRY_CONDITION(AllowEmptyMultiGeometries)
&& boost::empty(multipolygon))
{
return visitor.template apply<no_failure>();
}
// check validity of all polygons ring
debug_phase::apply(1);
if (! detail::check_iterator_range
<
per_polygon<VisitPolicy, Strategy>,
false // do not check for empty multipolygon (done above)
>::apply(boost::begin(multipolygon),
boost::end(multipolygon),
per_polygon<VisitPolicy, Strategy>(visitor, strategy)))
{
return false;
}
// compute turns and check if all are acceptable
debug_phase::apply(2);
typedef has_valid_self_turns<MultiPolygon, typename Strategy::cs_tag> has_valid_turns;
std::deque<typename has_valid_turns::turn_type> turns;
bool has_invalid_turns =
! has_valid_turns::apply(multipolygon, turns, visitor, strategy);
debug_print_turns(turns.begin(), turns.end());
if (has_invalid_turns)
{
return false;
}
// check if each polygon's interior rings are inside the
// exterior and not one inside the other
debug_phase::apply(3);
if (! have_holes_inside(boost::begin(multipolygon),
boost::end(multipolygon),
turns.begin(),
turns.end(),
visitor,
strategy))
{
return false;
}
// check that each polygon's interior is connected
debug_phase::apply(4);
if (! have_connected_interior(boost::begin(multipolygon),
boost::end(multipolygon),
turns.begin(),
turns.end(),
visitor,
strategy))
{
return false;
}
// check if polygon interiors are disjoint
debug_phase::apply(5);
return are_polygon_interiors_disjoint(boost::begin(multipolygon),
boost::end(multipolygon),
turns.begin(),
turns.end(),
visitor,
strategy);
}
};
}} // namespace detail::is_valid
#endif // DOXYGEN_NO_DETAIL
#ifndef DOXYGEN_NO_DISPATCH
namespace dispatch
{
// Not clear what the definition is.
// Right now we check that each element is simple (in fact valid), and
// that the MultiPolygon is also valid.
//
// Reference (for validity of MultiPolygons): OGC 06-103r4 (6.1.14)
template <typename MultiPolygon, bool AllowEmptyMultiGeometries>
struct is_valid
<
MultiPolygon, multi_polygon_tag, AllowEmptyMultiGeometries
> : detail::is_valid::is_valid_multipolygon
<
MultiPolygon, AllowEmptyMultiGeometries
>
{};
} // namespace dispatch
#endif // DOXYGEN_NO_DISPATCH
}} // namespace boost::geometry
#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_MULTIPOLYGON_HPP
Server : Apache/2.4.41 (Ubuntu)