node.cpp

在Linux下做的QuadTree的程序

/**********************************************************************
 * $Id: Node.cpp 1820 2006-09-06 16:54:23Z mloskot $
 *
 * GEOS - Geometry Engine Open Source
 * http://geos.refractions.net
 *
 * Copyright (C) 2006 Refractions Research Inc.
 * Copyright (C) 2001-2002 Vivid Solutions 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.
 *
 **********************************************************************/

#include <cassert>

#include <geos/index/bintree/Node.h>
#include <geos/index/bintree/Key.h>
#include <geos/index/bintree/Interval.h>

namespace geos {
namespace index { // geos.index
namespace bintree { // geos.index.bintree

Node*
Node::createNode(Interval *itemInterval)
{
	Key *key=new Key(itemInterval);
	//System.out.println("input: " + env + "  binaryEnv: " + key.getEnvelope());
	Node* node=new Node(new Interval(key->getInterval()),key->getLevel());
	delete key;
	return node;
}

Node*
Node::createExpanded(Node *node,Interval *addInterval)
{
	Interval *expandInt=new Interval(addInterval);
	if (node!=NULL) expandInt->expandToInclude(node->interval);
	Node *largerNode=createNode(expandInt);
	if (node!=NULL) largerNode->insert(node);
	delete expandInt;
	return largerNode;
}

Node::Node(Interval *newInterval,int newLevel)
{
	interval=newInterval;
	level=newLevel;
	centre=(interval->getMin()+interval->getMax())/2;
}

Node::~Node()
{
	delete interval;
}

Interval*
Node::getInterval()
{
	return interval;
}

bool
Node::isSearchMatch(Interval *itemInterval)
{
	return itemInterval->overlaps(interval);
}

/**
 * Returns the subnode containing the envelope.
 * Creates the node if
 * it does not already exist.
 */
Node*
Node::getNode(Interval *searchInterval)
{
	int subnodeIndex=getSubnodeIndex(searchInterval,centre);
	// if index is -1 searchEnv is not contained in a subnode
	if (subnodeIndex!=-1) {
		// create the node if it does not exist
		Node* node=getSubnode(subnodeIndex);
		// recursively search the found/created node
		return node->getNode(searchInterval);
	} else {
		return this;
	}
}

/**
 * Returns the smallest <i>existing</i>
 * node containing the envelope.
 */
NodeBase*
Node::find(Interval *searchInterval)
{
	int subnodeIndex=getSubnodeIndex(searchInterval,centre);
	if (subnodeIndex==-1)
		return this;
	if (subnode[subnodeIndex]!=NULL) {
		// query lies in subnode, so search it
		Node *node=subnode[subnodeIndex];
		return node->find(searchInterval);
	}
	// no existing subnode, so return this one anyway
	return this;
}

void
Node::insert(Node *node)
{
	assert(interval==NULL || interval->contains(node->interval));
	int index=getSubnodeIndex(node->interval,centre);
	if (node->level==level-1) {
		subnode[index]=node;
	} else {
		// the node is not a direct child, so make a new child node to contain it
		// and recursively insert the node
		Node* childNode=createSubnode(index);
		childNode->insert(node);
		subnode[index]=childNode;
	}
}

/**
 * get the subnode for the index.
 * If it doesn't exist, create it
 */
Node*
Node::getSubnode(int index)
{
	if (subnode[index]==NULL) {
		subnode[index]=createSubnode(index);
	}
	return subnode[index];
}

Node*
Node::createSubnode(int index)
{
	// create a new subnode in the appropriate interval
	double min=0.0;
	double max=0.0;
	switch (index) {
		case 0:
			min=interval->getMin();
			max=centre;
			break;
		case 1:
			min=centre;
			max=interval->getMax();
			break;
	}
	Interval* subInt=new Interval(min,max);
	Node *node=new Node(subInt,level-1);
	return node;
}

} // namespace geos.index.bintree
} // namespace geos.index
} // namespace geos

/**********************************************************************
 * $Log$
 * Revision 1.3  2006/03/22 16:01:33  strk
 * indexBintree.h header split, classes renamed to match JTS
 *
 **********************************************************************/