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 #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 {
00046 namespace 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::list<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
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 }
00495 }
00496 }
00497
00498 #endif //GEOS_TRIANGULATE_QUADEDGE_QUADEDGESUBDIVISION_H