GEOS  3.10.1
QuadEdgeSubdivision.h
1 /**********************************************************************
2  *
3  * GEOS - Geometry Engine Open Source
4  * http://geos.osgeo.org
5  *
6  * Copyright (C) 2012 Excensus LLC.
7  * Copyright (C) 2019 Daniel Baston
8  *
9  * This is free software; you can redistribute and/or modify it under
10  * the terms of the GNU Lesser General Licence as published
11  * by the Free Software Foundation.
12  * See the COPYING file for more information.
13  *
14  **********************************************************************
15  *
16  * Last port: triangulate/quadedge/QuadEdgeSubdivision.java r524
17  *
18  **********************************************************************/
19 
20 #ifndef GEOS_TRIANGULATE_QUADEDGE_QUADEDGESUBDIVISION_H
21 #define GEOS_TRIANGULATE_QUADEDGE_QUADEDGESUBDIVISION_H
22 
23 #include <memory>
24 #include <list>
25 #include <stack>
26 #include <unordered_set>
27 #include <array>
28 #include <vector>
29 
30 #include <geos/geom/MultiLineString.h>
31 #include <geos/triangulate/quadedge/QuadEdge.h>
32 #include <geos/triangulate/quadedge/QuadEdgeLocator.h>
33 #include <geos/triangulate/quadedge/QuadEdgeQuartet.h>
34 #include <geos/triangulate/quadedge/Vertex.h>
35 
36 namespace geos {
37 
38 namespace geom {
39 
40 class CoordinateSequence;
41 class GeometryCollection;
42 class MultiLineString;
43 class GeometryFactory;
44 class Coordinate;
45 class Geometry;
46 class Envelope;
47 }
48 
49 namespace triangulate { //geos.triangulate
50 namespace quadedge { //geos.triangulate.quadedge
51 
52 class TriangleVisitor;
53 
54 const double EDGE_COINCIDENCE_TOL_FACTOR = 1000;
55 
81 class GEOS_DLL QuadEdgeSubdivision {
82 public:
83  typedef std::vector<QuadEdge*> QuadEdgeList;
84 
93  static void getTriangleEdges(const QuadEdge& startQE,
94  const QuadEdge* triEdge[3]);
95 
96 private:
101  std::deque<QuadEdgeQuartet> quadEdges;
102  std::array<QuadEdge*, 3> startingEdges;
103  double tolerance;
104  double edgeCoincidenceTolerance;
105  std::array<Vertex, 3> frameVertex;
106  geom::Envelope frameEnv;
107  std::unique_ptr<QuadEdgeLocator> locator;
108  bool visit_state_clean;
109 
110 public:
119  QuadEdgeSubdivision(const geom::Envelope& env, double tolerance);
120 
121  virtual ~QuadEdgeSubdivision() = default;
122 
123 private:
124  virtual void createFrame(const geom::Envelope& env);
125 
126  virtual void initSubdiv();
127 
128 public:
134  inline double
135  getTolerance() const
136  {
137  return tolerance;
138  }
139 
145  inline const geom::Envelope&
146  getEnvelope() const
147  {
148  return frameEnv;
149  }
150 
157  inline std::deque<QuadEdgeQuartet>&
159  {
160  return quadEdges;
161  }
162 
170  inline void
171  setLocator(std::unique_ptr<QuadEdgeLocator> p_locator)
172  {
173  this->locator = std::move(p_locator);
174  }
175 
183  virtual QuadEdge& makeEdge(const Vertex& o, const Vertex& d);
184 
195  virtual QuadEdge& connect(QuadEdge& a, QuadEdge& b);
196 
203  void remove(QuadEdge& e);
204 
224  QuadEdge* locateFromEdge(const Vertex& v,
225  const QuadEdge& startEdge) const;
226 
237  inline QuadEdge*
238  locate(const Vertex& v) const
239  {
240  return locator->locate(v);
241  }
242 
253  inline QuadEdge*
255  {
256  return locator->locate(Vertex(p));
257  }
258 
270  QuadEdge* locate(const geom::Coordinate& p0, const geom::Coordinate& p1);
271 
287  QuadEdge& insertSite(const Vertex& v);
288 
295  bool isFrameEdge(const QuadEdge& e) const;
296 
305  bool isFrameBorderEdge(const QuadEdge& e) const;
306 
313  bool isFrameVertex(const Vertex& v) const;
314 
315 
324  bool isOnEdge(const QuadEdge& e, const geom::Coordinate& p) const;
325 
334  bool isVertexOfEdge(const QuadEdge& e, const Vertex& v) const;
335 
347  std::unique_ptr<QuadEdgeList> getPrimaryEdges(bool includeFrame);
348 
349  /*****************************************************************************
350  * Visitors
351  ****************************************************************************/
352 
353  void visitTriangles(TriangleVisitor* triVisitor, bool includeFrame);
354 
355 private:
356  typedef std::stack<QuadEdge*> QuadEdgeStack;
357  typedef std::vector<std::unique_ptr<geom::CoordinateSequence>> TriList;
358 
364  std::array<QuadEdge*, 3> m_triEdges;
365 
369  void prepareVisit();
370 
382  std::array<QuadEdge*, 3>* fetchTriangleToVisit(QuadEdge* edge, QuadEdgeStack& edgeStack, bool includeFrame);
383 
390  void getTriangleCoordinates(TriList* triList, bool includeFrame);
391 
392 private:
393  class TriangleCoordinatesVisitor;
394  class TriangleCircumcentreVisitor;
395 
396 public:
405  std::unique_ptr<geom::MultiLineString> getEdges(const geom::GeometryFactory& geomFact);
406 
417  std::unique_ptr<geom::GeometryCollection> getTriangles(const geom::GeometryFactory& geomFact);
418 
431  std::unique_ptr<geom::GeometryCollection> getVoronoiDiagram(const geom::GeometryFactory& geomFact);
432 
444  std::unique_ptr<geom::MultiLineString> getVoronoiDiagramEdges(const geom::GeometryFactory& geomFact);
445 
457  std::vector<std::unique_ptr<geom::Geometry>> getVoronoiCellPolygons(const geom::GeometryFactory& geomFact);
458 
470  std::vector<std::unique_ptr<geom::Geometry>> getVoronoiCellEdges(const geom::GeometryFactory& geomFact);
471 
485  std::unique_ptr<QuadEdgeSubdivision::QuadEdgeList> getVertexUniqueEdges(bool includeFrame);
486 
498  std::unique_ptr<geom::Geometry> getVoronoiCellPolygon(const QuadEdge* qe, const geom::GeometryFactory& geomFact);
499 
511  std::unique_ptr<geom::Geometry> getVoronoiCellEdge(const QuadEdge* qe, const geom::GeometryFactory& geomFact);
512 
513 };
514 
515 } //namespace geos.triangulate.quadedge
516 } //namespace geos.triangulate
517 } //namespace goes
518 
519 #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:254
An interface for algorithms which process the triangles in a QuadEdgeSubdivision. ...
Definition: TriangleVisitor.h:34
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:238
Coordinate is the lightweight class used to store coordinates.
Definition: Coordinate.h:60
Models a site (node) in a QuadEdgeSubdivision.
Definition: Vertex.h:61
Supplies a set of utility methods for building Geometry objects from CoordinateSequence or other Geom...
Definition: GeometryFactory.h:68
std::deque< QuadEdgeQuartet > & getEdges()
Gets the collection of base QuadEdges (one for every pair of vertices which is connected).
Definition: QuadEdgeSubdivision.h:158
A class that contains the QuadEdges representing a planar subdivision that models a triangulation...
Definition: QuadEdgeSubdivision.h:81
Basic namespace for all GEOS functionalities.
Definition: Angle.h:26
const geom::Envelope & getEnvelope() const
Gets the envelope of the Subdivision (including the frame).
Definition: QuadEdgeSubdivision.h:146
void setLocator(std::unique_ptr< QuadEdgeLocator > p_locator)
Sets the QuadEdgeLocator to use for locating containing triangles in this subdivision.
Definition: QuadEdgeSubdivision.h:171
A class that represents the edge data structure which implements the quadedge algebra.
Definition: QuadEdge.h:54
double getTolerance() const
Gets the vertex-equality tolerance value used in this subdivision.
Definition: QuadEdgeSubdivision.h:135