GEOS  3.9.0dev
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:
96  std::deque<QuadEdgeQuartet> quadEdges;
97  std::array<QuadEdge*, 3> startingEdges;
98  double tolerance;
99  double edgeCoincidenceTolerance;
100  std::array<Vertex, 3> frameVertex;
101  geom::Envelope frameEnv;
102  std::unique_ptr<QuadEdgeLocator> locator;
103  bool visit_state_clean;
104 
105 public:
114  QuadEdgeSubdivision(const geom::Envelope& env, double tolerance);
115 
116  virtual ~QuadEdgeSubdivision() = default;
117 
118 private:
119  virtual void createFrame(const geom::Envelope& env);
120 
121  virtual void initSubdiv();
122 
123 public:
129  inline double
130  getTolerance() const
131  {
132  return tolerance;
133  }
134 
140  inline const geom::Envelope&
141  getEnvelope() const
142  {
143  return frameEnv;
144  }
145 
152  inline std::deque<QuadEdgeQuartet>&
154  {
155  return quadEdges;
156  }
157 
165  inline void
166  setLocator(std::unique_ptr<QuadEdgeLocator> p_locator)
167  {
168  this->locator = std::move(p_locator);
169  }
170 
178  virtual QuadEdge& makeEdge(const Vertex& o, const Vertex& d);
179 
190  virtual QuadEdge& connect(QuadEdge& a, QuadEdge& b);
191 
198  void remove(QuadEdge& e);
199 
219  QuadEdge* locateFromEdge(const Vertex& v,
220  const QuadEdge& startEdge) const;
221 
232  inline QuadEdge*
233  locate(const Vertex& v) const
234  {
235  return locator->locate(v);
236  }
237 
248  inline QuadEdge*
250  {
251  return locator->locate(Vertex(p));
252  }
253 
265  QuadEdge* locate(const geom::Coordinate& p0, const geom::Coordinate& p1);
266 
282  QuadEdge& insertSite(const Vertex& v);
283 
290  bool isFrameEdge(const QuadEdge& e) const;
291 
300  bool isFrameBorderEdge(const QuadEdge& e) const;
301 
308  bool isFrameVertex(const Vertex& v) const;
309 
310 
319  bool isOnEdge(const QuadEdge& e, const geom::Coordinate& p) const;
320 
329  bool isVertexOfEdge(const QuadEdge& e, const Vertex& v) const;
330 
342  std::unique_ptr<QuadEdgeList> getPrimaryEdges(bool includeFrame);
343 
344  /*****************************************************************************
345  * Visitors
346  ****************************************************************************/
347 
348  void visitTriangles(TriangleVisitor* triVisitor, bool includeFrame);
349 
350 private:
351  typedef std::stack<QuadEdge*> QuadEdgeStack;
352  typedef std::vector<std::unique_ptr<geom::CoordinateSequence>> TriList;
353 
359  QuadEdge* triEdges[3];
360 
364  void prepareVisit();
365 
377  QuadEdge** fetchTriangleToVisit(QuadEdge* edge, QuadEdgeStack& edgeStack, bool includeFrame);
378 
385  void getTriangleCoordinates(TriList* triList, bool includeFrame);
386 
387 private:
388  class TriangleCoordinatesVisitor;
389  class TriangleCircumcentreVisitor;
390 
391 public:
400  std::unique_ptr<geom::MultiLineString> getEdges(const geom::GeometryFactory& geomFact);
401 
412  std::unique_ptr<geom::GeometryCollection> getTriangles(const geom::GeometryFactory& geomFact);
413 
426  std::unique_ptr<geom::GeometryCollection> getVoronoiDiagram(const geom::GeometryFactory& geomFact);
427 
439  std::unique_ptr<geom::MultiLineString> getVoronoiDiagramEdges(const geom::GeometryFactory& geomFact);
440 
452  std::vector<std::unique_ptr<geom::Geometry>> getVoronoiCellPolygons(const geom::GeometryFactory& geomFact);
453 
465  std::vector<std::unique_ptr<geom::Geometry>> getVoronoiCellEdges(const geom::GeometryFactory& geomFact);
466 
480  std::unique_ptr<QuadEdgeSubdivision::QuadEdgeList> getVertexUniqueEdges(bool includeFrame);
481 
493  std::unique_ptr<geom::Geometry> getVoronoiCellPolygon(const QuadEdge* qe, const geom::GeometryFactory& geomFact);
494 
506  std::unique_ptr<geom::Geometry> getVoronoiCellEdge(const QuadEdge* qe, const geom::GeometryFactory& geomFact);
507 
508 };
509 
510 } //namespace geos.triangulate.quadedge
511 } //namespace geos.triangulate
512 } //namespace goes
513 
514 #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:249
An interface for algorithms which process the triangles in a QuadEdgeSubdivision. ...
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:233
Models a site (node) in a QuadEdgeSubdivision.
Definition: Vertex.h:60
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:153
A class that contains the QuadEdges representing a planar subdivision that models a triangulation...
Definition: QuadEdgeSubdivision.h:80
Basic namespace for all GEOS functionalities.
Definition: IndexedNestedRingTester.h:26
void setLocator(std::unique_ptr< QuadEdgeLocator > p_locator)
Sets the QuadEdgeLocator to use for locating containing triangles in this subdivision.
Definition: QuadEdgeSubdivision.h:166
double getTolerance() const
Gets the vertex-equality tolerance value used in this subdivision.
Definition: QuadEdgeSubdivision.h:130
A class that represents the edge data structure which implements the quadedge algebra.
Definition: QuadEdge.h:54
const geom::Envelope & getEnvelope() const
Gets the envelope of the Subdivision (including the frame).
Definition: QuadEdgeSubdivision.h:141