GEOS  3.6.1
QuadEdgeSubdivision.h
1 /**********************************************************************
2  *
3  * GEOS - Geometry Engine Open Source
4  * http://geos.osgeo.org
5  *
6  * Copyright (C) 2012 Excensus LLC.
7  *
8  * This is free software; you can redistribute and/or modify it under
9  * the terms of the GNU Lesser General Licence as published
10  * by the Free Software Foundation.
11  * See the COPYING file for more information.
12  *
13  **********************************************************************
14  *
15  * Last port: triangulate/quadedge/QuadEdgeSubdivision.java r524
16  *
17  **********************************************************************/
18 
19 #ifndef GEOS_TRIANGULATE_QUADEDGE_QUADEDGESUBDIVISION_H
20 #define GEOS_TRIANGULATE_QUADEDGE_QUADEDGESUBDIVISION_H
21 
22 #include <memory>
23 #include <list>
24 #include <stack>
25 #include <set>
26 #include <vector>
27 
28 #include <geos/geom/MultiLineString.h>
29 #include <geos/triangulate/quadedge/QuadEdgeLocator.h>
30 #include <geos/triangulate/quadedge/Vertex.h>
31 
32 namespace geos {
33 
34 namespace geom {
35 
36  class CoordinateSequence;
37  class GeometryCollection;
38  class MultiLineString;
39  class GeometryFactory;
40  class Coordinate;
41  class Geometry;
42  class Envelope;
43 }
44 
45 namespace triangulate { //geos.triangulate
46 namespace quadedge { //geos.triangulate.quadedge
47 
48 class QuadEdge;
49 class TriangleVisitor;
50 
51 const double EDGE_COINCIDENCE_TOL_FACTOR = 1000;
52 
79 class GEOS_DLL QuadEdgeSubdivision {
80 public:
81  typedef std::vector<QuadEdge*> QuadEdgeList;
82 
92  static void getTriangleEdges(const QuadEdge &startQE,
93  const QuadEdge* triEdge[3]);
94 
95 private:
96  QuadEdgeList quadEdges;
97  QuadEdgeList createdEdges;
98  QuadEdge* startingEdges[3];
99  double tolerance;
100  double edgeCoincidenceTolerance;
101  Vertex frameVertex[3];
102  geom::Envelope frameEnv;
103  std::auto_ptr<QuadEdgeLocator> locator;
104 
105 public:
116  QuadEdgeSubdivision(const geom::Envelope &env, double tolerance);
117 
118  virtual ~QuadEdgeSubdivision();
119 
120 private:
121  virtual void createFrame(const geom::Envelope &env);
122 
123  virtual void initSubdiv(QuadEdge* initEdges[3]);
124 
125 public:
132  inline double getTolerance() const {
133  return tolerance;
134  }
135 
141  inline const geom::Envelope& getEnvelope() const {
142  return frameEnv;
143  }
144 
151  inline const QuadEdgeList& getEdges() const {
152  return quadEdges;
153  }
154 
162  inline void setLocator(std::auto_ptr<QuadEdgeLocator> locator) {
163  this->locator = locator;
164  }
165 
173  virtual QuadEdge& makeEdge(const Vertex &o, const Vertex &d);
174 
184  virtual QuadEdge& connect(QuadEdge &a, QuadEdge &b);
185 
193  void remove(QuadEdge &e);
194 
213  QuadEdge* locateFromEdge(const Vertex &v,
214  const QuadEdge &startEdge) const;
215 
225  inline QuadEdge* locate(const Vertex &v) const {
226  return locator->locate(v);
227  }
228 
238  inline QuadEdge* locate(const geom::Coordinate &p) {
239  return locator->locate(Vertex(p));
240  }
241 
252  QuadEdge* locate(const geom::Coordinate &p0, const geom::Coordinate &p1);
253 
270  QuadEdge& insertSite(const Vertex &v);
271 
279  bool isFrameEdge(const QuadEdge &e) const;
280 
290  bool isFrameBorderEdge(const QuadEdge &e) const;
291 
299  bool isFrameVertex(const Vertex &v) const;
300 
301 
312  bool isOnEdge(const QuadEdge &e, const geom::Coordinate &p) const;
313 
322  bool isVertexOfEdge(const QuadEdge &e, const Vertex &v) const;
323 
334  std::auto_ptr<QuadEdgeList> getPrimaryEdges(bool includeFrame);
335 
336  /*****************************************************************************
337  * Visitors
338  ****************************************************************************/
339 
340  void visitTriangles(TriangleVisitor *triVisitor, bool includeFrame);
341 
342 private:
343  typedef std::stack<QuadEdge*> QuadEdgeStack;
344  typedef std::set<QuadEdge*> QuadEdgeSet;
345  typedef std::list< geom::CoordinateSequence*> TriList;
346 
352  QuadEdge* triEdges[3];
353 
365  QuadEdge** fetchTriangleToVisit(QuadEdge *edge, QuadEdgeStack &edgeStack, bool includeFrame,
366  QuadEdgeSet &visitedEdges);
367 
375  void getTriangleCoordinates(TriList* triList, bool includeFrame);
376 
377 private:
378  class TriangleCoordinatesVisitor;
379  class TriangleCircumcentreVisitor;
380 
381 public:
389  std::auto_ptr<geom::MultiLineString> getEdges(const geom::GeometryFactory& geomFact);
390 
398  std::auto_ptr<geom::GeometryCollection> getTriangles(const geom::GeometryFactory &geomFact);
399 
410  std::auto_ptr<geom::GeometryCollection> getVoronoiDiagram(const geom::GeometryFactory& geomFact);
411 
422  std::auto_ptr<geom::MultiLineString> getVoronoiDiagramEdges(const geom::GeometryFactory& geomFact);
423 
434  std::auto_ptr< std::vector<geom::Geometry*> > getVoronoiCellPolygons(const geom::GeometryFactory& geomFact);
435 
446  std::auto_ptr< std::vector<geom::Geometry*> > getVoronoiCellEdges(const geom::GeometryFactory& geomFact);
447 
464  std::auto_ptr<QuadEdgeSubdivision::QuadEdgeList> getVertexUniqueEdges(bool includeFrame);
465 
477  std::auto_ptr<geom::Geometry> getVoronoiCellPolygon(QuadEdge* qe ,const geom::GeometryFactory& geomFact);
478 
490  std::auto_ptr<geom::Geometry> getVoronoiCellEdge(QuadEdge* qe ,const geom::GeometryFactory& geomFact);
491 
492 };
493 
494 } //namespace geos.triangulate.quadedge
495 } //namespace geos.triangulate
496 } //namespace goes
497 
498 #endif //GEOS_TRIANGULATE_QUADEDGE_QUADEDGESUBDIVISION_H
An Envelope defines a rectangulare region of the 2D coordinate plane.
Definition: Envelope.h:53
QuadEdge * locate(const geom::Coordinate &p)
Definition: QuadEdgeSubdivision.h:238
Definition: TriangleVisitor.h:34
QuadEdge * locate(const Vertex &v) const
Definition: QuadEdgeSubdivision.h:225
Coordinate is the lightweight class used to store coordinates.
Definition: Coordinate.h:60
void setLocator(std::auto_ptr< QuadEdgeLocator > locator)
Definition: QuadEdgeSubdivision.h:162
Supplies a set of utility methods for building Geometry objects from CoordinateSequence or other Geom...
Definition: GeometryFactory.h:67
const QuadEdgeList & getEdges() const
Definition: QuadEdgeSubdivision.h:151
Definition: QuadEdgeSubdivision.h:79
Basic namespace for all GEOS functionalities.
Definition: IndexedNestedRingTester.h:25
const geom::Envelope & getEnvelope() const
Definition: QuadEdgeSubdivision.h:141
Definition: QuadEdge.h:51
double getTolerance() const
Definition: QuadEdgeSubdivision.h:132