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