Branch data Line data Source code
1 : : /*
2 : : * Copyright 2003-2005 Daniel F. Savarese
3 : : * Copyright 2006-2009 Savarese Software Research Corporation
4 : : *
5 : : * Licensed under the Apache License, Version 2.0 (the "License");
6 : : * you may not use this file except in compliance with the License.
7 : : * You may obtain a copy of the License at
8 : : *
9 : : * https://www.savarese.com/software/ApacheLicense-2.0
10 : : *
11 : : * Unless required by applicable law or agreed to in writing, software
12 : : * distributed under the License is distributed on an "AS IS" BASIS,
13 : : * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 : : * See the License for the specific language governing permissions and
15 : : * limitations under the License.
16 : : */
17 : :
18 : : /**
19 : : * @file
20 : : * This header defines the rectangle_region class.
21 : : */
22 : :
23 : : #ifndef __SSRC_SPATIAL_RECTANGLE_REGION_H
24 : : #define __SSRC_SPATIAL_RECTANGLE_REGION_H
25 : :
26 : : #include <ssrc/libssrckdtree-packages.h>
27 : :
28 : : #include <tuple>
29 : :
30 : : __BEGIN_NS_SSRC_SPATIAL
31 : :
32 : : /**
33 : : * A rectangle_region implements the region concept for rectangular
34 : : * regions defined by a lower left-hand corner and an upper right-hand
35 : : * corner. The region concept is not yet fully defined and may change
36 : : * in a future version. Currently, a region must define a bounding
37 : : * box consisting of two public member variables—lower and
38 : : * upper—which specify the lower left and upper right corners
39 : : * of the box. In addition, a public non-static member function
40 : : * must be defined with with the signature: bool contains(const Point &)
41 : : *
42 : : * Region classes are intended to allow iteration over ranges within
43 : : * arbitrarily shaped regions without post-filtering a rectangular
44 : : * range, reducing the total number of comparisions. Such range
45 : : * searches can be performed with the
46 : : * kd_tree::begin<Region>(const Region &) and kd_tree<Region>::end() functions.
47 : : * rectangle_region is the default region type used by kd_tree for
48 : : * range searches.
49 : : */
50 : : template<typename Point,
51 : : const unsigned int i = NS_TR1::tuple_size<Point>::value - 1>
52 : : struct rectangle_region {
53 : : Point lower, upper;
54 : :
55 : : //rectangle_region() = default;
56 : : rectangle_region() : lower(), upper() { }
57 : :
58 : : rectangle_region(const Point & lower, const Point & upper) :
59 : : lower(lower), upper(upper)
60 : : { }
61 : :
62 : : // This is a helper function that is NOT part of the region concept.
63 : : static bool
64 : : contains(const Point & point, const Point & lower, const Point & upper)
65 : : {
66 : : return ((NS_TR1::get<i>(point) >= NS_TR1::get<i>(lower) &&
67 : : NS_TR1::get<i>(point) <= NS_TR1::get<i>(upper)) &&
68 : : rectangle_region<Point, i-1>::contains(point, lower, upper));
69 : : }
70 : :
71 : : /**
72 : : * Returns true if a given point is contained within the region. The
73 : : * point must lie within or on the boundary defining the region.
74 : : *
75 : : * @param point The point to test.
76 : : * @return True if a given point is contained within the region, false
77 : : * otherwise.
78 : : */
79 : : bool contains(const Point & point) const {
80 : : return rectangle_region::contains(point, lower, upper);
81 : : }
82 : : };
83 : :
84 : : template<typename Point>
85 : : struct rectangle_region<Point, 0> {
86 : : Point lower, upper;
87 : :
88 : : //rectangle_region() = default;
89 : : rectangle_region() : lower(), upper() { }
90 : :
91 : : rectangle_region(const Point & lower, const Point & upper) :
92 : : lower(lower), upper(upper)
93 : : { }
94 : :
95 : : // This is a helper function that is NOT part of the region concept.
96 : : static bool
97 : : contains(const Point & point, const Point & lower, const Point & upper) {
98 : : return !(NS_TR1::get<0>(point) < NS_TR1::get<0>(lower) ||
99 : : NS_TR1::get<0>(point) > NS_TR1::get<0>(upper));
100 : : }
101 : :
102 : :
103 : : bool contains(const Point & point) const {
104 : : return rectangle_region::contains(point, lower, upper);
105 : : }
106 : : };
107 : :
108 : : template<typename Point>
109 : : struct rectangle_region<Point, 1> {
110 : : Point lower, upper;
111 : :
112 : : //rectangle_region() = default;
113 [ + + ][ + + ]: 384 : rectangle_region() : lower(), upper() { }
[ + + ][ + + ]
[ + + ][ + + ]
114 : :
115 : 344121 : rectangle_region(const Point & lower, const Point & upper) :
116 : 344121 : lower(lower), upper(upper)
117 : 344121 : { }
118 : :
119 : : // This is a helper function that is NOT part of the region concept.
120 : : static bool
121 : 995454 : contains(const Point & point, const Point & lower, const Point & upper) {
122 : : return !(NS_TR1::get<0>(point) < NS_TR1::get<0>(lower) ||
123 : : NS_TR1::get<1>(point) < NS_TR1::get<1>(lower) ||
124 : : NS_TR1::get<0>(point) > NS_TR1::get<0>(upper) ||
125 [ + + ][ + + ]: 995454 : NS_TR1::get<1>(point) > NS_TR1::get<1>(upper));
[ + - ][ + - ]
[ + + ][ + + ]
[ + - ][ + - ]
[ + + ][ + + ]
[ + - ][ + - ]
126 : : }
127 : :
128 : 995454 : bool contains(const Point & point) const {
129 : 995454 : return rectangle_region::contains(point, lower, upper);
130 : : }
131 : : };
132 : :
133 : : template<typename Point>
134 : : struct rectangle_region<Point, 2> {
135 : : Point lower, upper;
136 : :
137 : : //rectangle_region() = default;
138 : : rectangle_region() : lower(), upper() { }
139 : :
140 : : rectangle_region(const Point & lower, const Point & upper) :
141 : : lower(lower), upper(upper)
142 : : { }
143 : :
144 : : // This is a helper function that is NOT part of the region concept.
145 : : static bool
146 : : contains(const Point & point, const Point & lower, const Point & upper) {
147 : : return !(NS_TR1::get<0>(point) < NS_TR1::get<0>(lower) ||
148 : : NS_TR1::get<1>(point) < NS_TR1::get<1>(lower) ||
149 : : NS_TR1::get<2>(point) < NS_TR1::get<2>(lower) ||
150 : : NS_TR1::get<0>(point) > NS_TR1::get<0>(upper) ||
151 : : NS_TR1::get<1>(point) > NS_TR1::get<1>(upper) ||
152 : : NS_TR1::get<2>(point) > NS_TR1::get<2>(upper));
153 : : }
154 : :
155 : : bool contains(const Point & point) const {
156 : : return rectangle_region::contains(point, lower, upper);
157 : : }
158 : : };
159 : :
160 : : __END_NS_SSRC_SPATIAL
161 : :
162 : : #endif
|
