GEOS  3.4.2
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 
27 #include <geos/geom/Envelope.h>
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 GeometryFactory;
39  class Coordinate;
40 }
41 
42 namespace triangulate { //geos.triangulate
43 namespace quadedge { //geos.triangulate.quadedge
44 
45 class QuadEdge;
46 class TriangleVisitor;
47 
48 const double EDGE_COINCIDENCE_TOL_FACTOR = 1000;
49 
76 class GEOS_DLL QuadEdgeSubdivision {
77 public:
78  typedef std::list<QuadEdge*> QuadEdgeList;
79 
89  static void getTriangleEdges(const QuadEdge &startQE,
90  const QuadEdge* triEdge[3]);
91 
92 private:
93  QuadEdgeList quadEdges;
94  QuadEdgeList createdEdges;
95  QuadEdge* startingEdges[3];
96  double tolerance;
97  double edgeCoincidenceTolerance;
98  Vertex frameVertex[3];
99  geom::Envelope frameEnv;
100  std::auto_ptr<QuadEdgeLocator> locator;
101 
102 public:
113  QuadEdgeSubdivision(const geom::Envelope &env, double tolerance);
114 
116 
117 private:
118  virtual void createFrame(const geom::Envelope &env);
119 
120  virtual void initSubdiv(QuadEdge* initEdges[3]);
121 
122 public:
129  inline double getTolerance() const {
130  return tolerance;
131  }
132 
138  inline const geom::Envelope& getEnvelope() const {
139  return frameEnv;
140  }
141 
148  inline const QuadEdgeList& getEdges() const {
149  return quadEdges;
150  }
151 
159  inline void setLocator(std::auto_ptr<QuadEdgeLocator> locator) {
160  this->locator = locator;
161  }
162 
170  virtual QuadEdge& makeEdge(const Vertex &o, const Vertex &d);
171 
181  virtual QuadEdge& connect(QuadEdge &a, QuadEdge &b);
182 
190  void remove(QuadEdge &e);
191 
210  QuadEdge* locateFromEdge(const Vertex &v,
211  const QuadEdge &startEdge) const;
212 
222  inline QuadEdge* locate(const Vertex &v) const {
223  return locator->locate(v);
224  }
225 
235  inline QuadEdge* locate(const geom::Coordinate &p) {
236  return locator->locate(Vertex(p));
237  }
238 
249  QuadEdge* locate(const geom::Coordinate &p0, const geom::Coordinate &p1);
250 
267  QuadEdge& insertSite(const Vertex &v);
268 
276  bool isFrameEdge(const QuadEdge &e) const;
277 
287  bool isFrameBorderEdge(const QuadEdge &e) const;
288 
296  bool isFrameVertex(const Vertex &v) const;
297 
298 
309  bool isOnEdge(const QuadEdge &e, const geom::Coordinate &p) const;
310 
319  bool isVertexOfEdge(const QuadEdge &e, const Vertex &v) const;
320 
331  std::auto_ptr<QuadEdgeList> getPrimaryEdges(bool includeFrame);
332 
333  /*****************************************************************************
334  * Visitors
335  ****************************************************************************/
336 
337  void visitTriangles(TriangleVisitor *triVisitor, bool includeFrame);
338 
339 private:
340  typedef std::stack<QuadEdge*> QuadEdgeStack;
341  typedef std::set<QuadEdge*> QuadEdgeSet;
342  typedef std::list< geom::CoordinateSequence*> TriList;
343 
349  QuadEdge* triEdges[3];
350 
362  QuadEdge** fetchTriangleToVisit(QuadEdge *edge, QuadEdgeStack &edgeStack, bool includeFrame,
363  QuadEdgeSet &visitedEdges);
364 
372  void getTriangleCoordinates(TriList* triList, bool includeFrame);
373 
374 private:
375  class TriangleCoordinatesVisitor;
376 
377 public:
385  std::auto_ptr<geom::MultiLineString> getEdges(const geom::GeometryFactory& geomFact);
386 
394  std::auto_ptr<geom::GeometryCollection> getTriangles(const geom::GeometryFactory &geomFact);
395 
396 };
397 
398 } //namespace geos.triangulate.quadedge
399 } //namespace geos.triangulate
400 } //namespace goes
401 
402 #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:235
Definition: TriangleVisitor.h:34
Coordinate is the lightweight class used to store coordinates.
Definition: Coordinate.h:60
QuadEdge * locate(const Vertex &v) const
Definition: QuadEdgeSubdivision.h:222
void setLocator(std::auto_ptr< QuadEdgeLocator > locator)
Definition: QuadEdgeSubdivision.h:159
Supplies a set of utility methods for building Geometry objects from CoordinateSequence or other Geom...
Definition: GeometryFactory.h:67
Definition: QuadEdgeSubdivision.h:76
double getTolerance() const
Definition: QuadEdgeSubdivision.h:129
const QuadEdgeList & getEdges() const
Definition: QuadEdgeSubdivision.h:148
Definition: QuadEdge.h:51
const geom::Envelope & getEnvelope() const
Definition: QuadEdgeSubdivision.h:138