QuadEdgeSubdivision.h

/**********************************************************************
 *
 * GEOS - Geometry Engine Open Source
 * http://geos.osgeo.org
 *
 * Copyright (C) 2012 Excensus LLC.
 *
 * This is free software; you can redistribute and/or modify it under
 * the terms of the GNU Lesser General Licence as published
 * by the Free Software Foundation. 
 * See the COPYING file for more information.
 *
 **********************************************************************
 *
 * Last port: triangulate/quadedge/QuadEdgeSubdivision.java r524
 *
 **********************************************************************/
 
#ifndef GEOS_TRIANGULATE_QUADEDGE_QUADEDGESUBDIVISION_H
#define GEOS_TRIANGULATE_QUADEDGE_QUADEDGESUBDIVISION_H
 
#include <memory>
#include <list>
#include <stack>
#include <set>
#include <vector>
 
#include <geos/geom/MultiLineString.h>
#include <geos/triangulate/quadedge/QuadEdgeLocator.h>
#include <geos/triangulate/quadedge/Vertex.h>
 
namespace geos {
 
namespace geom {
 
        class CoordinateSequence;
        class GeometryCollection;
        class MultiLineString;
        class GeometryFactory;
        class Coordinate;
        class Geometry;
        class Envelope;
}
 
namespace triangulate { //geos.triangulate
namespace quadedge { //geos.triangulate.quadedge
 
class QuadEdge;
class TriangleVisitor;
 
const double EDGE_COINCIDENCE_TOL_FACTOR = 1000;

class GEOS_DLL QuadEdgeSubdivision {
public:
        typedef std::vector<QuadEdge*> QuadEdgeList;

        static void getTriangleEdges(const QuadEdge &startQE,
                        const QuadEdge* triEdge[3]);
 
private:
        QuadEdgeList quadEdges;
        QuadEdgeList createdEdges;
        QuadEdge* startingEdges[3];
        double tolerance;
        double edgeCoincidenceTolerance;
        Vertex frameVertex[3];
        geom::Envelope frameEnv;
        std::auto_ptr<QuadEdgeLocator> locator;
 
public:
        QuadEdgeSubdivision(const geom::Envelope &env, double tolerance);
 
        virtual ~QuadEdgeSubdivision();
 
private:
        virtual void createFrame(const geom::Envelope &env);
        
        virtual void initSubdiv(QuadEdge* initEdges[3]);
        
public:
        inline double getTolerance() const {
                return tolerance;
        }

        inline const geom::Envelope& getEnvelope() const {
                return frameEnv;
        }

        inline const QuadEdgeList& getEdges() const {
                return quadEdges;
        }

        inline void setLocator(std::auto_ptr<QuadEdgeLocator> locator) {
                this->locator = locator;
        }

        virtual QuadEdge& makeEdge(const Vertex &o, const Vertex &d);

        virtual QuadEdge& connect(QuadEdge &a, QuadEdge &b);

        void remove(QuadEdge &e);

        QuadEdge* locateFromEdge(const Vertex &v,
                        const QuadEdge &startEdge) const;

        inline QuadEdge* locate(const Vertex &v) const {
                return locator->locate(v);
        }

        inline QuadEdge* locate(const geom::Coordinate &p) {
                return locator->locate(Vertex(p));
        }

        QuadEdge* locate(const geom::Coordinate &p0, const geom::Coordinate &p1);

        QuadEdge& insertSite(const Vertex &v);

        bool isFrameEdge(const QuadEdge &e) const;

        bool isFrameBorderEdge(const QuadEdge &e) const;

        bool isFrameVertex(const Vertex &v) const;
 

        bool isOnEdge(const QuadEdge &e, const geom::Coordinate &p) const;

        bool isVertexOfEdge(const QuadEdge &e, const Vertex &v) const;

        std::auto_ptr<QuadEdgeList> getPrimaryEdges(bool includeFrame);
  
        /*****************************************************************************
         * Visitors
         ****************************************************************************/
 
        void visitTriangles(TriangleVisitor *triVisitor, bool includeFrame);
 
private:
        typedef std::stack<QuadEdge*> QuadEdgeStack;
        typedef std::set<QuadEdge*> QuadEdgeSet;
        typedef std::list< geom::CoordinateSequence*> TriList;

        QuadEdge* triEdges[3];

        QuadEdge** fetchTriangleToVisit(QuadEdge *edge, QuadEdgeStack &edgeStack, bool includeFrame,
                        QuadEdgeSet &visitedEdges);

        void getTriangleCoordinates(TriList* triList, bool includeFrame);
 
private:
        class TriangleCoordinatesVisitor;
        class TriangleCircumcentreVisitor;
 
public:
        std::auto_ptr<geom::MultiLineString> getEdges(const geom::GeometryFactory& geomFact);

        std::auto_ptr<geom::GeometryCollection> getTriangles(const geom::GeometryFactory &geomFact);

        std::auto_ptr<geom::GeometryCollection> getVoronoiDiagram(const geom::GeometryFactory& geomFact);

        std::auto_ptr<geom::MultiLineString> getVoronoiDiagramEdges(const geom::GeometryFactory& geomFact);

        std::auto_ptr< std::vector<geom::Geometry*> > getVoronoiCellPolygons(const geom::GeometryFactory& geomFact);

        std::auto_ptr< std::vector<geom::Geometry*> > getVoronoiCellEdges(const geom::GeometryFactory& geomFact);
        
        std::auto_ptr<QuadEdgeSubdivision::QuadEdgeList> getVertexUniqueEdges(bool includeFrame);

        std::auto_ptr<geom::Geometry> getVoronoiCellPolygon(QuadEdge* qe ,const geom::GeometryFactory& geomFact);

        std::auto_ptr<geom::Geometry> getVoronoiCellEdge(QuadEdge* qe ,const geom::GeometryFactory& geomFact);
 
};
 
} //namespace geos.triangulate.quadedge
} //namespace geos.triangulate
} //namespace goes
 
#endif //GEOS_TRIANGULATE_QUADEDGE_QUADEDGESUBDIVISION_H