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 
00027 #include <geos/geom/Envelope.h>
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 GeometryFactory;
00039         class Coordinate;
00040 }
00041 
00042 namespace triangulate { //geos.triangulate
00043 namespace quadedge { //geos.triangulate.quadedge
00044 
00045 class QuadEdge;
00046 class TriangleVisitor;
00047 
00048 const double EDGE_COINCIDENCE_TOL_FACTOR = 1000;
00049 
00076 class GEOS_DLL QuadEdgeSubdivision {
00077 public:
00078         typedef std::list<QuadEdge*> QuadEdgeList;
00079 
00089         static void getTriangleEdges(const QuadEdge &startQE,
00090                         const QuadEdge* triEdge[3]);
00091 
00092 private:
00093         QuadEdgeList quadEdges;
00094         QuadEdgeList createdEdges;
00095         QuadEdge* startingEdges[3];
00096         double tolerance;
00097         double edgeCoincidenceTolerance;
00098         Vertex frameVertex[3];
00099         geom::Envelope frameEnv;
00100         std::auto_ptr<QuadEdgeLocator> locator;
00101 
00102 public:
00113         QuadEdgeSubdivision(const geom::Envelope &env, double tolerance);
00114 
00115         ~QuadEdgeSubdivision();
00116 
00117 private:
00118         virtual void createFrame(const geom::Envelope &env);
00119         
00120         virtual void initSubdiv(QuadEdge* initEdges[3]);
00121         
00122 public:
00129         inline double getTolerance() const {
00130                 return tolerance;
00131         }
00132 
00138         inline const geom::Envelope& getEnvelope() const {
00139                 return frameEnv;
00140         }
00141 
00148         inline const QuadEdgeList& getEdges() const {
00149                 return quadEdges;
00150         }
00151 
00159         inline void setLocator(std::auto_ptr<QuadEdgeLocator> locator) {
00160                 this->locator = locator;
00161         }
00162 
00170         virtual QuadEdge& makeEdge(const Vertex &o, const Vertex &d);
00171 
00181         virtual QuadEdge& connect(QuadEdge &a, QuadEdge &b);
00182 
00190         void remove(QuadEdge &e);
00191 
00210         QuadEdge* locateFromEdge(const Vertex &v,
00211                         const QuadEdge &startEdge) const;
00212 
00222         inline QuadEdge* locate(const Vertex &v) const {
00223                 return locator->locate(v);
00224         }
00225 
00235         inline QuadEdge* locate(const geom::Coordinate &p) {
00236                 return locator->locate(Vertex(p));
00237         }
00238 
00249         QuadEdge* locate(const geom::Coordinate &p0, const geom::Coordinate &p1);
00250 
00267         QuadEdge& insertSite(const Vertex &v);
00268 
00276         bool isFrameEdge(const QuadEdge &e) const;
00277 
00287         bool isFrameBorderEdge(const QuadEdge &e) const;
00288 
00296         bool isFrameVertex(const Vertex &v) const;
00297 
00298 
00309         bool isOnEdge(const QuadEdge &e, const geom::Coordinate &p) const;
00310 
00319         bool isVertexOfEdge(const QuadEdge &e, const Vertex &v) const;
00320 
00331         std::auto_ptr<QuadEdgeList> getPrimaryEdges(bool includeFrame);
00332   
00333         /*****************************************************************************
00334          * Visitors
00335          ****************************************************************************/
00336 
00337         void visitTriangles(TriangleVisitor *triVisitor, bool includeFrame);
00338 
00339 private:
00340         typedef std::stack<QuadEdge*> QuadEdgeStack;
00341         typedef std::set<QuadEdge*> QuadEdgeSet;
00342         typedef std::list< geom::CoordinateSequence*> TriList;
00343 
00349         QuadEdge* triEdges[3];
00350 
00362         QuadEdge** fetchTriangleToVisit(QuadEdge *edge, QuadEdgeStack &edgeStack, bool includeFrame,
00363                         QuadEdgeSet &visitedEdges);
00364 
00372         void getTriangleCoordinates(TriList* triList, bool includeFrame);
00373 
00374 private:
00375         class TriangleCoordinatesVisitor; 
00376 
00377 public:
00385         std::auto_ptr<geom::MultiLineString> getEdges(const geom::GeometryFactory& geomFact);
00386 
00394         std::auto_ptr<geom::GeometryCollection> getTriangles(const geom::GeometryFactory &geomFact);
00395 
00396 };
00397 
00398 } //namespace geos.triangulate.quadedge
00399 } //namespace geos.triangulate
00400 } //namespace goes
00401 
00402 #endif //GEOS_TRIANGULATE_QUADEDGE_QUADEDGESUBDIVISION_H

Generated on 10 Sep 2013 for GEOS by  doxygen 1.4.7