GEOS  3.10.0
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 
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 
271 
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
Coordinate is the lightweight class used to store coordinates.
Definition: Coordinate.h:60
An Envelope defines a rectangulare region of the 2D coordinate plane.
Definition: Envelope.h:58
Supplies a set of utility methods for building Geometry objects from CoordinateSequence or other Geom...
Definition: GeometryFactory.h:68
A class that contains the QuadEdges representing a planar subdivision that models a triangulation.
Definition: QuadEdgeSubdivision.h:81
bool isFrameBorderEdge(const QuadEdge &e) const
Tests whether a QuadEdge is an edge on the border of the frame facets and the internal facets....
std::unique_ptr< geom::GeometryCollection > getTriangles(const geom::GeometryFactory &geomFact)
Gets the geometry for the triangles in a triangulated subdivision as a GeometryCollection of triangul...
bool isFrameEdge(const QuadEdge &e) const
Tests whether a QuadEdge is an edge incident on a frame triangle vertex.
QuadEdge * locate(const geom::Coordinate &p)
Finds a quadedge of a triangle containing a location specified by a geom::Coordinate,...
Definition: QuadEdgeSubdivision.h:254
virtual QuadEdge & connect(QuadEdge &a, QuadEdge &b)
Creates a new QuadEdge connecting the destination of a to the origin of b, in such a way that all thr...
std::unique_ptr< geom::Geometry > getVoronoiCellEdge(const QuadEdge *qe, const geom::GeometryFactory &geomFact)
Gets the Voronoi cell edge around a site specified by the origin of a QuadEdge.
static void getTriangleEdges(const QuadEdge &startQE, const QuadEdge *triEdge[3])
Gets the edges for the triangle to the left of the given QuadEdge.
const geom::Envelope & getEnvelope() const
Gets the envelope of the Subdivision (including the frame).
Definition: QuadEdgeSubdivision.h:146
bool isFrameVertex(const Vertex &v) const
Tests whether a vertex is a vertex of the outer triangle.
QuadEdge * locate(const geom::Coordinate &p0, const geom::Coordinate &p1)
Locates the edge between the given vertices, if it exists in the subdivision.
void remove(QuadEdge &e)
Deletes a quadedge from the subdivision. Linked quadedges are updated to reflect the deletion.
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
std::deque< QuadEdgeQuartet > & getEdges()
Gets the collection of base QuadEdges (one for every pair of vertices which is connected).
Definition: QuadEdgeSubdivision.h:158
QuadEdgeSubdivision(const geom::Envelope &env, double tolerance)
Creates a new instance of a quad-edge subdivision based on a frame triangle that encloses a supplied ...
std::unique_ptr< geom::Geometry > getVoronoiCellPolygon(const QuadEdge *qe, const geom::GeometryFactory &geomFact)
Gets the Voronoi cell around a site specified by the origin of a QuadEdge.
std::vector< std::unique_ptr< geom::Geometry > > getVoronoiCellEdges(const geom::GeometryFactory &geomFact)
Gets a List of LineStrings for the Voronoi cells of this triangulation.
std::unique_ptr< QuadEdgeSubdivision::QuadEdgeList > getVertexUniqueEdges(bool includeFrame)
Gets a collection of QuadEdges whose origin vertices are a unique set which includes all vertices in ...
std::unique_ptr< QuadEdgeList > getPrimaryEdges(bool includeFrame)
Gets all primary quadedges in the subdivision.
double getTolerance() const
Gets the vertex-equality tolerance value used in this subdivision.
Definition: QuadEdgeSubdivision.h:135
bool isOnEdge(const QuadEdge &e, const geom::Coordinate &p) const
Tests whether a Coordinate lies on a QuadEdge, up to a tolerance determined by the subdivision tolera...
virtual QuadEdge & makeEdge(const Vertex &o, const Vertex &d)
Creates a new quadedge, recording it in the edges list.
std::unique_ptr< geom::GeometryCollection > getVoronoiDiagram(const geom::GeometryFactory &geomFact)
Gets the cells in the Voronoi diagram for this triangulation. The cells are returned as a GeometryCol...
std::vector< std::unique_ptr< geom::Geometry > > getVoronoiCellPolygons(const geom::GeometryFactory &geomFact)
Gets a List of Polygons for the Voronoi cells of this triangulation.
std::unique_ptr< geom::MultiLineString > getVoronoiDiagramEdges(const geom::GeometryFactory &geomFact)
Gets the cells in the Voronoi diagram for this triangulation.
std::unique_ptr< geom::MultiLineString > getEdges(const geom::GeometryFactory &geomFact)
Gets the geometry for the edges in the subdivision as a MultiLineString containing 2-point lines.
QuadEdge * locateFromEdge(const Vertex &v, const QuadEdge &startEdge) const
Locates an edge of a triangle which contains a location specified by a Vertex v.
QuadEdge & insertSite(const Vertex &v)
Inserts a new site into the Subdivision, connecting it to the vertices of the containing triangle (or...
void setLocator(std::unique_ptr< QuadEdgeLocator > p_locator)
Sets the QuadEdgeLocator to use for locating containing triangles in this subdivision.
Definition: QuadEdgeSubdivision.h:171
bool isVertexOfEdge(const QuadEdge &e, const Vertex &v) const
Tests whether a Vertex is the start or end vertex of a QuadEdge, up to the subdivision tolerance dist...
A class that represents the edge data structure which implements the quadedge algebra.
Definition: QuadEdge.h:54
An interface for algorithms which process the triangles in a QuadEdgeSubdivision.
Definition: TriangleVisitor.h:34
Models a site (node) in a QuadEdgeSubdivision.
Definition: Vertex.h:61
Basic namespace for all GEOS functionalities.
Definition: Angle.h:26