1 /****************************************************************************** 2 * Project: libspatialindex - A C++ library for spatial indexing 3 * Author: Marios Hadjieleftheriou, mhadji@gmail.com 4 ****************************************************************************** 5 * Copyright (c) 2002, Marios Hadjieleftheriou 6 * 7 * All rights reserved. 8 * 9 * Permission is hereby granted, free of charge, to any person obtaining a 10 * copy of this software and associated documentation files (the "Software"), 11 * to deal in the Software without restriction, including without limitation 12 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 13 * and/or sell copies of the Software, and to permit persons to whom the 14 * Software is furnished to do so, subject to the following conditions: 15 * 16 * The above copyright notice and this permission notice shall be included 17 * in all copies or substantial portions of the Software. 18 * 19 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS 20 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 21 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 22 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 23 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 24 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 25 * DEALINGS IN THE SOFTWARE. 26 ******************************************************************************/ 27 28 #pragma once 29 30 #include "Statistics.h" 31 #include "Node.h" 32 #include "PointerPoolNode.h" 33 34 namespace SpatialIndex 35 { 36 namespace RTree 37 { 38 class RTree : public ISpatialIndex 39 { 40 //class NNEntry; 41 42 public: 43 RTree(IStorageManager&, Tools::PropertySet&); 44 // String Value Description 45 // ---------------------------------------------- 46 // IndexIndentifier VT_LONG If specified an existing index will be openened from the supplied 47 // storage manager with the given index id. Behaviour is unspecified 48 // if the index id or the storage manager are incorrect. 49 // Dimension VT_ULONG Dimensionality of the data that will be inserted. 50 // IndexCapacity VT_ULONG The index node capacity. Default is 100. 51 // LeafCapactiy VT_ULONG The leaf node capacity. Default is 100. 52 // FillFactor VT_DOUBLE The fill factor. Default is 70% 53 // TreeVariant VT_LONG Can be one of Linear, Quadratic or Rstar. Default is Rstar 54 // NearMinimumOverlapFactor VT_ULONG Default is 32. 55 // SplitDistributionFactor VT_DOUBLE Default is 0.4 56 // ReinsertFactor VT_DOUBLE Default is 0.3 57 // EnsureTightMBRs VT_BOOL Default is true 58 // IndexPoolCapacity VT_LONG Default is 100 59 // LeafPoolCapacity VT_LONG Default is 100 60 // RegionPoolCapacity VT_LONG Default is 1000 61 // PointPoolCapacity VT_LONG Default is 500 62 63 virtual ~RTree(); 64 65 66 67 // 68 // ISpatialIndex interface 69 // 70 virtual void insertData(uint32_t len, const byte* pData, const IShape& shape, id_type shapeIdentifier); 71 virtual bool deleteData(const IShape& shape, id_type id); 72 virtual void containsWhatQuery(const IShape& query, IVisitor& v); 73 virtual void intersectsWithQuery(const IShape& query, IVisitor& v); 74 virtual void pointLocationQuery(const Point& query, IVisitor& v); 75 virtual void nearestNeighborQuery(uint32_t k, const IShape& query, IVisitor& v, INearestNeighborComparator&); 76 virtual void nearestNeighborQuery(uint32_t k, const IShape& query, IVisitor& v); 77 virtual void selfJoinQuery(const IShape& s, IVisitor& v); 78 virtual void queryStrategy(IQueryStrategy& qs); 79 virtual void getIndexProperties(Tools::PropertySet& out) const; 80 virtual void addCommand(ICommand* pCommand, CommandType ct); 81 virtual bool isIndexValid(); 82 virtual void getStatistics(IStatistics** out) const; 83 84 private: 85 void initNew(Tools::PropertySet&); 86 void initOld(Tools::PropertySet& ps); 87 void storeHeader(); 88 void loadHeader(); 89 90 void insertData_impl(uint32_t dataLength, byte* pData, Region& mbr, id_type id); 91 void insertData_impl(uint32_t dataLength, byte* pData, Region& mbr, id_type id, uint32_t level, byte* overflowTable); 92 bool deleteData_impl(const Region& mbr, id_type id); 93 94 id_type writeNode(Node*); 95 NodePtr readNode(id_type page); 96 void deleteNode(Node*); 97 98 void rangeQuery(RangeQueryType type, const IShape& query, IVisitor& v); 99 void selfJoinQuery(id_type id1, id_type id2, const Region& r, IVisitor& vis); 100 void visitSubTree(NodePtr subTree, IVisitor& v); 101 102 IStorageManager* m_pStorageManager; 103 104 id_type m_rootID, m_headerID; 105 106 RTreeVariant m_treeVariant; 107 108 double m_fillFactor; 109 110 uint32_t m_indexCapacity; 111 112 uint32_t m_leafCapacity; 113 114 uint32_t m_nearMinimumOverlapFactor; 115 // The R*-Tree 'p' constant, for calculating nearly minimum overlap cost. 116 // [Beckmann, Kriegel, Schneider, Seeger 'The R*-tree: An efficient and Robust Access Method 117 // for Points and Rectangles', Section 4.1] 118 119 double m_splitDistributionFactor; 120 // The R*-Tree 'm' constant, for calculating spliting distributions. 121 // [Beckmann, Kriegel, Schneider, Seeger 'The R*-tree: An efficient and Robust Access Method 122 // for Points and Rectangles', Section 4.2] 123 124 double m_reinsertFactor; 125 // The R*-Tree 'p' constant, for removing entries at reinserts. 126 // [Beckmann, Kriegel, Schneider, Seeger 'The R*-tree: An efficient and Robust Access Method 127 // for Points and Rectangles', Section 4.3] 128 129 uint32_t m_dimension; 130 131 Region m_infiniteRegion; 132 133 Statistics m_stats; 134 135 bool m_bTightMBRs; 136 137 Tools::PointerPool<Point> m_pointPool; 138 Tools::PointerPool<Region> m_regionPool; 139 Tools::PointerPool<Node> m_indexPool; 140 Tools::PointerPool<Node> m_leafPool; 141 142 std::vector<Tools::SmartPointer<ICommand> > m_writeNodeCommands; 143 std::vector<Tools::SmartPointer<ICommand> > m_readNodeCommands; 144 std::vector<Tools::SmartPointer<ICommand> > m_deleteNodeCommands; 145 146 #ifdef HAVE_PTHREAD_H 147 pthread_mutex_t m_lock; 148 #endif 149 150 class NNEntry 151 { 152 public: 153 id_type m_id; 154 IEntry* m_pEntry; 155 double m_minDist; 156 NNEntry(id_type id,IEntry * e,double f)157 NNEntry(id_type id, IEntry* e, double f) : m_id(id), m_pEntry(e), m_minDist(f) {} ~NNEntry()158 ~NNEntry() {} 159 160 struct ascending : public std::binary_function<NNEntry*, NNEntry*, bool> 161 { operatorascending162 bool operator()(const NNEntry* __x, const NNEntry* __y) const { return __x->m_minDist > __y->m_minDist; } 163 }; 164 }; // NNEntry 165 166 class NNComparator : public INearestNeighborComparator 167 { 168 public: getMinimumDistance(const IShape & query,const IShape & entry)169 double getMinimumDistance(const IShape& query, const IShape& entry) 170 { 171 return query.getMinimumDistance(entry); 172 } 173 getMinimumDistance(const IShape & query,const IData & data)174 double getMinimumDistance(const IShape& query, const IData& data) 175 { 176 IShape* pS; 177 data.getShape(&pS); 178 double ret = query.getMinimumDistance(*pS); 179 delete pS; 180 return ret; 181 } 182 }; // NNComparator 183 184 class ValidateEntry 185 { 186 public: ValidateEntry(Region & r,NodePtr & pNode)187 ValidateEntry(Region& r, NodePtr& pNode) : m_parentMBR(r), m_pNode(pNode) {} 188 189 Region m_parentMBR; 190 NodePtr m_pNode; 191 }; // ValidateEntry 192 193 friend class Node; 194 friend class Leaf; 195 friend class Index; 196 friend class BulkLoader; 197 198 friend std::ostream& operator<<(std::ostream& os, const RTree& t); 199 }; // RTree 200 201 std::ostream& operator<<(std::ostream& os, const RTree& t); 202 } 203 } 204