src/rtree/RTree.h

Go to the documentation of this file.

/******************************************************************************
 * Project:  libspatialindex - A C++ library for spatial indexing
 * Author:   Marios Hadjieleftheriou, mhadji@gmail.com
 ******************************************************************************
 * Copyright (c) 2002, Marios Hadjieleftheriou
 *
 * All rights reserved.
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included
 * in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
 * DEALINGS IN THE SOFTWARE.
******************************************************************************/
 
#pragma once
 
#include "Statistics.h"
#include "Node.h"
#include "PointerPoolNode.h"
#include <memory>
 
namespace SpatialIndex
{
    namespace RTree
    {
        class RTree : public ISpatialIndex
        {
                  //class NNEntry;
 
        public:
            RTree(IStorageManager&, Tools::PropertySet&);
                // String                   Value     Description
                // ----------------------------------------------
                // IndexIndentifier         VT_LONG   If specified an existing index will be openened from the supplied
                //                          storage manager with the given index id. Behaviour is unspecified
                //                          if the index id or the storage manager are incorrect.
                // Dimension                VT_ULONG  Dimensionality of the data that will be inserted.
                // IndexCapacity            VT_ULONG  The index node capacity. Default is 100.
                // LeafCapactiy             VT_ULONG  The leaf node capacity. Default is 100.
                // FillFactor               VT_DOUBLE The fill factor. Default is 70%
                // TreeVariant              VT_LONG   Can be one of Linear, Quadratic or Rstar. Default is Rstar
                // NearMinimumOverlapFactor VT_ULONG  Default is 32.
                // SplitDistributionFactor  VT_DOUBLE Default is 0.4
                // ReinsertFactor           VT_DOUBLE Default is 0.3
                // EnsureTightMBRs          VT_BOOL   Default is true
                // IndexPoolCapacity        VT_LONG   Default is 100
                // LeafPoolCapacity         VT_LONG   Default is 100
                // RegionPoolCapacity       VT_LONG   Default is 1000
                // PointPoolCapacity        VT_LONG   Default is 500
 
            ~RTree() ;
 
 
 
            //
            // ISpatialIndex interface
            //
            virtual void insertData(uint32_t len, const uint8_t* pData, const IShape& shape, id_type shapeIdentifier) ;
            virtual bool deleteData(const IShape& shape, id_type id) ;
            virtual void internalNodesQuery(const IShape& query, IVisitor& v) ;
            virtual void containsWhatQuery(const IShape& query, IVisitor& v) ;
            virtual void intersectsWithQuery(const IShape& query, IVisitor& v) ;
            virtual void pointLocationQuery(const Point& query, IVisitor& v) ;
            virtual void nearestNeighborQuery(uint32_t k, const IShape& query, IVisitor& v, INearestNeighborComparator&);
            virtual void nearestNeighborQuery(uint32_t k, const IShape& query, IVisitor& v);
            virtual void selfJoinQuery(const IShape& s, IVisitor& v) ;
            virtual void queryStrategy(IQueryStrategy& qs) ;
            virtual void getIndexProperties(Tools::PropertySet& out) const ;
            virtual void addCommand(ICommand* pCommand, CommandType ct) ;
            virtual bool isIndexValid() ;
            virtual void getStatistics(IStatistics** out) const ;
            virtual void flush() ;
 
        private:
            void initNew(Tools::PropertySet&);
            void initOld(Tools::PropertySet& ps);
            void storeHeader();
            void loadHeader();
 
            void insertData_impl(uint32_t dataLength, uint8_t* pData, Region& mbr, id_type id);
            void insertData_impl(uint32_t dataLength, uint8_t* pData, Region& mbr, id_type id, uint32_t level, uint8_t* overflowTable);
            bool deleteData_impl(const Region& mbr, id_type id);
 
            id_type writeNode(Node*);
            NodePtr readNode(id_type page);
            void deleteNode(Node*);
 
            void rangeQuery(RangeQueryType type, const IShape& query, IVisitor& v);
            void selfJoinQuery(id_type id1, id_type id2, const Region& r, IVisitor& vis);
            void visitSubTree(NodePtr subTree, IVisitor& v);
 
            IStorageManager* m_pStorageManager;
 
            id_type m_rootID, m_headerID;
 
            RTreeVariant m_treeVariant;
 
            double m_fillFactor;
 
            uint32_t m_indexCapacity;
 
            uint32_t m_leafCapacity;
 
            uint32_t m_nearMinimumOverlapFactor;
                // The R*-Tree 'p' constant, for calculating nearly minimum overlap cost.
                // [Beckmann, Kriegel, Schneider, Seeger 'The R*-tree: An efficient and Robust Access Method
                // for Points and Rectangles', Section 4.1]
 
            double m_splitDistributionFactor;
                // The R*-Tree 'm' constant, for calculating spliting distributions.
                // [Beckmann, Kriegel, Schneider, Seeger 'The R*-tree: An efficient and Robust Access Method
                // for Points and Rectangles', Section 4.2]
 
            double m_reinsertFactor;
                // The R*-Tree 'p' constant, for removing entries at reinserts.
                // [Beckmann, Kriegel, Schneider, Seeger 'The R*-tree: An efficient and Robust Access Method
                //  for Points and Rectangles', Section 4.3]
 
            uint32_t m_dimension;
 
            Region m_infiniteRegion;
 
            Statistics m_stats;
 
            bool m_bTightMBRs;
 
            Tools::PointerPool<Point> m_pointPool;
            Tools::PointerPool<Region> m_regionPool;
            Tools::PointerPool<Node> m_indexPool;
            Tools::PointerPool<Node> m_leafPool;
 
            std::vector<std::shared_ptr<ICommand> > m_writeNodeCommands;
            std::vector<std::shared_ptr<ICommand> > m_readNodeCommands;
            std::vector<std::shared_ptr<ICommand> > m_deleteNodeCommands;
 
            class NNEntry
            {
            public:
                id_type m_id;
                IEntry* m_pEntry;
                double m_minDist;
 
                NNEntry(id_type id, IEntry* e, double f) : m_id(id), m_pEntry(e), m_minDist(f) {}
                ~NNEntry() = default;
 
            }; // NNEntry
 
            class NNComparator : public INearestNeighborComparator
            {
            public:
                double getMinimumDistance(const IShape& query, const IShape& entry) 
                {
                    return query.getMinimumDistance(entry);
                }
 
                double getMinimumDistance(const IShape& query, const IData& data) 
                {
                    IShape* pS;
                    data.getShape(&pS);
                    double ret = query.getMinimumDistance(*pS);
                    delete pS;
                    return ret;
                }
            }; // NNComparator
 
            class ValidateEntry
            {
            public:
                ValidateEntry(Region& r, NodePtr& pNode) : m_parentMBR(r), m_pNode(pNode) {}
 
                Region m_parentMBR;
                NodePtr m_pNode;
            }; // ValidateEntry
 
            friend class Node;
            friend class Leaf;
            friend class Index;
            friend class BulkLoader;
 
            friend std::ostream& operator<<(std::ostream& os, const RTree& t);
        }; // RTree
 
        std::ostream& operator<<(std::ostream& os, const RTree& t);
    }
}