/********************************************************************** * * GEOS - Geometry Engine Open Source * http://geos.osgeo.org * * Copyright (C) 2006 Refractions Research Inc. * * This is free software; you can redistribute and/or modify it under * the terms of the GNU Lesser General Public Licence as published * by the Free Software Foundation. * See the COPYING file for more information. * **********************************************************************/ #ifndef GEOS_INDEX_STRTREE_SIRTREE_H #define GEOS_INDEX_STRTREE_SIRTREE_H #include #include // for inheritance #include // for inline #include #include namespace geos { namespace index { // geos::index namespace strtree { // geos::index::strtree /** \brief * One-dimensional version of an STR-packed R-tree. * * SIR stands for "Sort-Interval-Recursive". * * STR-packed R-trees are described in: * P. Rigaux, Michel Scholl and Agnes Voisard. Spatial Databases With * Application To GIS. Morgan Kaufmann, San Francisco, 2002. * * @see STRtree */ class GEOS_DLL SIRtree: public AbstractSTRtree { using AbstractSTRtree::insert; using AbstractSTRtree::query; public: /** \brief * Constructs an SIRtree with the default node capacity. */ SIRtree(); /** \brief * Constructs an SIRtree with the given maximum number of child nodes * that a node may have */ SIRtree(std::size_t nodeCapacity); virtual ~SIRtree(); void insert(double x1, double x2, void* item); /** * Returns items whose bounds intersect the given bounds. * @param x1 possibly equal to x2 */ std::vector* query(double x1, double x2) { std::vector* results = new std::vector(); Interval interval(std::min(x1, x2), std::max(x1, x2)); AbstractSTRtree::query(&interval, *results); return results; } /** * Returns items whose bounds intersect the given value. */ std::vector* query(double x) { return query(x,x); } protected: class SIRIntersectsOp:public AbstractSTRtree::IntersectsOp { public: bool intersects(const void* aBounds, const void* bBounds); }; /** \brief * Sorts the childBoundables then divides them into groups of size M, where * M is the node capacity. */ std::auto_ptr createParentBoundables( BoundableList* childBoundables, int newLevel); AbstractNode* createNode(int level); IntersectsOp* getIntersectsOp() {return intersectsOp;} std::auto_ptr sortBoundables(const BoundableList* input); private: IntersectsOp* intersectsOp; }; } // namespace geos::index::strtree } // namespace geos::index } // namespace geos #endif // GEOS_INDEX_STRTREE_SIRTREE_H