GEOS  3.8.0dev
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 <unordered_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 
78 class GEOS_DLL QuadEdgeSubdivision {
79 public:
80  typedef std::vector<QuadEdge*> QuadEdgeList;
81 
90  static void getTriangleEdges(const QuadEdge& startQE,
91  const QuadEdge* triEdge[3]);
92 
93 private:
94  QuadEdgeList quadEdges;
95  QuadEdgeList createdEdges;
96  QuadEdge* startingEdges[3];
97  double tolerance;
98  double edgeCoincidenceTolerance;
99  Vertex frameVertex[3];
100  geom::Envelope frameEnv;
101  std::unique_ptr<QuadEdgeLocator> locator;
102 
103 public:
112  QuadEdgeSubdivision(const geom::Envelope& env, double tolerance);
113 
114  virtual ~QuadEdgeSubdivision();
115 
116 private:
117  virtual void createFrame(const geom::Envelope& env);
118 
119  virtual void initSubdiv(QuadEdge* initEdges[3]);
120 
121 public:
127  inline double
128  getTolerance() const
129  {
130  return tolerance;
131  }
132 
138  inline const geom::Envelope&
139  getEnvelope() const
140  {
141  return frameEnv;
142  }
143 
150  inline const QuadEdgeList&
151  getEdges() const
152  {
153  return quadEdges;
154  }
155 
163  inline void
164  setLocator(std::unique_ptr<QuadEdgeLocator> p_locator)
165  {
166  this->locator = std::move(p_locator);
167  }
168 
176  virtual QuadEdge& makeEdge(const Vertex& o, const Vertex& d);
177 
188  virtual QuadEdge& connect(QuadEdge& a, QuadEdge& b);
189 
197  void remove(QuadEdge& e);
198 
218  QuadEdge* locateFromEdge(const Vertex& v,
219  const QuadEdge& startEdge) const;
220 
231  inline QuadEdge*
232  locate(const Vertex& v) const
233  {
234  return locator->locate(v);
235  }
236 
247  inline QuadEdge*
249  {
250  return locator->locate(Vertex(p));
251  }
252 
264  QuadEdge* locate(const geom::Coordinate& p0, const geom::Coordinate& p1);
265 
281  QuadEdge& insertSite(const Vertex& v);
282 
289  bool isFrameEdge(const QuadEdge& e) const;
290 
299  bool isFrameBorderEdge(const QuadEdge& e) const;
300 
307  bool isFrameVertex(const Vertex& v) const;
308 
309 
318  bool isOnEdge(const QuadEdge& e, const geom::Coordinate& p) const;
319 
328  bool isVertexOfEdge(const QuadEdge& e, const Vertex& v) const;
329 
341  std::unique_ptr<QuadEdgeList> getPrimaryEdges(bool includeFrame);
342 
343  /*****************************************************************************
344  * Visitors
345  ****************************************************************************/
346 
347  void visitTriangles(TriangleVisitor* triVisitor, bool includeFrame);
348 
349 private:
350  typedef std::stack<QuadEdge*> QuadEdgeStack;
351  typedef std::unordered_set<QuadEdge*> QuadEdgeSet;
352  typedef std::vector<geom::CoordinateSequence*> TriList;
353 
359  QuadEdge* triEdges[3];
360 
372  QuadEdge** fetchTriangleToVisit(QuadEdge* edge, QuadEdgeStack& edgeStack, bool includeFrame,
373  QuadEdgeSet& visitedEdges);
374 
381  void getTriangleCoordinates(TriList* triList, bool includeFrame);
382 
383 private:
384  class TriangleCoordinatesVisitor;
385  class TriangleCircumcentreVisitor;
386 
387 public:
396  std::unique_ptr<geom::MultiLineString> getEdges(const geom::GeometryFactory& geomFact);
397 
408  std::unique_ptr<geom::GeometryCollection> getTriangles(const geom::GeometryFactory& geomFact);
409 
422  std::unique_ptr<geom::GeometryCollection> getVoronoiDiagram(const geom::GeometryFactory& geomFact);
423 
435  std::unique_ptr<geom::MultiLineString> getVoronoiDiagramEdges(const geom::GeometryFactory& geomFact);
436 
448  std::vector<std::unique_ptr<geom::Geometry>> getVoronoiCellPolygons(const geom::GeometryFactory& geomFact);
449 
461  std::unique_ptr< std::vector<geom::Geometry*> > getVoronoiCellEdges(const geom::GeometryFactory& geomFact);
462 
476  std::unique_ptr<QuadEdgeSubdivision::QuadEdgeList> getVertexUniqueEdges(bool includeFrame);
477 
489  std::unique_ptr<geom::Geometry> getVoronoiCellPolygon(const QuadEdge* qe, const geom::GeometryFactory& geomFact);
490 
502  std::unique_ptr<geom::Geometry> getVoronoiCellEdge(const QuadEdge* qe, const geom::GeometryFactory& geomFact);
503 
504 };
505 
506 } //namespace geos.triangulate.quadedge
507 } //namespace geos.triangulate
508 } //namespace goes
509 
510 #endif //GEOS_TRIANGULATE_QUADEDGE_QUADEDGESUBDIVISION_H
An Envelope defines a rectangulare region of the 2D coordinate plane.
Definition: Envelope.h:58
QuadEdge * locate(const geom::Coordinate &p)
Finds a quadedge of a triangle containing a location specified by a geom::Coordinate, if one exists.
Definition: QuadEdgeSubdivision.h:248
Definition: TriangleVisitor.h:34
Coordinate is the lightweight class used to store coordinates.
Definition: Coordinate.h:60
QuadEdge * locate(const Vertex &v) const
Finds a quadedge of a triangle containing a location specified by a Vertex, if one exists...
Definition: QuadEdgeSubdivision.h:232
Models a site (node) in a QuadEdgeSubdivision.
Definition: Vertex.h:59
Supplies a set of utility methods for building Geometry objects from CoordinateSequence or other Geom...
Definition: GeometryFactory.h:66
A class that contains the QuadEdges representing a planar subdivision that models a triangulation...
Definition: QuadEdgeSubdivision.h:78
Basic namespace for all GEOS functionalities.
Definition: IndexedNestedRingTester.h:25
void setLocator(std::unique_ptr< QuadEdgeLocator > p_locator)
Sets the QuadEdgeLocator to use for locating containing triangles in this subdivision.
Definition: QuadEdgeSubdivision.h:164
double getTolerance() const
Gets the vertex-equality tolerance value used in this subdivision.
Definition: QuadEdgeSubdivision.h:128
const QuadEdgeList & getEdges() const
Gets the collection of base QuadEdges (one for every pair of vertices which is connected).
Definition: QuadEdgeSubdivision.h:151
A class that represents the edge data structure which implements the quadedge algebra.
Definition: QuadEdge.h:51
const geom::Envelope & getEnvelope() const
Gets the envelope of the Subdivision (including the frame).
Definition: QuadEdgeSubdivision.h:139