GEOS  3.9.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 <vector>
28 
29 #include <geos/geom/MultiLineString.h>
30 #include <geos/triangulate/quadedge/QuadEdge.h>
31 #include <geos/triangulate/quadedge/QuadEdgeLocator.h>
32 #include <geos/triangulate/quadedge/QuadEdgeQuartet.h>
33 #include <geos/triangulate/quadedge/Vertex.h>
34 
35 namespace geos {
36 
37 namespace geom {
38 
39 class CoordinateSequence;
40 class GeometryCollection;
41 class MultiLineString;
42 class GeometryFactory;
43 class Coordinate;
44 class Geometry;
45 class Envelope;
46 }
47 
48 namespace triangulate { //geos.triangulate
49 namespace quadedge { //geos.triangulate.quadedge
50 
51 class TriangleVisitor;
52 
53 const double EDGE_COINCIDENCE_TOL_FACTOR = 1000;
54 
80 class GEOS_DLL QuadEdgeSubdivision {
81 public:
82  typedef std::vector<QuadEdge*> QuadEdgeList;
83 
92  static void getTriangleEdges(const QuadEdge& startQE,
93  const QuadEdge* triEdge[3]);
94 
95 private:
100  std::deque<QuadEdgeQuartet> quadEdges;
101  std::array<QuadEdge*, 3> startingEdges;
102  double tolerance;
103  double edgeCoincidenceTolerance;
104  std::array<Vertex, 3> frameVertex;
105  geom::Envelope frameEnv;
106  std::unique_ptr<QuadEdgeLocator> locator;
107  bool visit_state_clean;
108 
109 public:
118  QuadEdgeSubdivision(const geom::Envelope& env, double tolerance);
119 
120  virtual ~QuadEdgeSubdivision() = default;
121 
122 private:
123  virtual void createFrame(const geom::Envelope& env);
124 
125  virtual void initSubdiv();
126 
127 public:
133  inline double
134  getTolerance() const
135  {
136  return tolerance;
137  }
138 
144  inline const geom::Envelope&
145  getEnvelope() const
146  {
147  return frameEnv;
148  }
149 
156  inline std::deque<QuadEdgeQuartet>&
158  {
159  return quadEdges;
160  }
161 
169  inline void
170  setLocator(std::unique_ptr<QuadEdgeLocator> p_locator)
171  {
172  this->locator = std::move(p_locator);
173  }
174 
182  virtual QuadEdge& makeEdge(const Vertex& o, const Vertex& d);
183 
194  virtual QuadEdge& connect(QuadEdge& a, QuadEdge& b);
195 
202  void remove(QuadEdge& e);
203 
224  const QuadEdge& startEdge) const;
225 
236  inline QuadEdge*
237  locate(const Vertex& v) const
238  {
239  return locator->locate(v);
240  }
241 
252  inline QuadEdge*
254  {
255  return locator->locate(Vertex(p));
256  }
257 
270 
287 
294  bool isFrameEdge(const QuadEdge& e) const;
295 
304  bool isFrameBorderEdge(const QuadEdge& e) const;
305 
312  bool isFrameVertex(const Vertex& v) const;
313 
314 
323  bool isOnEdge(const QuadEdge& e, const geom::Coordinate& p) const;
324 
333  bool isVertexOfEdge(const QuadEdge& e, const Vertex& v) const;
334 
346  std::unique_ptr<QuadEdgeList> getPrimaryEdges(bool includeFrame);
347 
348  /*****************************************************************************
349  * Visitors
350  ****************************************************************************/
351 
352  void visitTriangles(TriangleVisitor* triVisitor, bool includeFrame);
353 
354 private:
355  typedef std::stack<QuadEdge*> QuadEdgeStack;
356  typedef std::vector<std::unique_ptr<geom::CoordinateSequence>> TriList;
357 
363  QuadEdge* triEdges[3];
364 
368  void prepareVisit();
369 
381  QuadEdge** fetchTriangleToVisit(QuadEdge* edge, QuadEdgeStack& edgeStack, bool includeFrame);
382 
389  void getTriangleCoordinates(TriList* triList, bool includeFrame);
390 
391 private:
392  class TriangleCoordinatesVisitor;
393  class TriangleCircumcentreVisitor;
394 
395 public:
404  std::unique_ptr<geom::MultiLineString> getEdges(const geom::GeometryFactory& geomFact);
405 
416  std::unique_ptr<geom::GeometryCollection> getTriangles(const geom::GeometryFactory& geomFact);
417 
430  std::unique_ptr<geom::GeometryCollection> getVoronoiDiagram(const geom::GeometryFactory& geomFact);
431 
443  std::unique_ptr<geom::MultiLineString> getVoronoiDiagramEdges(const geom::GeometryFactory& geomFact);
444 
456  std::vector<std::unique_ptr<geom::Geometry>> getVoronoiCellPolygons(const geom::GeometryFactory& geomFact);
457 
469  std::vector<std::unique_ptr<geom::Geometry>> getVoronoiCellEdges(const geom::GeometryFactory& geomFact);
470 
484  std::unique_ptr<QuadEdgeSubdivision::QuadEdgeList> getVertexUniqueEdges(bool includeFrame);
485 
497  std::unique_ptr<geom::Geometry> getVoronoiCellPolygon(const QuadEdge* qe, const geom::GeometryFactory& geomFact);
498 
510  std::unique_ptr<geom::Geometry> getVoronoiCellEdge(const QuadEdge* qe, const geom::GeometryFactory& geomFact);
511 
512 };
513 
514 } //namespace geos.triangulate.quadedge
515 } //namespace geos.triangulate
516 } //namespace goes
517 
518 #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:80
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:253
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:145
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:237
std::deque< QuadEdgeQuartet > & getEdges()
Gets the collection of base QuadEdges (one for every pair of vertices which is connected).
Definition: QuadEdgeSubdivision.h:157
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:134
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:170
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:60
Basic namespace for all GEOS functionalities.
Definition: IndexedNestedRingTester.h:26