polygonizegraph.cpp

在Linux下做的QuadTree的程序

/**********************************************************************
 * $Id: PolygonizeGraph.cpp 1820 2006-09-06 16:54:23Z mloskot $
 *
 * GEOS - Geometry Engine Open Source
 * http://geos.refractions.net
 *
 * Copyright (C) 2005-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 <geos/operation/polygonize/PolygonizeGraph.h>
#include <geos/operation/polygonize/PolygonizeDirectedEdge.h>
#include <geos/operation/polygonize/PolygonizeEdge.h>
#include <geos/operation/polygonize/EdgeRing.h>
#include <geos/planargraph/Node.h>
#include <geos/planargraph/DirectedEdgeStar.h>
#include <geos/planargraph/DirectedEdge.h>
#include <geos/geom/CoordinateSequence.h>
#include <geos/geom/LineString.h>

#include <cassert>
#include <vector>

//using namespace std;
using namespace geos::planargraph;
using namespace geos::geom;

namespace geos {
namespace operation { // geos.operation
namespace polygonize { // geos.operation.polygonize

int
PolygonizeGraph::getDegreeNonDeleted(Node *node)
{
	std::vector<DirectedEdge*> &edges=node->getOutEdges()->getEdges();
	int degree=0;
	for(unsigned int i=0; i<edges.size(); ++i) {
		PolygonizeDirectedEdge *de=(PolygonizeDirectedEdge*)edges[i];
		if (!de->isMarked()) ++degree;
	}
	return degree;
}

int
PolygonizeGraph::getDegree(Node *node, long label)
{
	std::vector<DirectedEdge*> &edges=node->getOutEdges()->getEdges();
	int degree=0;
	for(unsigned int i=0; i<edges.size(); ++i)
	{
		PolygonizeDirectedEdge *de=(PolygonizeDirectedEdge*)edges[i];
		if (de->getLabel()==label) ++degree;
	}
	return degree;
}

/**
 * Deletes all edges at a node
 */
void
PolygonizeGraph::deleteAllEdges(Node *node)
{
	std::vector<DirectedEdge*> &edges=node->getOutEdges()->getEdges();
	for(unsigned int i=0; i<edges.size(); ++i) {
		PolygonizeDirectedEdge *de=(PolygonizeDirectedEdge*)edges[i];
		de->setMarked(true);
		PolygonizeDirectedEdge *sym=(PolygonizeDirectedEdge*) de->getSym();
		if (sym!=NULL)
			sym->setMarked(true);
	}
}

/*
 * Create a new polygonization graph.
 */
PolygonizeGraph::PolygonizeGraph(const GeometryFactory *newFactory):
	factory(newFactory)
{
}

/*
 * Destroy a PolygonizeGraph
 */
PolygonizeGraph::~PolygonizeGraph()
{
	unsigned int i;
	for (i=0; i<newEdges.size(); i++)
		delete newEdges[i];
	for (i=0; i<newDirEdges.size(); i++)
		delete newDirEdges[i];
	for (i=0; i<newNodes.size(); i++)
		delete newNodes[i];
	for (i=0; i<newEdgeRings.size(); i++)
		delete newEdgeRings[i];
	for (i=0; i<newCoords.size(); i++) delete newCoords[i];
}

/*
 * Add a LineString forming an edge of the polygon graph.
 * @param line the line to add
 */
void
PolygonizeGraph::addEdge(const LineString *line)
{
	if (line->isEmpty()) return;

	CoordinateSequence *linePts=CoordinateSequence::removeRepeatedPoints(line->getCoordinatesRO());

	/*
	 * This would catch invalid linestrings
	 * (containing duplicated points only)
	 */
	if ( linePts->getSize() < 2 )
	{
		delete linePts;
		return;
	}

	const Coordinate& startPt=linePts->getAt(0);
	const Coordinate& endPt=linePts->getAt(linePts->getSize()-1);
	Node *nStart=getNode(startPt);
	Node *nEnd=getNode(endPt);
	DirectedEdge *de0=new PolygonizeDirectedEdge(nStart, nEnd, linePts->getAt(1), true);
	newDirEdges.push_back(de0);
	DirectedEdge *de1=new PolygonizeDirectedEdge(nEnd, nStart,
			linePts->getAt(linePts->getSize()-2), false);
	newDirEdges.push_back(de1);
	Edge *edge=new PolygonizeEdge(line);
	newEdges.push_back(edge);
	edge->setDirectedEdges(de0, de1);
	add(edge);

	newCoords.push_back(linePts);
}

Node *
PolygonizeGraph::getNode(const Coordinate& pt)
{
	Node *node=findNode(pt);
	if (node==NULL) {
		node=new Node(pt);
		newNodes.push_back(node);
		// ensure node is only added once to graph
		add(node);
	}
	return node;
}

void
PolygonizeGraph::computeNextCWEdges()
{
	std::vector<Node*> *pns=getNodes();
	// set the next pointers for the edges around each node
	for(int i=0;i<(int)pns->size();i++) {
		Node *node=(*pns)[i];
		computeNextCWEdges(node);
	}
	delete pns;
}

/*
 * Convert the maximal edge rings found by the initial graph traversal
 * into the minimal edge rings required by JTS polygon topology rules.
 *
 * @param ringEdges the list of start edges for the edgeRings to convert.
 */
void
PolygonizeGraph::convertMaximalToMinimalEdgeRings(std::vector<PolygonizeDirectedEdge*> *ringEdges)
{
	for(int i=0;i<(int)ringEdges->size();i++)
	{
		PolygonizeDirectedEdge *de=(*ringEdges)[i];
		long label=de->getLabel();
		std::vector<Node*> *intNodes=findIntersectionNodes(de, label);
		if (intNodes==NULL) continue;

		// flip the next pointers on the intersection nodes to
		// create minimal edge rings
		//std::vector<Node*> *pns=getNodes();

		// set the next pointers for the edges around each node
		for(int j=0;j<(int)intNodes->size();j++) {
			Node *node=(*intNodes)[j];
			computeNextCCWEdges(node, label);
		}

		delete intNodes;
	}
}

/*
 * Finds all nodes in a maximal edgering which are self-intersection nodes
 * @param startDE
 * @param label
 * @return the list of intersection nodes found,
 * or <code>NULL</code> if no intersection nodes were found.
 * Ownership of returned object goes to caller.
 */
std::vector<Node*>*
PolygonizeGraph::findIntersectionNodes(PolygonizeDirectedEdge *startDE, long label)
{
	PolygonizeDirectedEdge *de=startDE;
	std::vector<Node*> *intNodes=NULL;
	do {
		Node *node=de->getFromNode();
		if (getDegree(node, label) > 1) {
			if (intNodes==NULL)
				intNodes=new std::vector<Node*>();
			intNodes->push_back(node);
		}
		de=de->getNext();
		assert(de!=NULL); // found NULL DE in ring
		assert(de==startDE || !de->isInRing()); // found DE already in ring
	} while (de!=startDE);
	return intNodes;
}

/**
 * Computes the EdgeRings formed by the edges in this graph.
 * @return a list of the EdgeRing found by the polygonization process.
 */
std::vector<EdgeRing*>*
PolygonizeGraph::getEdgeRings()
{
	// maybe could optimize this, since most of these pointers should
	// be set correctly already
	// by deleteCutEdges()
	computeNextCWEdges();

	// clear labels of all edges in graph
	label(dirEdges, -1);
	std::vector<PolygonizeDirectedEdge*> *maximalRings=findLabeledEdgeRings(dirEdges);
	convertMaximalToMinimalEdgeRings(maximalRings);
	delete maximalRings;

	// find all edgerings
	std::vector<EdgeRing*> *edgeRingList=new std::vector<EdgeRing*>();
	for(unsigned int i=0; i<dirEdges.size(); ++i)
	{
		PolygonizeDirectedEdge *de=(PolygonizeDirectedEdge*)dirEdges[i];
		if (de->isMarked()) continue;
		if (de->isInRing()) continue;
		EdgeRing *er=findEdgeRing(de);
		edgeRingList->push_back(er);
	}
	return edgeRingList;
}

/**
*
* @param dirEdges a List of the DirectedEdges in the graph
* @return a List of DirectedEdges, one for each edge ring found
*/
std::vector<PolygonizeDirectedEdge*>*
PolygonizeGraph::findLabeledEdgeRings(std::vector<DirectedEdge*> &dirEdges)
{
	std::vector<PolygonizeDirectedEdge*> *edgeRingStarts=new std::vector<PolygonizeDirectedEdge*>();
	// label the edge rings formed
	long currLabel=1;
	for(unsigned int i=0; i<dirEdges.size(); ++i)
	{
		PolygonizeDirectedEdge *de=(PolygonizeDirectedEdge*)dirEdges[i];
		if (de->isMarked()) continue;
		if (de->getLabel() >= 0) continue;
		edgeRingStarts->push_back(de);
		std::vector<DirectedEdge*> *edges=findDirEdgesInRing(de);
		label(*edges, currLabel);
		delete edges;
		++currLabel;
	}
	return edgeRingStarts;
}

/*
 * Finds and removes all cut edges from the graph.
 * @return a list of the LineString forming the removed cut edges
 */
std::vector<const LineString*> *
PolygonizeGraph::deleteCutEdges()
{
	computeNextCWEdges();

	// label the current set of edgerings
	delete findLabeledEdgeRings(dirEdges);

	/*
	 * Cut Edges are edges where both dirEdges have the same label.
	 * Delete them, and record them
	 */
	std::vector<const LineString*> *cutLines=new std::vector<const LineString*>();
	for(unsigned int i=0; i<dirEdges.size(); ++i) {
		PolygonizeDirectedEdge *de=(PolygonizeDirectedEdge*)dirEdges[i];
		if (de->isMarked()) continue;
		PolygonizeDirectedEdge *sym=(PolygonizeDirectedEdge*) de->getSym();
		if (de->getLabel()==sym->getLabel()) {
			de->setMarked(true);
			sym->setMarked(true);