001: /*
002: * The JTS Topology Suite is a collection of Java classes that
003: * implement the fundamental operations required to validate a given
004: * geo-spatial data set to a known topological specification.
005: *
006: * Copyright (C) 2001 Vivid Solutions
007: *
008: * This library is free software; you can redistribute it and/or
009: * modify it under the terms of the GNU Lesser General Public
010: * License as published by the Free Software Foundation; either
011: * version 2.1 of the License, or (at your option) any later version.
012: *
013: * This library is distributed in the hope that it will be useful,
014: * but WITHOUT ANY WARRANTY; without even the implied warranty of
015: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
016: * Lesser General Public License for more details.
017: *
018: * You should have received a copy of the GNU Lesser General Public
019: * License along with this library; if not, write to the Free Software
020: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
021: *
022: * For more information, contact:
023: *
024: * Vivid Solutions
025: * Suite #1A
026: * 2328 Government Street
027: * Victoria BC V8T 5G5
028: * Canada
029: *
030: * (250)385-6040
031: * www.vividsolutions.com
032: */
033: package com.vividsolutions.jts.index.quadtree;
034:
035: import com.vividsolutions.jts.geom.Coordinate;
036: import com.vividsolutions.jts.geom.Envelope;
037:
038: /**
039: * A Key is a unique identifier for a node in a quadtree.
040: * It contains a lower-left point and a level number. The level number
041: * is the power of two for the size of the node envelope
042: *
043: * @version 1.7
044: */
045: public class Key {
046:
047: public static int computeQuadLevel(Envelope env) {
048: double dx = env.getWidth();
049: double dy = env.getHeight();
050: double dMax = dx > dy ? dx : dy;
051: int level = DoubleBits.exponent(dMax) + 1;
052: return level;
053: }
054:
055: // the fields which make up the key
056: private Coordinate pt = new Coordinate();
057: private int level = 0;
058: // auxiliary data which is derived from the key for use in computation
059: private Envelope env = null;
060:
061: public Key(Envelope itemEnv) {
062: computeKey(itemEnv);
063: }
064:
065: public Coordinate getPoint() {
066: return pt;
067: }
068:
069: public int getLevel() {
070: return level;
071: }
072:
073: public Envelope getEnvelope() {
074: return env;
075: }
076:
077: public Coordinate getCentre() {
078: return new Coordinate((env.getMinX() + env.getMaxX()) / 2, (env
079: .getMinY() + env.getMaxY()) / 2);
080: }
081:
082: /**
083: * return a square envelope containing the argument envelope,
084: * whose extent is a power of two and which is based at a power of 2
085: */
086: public void computeKey(Envelope itemEnv) {
087: level = computeQuadLevel(itemEnv);
088: env = new Envelope();
089: computeKey(level, itemEnv);
090: // MD - would be nice to have a non-iterative form of this algorithm
091: while (!env.contains(itemEnv)) {
092: level += 1;
093: computeKey(level, itemEnv);
094: }
095: }
096:
097: private void computeKey(int level, Envelope itemEnv) {
098: double quadSize = DoubleBits.powerOf2(level);
099: pt.x = Math.floor(itemEnv.getMinX() / quadSize) * quadSize;
100: pt.y = Math.floor(itemEnv.getMinY() / quadSize) * quadSize;
101: env.init(pt.x, pt.x + quadSize, pt.y, pt.y + quadSize);
102: }
103: }
|