src/index/bintree/Key.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 #include <geos/index/bintree/Key.h>
  17 #include <geos/index/bintree/Interval.h>
  18 #include <geos/index/quadtree/DoubleBits.h>
  19
  20 #include <cmath>
  21
  22 namespace geos {
  23 namespace index { // geos.index
  24 namespace bintree { // geos.index.bintree
  25
  26 int
  27 Key::computeLevel(Interval *newInterval)
  28 {
  29         using geos::index::quadtree::DoubleBits;
  30         double dx=newInterval->getWidth();
  31         //int level = BinaryPower.exponent(dx) + 1;
  32         int level=DoubleBits::exponent(dx)+1;
  33         return level;
  34 }
  35
  36 Key::Key(Interval *newInterval)
  37 {
  38         interval=NULL;
  39         pt=0.0;
  40         level=0;
  41         computeKey(newInterval);
  42 }
  43
  44 Key::~Key()
  45 {
  46         delete interval;
  47 }
  48
  49 double
  50 Key::getPoint()
  51 {
  52         return pt;
  53 }
  54
  55 int
  56 Key::getLevel()
  57 {
  58         return level;
  59 }
  60
  61 Interval*
  62 Key::getInterval()
  63 {
  64         return interval;
  65 }
  66
  67 /**
  68  * return a square envelope containing the argument envelope,
  69  * whose extent is a power of two and which is based at a power of 2
  70  */
  71 void
  72 Key::computeKey(Interval *itemInterval)
  73 {
  74         level=computeLevel(itemInterval);
  75         delete interval;
  76         interval=new Interval();
  77         computeInterval(level,itemInterval);
  78         // MD - would be nice to have a non-iterative form of this algorithm
  79         while (!interval->contains(itemInterval)) {
  80                 level+=1;
  81                 computeInterval(level,itemInterval);
  82         }
  83 }
  84
  85 void
  86 Key::computeInterval(int level, Interval *itemInterval)
  87 {
  88         using geos::index::quadtree::DoubleBits;
  89
  90         double size=DoubleBits::powerOf2(level);
  91         //double size = pow2.power(level);
  92         pt=std::floor(itemInterval->getMin()/size)*size;
  93         interval->init(pt,pt+size);
  94 }
  95
  96 } // namespace geos.index.bintree
  97 } // namespace geos.index
  98 } // namespace geos
  99
 100 /**********************************************************************
 101  * $Log$
 102  * Revision 1.11  2006/03/22 16:01:33  strk
 103  * indexBintree.h header split, classes renamed to match JTS
 104  *
 105  * Revision 1.10  2006/03/22 12:22:50  strk
 106  * indexQuadtree.h split
 107  **********************************************************************/
 108