rtree.cc

一个非常好的GIS开源新版本

// Spatial Index Library
//
// Copyright (C) 2002 Navel Ltd.
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
//
//  Email:
//    [e-mail]

#include "../spatialindex/SpatialIndexImpl.h"

#include "Node.h"
#include "Leaf.h"
#include "Index.h"
#include "BulkLoader.h"

#include "RTree.h"

using std::stack;
using std::vector;
using std::priority_queue;

RTree::Data::Data(unsigned long len, byte* pData, Region& r, long id)
	: m_id(id), m_region(r), m_pData(0), m_dataLength(len)
{
	if (m_dataLength > 0)
	{
		m_pData = new byte[m_dataLength];
		memcpy(m_pData, pData, m_dataLength);
	}
}

RTree::Data::~Data()
{
	delete[] m_pData;
}

RTree::Data* RTree::Data::clone()
{
	return new Data(m_dataLength, m_pData, m_region, m_id);
}

long RTree::Data::getIdentifier() const
{
	return m_id;
}

void RTree::Data::getShape(IShape** out) const
{
	*out = new Region(m_region);
}

void RTree::Data::getData(unsigned long& len, byte** data) const
{
	len = m_dataLength;
	*data = 0;

	if (m_dataLength > 0)
	{
		*data = new byte[m_dataLength];
		memcpy(*data, m_pData, m_dataLength);
	}
}

unsigned long RTree::Data::getByteArraySize()
{
	return
		sizeof(long) +
		sizeof(unsigned long) +
		m_dataLength +
		m_region.getByteArraySize();
}

void RTree::Data::loadFromByteArray(const byte* ptr)
{
	memcpy(&m_id, ptr, sizeof(long));
	ptr += sizeof(long);

	delete[] m_pData;
	m_pData = 0;

	memcpy(&m_dataLength, ptr, sizeof(unsigned long));
	ptr += sizeof(unsigned long);

	if (m_dataLength > 0)
	{
		m_pData = new byte[m_dataLength];
		memcpy(m_pData, ptr, m_dataLength);
		ptr += m_dataLength;
	}

	m_region.loadFromByteArray(ptr);
}

void RTree::Data::storeToByteArray(byte** data, unsigned long& len)
{
	// it is thread safe this way.
	unsigned long regionsize;
	byte* regiondata = 0;
	m_region.storeToByteArray(&regiondata, regionsize);

	len = sizeof(long) + sizeof(unsigned long) + m_dataLength + regionsize;

	*data = new byte[len];
	byte* ptr = *data;

	memcpy(ptr, &m_id, sizeof(long));
	ptr += sizeof(long);
	memcpy(ptr, &m_dataLength, sizeof(unsigned long));
	ptr += sizeof(unsigned long);

	if (m_dataLength > 0)
	{
		memcpy(ptr, m_pData, m_dataLength);
		ptr += m_dataLength;
	}

	memcpy(ptr, regiondata, regionsize);
	delete[] regiondata;
	// ptr += regionsize;
}

SpatialIndex::ISpatialIndex* SpatialIndex::RTree::returnRTree(SpatialIndex::IStorageManager& sm, Tools::PropertySet& ps)
{
	SpatialIndex::ISpatialIndex* si = new SpatialIndex::RTree::RTree(sm, ps);
	return si;
}

SpatialIndex::ISpatialIndex* SpatialIndex::RTree::createNewRTree(
	SpatialIndex::IStorageManager& sm,
	double fillFactor,
	unsigned long indexCapacity,
	unsigned long leafCapacity,
	unsigned long dimension,
	RTreeVariant rv,
	long& indexIdentifier)
{
	Tools::Variant var;
	Tools::PropertySet ps;

	var.m_varType = Tools::VT_DOUBLE;
	var.m_val.dblVal = fillFactor;
	ps.setProperty("FillFactor", var);

	var.m_varType = Tools::VT_ULONG;
	var.m_val.ulVal = indexCapacity;
	ps.setProperty("IndexCapacity", var);

	var.m_varType = Tools::VT_ULONG;
	var.m_val.ulVal = leafCapacity;
	ps.setProperty("LeafCapacity", var);

	var.m_varType = Tools::VT_ULONG;
	var.m_val.ulVal = dimension;
	ps.setProperty("Dimension", var);

	var.m_varType = Tools::VT_LONG;
	var.m_val.lVal = rv;
	ps.setProperty("TreeVariant", var);

	ISpatialIndex* ret = returnRTree(sm, ps);

	var = ps.getProperty("IndexIdentifier");
	indexIdentifier = var.m_val.lVal;

	return ret;
}

SpatialIndex::ISpatialIndex* SpatialIndex::RTree::createAndBulkLoadNewRTree(
	BulkLoadMethod m,
	IDataStream& stream,
	SpatialIndex::IStorageManager& sm,
	double fillFactor,
	unsigned long indexCapacity,
	unsigned long leafCapacity,
	unsigned long dimension,
	SpatialIndex::RTree::RTreeVariant rv,
	long& indexIdentifier)
{
	SpatialIndex::ISpatialIndex* tree = createNewRTree(sm, fillFactor, indexCapacity, leafCapacity, dimension, rv, indexIdentifier);

	unsigned long bindex = static_cast<unsigned long>(std::floor(static_cast<double>(indexCapacity * fillFactor)));
	unsigned long bleaf = static_cast<unsigned long>(std::floor(static_cast<double>(leafCapacity * fillFactor)));

	SpatialIndex::RTree::BulkLoader bl;

	switch (m)
	{
	case BLM_STR:
		//FIXME: find available memory here.
		bl.bulkLoadUsingSTR(static_cast<RTree*>(tree), stream, bindex, bleaf, 200000);
		break;
	default:
		throw Tools::IllegalArgumentException("createAndBulkLoadNewRTree: Unknown bulk load method.");
		break;
	}

	return tree;
}

SpatialIndex::ISpatialIndex* SpatialIndex::RTree::loadRTree(IStorageManager& sm, long indexIdentifier)
{
	Tools::Variant var;
	Tools::PropertySet ps;

	var.m_varType = Tools::VT_LONG;
	var.m_val.lVal = indexIdentifier;
	ps.setProperty("IndexIdentifier", var);

	return returnRTree(sm, ps);
}

SpatialIndex::RTree::RTree::RTree(IStorageManager& sm, Tools::PropertySet& ps) :
	m_pStorageManager(&sm),
	m_rootID(StorageManager::NewPage),
	m_headerID(StorageManager::NewPage),
	m_treeVariant(RV_RSTAR),
	m_fillFactor(0.7),
	m_indexCapacity(100),
	m_leafCapacity(100),
	m_nearMinimumOverlapFactor(32),
	m_splitDistributionFactor(0.4),
	m_reinsertFactor(0.3),
	m_dimension(2),
	m_bTightMBRs(true),
	m_pointPool(500),
	m_regionPool(1000),
	m_indexPool(100),
	m_leafPool(100)
{
#ifdef PTHREADS
	pthread_rwlock_init(&m_rwLock, NULL);
#else
	m_rwLock = false;
#endif

	Tools::Variant var = ps.getProperty("IndexIdentifier");
	if (var.m_varType != Tools::VT_EMPTY)
	{
		if (var.m_varType != Tools::VT_LONG) throw Tools::IllegalArgumentException("RTree: Property IndexIdentifier must be Tools::VT_LONG");
		m_headerID = var.m_val.lVal;
		initOld(ps);
	}
	else
	{
		initNew(ps);
		var.m_varType = Tools::VT_LONG;
		var.m_val.lVal = m_headerID;
		ps.setProperty("IndexIdentifier", var);
	}
}

SpatialIndex::RTree::RTree::~RTree()
{
#ifdef PTHREADS
	pthread_rwlock_destroy(&m_rwLock);
#endif

	storeHeader();
}

//
// ISpatialIndex interface
//

void SpatialIndex::RTree::RTree::insertData(unsigned long len, const byte* pData, const IShape& shape, long id)
{
	if (shape.getDimension() != m_dimension) throw Tools::IllegalArgumentException("insertData: Shape has the wrong number of dimensions.");

#ifdef PTHREADS
	Tools::ExclusiveLock lock(&m_rwLock);
#else
	if (m_rwLock == false) m_rwLock = true;
	else throw Tools::ResourceLockedException("insertData: cannot acquire an exclusive lock");
#endif

	try
	{
		// convert the shape into a Region (R-Trees index regions only; i.e., approximations of the shapes).
		RegionPtr mbr = m_regionPool.acquire();
		shape.getMBR(*mbr);

		byte* buffer = 0;

		if (len > 0)
		{
			buffer = new byte[len];
			memcpy(buffer, pData, len);
		}

		insertData_impl(len, buffer, *mbr, id);
			// the buffer is stored in the tree. Do not delete here.

#ifndef PTHREADS
		m_rwLock = false;
#endif
	}
	catch (...)
	{
#ifndef PTHREADS
		m_rwLock = false;
#endif
		throw;
	}
}

bool SpatialIndex::RTree::RTree::deleteData(const IShape& shape, long id)
{
	if (shape.getDimension() != m_dimension) throw Tools::IllegalArgumentException("deleteData: Shape has the wrong number of dimensions.");

#ifdef PTHREADS
	Tools::ExclusiveLock lock(&m_rwLock);
#else
	if (m_rwLock == false) m_rwLock = true;
	else throw Tools::ResourceLockedException("deleteData: cannot acquire an exclusive lock");
#endif

	try
	{
		RegionPtr mbr = m_regionPool.acquire();
		shape.getMBR(*mbr);
		bool ret = deleteData_impl(*mbr, id);

#ifndef PTHREADS
		m_rwLock = false;
#endif

		return ret;
	}
	catch (...)
	{
#ifndef PTHREADS
		m_rwLock = false;
#endif
		throw;
	}
}

void SpatialIndex::RTree::RTree::containsWhatQuery(const IShape& query, IVisitor& v)
{
	if (query.getDimension() != m_dimension) throw Tools::IllegalArgumentException("containsWhatQuery: Shape has the wrong number of dimensions.");
	rangeQuery(ContainmentQuery, query, v);
}

void SpatialIndex::RTree::RTree::intersectsWithQuery(const IShape& query, IVisitor& v)
{
	if (query.getDimension() != m_dimension) throw Tools::IllegalArgumentException("intersectsWithQuery: Shape has the wrong number of dimensions.");
	rangeQuery(IntersectionQuery, query, v);
}

void SpatialIndex::RTree::RTree::pointLocationQuery(const Point& query, IVisitor& v)
{
	if (query.m_dimension != m_dimension) throw Tools::IllegalArgumentException("pointLocationQuery: Shape has the wrong number of dimensions.");
	Region r(query, query);
	rangeQuery(IntersectionQuery, r, v);
}

void SpatialIndex::RTree::RTree::nearestNeighborQuery(long k, const IShape& query, IVisitor& v, INearestNeighborComparator& nnc)
{
	if (query.getDimension() != m_dimension) throw Tools::IllegalArgumentException("nearestNeighborQuery: Shape has the wrong number of dimensions.");

#ifdef PTHREADS
	Tools::SharedLock lock(&m_rwLock);
#else
	if (m_rwLock == false) m_rwLock = true;
	else throw Tools::ResourceLockedException("nearestNeighborQuery: cannot acquire a shared lock");
#endif

	try
	{
		priority_queue<NNEntry*, vector<NNEntry*>, NNEntry::ascending> queue;

		queue.push(new NNEntry(m_rootID, 0, 0.0));

		long count = 0;
		double knearest = 0.0;

		while (! queue.empty())
		{
			NNEntry* pFirst = queue.top();

			// report all nearest neighbors with equal greatest distances.
			// (neighbors can be more than k, if many happen to have the same greatest distance).
			if (count >= k && pFirst->m_minDist > knearest)	break;

			queue.pop();

			if (pFirst->m_pEntry == 0)
			{
				// n is a leaf or an index.
				NodePtr n = readNode(pFirst->m_id);
				v.visitNode(*n);

				for (unsigned long cChild = 0; cChild < n->m_children; cChild++)
				{
					if (n->m_level == 0)
					{
						Data* e = new Data(n->m_pDataLength[cChild], n->m_pData[cChild], *(n->m_ptrMBR[cChild]), n->m_pIdentifier[cChild]);
						// we need to compare the query with the actual data entry here, so we call the
						// appropriate getMinimumDistance method of NearestNeighborComparator.
						queue.push(new NNEntry(n->m_pIdentifier[cChild], e, nnc.getMinimumDistance(query, *e)));
					}
					else
					{
						queue.push(new NNEntry(n->m_pIdentifier[cChild], 0, nnc.getMinimumDistance(query, *(n->m_ptrMBR[cChild]))));
					}
				}
			}
			else
			{
				v.visitData(*(static_cast<IData*>(pFirst->m_pEntry)));
				m_stats.m_queryResults++;
				count++;
				knearest = pFirst->m_minDist;
				delete pFirst->m_pEntry;
			}

			delete pFirst;
		}

		while (! queue.empty())
		{
			NNEntry* e = queue.top(); queue.pop();
			if (e->m_pEntry != 0) delete e->m_pEntry;
			delete e;
		}

#ifndef PTHREADS
		m_rwLock = false;
#endif
	}
	catch (...)
	{
#ifndef PTHREADS
		m_rwLock = false;
#endif
		throw;
	}
}

void SpatialIndex::RTree::RTree::nearestNeighborQuery(long k, const IShape& query, IVisitor& v)
{
	if (query.getDimension() != m_dimension) throw Tools::IllegalArgumentException("nearestNeighborQuery: Shape has the wrong number of dimensions.");
	NNComparator nnc;
	nearestNeighborQuery(k, query, v, nnc);
}

void SpatialIndex::RTree::RTree::selfJoinQuery(const IShape& query, IVisitor& v)
{
	if (query.getDimension() != m_dimension) throw Tools::IllegalArgumentException("selfJoinQuery: Shape has the wrong number of dimensions.");

#ifdef PTHREADS
	Tools::SharedLock lock(&m_rwLock);
#else
	if (m_rwLock == false) m_rwLock = true;
	else throw Tools::ResourceLockedException("selfJoinQuery: cannot acquire a shared lock");
#endif

	try
	{
		RegionPtr mbr = m_regionPool.acquire();
		query.getMBR(*mbr);
		selfJoinQuery(m_rootID, m_rootID, *mbr, v);