00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
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 {
00043 namespace 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
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 }
00399 }
00400 }
00401
00402 #endif //GEOS_TRIANGULATE_QUADEDGE_QUADEDGESUBDIVISION_H