GEOS
3.2.3
|
00001 /********************************************************************** 00002 * $Id: Quadtree.h 2556 2009-06-06 22:22:28Z strk $ 00003 * 00004 * GEOS - Geometry Engine Open Source 00005 * http://geos.refractions.net 00006 * 00007 * Copyright (C) 2006 Refractions Research Inc. 00008 * 00009 * This is free software; you can redistribute and/or modify it under 00010 * the terms of the GNU Lesser General Public Licence as published 00011 * by the Free Software Foundation. 00012 * See the COPYING file for more information. 00013 * 00014 ********************************************************************** 00015 * 00016 * Last port: index/quadtree/Quadtree.java rev. 1.16 (JTS-1.10) 00017 * 00018 **********************************************************************/ 00019 00020 #ifndef GEOS_IDX_QUADTREE_QUADTREE_H 00021 #define GEOS_IDX_QUADTREE_QUADTREE_H 00022 00023 #include <geos/export.h> 00024 #include <geos/index/SpatialIndex.h> // for inheritance 00025 #include <geos/index/quadtree/Root.h> // for composition 00026 00027 #include <vector> 00028 #include <string> 00029 00030 // Forward declarations 00031 namespace geos { 00032 namespace geom { 00033 class Envelope; 00034 } 00035 namespace index { 00036 namespace quadtree { 00037 // class Root; 00038 } 00039 } 00040 } 00041 00042 namespace geos { 00043 namespace index { // geos::index 00044 namespace quadtree { // geos::index::quadtree 00045 00068 class GEOS_DLL Quadtree: public SpatialIndex { 00069 00070 private: 00071 00072 std::vector<geom::Envelope *> newEnvelopes; 00073 00074 void collectStats(const geom::Envelope& itemEnv); 00075 00076 Root root; 00077 00089 double minExtent; 00090 00091 public: 00099 static geom::Envelope* ensureExtent(const geom::Envelope *itemEnv, 00100 double minExtent); 00101 00106 Quadtree() 00107 : 00108 root(), 00109 minExtent(1.0) 00110 {} 00111 00112 ~Quadtree(); 00113 00115 int depth(); 00116 00118 int size(); 00119 00120 void insert(const geom::Envelope *itemEnv, void *item); 00121 00139 void query(const geom::Envelope *searchEnv, std::vector<void*>& ret); 00140 00141 00158 void query(const geom::Envelope *searchEnv, ItemVisitor& visitor) 00159 { 00160 /* 00161 * the items that are matched are the items in quads which 00162 * overlap the search envelope 00163 */ 00164 root.visit(searchEnv, visitor); 00165 } 00166 00174 bool remove(const geom::Envelope* itemEnv, void* item); 00175 00177 std::vector<void*>* queryAll(); 00178 00179 std::string toString() const; 00180 00181 }; 00182 00183 00184 } // namespace geos::index::quadtree 00185 } // namespace geos::index 00186 } // namespace geos 00187 00188 #endif // GEOS_IDX_QUADTREE_QUADTREE_H 00189 00190 /********************************************************************** 00191 * $Log$ 00192 * Revision 1.2 2006/04/03 08:29:30 strk 00193 * Added port info, cleaned up log message, minor assertion checking. 00194 * 00195 * Revision 1.1 2006/03/22 12:22:50 strk 00196 * indexQuadtree.h split 00197 * 00198 **********************************************************************/ 00199