src/index/quadtree/Node.cpp

   1 /**********************************************************************
   2  *
   3  * GEOS - Geometry Engine Open Source
   4  * http://geos.osgeo.org
   5  *
   6  * Copyright (C) 2006 Refractions Research Inc.
   7  * Copyright (C) 2001-2002 Vivid Solutions Inc.
   8  *
   9  * This is free software; you can redistribute and/or modify it under
  10  * the terms of the GNU Lesser General Public Licence as published
  11  * by the Free Software Foundation.
  12  * See the COPYING file for more information.
  13  *
  14  **********************************************************************
  15  *
  16  * Last port: index/quadtree/Node.java rev 1.8 (JTS-1.10)
  17  *
  18  **********************************************************************/
  19
  20 #include <geos/index/quadtree/Node.h>
  21 #include <geos/index/quadtree/Key.h>
  22 #include <geos/geom/Envelope.h>
  23
  24 #include <string>
  25 #include <sstream>
  26 #include <cassert>
  27
  28 #ifndef GEOS_DEBUG
  29 #define GEOS_DEBUG 0
  30 #endif
  31
  32 #if GEOS_DEBUG
  33 #include <iostream>
  34 #endif
  35
  36 using namespace std;
  37 using namespace geos::geom;
  38
  39 namespace geos {
  40 namespace index { // geos.index
  41 namespace quadtree { // geos.index.quadtree
  42
  43 /* public static */
  44 std::auto_ptr<Node>
  45 Node::createNode(const Envelope& env)
  46 {
  47         Key key(env);
  48
  49         std::auto_ptr<Envelope> nenv ( new Envelope(key.getEnvelope()) );
  50         std::auto_ptr<Node> node (
  51                 new Node(nenv, key.getLevel())
  52         );
  53         return node;
  54 }
  55
  56 /* static public */
  57 std::auto_ptr<Node>
  58 Node::createExpanded(std::auto_ptr<Node> node, const Envelope& addEnv)
  59 {
  60         Envelope expandEnv(addEnv);
  61         if ( node.get() ) // should this be asserted ?
  62         {
  63                 expandEnv.expandToInclude(node->getEnvelope());
  64         }
  65
  66 #if GEOS_DEBUG
  67         cerr<<"Node::createExpanded computed "<<expandEnv.toString()<<endl;
  68 #endif
  69
  70         std::auto_ptr<Node> largerNode = createNode(expandEnv);
  71         if ( node.get() ) // should this be asserted ?
  72         {
  73                 largerNode->insertNode(node);
  74         }
  75
  76         return largerNode;
  77 }
  78
  79 /*public*/
  80 Node*
  81 Node::getNode(const Envelope *searchEnv)
  82 {
  83         int subnodeIndex = getSubnodeIndex(searchEnv, centre);
  84         // if subquadIndex is -1 searchEnv is not contained in a subquad
  85         if (subnodeIndex != -1)
  86         {
  87                 // create the quad if it does not exist
  88                 Node *node = getSubnode(subnodeIndex);
  89                 // recursively search the found/created quad
  90                 return node->getNode(searchEnv);
  91         }
  92         else
  93         {
  94                 return this;
  95         }
  96 }
  97
  98 /*public*/
  99 NodeBase*
 100 Node::find(const Envelope *searchEnv)
 101 {
 102         int subnodeIndex=getSubnodeIndex(searchEnv, centre);
 103         if (subnodeIndex==-1)
 104                 return this;
 105         if (subnode[subnodeIndex]!=NULL) {
 106                 // query lies in subquad, so search it
 107                 Node *node=subnode[subnodeIndex];
 108                 return node->find(searchEnv);
 109         }
 110         // no existing subquad, so return this one anyway
 111         return this;
 112 }
 113
 114 void
 115 Node::insertNode(std::auto_ptr<Node> node)
 116 {
 117         assert( env->contains(node->getEnvelope()) );
 118
 119         int index = getSubnodeIndex(node->getEnvelope(), centre);
 120         assert(index >= 0);
 121
 122         if (node->level == level-1)
 123         {
 124                 // We take ownership of node
 125                 delete subnode[index];
 126                 subnode[index] = node.release();
 127
 128                 //System.out.println("inserted");
 129         }
 130         else
 131         {
 132                 // the quad is not a direct child, so make a new child
 133                 // quad to contain it and recursively insert the quad
 134                 std::auto_ptr<Node> childNode ( createSubnode(index) );
 135
 136                 // childNode takes ownership of node
 137                 childNode->insertNode(node);
 138
 139                 // We take ownership of childNode
 140                 delete subnode[index];
 141                 subnode[index] = childNode.release();
 142         }
 143 }
 144
 145 Node*
 146 Node::getSubnode(int index)
 147 {
 148         assert(index >=0 && index < 4);
 149         if (subnode[index] == NULL)
 150         {
 151                 subnode[index] = createSubnode(index).release();
 152         }
 153         return subnode[index];
 154 }
 155
 156 std::auto_ptr<Node>
 157 Node::createSubnode(int index)
 158 {
 159         // create a new subquad in the appropriate quadrant
 160         double minx=0.0;
 161         double maxx=0.0;
 162         double miny=0.0;
 163         double maxy=0.0;
 164
 165         switch (index) {
 166                 case 0:
 167                         minx=env->getMinX();
 168                         maxx=centre.x;
 169                         miny=env->getMinY();
 170                         maxy=centre.y;
 171                         break;
 172                 case 1:
 173                         minx=centre.x;
 174                         maxx=env->getMaxX();
 175                         miny=env->getMinY();
 176                         maxy=centre.y;
 177                         break;
 178                 case 2:
 179                         minx=env->getMinX();
 180                         maxx=centre.x;
 181                         miny=centre.y;
 182                         maxy=env->getMaxY();
 183                         break;
 184                 case 3:
 185                         minx=centre.x;
 186                         maxx=env->getMaxX();
 187                         miny=centre.y;
 188                         maxy=env->getMaxY();
 189                         break;
 190         }
 191         std::auto_ptr<Envelope> sqEnv ( new Envelope(minx,maxx,miny,maxy) );
 192         std::auto_ptr<Node> node ( new Node(sqEnv, level-1) );
 193         return node;
 194 }
 195
 196 string
 197 Node::toString() const
 198 {
 199         ostringstream os;
 200         os <<"L"<<level<<" "<<env->toString()<<" Ctr["<<centre.toString()<<"]";
 201         os <<" "+NodeBase::toString();
 202         return os.str();
 203 }
 204
 205
 206 } // namespace geos.index.quadtree
 207 } // namespace geos.index
 208 } // namespace geos
 209
 210 /**********************************************************************
 211  * $Log$
 212  * Revision 1.2  2006/03/23 13:31:58  strk
 213  * Fixed to allow build with GEOS_DEBUG
 214  *
 215  * Revision 1.1  2006/03/22 14:28:53  strk
 216  * Filenames renamed to match class names (matching JTS)
 217  *
 218  * Revision 1.17  2006/03/22 12:22:50  strk
 219  * indexQuadtree.h split
 220  *
 221  **********************************************************************/
 222