GEOS
3.4.2
|
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