GEOS  3.6.2
QuadEdgeSubdivision.h
00001 /**********************************************************************
00002  *
00003  * GEOS - Geometry Engine Open Source
00004  * http://geos.osgeo.org
00005  *
00006  * Copyright (C) 2012 Excensus LLC.
00007  *
00008  * This is free software; you can redistribute and/or modify it under
00009  * the terms of the GNU Lesser General Licence as published
00010  * by the Free Software Foundation. 
00011  * See the COPYING file for more information.
00012  *
00013  **********************************************************************
00014  *
00015  * Last port: triangulate/quadedge/QuadEdgeSubdivision.java r524
00016  *
00017  **********************************************************************/
00018 
00019 #ifndef GEOS_TRIANGULATE_QUADEDGE_QUADEDGESUBDIVISION_H
00020 #define GEOS_TRIANGULATE_QUADEDGE_QUADEDGESUBDIVISION_H
00021 
00022 #include <memory>
00023 #include <list>
00024 #include <stack>
00025 #include <set>
00026 #include <vector>
00027 
00028 #include <geos/geom/MultiLineString.h>
00029 #include <geos/triangulate/quadedge/QuadEdgeLocator.h>
00030 #include <geos/triangulate/quadedge/Vertex.h>
00031 
00032 namespace geos {
00033 
00034 namespace geom {
00035 
00036         class CoordinateSequence;
00037         class GeometryCollection;
00038         class MultiLineString;
00039         class GeometryFactory;
00040         class Coordinate;
00041         class Geometry;
00042         class Envelope;
00043 }
00044 
00045 namespace triangulate { //geos.triangulate
00046 namespace quadedge { //geos.triangulate.quadedge
00047 
00048 class QuadEdge;
00049 class TriangleVisitor;
00050 
00051 const double EDGE_COINCIDENCE_TOL_FACTOR = 1000;
00052 
00079 class GEOS_DLL QuadEdgeSubdivision {
00080 public:
00081         typedef std::vector<QuadEdge*> QuadEdgeList;
00082 
00092         static void getTriangleEdges(const QuadEdge &startQE,
00093                         const QuadEdge* triEdge[3]);
00094 
00095 private:
00096         QuadEdgeList quadEdges;
00097         QuadEdgeList createdEdges;
00098         QuadEdge* startingEdges[3];
00099         double tolerance;
00100         double edgeCoincidenceTolerance;
00101         Vertex frameVertex[3];
00102         geom::Envelope frameEnv;
00103         std::auto_ptr<QuadEdgeLocator> locator;
00104 
00105 public:
00116         QuadEdgeSubdivision(const geom::Envelope &env, double tolerance);
00117 
00118         virtual ~QuadEdgeSubdivision();
00119 
00120 private:
00121         virtual void createFrame(const geom::Envelope &env);
00122         
00123         virtual void initSubdiv(QuadEdge* initEdges[3]);
00124         
00125 public:
00132         inline double getTolerance() const {
00133                 return tolerance;
00134         }
00135 
00141         inline const geom::Envelope& getEnvelope() const {
00142                 return frameEnv;
00143         }
00144 
00151         inline const QuadEdgeList& getEdges() const {
00152                 return quadEdges;
00153         }
00154 
00162         inline void setLocator(std::auto_ptr<QuadEdgeLocator> locator) {
00163                 this->locator = locator;
00164         }
00165 
00173         virtual QuadEdge& makeEdge(const Vertex &o, const Vertex &d);
00174 
00184         virtual QuadEdge& connect(QuadEdge &a, QuadEdge &b);
00185 
00193         void remove(QuadEdge &e);
00194 
00213         QuadEdge* locateFromEdge(const Vertex &v,
00214                         const QuadEdge &startEdge) const;
00215 
00225         inline QuadEdge* locate(const Vertex &v) const {
00226                 return locator->locate(v);
00227         }
00228 
00238         inline QuadEdge* locate(const geom::Coordinate &p) {
00239                 return locator->locate(Vertex(p));
00240         }
00241 
00252         QuadEdge* locate(const geom::Coordinate &p0, const geom::Coordinate &p1);
00253 
00270         QuadEdge& insertSite(const Vertex &v);
00271 
00279         bool isFrameEdge(const QuadEdge &e) const;
00280 
00290         bool isFrameBorderEdge(const QuadEdge &e) const;
00291 
00299         bool isFrameVertex(const Vertex &v) const;
00300 
00301 
00312         bool isOnEdge(const QuadEdge &e, const geom::Coordinate &p) const;
00313 
00322         bool isVertexOfEdge(const QuadEdge &e, const Vertex &v) const;
00323 
00334         std::auto_ptr<QuadEdgeList> getPrimaryEdges(bool includeFrame);
00335   
00336         /*****************************************************************************
00337          * Visitors
00338          ****************************************************************************/
00339 
00340         void visitTriangles(TriangleVisitor *triVisitor, bool includeFrame);
00341 
00342 private:
00343         typedef std::stack<QuadEdge*> QuadEdgeStack;
00344         typedef std::set<QuadEdge*> QuadEdgeSet;
00345         typedef std::list< geom::CoordinateSequence*> TriList;
00346 
00352         QuadEdge* triEdges[3];
00353 
00365         QuadEdge** fetchTriangleToVisit(QuadEdge *edge, QuadEdgeStack &edgeStack, bool includeFrame,
00366                         QuadEdgeSet &visitedEdges);
00367 
00375         void getTriangleCoordinates(TriList* triList, bool includeFrame);
00376 
00377 private:
00378         class TriangleCoordinatesVisitor;
00379         class TriangleCircumcentreVisitor;
00380 
00381 public:
00389         std::auto_ptr<geom::MultiLineString> getEdges(const geom::GeometryFactory& geomFact);
00390 
00398         std::auto_ptr<geom::GeometryCollection> getTriangles(const geom::GeometryFactory &geomFact);
00399 
00410         std::auto_ptr<geom::GeometryCollection> getVoronoiDiagram(const geom::GeometryFactory& geomFact);
00411 
00422         std::auto_ptr<geom::MultiLineString> getVoronoiDiagramEdges(const geom::GeometryFactory& geomFact);
00423 
00434         std::auto_ptr< std::vector<geom::Geometry*> > getVoronoiCellPolygons(const geom::GeometryFactory& geomFact);
00435 
00446         std::auto_ptr< std::vector<geom::Geometry*> > getVoronoiCellEdges(const geom::GeometryFactory& geomFact);
00447         
00464         std::auto_ptr<QuadEdgeSubdivision::QuadEdgeList> getVertexUniqueEdges(bool includeFrame);
00465 
00477         std::auto_ptr<geom::Geometry> getVoronoiCellPolygon(QuadEdge* qe ,const geom::GeometryFactory& geomFact);
00478 
00490         std::auto_ptr<geom::Geometry> getVoronoiCellEdge(QuadEdge* qe ,const geom::GeometryFactory& geomFact);
00491 
00492 };
00493 
00494 } //namespace geos.triangulate.quadedge
00495 } //namespace geos.triangulate
00496 } //namespace goes
00497 
00498 #endif //GEOS_TRIANGULATE_QUADEDGE_QUADEDGESUBDIVISION_H