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
|
/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
/*************************************************************************
*
* Copyright (c) 2020 Kohei Yoshida
*
* Permission is hereby granted, free of charge, to any person
* obtaining a copy of this software and associated documentation
* files (the "Software"), to deal in the Software without
* restriction, including without limitation the rights to use,
* copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the
* Software is furnished to do so, subject to the following
* conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
* OTHER DEALINGS IN THE SOFTWARE.
*
************************************************************************/
#include <mdds/rtree.hpp>
#include <iostream>
#include <fstream>
// Make the node capacity intentionally small.
struct tiny_traits_2d
{
constexpr static size_t dimensions = 2;
constexpr static size_t min_node_size = 2;
constexpr static size_t max_node_size = 5;
constexpr static size_t max_tree_depth = 100;
constexpr static bool enable_forced_reinsertion = true;
constexpr static size_t reinsertion_size = 2;
};
using rt_type = mdds::rtree<int, int, tiny_traits_2d>;
int main() try
{
// 2D rectangle with the top-left position (x, y), width and height.
struct rect
{
int x;
int y;
int w;
int h;
};
std::vector<rect> rects =
{
{ 3731, 2433, 1356, 937 },
{ 6003, 3172, 1066, 743 },
{ 4119, 6403, 825, 1949 },
{ 10305, 2315, 776, 548 },
{ 13930, 5468, 1742, 626 },
{ 8614, 4107, 2709, 1793 },
{ 14606, 1887, 5368, 1326 },
{ 17990, 5196, 1163, 1911 },
{ 6728, 7881, 3676, 1210 },
{ 14704, 9789, 5271, 1092 },
{ 4071, 10723, 4739, 898 },
{ 11755, 9010, 1357, 2806 },
{ 13978, 4068, 776, 509 },
{ 17507, 3717, 777, 471 },
{ 20358, 6092, 824, 1093 },
{ 6390, 4535, 1066, 1715 },
{ 13978, 7182, 2516, 1365 },
{ 17942, 11580, 2854, 665 },
{ 9919, 10450, 873, 1716 },
{ 5568, 13215, 7446, 509 },
{ 7357, 15277, 3145, 3234 },
{ 3539, 12592, 631, 509 },
{ 4747, 14498, 825, 626 },
{ 4554, 16913, 969, 1443 },
{ 12771, 14693, 2323, 548 },
{ 18714, 8193, 2372, 586 },
{ 22292, 2743, 487, 1638 },
{ 20987, 17535, 1163, 1249 },
{ 19536, 18859, 632, 431 },
{ 19778, 15394, 1356, 626 },
{ 22969, 15394, 631, 2066 },
};
rt_type tree;
// Insert the rectangle objects into the tree.
int value = 0;
for (const auto& rect : rects)
tree.insert({{rect.x, rect.y}, {rect.x + rect.w, rect.y + rect.h}}, value++);
// Export the tree structure as a SVG for visualization.
std::string tree_svg = tree.export_tree(rt_type::export_tree_type::extent_as_svg);
std::ofstream fout("bounds.svg");
fout << tree_svg;
return EXIT_SUCCESS;
}
catch (...)
{
return EXIT_FAILURE;
}
/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
