Skip to content

Commit 160e96e

Browse files
cirosantillicirosantilli
committed
boost-rtree
1 parent d36527f commit 160e96e

28 files changed

Lines changed: 1155 additions & 322 deletions

‎boost/README.md‎

Lines changed: 6 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,11 @@
11
# Boost
22

3-
1. [main.c](main.c)
4-
1. [graph.c](graph.c)
3+
1. [main](main.cpp)
4+
1. [graph](graph.cpp)
5+
1. [Geometry](geometry.md)
6+
1. [point](point.cpp)
7+
1. [box](box.cpp)
8+
1. [rtree](rtree.cpp)
59

610
Boost is the most important C++ utilities library.
711

‎boost/box.cpp‎

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
#include "common.hpp"
2+
3+
int main() {
4+
typedef bg::model::point<int, 2, bg::cs::cartesian> Point;
5+
typedef bg::model::box<Point> Box;
6+
7+
{
8+
// Get them.
9+
{
10+
Point p1(1, 2);
11+
Point p2(3, 4);
12+
Box b(p1, p2);
13+
assert(bg::equals(b.min_corner(), p1));
14+
assert(bg::equals(b.max_corner(), p2));
15+
}
16+
17+
// TODO: does it make a difference which is which?
18+
{
19+
Point p1(3, 4);
20+
Point p2(1, 2);
21+
Box b(p1, p2);
22+
assert(bg::equals(b.min_corner(), p1));
23+
assert(bg::equals(b.max_corner(), p2));
24+
}
25+
}
26+
}

‎boost/common.hpp‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
#ifndef COMMON_HPP
2+
#define COMMON_HPP
3+
4+
#include <algorithm>
5+
#include <cassert>
6+
#include <iterator>
7+
#include <set>
8+
#include <unordered_map>
9+
#include <unordered_set>
10+
#include <utility> // pair
11+
#include <vector>
12+
13+
#include <boost/geometry.hpp>
14+
#include <boost/iterator.hpp>
15+
16+
namespace bg = boost::geometry;
17+
namespace bgi = bg::index;
18+
19+
#endif

‎boost/geometry.md‎

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
# Geometry
2+
3+
Most important thing is `rtree`, which is like an N-dimensional binary tree, and allows for log(n) queries.
4+
5+
Also clone the library and look into the ton of examples that come with the source:
6+
7+
git clone https://github.com/boostorg/geometry

‎boost/main.cpp‎

Lines changed: 7 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -29,7 +29,8 @@ int main() {
2929
assert((strs == std::vector<std::string>{"a", "", "b", "cd"}));
3030
}
3131

32-
// #strip ##filter
32+
// # strip
33+
// #filter
3334
{
3435
// Single character, no single function in C++11.
3536
{
@@ -53,7 +54,11 @@ int main() {
5354

5455

5556
/*
56-
#filesystem #path #join
57+
# filesystem
58+
59+
# path
60+
61+
# join
5762
5863
Proposed for inclusion on TR2.
5964
*/

‎boost/point.cpp‎

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
#include "common.hpp"
2+
3+
int main() {
4+
typedef bg::model::point<int, 2, bg::cs::cartesian> Point;
5+
6+
// get
7+
{
8+
Point p(1, 2);
9+
assert(p.get<0>() == 1);
10+
assert(p.get<1>() == 2);
11+
}
12+
13+
// set
14+
{
15+
Point p(1, 2);
16+
p.set<0>(3);
17+
assert(p.get<0>() == 3);
18+
}
19+
20+
// ==
21+
{
22+
assert(bg::equals(Point(1, 2), Point(1, 2)));
23+
}
24+
25+
// TODO exercise the cartesian thing.
26+
27+
// Hash: nope in boost 1.61. Thus cannot put into unordered set.
28+
// https://github.com/boostorg/geometry/issues/374
29+
30+
// < > relational operators: nope. Thus cannot put into ordered set.
31+
// But makes sense, since < > don't have a nice interpretation for 2D points.
32+
// https://github.com/boostorg/geometry/issues/374
33+
}

‎boost/rtree.cpp‎

Lines changed: 272 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,272 @@
1+
/*
2+
Contains either:
3+
4+
- Point, Box or Segment, or something adapted to them
5+
- std::pair<Point, Data>
6+
- std::tuple<Point, ..., ...>
7+
8+
Documented at: http://www.boost.org/doc/libs/1_62_0/libs/geometry/doc/html/geometry/spatial_indexes/creation_and_modification.html
9+
10+
TODO
11+
12+
- randomized perf test vs linear search.
13+
14+
- ellipses, infinite lines, other parametrized surfaces:
15+
http://boost-geometry.203548.n3.nabble.com/intersection-between-a-sphere-and-a-line-td4025167.html
16+
*/
17+
18+
#include "common.hpp"
19+
20+
// TODO this must be included separately for BOOST_GEOMETRY_REGISTER_POINT_2D.
21+
#include <boost/geometry/geometries/register/point.hpp>
22+
23+
// Copied from the docs, checking that it works.
24+
25+
class MyPoint {
26+
public:
27+
int x;
28+
int y;
29+
int getX() const { return this->x; }
30+
int getY() const { return this->y; }
31+
int setX(int x) { this->x = x; }
32+
int setY(int y) { this->y = y; }
33+
MyPoint(){}
34+
MyPoint(int x, int y) : x(x), y(y) {}
35+
};
36+
37+
// Magic, equivalent to the large namespace injection below.
38+
//BOOST_GEOMETRY_REGISTER_POINT_2D(MyPoint, int, bg::cs::cartesian, x, y)
39+
// Nope, must be able to assign directly to the fields.
40+
//BOOST_GEOMETRY_REGISTER_POINT_2D(MyPoint, int, bg::cs::cartesian, getX(), getY())
41+
42+
namespace boost { namespace geometry { namespace traits {
43+
template<> struct tag<MyPoint>
44+
{ typedef point_tag type; };
45+
46+
template<> struct coordinate_type<MyPoint>
47+
{ typedef int type; };
48+
49+
template<> struct coordinate_system<MyPoint>
50+
{ typedef cs::cartesian type; };
51+
52+
template<> struct dimension<MyPoint> : boost::mpl::int_<2> {};
53+
54+
template<>
55+
struct access<MyPoint, 0> {
56+
static int get(MyPoint const& p) {
57+
return p.getX();
58+
}
59+
static void set(MyPoint& p, int const& value) {
60+
p.setX(value);
61+
}
62+
};
63+
64+
template<>
65+
struct access<MyPoint, 1> {
66+
static int get(MyPoint const& p) {
67+
return p.getY();
68+
}
69+
static void set(MyPoint& p, int const& value) {
70+
p.setY(value);
71+
}
72+
};
73+
} } }
74+
75+
// Our custom point class.
76+
typedef MyPoint Point;
77+
// Byilt-in point.
78+
//typedef bg::model::point<int, 2, bg::cs::cartesian> Point;
79+
typedef bg::model::box<Point> Box;
80+
typedef std::pair<Point, int> Value;
81+
typedef bgi::rtree<Value, bgi::linear<16>> Rtree;
82+
typedef std::unordered_set<Value::second_type> ValueSet;
83+
typedef std::vector<Value::second_type> ValueVector;
84+
85+
template<typename T>
86+
class MyInsertIterator : public std::insert_iterator<T> {
87+
public:
88+
using std::insert_iterator<T>::insert_iterator;
89+
MyInsertIterator& operator=(const Value& rhs) {
90+
this->std::insert_iterator<T>::operator=(rhs.second);
91+
}
92+
};
93+
94+
// Helper to write less for our tests.
95+
// Go go, NRVO!
96+
template<typename Predicates, typename Rtree>
97+
ValueSet getValueSet(const Rtree& rtree, const Predicates& predicates) {
98+
ValueSet result;
99+
auto it = rtree.qbegin(predicates);
100+
auto end = rtree.qend();
101+
while (it != end) {
102+
result.insert(it->second);
103+
++it;
104+
}
105+
return result;
106+
107+
// TODO why not working
108+
// Remember that Point is neither hashable nor ordered < >,
109+
// so direct insertion into set or unordered won't work:
110+
// we need to get the value out somehow.
111+
//rtree.query(
112+
//bgi::intersects(Box(Point(0, 0), Point(4, 4))),
113+
//MyInsertIterator<decltype(result)>(result, result.end())
114+
//);
115+
}
116+
117+
// Works, but sometimes hard to verify if correct since order not specified.
118+
template<typename Predicates>
119+
ValueVector getValueVector(const Rtree& rtree, const Predicates& predicates) {
120+
ValueVector result;
121+
auto it = rtree.qbegin(predicates);
122+
auto end = rtree.qend();
123+
while (it != end) {
124+
result.push_back(it->second);
125+
++it;
126+
}
127+
return result;
128+
}
129+
130+
// Adapt pointers to values.
131+
namespace boost { namespace geometry { namespace index {
132+
template <typename Box>
133+
struct indexable<Box*>
134+
{
135+
typedef Box* V;
136+
typedef Box const& result_type;
137+
result_type operator()(V const& v) const { return *v; }
138+
};
139+
}}}
140+
typedef std::pair<Point*, int> Valuep;
141+
typedef bgi::rtree<Valuep, bgi::linear<16>> Rtreep;
142+
143+
int main() {
144+
// Basic examples.
145+
{
146+
Rtree rtree;
147+
rtree.insert(Value(Point(1, 1), 1));
148+
rtree.insert(Value(Point(3, 3), 3));
149+
150+
// Basic intersect queries.
151+
assert(
152+
getValueSet(rtree, bgi::intersects(Box(Point(0, 0), Point(4, 4))))
153+
== ValueSet({1, 3})
154+
);
155+
assert(
156+
getValueSet(rtree, bgi::intersects(Box(Point(0, 0), Point(2, 2))))
157+
== ValueSet({1})
158+
);
159+
assert(
160+
getValueSet(rtree, bgi::intersects(Box(Point(2, 2), Point(4, 4))))
161+
== ValueSet({3})
162+
);
163+
assert(
164+
getValueSet(rtree, bgi::intersects(Box(Point(4, 4), Point(5, 5))))
165+
== ValueSet({})
166+
);
167+
168+
// Edges are counted in.
169+
assert(
170+
getValueSet(rtree, bgi::intersects(Box(Point(0, 0), Point(1, 1))))
171+
== ValueSet({1})
172+
);
173+
assert(
174+
getValueSet(rtree, bgi::intersects(Box(Point(1, 1), Point(2, 2))))
175+
== ValueSet({1})
176+
);
177+
178+
// TODO is nearest first guaranteed?
179+
// http://stackoverflow.com/questions/41552048/do-boost-geometry-nearest-queries-always-sort-results-ordered-by-smallest-distan
180+
assert(
181+
getValueVector(rtree, bgi::nearest(Point(1, 1), 1))
182+
== ValueVector({1})
183+
);
184+
assert(
185+
getValueVector(rtree, bgi::nearest(Point(1, 1), 2))
186+
== ValueVector({1, 3})
187+
);
188+
assert(
189+
getValueVector(rtree, bgi::nearest(Point(3, 3), 1))
190+
== ValueVector({3})
191+
);
192+
assert(
193+
getValueVector(rtree, bgi::nearest(Point(3, 3), 2))
194+
== ValueVector({3, 1})
195+
);
196+
assert(
197+
getValueVector(rtree, bgi::nearest(Point(0, 0), 2))
198+
== ValueVector({1, 3})
199+
);
200+
assert(
201+
getValueVector(rtree, bgi::nearest(Point(4, 4), 2))
202+
== ValueVector({3, 1})
203+
);
204+
}
205+
206+
// Duplicate points.
207+
{
208+
Rtree rtree;
209+
rtree.insert(Value(Point(1, 1), 1));
210+
rtree.insert(Value(Point(1, 1), 1));
211+
assert(
212+
getValueVector(rtree, bgi::intersects(Point(1, 1)))
213+
== ValueVector({1, 1})
214+
);
215+
216+
// .remove() removes only one duplicate at a time.
217+
rtree.remove(Value(Point(1, 1), 1));
218+
assert(
219+
getValueVector(rtree, bgi::intersects(Point(1, 1)))
220+
== ValueVector({1})
221+
);
222+
rtree.remove(Value(Point(1, 1), 1));
223+
assert(
224+
getValueVector(rtree, bgi::intersects(Point(1, 1)))
225+
== ValueVector({})
226+
);
227+
}
228+
229+
// remove
230+
{
231+
Rtree rtree;
232+
rtree.insert(Value(Point(1, 1), 1));
233+
rtree.insert(Value(Point(1, 1), 2));
234+
235+
// Sanity check.
236+
assert(
237+
getValueSet(rtree, bgi::intersects(Point(1, 1)))
238+
== ValueSet({1, 2})
239+
);
240+
241+
// The entire value must be given and compare == to be removed.
242+
assert(rtree.remove(std::make_pair(Point(1, 1), 1)) == 1);
243+
assert(
244+
getValueVector(rtree, bgi::intersects(Point(1, 1)))
245+
== ValueVector({2})
246+
);
247+
248+
// Return 0 if no removal was done.
249+
assert(rtree.remove(std::make_pair(Point(1, 1), 1)) == 0);
250+
assert(
251+
getValueVector(rtree, bgi::intersects(Point(1, 1)))
252+
== ValueVector({2})
253+
);
254+
}
255+
256+
// Adapt pointer values.
257+
// Only the indexable part is adapted in this example.
258+
// See value_shared_ptr.cpp example in the source tree, same for smart pointers.
259+
{
260+
Rtreep rtree;
261+
rtree.insert(Valuep(new Point(1, 1), 1));
262+
rtree.insert(Valuep(new Point(3, 3), 3));
263+
assert(
264+
getValueSet(rtree, bgi::intersects(Box(Point(0, 0), Point(2, 2))))
265+
== ValueSet({1})
266+
);
267+
// Leak. Smart pointers. Meh.
268+
}
269+
270+
// update
271+
// TODO: any hint insertion iterator as in std::set? Seems not.
272+
}

0 commit comments

Comments
 (0)