1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
|
// Boost.Geometry (aka GGL, Generic Geometry Library)
// Copyright (c) 2014 Oracle and/or its affiliates.
// Use, modification and distribution is subject to the Boost Software License,
// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_BOUNDARY_CHECKER_HPP
#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_BOUNDARY_CHECKER_HPP
#include <boost/geometry/util/range.hpp>
#include <boost/geometry/algorithms/num_points.hpp>
#include <boost/geometry/algorithms/detail/sub_range.hpp>
#include <boost/geometry/algorithms/detail/equals/point_point.hpp>
namespace boost { namespace geometry
{
#ifndef DOXYGEN_NO_DETAIL
namespace detail { namespace relate {
enum boundary_query { boundary_front, boundary_back, boundary_any };
template <typename Geometry,
typename Tag = typename geometry::tag<Geometry>::type>
class boundary_checker {};
template <typename Geometry>
class boundary_checker<Geometry, linestring_tag>
{
typedef typename point_type<Geometry>::type point_type;
public:
boundary_checker(Geometry const& g)
: has_boundary( boost::size(g) >= 2
&& !detail::equals::equals_point_point(range::front(g), range::back(g)) )
, geometry(g)
{}
template <boundary_query BoundaryQuery>
bool is_endpoint_boundary(point_type const& pt) const
{
boost::ignore_unused_variable_warning(pt);
#ifdef BOOST_GEOMETRY_DEBUG_RELATE_BOUNDARY_CHECKER
// may give false positives for INT
BOOST_ASSERT( (BoundaryQuery == boundary_front || BoundaryQuery == boundary_any)
&& detail::equals::equals_point_point(pt, range::front(geometry))
|| (BoundaryQuery == boundary_back || BoundaryQuery == boundary_any)
&& detail::equals::equals_point_point(pt, range::back(geometry)) );
#endif
return has_boundary;
}
private:
bool has_boundary;
Geometry const& geometry;
};
template <typename Geometry>
class boundary_checker<Geometry, multi_linestring_tag>
{
typedef typename point_type<Geometry>::type point_type;
public:
boundary_checker(Geometry const& g)
: is_filled(false), geometry(g)
{}
// First call O(NlogN)
// Each next call O(logN)
template <boundary_query BoundaryQuery>
bool is_endpoint_boundary(point_type const& pt) const
{
typedef typename boost::range_size<Geometry>::type size_type;
size_type multi_count = boost::size(geometry);
if ( multi_count < 1 )
return false;
if ( ! is_filled )
{
//boundary_points.clear();
boundary_points.reserve(multi_count * 2);
typedef typename boost::range_iterator<Geometry const>::type multi_iterator;
for ( multi_iterator it = boost::begin(geometry) ;
it != boost::end(geometry) ; ++ it )
{
// empty or point - no boundary
if ( boost::size(*it) < 2 )
continue;
// linear ring or point - no boundary
if ( equals::equals_point_point(range::front(*it), range::back(*it)) )
continue;
boundary_points.push_back(range::front(*it));
boundary_points.push_back(range::back(*it));
}
std::sort(boundary_points.begin(), boundary_points.end(), geometry::less<point_type>());
is_filled = true;
}
std::size_t equal_points_count
= boost::size(
std::equal_range(boundary_points.begin(),
boundary_points.end(),
pt,
geometry::less<point_type>())
);
return equal_points_count % 2 != 0;// && equal_points_count > 0; // the number is odd and > 0
}
private:
mutable bool is_filled;
// TODO: store references/pointers instead of points?
mutable std::vector<point_type> boundary_points;
Geometry const& geometry;
};
}} // namespace detail::relate
#endif // DOXYGEN_NO_DETAIL
}} // namespace boost::geometry
#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_BOUNDARY_CHECKER_HPP
|
