Line data Source code
1 : /******************************************************************************
2 : *
3 : * Project: FlatGeobuf
4 : * Purpose: Packed RTree management
5 : * Author: Björn Harrtell <bjorn at wololo dot org>
6 : *
7 : ******************************************************************************
8 : * Copyright (c) 2018-2020, Björn Harrtell <bjorn at wololo dot org>
9 : *
10 : * Permission is hereby granted, free of charge, to any person obtaining a
11 : * copy of this software and associated documentation files (the "Software"),
12 : * to deal in the Software without restriction, including without limitation
13 : * the rights to use, copy, modify, merge, publish, distribute, sublicense,
14 : * and/or sell copies of the Software, and to permit persons to whom the
15 : * Software is furnished to do so, subject to the following conditions:
16 : *
17 : * The above copyright notice and this permission notice shall be included
18 : * in all copies or substantial portions of the Software.
19 : *
20 : * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
21 : * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
22 : * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
23 : * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
24 : * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
25 : * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
26 : * DEALINGS IN THE SOFTWARE.
27 : ****************************************************************************/
28 :
29 : // NOTE: The upstream of this file is in
30 : // https://github.com/bjornharrtell/flatgeobuf/tree/master/src/cpp
31 :
32 : #ifndef FLATGEOBUF_PACKEDRTREE_H_
33 : #define FLATGEOBUF_PACKEDRTREE_H_
34 :
35 : #include <cmath>
36 : #include <deque>
37 : #include <numeric>
38 :
39 : #include "flatbuffers/flatbuffers.h"
40 :
41 : namespace FlatGeobuf
42 : {
43 :
44 : struct NodeItem
45 : {
46 : double minX;
47 : double minY;
48 : double maxX;
49 : double maxY;
50 : uint64_t offset;
51 :
52 115 : double width() const
53 : {
54 115 : return maxX - minX;
55 : }
56 :
57 115 : double height() const
58 : {
59 115 : return maxY - minY;
60 : }
61 :
62 : static NodeItem sum(NodeItem a, const NodeItem &b)
63 : {
64 : a.expand(b);
65 : return a;
66 : }
67 :
68 : static NodeItem create(uint64_t offset = 0);
69 : const NodeItem &expand(const NodeItem &r);
70 : bool intersects(const NodeItem &r) const;
71 : std::vector<double> toVector();
72 : };
73 :
74 : struct Item
75 : {
76 : NodeItem nodeItem;
77 : };
78 :
79 : struct SearchResultItem
80 : {
81 : uint64_t offset;
82 : uint64_t index;
83 : };
84 :
85 : std::ostream &operator<<(std::ostream &os, NodeItem const &value);
86 :
87 : uint32_t hilbert(uint32_t x, uint32_t y);
88 : uint32_t hilbert(const NodeItem &n, uint32_t hilbertMax, const double minX,
89 : const double minY, const double width, const double height);
90 : void hilbertSort(std::vector<std::shared_ptr<Item>> &items);
91 :
92 : constexpr uint32_t HILBERT_MAX = (1 << 16) - 1;
93 :
94 : template <class ITEM_TYPE>
95 230 : NodeItem calcExtent(const std::deque<ITEM_TYPE> &items)
96 : {
97 460 : return std::accumulate(items.begin(), items.end(), NodeItem::create(0),
98 318 : [](NodeItem a, const ITEM_TYPE &b) -> NodeItem
99 778 : { return a.expand(b.nodeItem); });
100 : }
101 :
102 115 : template <class ITEM_TYPE> void hilbertSort(std::deque<ITEM_TYPE> &items)
103 : {
104 115 : NodeItem extent = calcExtent(items);
105 115 : const double minX = extent.minX;
106 115 : const double minY = extent.minY;
107 115 : const double width = extent.width();
108 115 : const double height = extent.height();
109 115 : std::sort(
110 : items.begin(), items.end(),
111 238 : [minX, minY, width, height](const ITEM_TYPE &a, const ITEM_TYPE &b)
112 : {
113 : uint32_t ha =
114 119 : hilbert(a.nodeItem, HILBERT_MAX, minX, minY, width, height);
115 : uint32_t hb =
116 119 : hilbert(b.nodeItem, HILBERT_MAX, minX, minY, width, height);
117 119 : return ha > hb;
118 : });
119 115 : }
120 :
121 : void hilbertSort(std::vector<NodeItem> &items);
122 : NodeItem calcExtent(const std::vector<std::shared_ptr<Item>> &items);
123 : NodeItem calcExtent(const std::vector<NodeItem> &rects);
124 :
125 : /**
126 : * Packed R-Tree
127 : * Based on https://github.com/mourner/flatbush
128 : */
129 : class PackedRTree
130 : {
131 : NodeItem _extent;
132 : NodeItem *_nodeItems = nullptr;
133 : uint64_t _numItems;
134 : uint64_t _numNodes;
135 : uint16_t _nodeSize;
136 : std::vector<std::pair<uint64_t, uint64_t>> _levelBounds;
137 : void init(const uint16_t nodeSize);
138 : void generateNodes();
139 : void fromData(const void *data);
140 :
141 : public:
142 115 : ~PackedRTree()
143 115 : {
144 115 : if (_nodeItems != nullptr)
145 115 : delete[] _nodeItems;
146 115 : }
147 :
148 : PackedRTree(const std::vector<std::shared_ptr<Item>> &items,
149 : const NodeItem &extent, const uint16_t nodeSize = 16);
150 : PackedRTree(const std::vector<NodeItem> &nodes, const NodeItem &extent,
151 : const uint16_t nodeSize = 16);
152 : PackedRTree(const void *data, const uint64_t numItems,
153 : const uint16_t nodeSize = 16);
154 : PackedRTree(std::function<void(NodeItem *)> fillNodeItems,
155 : const uint64_t numItems, const NodeItem &extent,
156 : const uint16_t nodeSize = 16);
157 : std::vector<SearchResultItem> search(double minX, double minY, double maxX,
158 : double maxY) const;
159 : static std::vector<SearchResultItem> streamSearch(
160 : const uint64_t numItems, const uint16_t nodeSize, const NodeItem &item,
161 : const std::function<void(uint8_t *, size_t, size_t)> &readNode);
162 : static std::vector<std::pair<uint64_t, uint64_t>>
163 : generateLevelBounds(const uint64_t numItems, const uint16_t nodeSize);
164 : uint64_t size() const;
165 : static uint64_t size(const uint64_t numItems, const uint16_t nodeSize = 16);
166 : NodeItem getExtent() const;
167 : void streamWrite(const std::function<void(uint8_t *, size_t)> &writeData);
168 : };
169 :
170 : } // namespace FlatGeobuf
171 :
172 : #endif
|
