GEOS
3.6.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 #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