summaryrefslogtreecommitdiffstats
path: root/doc/rtree.rst
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--doc/rtree.rst727
1 files changed, 727 insertions, 0 deletions
diff --git a/doc/rtree.rst b/doc/rtree.rst
new file mode 100644
index 0000000..4f691e2
--- /dev/null
+++ b/doc/rtree.rst
@@ -0,0 +1,727 @@
+
+.. highlight:: cpp
+
+R-tree
+======
+
+Overview
+--------
+
+`R-tree <https://en.wikipedia.org/wiki/R-tree>`_ is a tree-based data
+structure designed for optimal query performance on multi-dimensional spatial
+objects with rectangular bounding shapes. The R-tree implementation included
+in this library is a variant of R-tree known as `R*-tree
+<https://en.wikipedia.org/wiki/R*_tree>`_ which differs from the original
+R-tree in that it may re-insert an object if the insertion of that object
+would cause the original target directory to overflow. Such re-insertions
+lead to more balanced tree which in turn lead to better query performance, at
+the expense of slightly more overhead at insertion time.
+
+Our implementation of R-tree theoretically supports any number of dimensions
+although certain functionalities, especially those related to visualization,
+are only supported for 2-dimensional instances.
+
+R-tree consists of three types of nodes. Value nodes store the values
+inserted externally and always sit at the bottom of the tree. Leaf directory
+nodes sit directly above the value nodes, and store only value nodes as their
+child nodes. The rest are all non-leaf directory nodes which can either store
+leaf or non-leaf directory nodes.
+
+
+Quick start
+-----------
+
+Let's go through a very simple example to demonstrate how to use
+:cpp:class:`~mdds::rtree`. First, you need to specify a concrete type by
+specifying the key type and value type to use::
+
+ #include <mdds/rtree.hpp>
+
+ #include <string>
+ #include <iostream>
+
+ // key values are of type double, and we are storing std::string as a
+ // value for each spatial object. By default, tree becomes 2-dimensional
+ // object store unless otherwise specified.
+ using rt_type = mdds::rtree<double, std::string>;
+
+You'll only need to specify the types of key and value here unless you want to
+customize other properties of :cpp:class:`~mdds::rtree` including the number
+of dimensions. By default, :cpp:class:`~mdds::rtree` sets the number of
+dimensions to 2.
+
+::
+
+ rt_type tree;
+
+Instantiating an rtree instance should be no brainer as it requires no input
+parameters. Now, let's insert some data::
+
+ tree.insert({{0.0, 0.0}, {15.0, 20.0}}, "first rectangle data");
+
+This inserts a string value associated with a bounding rectangle of (0, 0) -
+(15, 20). Note that in the above code we are passing the bounding rectangle
+parameter to rtree's :cpp:func:`~mdds::rtree::insert` method as a nested
+initializer list, which implicitly gets converted to
+:cpp:class:`~mdds::rtree::extent_type`. You can also use the underlying type
+directly as follows::
+
+ rt_type::extent_type bounds({-2.0, -1.0}, {1.0, 2.0});
+ std::cout << "inserting value for " << bounds.to_string() << std::endl;
+ tree.insert(bounds, "second rectangle data");
+
+which inserts a string value associated with a bounding rectangle of (-2, -1)
+to (1, 2). You may have noticed that this code also uses extent_type's
+:cpp:func:`~mdds::rtree::extent_type::to_string` method which returns a string
+representation of the bounding rectangle. This may come in handy when
+debugging your code. This method should work as long as the key type used in
+your rtree class overloads ``std::ostream``'s ``<<`` operator function.
+
+Running this code will generate the following output:
+
+.. code-block:: none
+
+ inserting value for (-2, -1) - (1, 2)
+
+As :cpp:class:`~mdds::rtree::extent_type` consists of two members called
+``start`` and ``end`` both of which are of type
+:cpp:class:`~mdds::rtree::point_type`, which in turn contains an array of keys
+called ``d`` whose size equals the number of dimensions, you can modify the
+extent directly::
+
+ bounds.start.d[0] = -1.0; // Change the first dimension value of the start rectangle point.
+ bounds.end.d[1] += 1.0; // Increment the second dimension value of the end rectangle point.
+ std::cout << "inserting value for " << bounds.to_string() << std::endl;
+ tree.insert(bounds, "third rectangle data");
+
+This code will insert a string value associated with a rectangle of (-1, -1)
+to (1, 3), and will generate the following output:
+
+.. code-block:: none
+
+ inserting value for (-1, -1) - (1, 3)
+
+So far we have only inserted data associated with rectangle shapes, but
+:cpp:class:`~mdds::rtree` also allows data associated with points to co-exist
+in the same tree. The following code inserts a string value associated with a
+point (5, 6)::
+
+ tree.insert({5.0, 6.0}, "first point data");
+
+Like the verfy first rectangle data we've inserted, we are passing the point
+data as an initializer list of two elements (for 2-dimensional data storage),
+which will implicitly get converted to :cpp:class:`~mdds::rtree::point_type`
+before it enters into the call.
+
+Now that some data have been inserted, it's time to run some queries. Let's
+query all objects that overlap with a certain rectangular region either
+partially or fully. The following code will do just that::
+
+ // Search for all objects that overlap with a (4, 4) - (7, 7) rectangle.
+ auto results = tree.search({{4.0, 4.0}, {7.0, 7.0}}, rt_type::search_type::overlap);
+
+ for (const std::string& v : results)
+ std::cout << "value: " << v << std::endl;
+
+In this query, we are specifying the search region to be (4, 4) to (7, 7)
+which should overlap with the first rectangle data and the first point data.
+Indeed, when you execute this code, you will see the following output:
+
+.. code-block:: none
+
+ value: first rectangle data
+ value: first point data
+
+indicating that the query region does overlap with two of the stored values
+
+Note that the :cpp:func:`~mdds::rtree::search` method takes exactly two
+arguments; the first one specifies the search region while the second two
+specifies the type of search to be performed. In the above call we passed
+:cpp:type:`~mdds::detail::rtree::search_type`'s ``overlap`` enum value which
+picks up all values whose bounding rectangles overlap with the search region
+either partially or fully.
+
+Sometimes, however, you may need to find a value whose bounding rectangle
+matches exactly the search region you specify in your query. You can achieve
+that by setting the search type to ``match``.
+
+Here is an example::
+
+ // Search for all objects whose bounding rectangles are exactly (4, 4) - (7, 7).
+ auto results = tree.search({{4.0, 4.0}, {7.0, 7.0}}, rt_type::search_type::match);
+ std::cout << "number of results: " << std::distance(results.begin(), results.end()) << std::endl;
+
+The search region is identical to that of the previous example, but the search
+type is set to ``match`` instead. Then the next line will count the number of
+results and print it out. The output you will see is as follows:
+
+.. code-block:: none
+
+ number of results: 0
+
+indicating that the results are empty. That is expected since none of the
+objects stored in the tree have an exact bounding rectangle of (4, 4) - (7,
+7). When you change the search region to (0, 0) - (15, 20), however, you'll
+get one object back. Here is the actual code::
+
+ // Search for all objects whose bounding rectangles are exactly (0, 0) - (15, 20).
+ auto results = tree.search({{0.0, 0.0}, {15.0, 20.0}}, rt_type::search_type::match);
+ std::cout << "number of results: " << std::distance(results.begin(), results.end()) << std::endl;
+
+which is identical to the previous one except for the search resion. This is
+its output:
+
+.. code-block:: none
+
+ number of results: 1
+
+indicating that it has found exactly one object whose bounding rectangle
+exactly matches the search region.
+
+It's worth mentioning that :cpp:class:`~mdds::rtree` supports storage of
+multiple objects with identical bounding rectangle. As such, searching with
+the search type of ``match`` can return more than one result.
+
+As you may have noticed in these example codes, the
+:cpp:class:`~mdds::rtree::search_results` object does provide
+:cpp:func:`~mdds::rtree::search_results::begin` and
+:cpp:func:`~mdds::rtree::search_results::end` methods that return standard
+iterators which you can plug into various iterator algorithms from the STL.
+Dereferencing the iterator will return a reference to the stored value i.e.
+this line::
+
+ std::cout << "value: " << *results.begin() << std::endl;
+
+which immediately comes after the previous search will output:
+
+.. code-block:: none
+
+ value: first rectangle data
+
+In addition to accessing the value that the iterator references, you can also
+query from the same iterator object the bounding rectangle associated with the
+value as well as its depth in the tree by calling its
+:cpp:func:`~mdds::rtree::iterator_base::extent` and
+:cpp:func:`~mdds::rtree::iterator_base::depth` methods, respectively, as in
+the following code::
+
+ auto it = results.begin();
+ std::cout << "value: " << *it << std::endl;
+ std::cout << "extent: " << it.extent().to_string() << std::endl;
+ std::cout << "depth: " << it.depth() << std::endl;
+
+Running this code will produce the following output:
+
+.. code-block:: none
+
+ value: first rectangle data
+ extent: (0, 0) - (15, 20)
+ depth: 1
+
+A depth value represents the distance of the node where the value is stored
+from the root node of the tree, and is technically 0-based. However, you will
+never see a depth of 0 in the search results since the root node of a R-tree
+is always a directory node, and a directory node only stores other child nodes
+and never a value (hence never appears in the search results).
+
+
+Removing a value from tree
+--------------------------
+
+Removing an existing value from the tree first requires you to perform the
+search to obtian search results, then from the search results get the iterator
+and advance it to the position of the value you wish to remove. Once you have
+your iterator set to the right position, pass it to the
+:cpp:func:`~mdds::rtree::erase` method to remove that value.
+
+Note that you can only remove one value at a time, and the iterator becomes
+invalid each time you call the :cpp:func:`~mdds::rtree::erase` method to
+remove a value.
+
+Here is a contrived example to demonstrate how erasing a value works::
+
+ #include <mdds/rtree.hpp>
+
+ #include <string>
+ #include <iostream>
+
+ int main()
+ {
+ using rt_type = mdds::rtree<int, std::string>;
+
+ rt_type tree;
+
+ // Insert multiple values at the same point.
+ tree.insert({1, 1}, "A");
+ tree.insert({1, 1}, "B");
+ tree.insert({1, 1}, "C");
+ tree.insert({1, 1}, "D");
+ tree.insert({1, 1}, "E");
+
+ // This should return all five values.
+ auto results = tree.search({1, 1}, rt_type::search_type::match);
+
+ for (const std::string& v : results)
+ std::cout << v << std::endl;
+
+ // Erase "C".
+ for (auto it = results.begin(); it != results.end(); ++it)
+ {
+ if (*it == "C")
+ {
+ tree.erase(it);
+ break; // This invalidates the iterator. Bail out.
+ }
+ }
+
+ std::cout << "'C' has been erased." << std::endl;
+
+ // Now this should only return A, B, D and E.
+ results = tree.search({1, 1}, rt_type::search_type::match);
+
+ for (const std::string& v : results)
+ std::cout << v << std::endl;
+
+ return EXIT_SUCCESS;
+ }
+
+In this code, we are intentionally putting 5 values to the same 2-dimensional
+point (1, 1), then removing one of them based on matching criteria (of being
+equal to "C").
+
+Compiling and running this code will generate the following output:
+
+.. code-block:: none
+
+ A
+ B
+ C
+ D
+ E
+ 'C' has been erased.
+ A
+ B
+ D
+ E
+
+which clearly shows that the 'C' has been successfully erased.
+
+
+Visualize R-tree structure
+--------------------------
+
+In this section we will illustrate a way to visualize an R-tree structure via
+:cpp:func:`~mdds::rtree::export_tree` method, which can be useful when you
+need to visually inspect the tree structure to see how well balanced it is (or
+not).
+
+We will be using the following set of 2-dimensional rectangles as the bounding
+rectangles for input values.
+
+.. figure:: _static/images/rtree_bounds_src.png
+ :align: center
+
+For input values, we'll simply use linearly increasing series of integer
+values, but the values themselves are not the focus of this section, and we'll
+not talk much about that. We will also intentionally make the capacity of
+directory nodes smaller so that the tree will split more frequently during
+insertion even for smaller number of inputs.
+
+Now, let's take a look at the code::
+
+ #include <mdds/rtree.hpp>
+
+ #include <iostream>
+ #include <fstream>
+
+ // Make the node capacity intentionally small.
+ struct tiny_trait_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_trait_2d>;
+
+ int main()
+ {
+ // 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;
+ }
+
+First, we need to talk about how the concrete rtree type is instantiated::
+
+ // Make the node capacity intentionally small.
+ struct tiny_trait_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_trait_2d>;
+
+The first and second template arguments specify the key and value types to be
+both ``int``. This time around, however, we are passing a third template
+argument which is a struct containing several static constant values. These
+constant values define certain characteristics of your R-tree, and there are
+some restrictions you need to be aware of in case you need to use your own
+custom trait for your R-tree. Refer to
+:cpp:class:`~mdds::detail::rtree::default_rtree_traits`, which is the default
+trait used when you don't specify your own, for the descriptions of the
+individual constants that your trait struct is expected to have as well as
+restrictions that you must be aware of.
+
+Also be aware that these constants must all be constant expressions with
+``constexpr`` specifiers, as some of them are used within ``static_assert``
+declarations, and even those that are currently not used within
+``static_assert`` may be used in ``static_assert`` in the future.
+
+As far as our current example goes, the only part of the custom trait we need
+to highlight is that we are setting the directory node size to 2-to-5 instead
+of the default size of 40-to-100, to trigger more node splits and make the
+tree artificially deeper.
+
+Let's move on to the next part of the code::
+
+ // 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 },
+ };
+
+This ``rects`` variable holds an array of 2-dimensional rectangle data that
+represent the positions and sizes of rectangles shown earlier in this section.
+This will be used as bounding rectangles for the input values in the next part
+of the code::
+
+ 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++);
+
+Here, the tree is instantiated, and the rectangles are inserted with their
+associated values one at a time. Once the tree is populated, the code that
+follows will export the structure of the tree as an SVG string, which will
+then be saved to a file on disk::
+
+ // 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;
+
+When you open the exported SVG file named **bounds.svg** in a SVG viewer,
+you'll see something similar to this:
+
+.. figure:: _static/images/rtree_bounds_tree.png
+ :align: center
+
+which depicts not only the bounding rectangles of the inserted values
+(the red rectangles), but also the bounding rectangles of the directory
+nodes as well (the light green rectangles).
+
+
+Bulk-loading data
+-----------------
+
+In this section we will explore on how to bulk-load data into an
+:cpp:class:`~mdds::rtree` instance via rtree's own
+:cpp:class:`~mdds::rtree::bulk_loader` class. In this example, we'll be using
+the same custom trait we've used in the previous section in order to
+artificially promote the rate of node splits. The first part of the code::
+
+ #include <mdds/rtree.hpp>
+
+ #include <iostream>
+ #include <fstream>
+
+ // Make the node capacity intentionally small.
+ struct tiny_trait_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_trait_2d>;
+
+is pretty much identical to the example in the last section. The next part of
+the code defines what bounding rectangles to be inserted. Here, we are using
+a different set of rectangles than the previous example to illustrate the
+difference between a series of normal insertions and bulk-loading::
+
+ // 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 =
+ {
+ { 3538, 9126, 1908, 1908 },
+ { 34272, 52053, 2416, 2543 },
+ { 32113, 9761, 2416, 638 },
+ { 16493, 16747, 7369, 2289 },
+ { 29192, 23732, 3432, 2035 },
+ { 35797, 17000, 1781, 892 },
+ { 15857, 29319, 2162, 1654 },
+ { 5825, 24239, 3559, 8512 },
+ { 9127, 46846, 2543, 1019 },
+ { 7094, 54338, 5210, 892 },
+ { 18779, 39734, 3813, 10417 },
+ { 32749, 35923, 2289, 2924 },
+ { 26018, 31098, 257, 2797 },
+ { 6713, 37066, 2924, 1146 },
+ { 19541, 3157, 3305, 1146 },
+ { 21953, 10904, 4448, 892 },
+ { 15984, 24240, 5210, 1273 },
+ { 8237, 15350, 2670, 2797 },
+ { 17001, 13826, 4067, 1273 },
+ { 30970, 13826, 3940, 765 },
+ { 9634, 6587, 1654, 1781 },
+ { 38464, 47099, 511, 1400 },
+ { 20556, 54085, 1400, 1527 },
+ { 37575, 24113, 1019, 765 },
+ { 20429, 21064, 1146, 1400 },
+ { 31733, 4427, 2543, 638 },
+ { 2142, 27161, 1273, 7369 },
+ { 3920, 43289, 8131, 1146 },
+ { 14714, 34272, 1400, 4956 },
+ { 38464, 41258, 1273, 1273 },
+ { 35542, 45703, 892, 1273 },
+ { 25891, 50783, 1273, 5083 },
+ { 35415, 28431, 2924, 1781 },
+ { 15476, 7349, 1908, 765 },
+ { 12555, 11159, 1654, 2035 },
+ { 11158, 21445, 1908, 2416 },
+ { 23350, 28049, 3432, 892 },
+ { 28684, 15985, 2416, 4321 },
+ { 24620, 21953, 1654, 638 },
+ { 30208, 30716, 2670, 2162 },
+ { 26907, 44179, 2797, 4067 },
+ { 21191, 35416, 2162, 1019 },
+ { 27668, 38717, 638, 3178 },
+ { 3666, 50528, 2035, 1400 },
+ { 15349, 48750, 2670, 1654 },
+ { 28430, 7221, 2162, 892 },
+ { 4808, 3158, 2416, 1273 },
+ { 38464, 3666, 1527, 1781 },
+ { 2777, 20937, 2289, 1146 },
+ { 38209, 9254, 1908, 1781 },
+ { 2269, 56497, 2289, 892 },
+ };
+
+As with the previous example, each line contains the top-left position as well
+as the size of a rectangle. We are now going to insert these rectangles in
+two different ways.
+
+First, we insert them via normal :cpp:func:`~mdds::rtree::insert` method::
+
+ void load_tree()
+ {
+ 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("bounds2.svg");
+ fout << tree_svg;
+ }
+
+This code should look familiar since it's nearly identical to the code in the
+previous section. After the insertion is done, we export the tree as an SVG
+to visualize its structure.
+
+Next, we insert the same set of rectangles via
+:cpp:class:`~mdds::rtree::bulk_loader`::
+
+ void bulkload_tree()
+ {
+ rt_type::bulk_loader loader;
+
+ // Insert the rectangle objects into the tree.
+ int value = 0;
+ for (const auto& rect : rects)
+ loader.insert({{rect.x, rect.y}, {rect.x + rect.w, rect.y + rect.h}}, value++);
+
+ // Start bulk-loading the tree.
+ rt_type tree = loader.pack();
+
+ // 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("bounds2-bulkload.svg");
+ fout << tree_svg;
+ }
+
+Inserting via :cpp:class:`~mdds::rtree::bulk_loader` shouldn't be too
+different than inserting via rtree's own insert methods. The only
+difference is that you instantiate a
+:cpp:class:`~mdds::rtree::bulk_loader` instance to insert all your data
+to it, then call its :cpp:func:`~mdds::rtree::bulk_loader::pack` method
+at the end to construct the final :cpp:class:`~mdds::rtree` instance.
+
+When the insertion is done and the tree instance created, we are once again
+exporting its structure to an SVG file for visualization.
+
+There are primarily two advantages to using
+:cpp:class:`~mdds::rtree::bulk_loader` to load data. First, unlike the
+normal insertion, bulk-loading does not trigger re-insertion nor node
+splits on the fly. Second, a tree created from bulk loader is typically
+well balanced than if you insert the same data through normal insertion.
+That is because the bulk loader sorts the data with respect to their
+bounding rectangles ahead of time and partition them evenly. The tree
+is then built from the bottom-up. You can visually see the effect of
+this when comparing the two trees built in our current example.
+
+The first one is from the tree built via normal insertion:
+
+.. figure:: _static/images/rtree_bounds2_tree.png
+ :align: center
+
+The top part of the picture looks very "busy" indicated by a darker
+green area representative of more directory nodes overlaping with each
+other. In general, the rectangles look bigger and show higher degree of
+overlaps.
+
+This one, on the other hand, is from the tree built with the same data
+set but through bulk-loading:
+
+.. figure:: _static/images/rtree_bounds2_tree_bulkload.png
+ :align: center
+
+The rectangles generally look smaller and show much less overlaps than the
+previous picture, which is considered to be a more balanced R-tree structure.
+
+
+API Reference
+-------------
+
+.. doxygenclass:: mdds::rtree
+ :members:
+
+.. doxygenstruct:: mdds::detail::rtree::default_rtree_traits
+ :members:
+
+.. doxygenstruct:: mdds::detail::rtree::integrity_check_properties
+ :members:
+
+.. doxygenenum:: mdds::detail::rtree::export_tree_type
+ :project: mdds
+
+.. doxygenenum:: mdds::detail::rtree::search_type
+ :project: mdds
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-22 22:55:17 +0000