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             :  * SPDX-License-Identifier: MIT
      11             :  ****************************************************************************/
      12             : 
      13             : // NOTE: The upstream of this file is in
      14             : // https://github.com/bjornharrtell/flatgeobuf/tree/master/src/cpp
      15             : 
      16             : #ifndef FLATGEOBUF_PACKEDRTREE_H_
      17             : #define FLATGEOBUF_PACKEDRTREE_H_
      18             : 
      19             : #include <cmath>
      20             : #include <deque>
      21             : #include <numeric>
      22             : 
      23             : #include "flatbuffers/flatbuffers.h"
      24             : 
      25             : namespace FlatGeobuf
      26             : {
      27             : 
      28             : struct NodeItem
      29             : {
      30             :     double minX;
      31             :     double minY;
      32             :     double maxX;
      33             :     double maxY;
      34             :     uint64_t offset;
      35             : 
      36         116 :     double width() const
      37             :     {
      38         116 :         return maxX - minX;
      39             :     }
      40             : 
      41         116 :     double height() const
      42             :     {
      43         116 :         return maxY - minY;
      44             :     }
      45             : 
      46             :     static NodeItem sum(NodeItem a, const NodeItem &b)
      47             :     {
      48             :         a.expand(b);
      49             :         return a;
      50             :     }
      51             : 
      52             :     static NodeItem create(uint64_t offset = 0);
      53             :     const NodeItem &expand(const NodeItem &r);
      54             :     bool intersects(const NodeItem &r) const;
      55             :     std::vector<double> toVector();
      56             : };
      57             : 
      58             : struct Item
      59             : {
      60             :     NodeItem nodeItem;
      61             : };
      62             : 
      63             : struct SearchResultItem
      64             : {
      65             :     uint64_t offset;
      66             :     uint64_t index;
      67             : };
      68             : 
      69             : std::ostream &operator<<(std::ostream &os, NodeItem const &value);
      70             : 
      71             : uint32_t hilbert(uint32_t x, uint32_t y);
      72             : uint32_t hilbert(const NodeItem &n, uint32_t hilbertMax, const double minX,
      73             :                  const double minY, const double width, const double height);
      74             : void hilbertSort(std::vector<std::shared_ptr<Item>> &items);
      75             : 
      76             : constexpr uint32_t HILBERT_MAX = (1 << 16) - 1;
      77             : 
      78             : template <class ITEM_TYPE>
      79         232 : NodeItem calcExtent(const std::deque<ITEM_TYPE> &items)
      80             : {
      81         464 :     return std::accumulate(items.begin(), items.end(), NodeItem::create(0),
      82         322 :                            [](NodeItem a, const ITEM_TYPE &b) -> NodeItem
      83         786 :                            { return a.expand(b.nodeItem); });
      84             : }
      85             : 
      86         116 : template <class ITEM_TYPE> void hilbertSort(std::deque<ITEM_TYPE> &items)
      87             : {
      88         116 :     NodeItem extent = calcExtent(items);
      89         116 :     const double minX = extent.minX;
      90         116 :     const double minY = extent.minY;
      91         116 :     const double width = extent.width();
      92         116 :     const double height = extent.height();
      93         116 :     std::sort(
      94             :         items.begin(), items.end(),
      95         240 :         [minX, minY, width, height](const ITEM_TYPE &a, const ITEM_TYPE &b)
      96             :         {
      97             :             uint32_t ha =
      98         120 :                 hilbert(a.nodeItem, HILBERT_MAX, minX, minY, width, height);
      99             :             uint32_t hb =
     100         120 :                 hilbert(b.nodeItem, HILBERT_MAX, minX, minY, width, height);
     101         120 :             return ha > hb;
     102             :         });
     103         116 : }
     104             : 
     105             : void hilbertSort(std::vector<NodeItem> &items);
     106             : NodeItem calcExtent(const std::vector<std::shared_ptr<Item>> &items);
     107             : NodeItem calcExtent(const std::vector<NodeItem> &rects);
     108             : 
     109             : /**
     110             :  * Packed R-Tree
     111             :  * Based on https://github.com/mourner/flatbush
     112             :  */
     113             : class PackedRTree
     114             : {
     115             :     NodeItem _extent;
     116             :     NodeItem *_nodeItems = nullptr;
     117             :     uint64_t _numItems;
     118             :     uint64_t _numNodes;
     119             :     uint16_t _nodeSize;
     120             :     std::vector<std::pair<uint64_t, uint64_t>> _levelBounds;
     121             :     void init(const uint16_t nodeSize);
     122             :     void generateNodes();
     123             :     void fromData(const void *data);
     124             : 
     125             :   public:
     126         116 :     ~PackedRTree()
     127         116 :     {
     128         116 :         if (_nodeItems != nullptr)
     129         116 :             delete[] _nodeItems;
     130         116 :     }
     131             : 
     132             :     PackedRTree(const std::vector<std::shared_ptr<Item>> &items,
     133             :                 const NodeItem &extent, const uint16_t nodeSize = 16);
     134             :     PackedRTree(const std::vector<NodeItem> &nodes, const NodeItem &extent,
     135             :                 const uint16_t nodeSize = 16);
     136             :     PackedRTree(const void *data, const uint64_t numItems,
     137             :                 const uint16_t nodeSize = 16);
     138             :     PackedRTree(std::function<void(NodeItem *)> fillNodeItems,
     139             :                 const uint64_t numItems, const NodeItem &extent,
     140             :                 const uint16_t nodeSize = 16);
     141             :     std::vector<SearchResultItem> search(double minX, double minY, double maxX,
     142             :                                          double maxY) const;
     143             :     static std::vector<SearchResultItem> streamSearch(
     144             :         const uint64_t numItems, const uint16_t nodeSize, const NodeItem &item,
     145             :         const std::function<void(uint8_t *, size_t, size_t)> &readNode);
     146             :     static std::vector<std::pair<uint64_t, uint64_t>>
     147             :     generateLevelBounds(const uint64_t numItems, const uint16_t nodeSize);
     148             :     uint64_t size() const;
     149             :     static uint64_t size(const uint64_t numItems, const uint16_t nodeSize = 16);
     150             :     NodeItem getExtent() const;
     151             :     void streamWrite(const std::function<void(uint8_t *, size_t)> &writeData);
     152             : };
     153             : 
     154             : }  // namespace FlatGeobuf
     155             : 
     156             : #endif