GEOS  3.12.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 #pragma once
21 
22 #include <memory>
23 #include <list>
24 #include <stack>
25 #include <unordered_set>
26 #include <array>
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 
55 //-- Frame size factor for initializing subdivision frame. Larger is more robust
56 const double FRAME_SIZE_FACTOR = 100;
57 
83 class GEOS_DLL QuadEdgeSubdivision {
84 public:
85  typedef std::vector<QuadEdge*> QuadEdgeList;
86 
95  static void getTriangleEdges(const QuadEdge& startQE,
96  const QuadEdge* triEdge[3]);
97 
98 private:
103  std::deque<QuadEdgeQuartet> quadEdges;
104  std::array<QuadEdge*, 3> startingEdges;
105  double tolerance;
106  double edgeCoincidenceTolerance;
107  std::array<Vertex, 3> frameVertex;
108  geom::Envelope frameEnv;
109  std::unique_ptr<QuadEdgeLocator> locator;
110  bool visit_state_clean;
111 
112 public:
121  QuadEdgeSubdivision(const geom::Envelope& env, double tolerance);
122 
123  virtual ~QuadEdgeSubdivision() = default;
124 
125 private:
126  virtual void createFrame(const geom::Envelope& env);
127 
128  virtual void initSubdiv();
129 
130 public:
136  inline double
137  getTolerance() const
138  {
139  return tolerance;
140  }
141 
147  inline const geom::Envelope&
148  getEnvelope() const
149  {
150  return frameEnv;
151  }
152 
159  inline std::deque<QuadEdgeQuartet>&
161  {
162  return quadEdges;
163  }
164 
172  inline void
173  setLocator(std::unique_ptr<QuadEdgeLocator> p_locator)
174  {
175  this->locator = std::move(p_locator);
176  }
177 
185  virtual QuadEdge& makeEdge(const Vertex& o, const Vertex& d);
186 
197  virtual QuadEdge& connect(QuadEdge& a, QuadEdge& b);
198 
205  void remove(QuadEdge& e);
206 
226  QuadEdge* locateFromEdge(const Vertex& v,
227  const QuadEdge& startEdge) const;
228 
239  inline QuadEdge*
240  locate(const Vertex& v) const
241  {
242  return locator->locate(v);
243  }
244 
255  inline QuadEdge*
257  {
258  return locator->locate(Vertex(p));
259  }
260 
272  QuadEdge* locate(const geom::Coordinate& p0, const geom::Coordinate& p1);
273 
289  QuadEdge& insertSite(const Vertex& v);
290 
297  bool isFrameEdge(const QuadEdge& e) const;
298 
307  bool isFrameBorderEdge(const QuadEdge& e) const;
308 
315  bool isFrameVertex(const Vertex& v) const;
316 
317 
326  bool isOnEdge(const QuadEdge& e, const geom::Coordinate& p) const;
327 
336  bool isVertexOfEdge(const QuadEdge& e, const Vertex& v) const;
337 
349  std::unique_ptr<QuadEdgeList> getPrimaryEdges(bool includeFrame);
350 
351  /*****************************************************************************
352  * Visitors
353  ****************************************************************************/
354 
355  void visitTriangles(TriangleVisitor* triVisitor, bool includeFrame);
356 
357 private:
358  typedef std::stack<QuadEdge*> QuadEdgeStack;
359  typedef std::vector<std::unique_ptr<geom::CoordinateSequence>> TriList;
360 
366  std::array<QuadEdge*, 3> m_triEdges;
367 
371  void prepareVisit();
372 
384  std::array<QuadEdge*, 3>* fetchTriangleToVisit(QuadEdge* edge, QuadEdgeStack& edgeStack, bool includeFrame);
385 
392  void getTriangleCoordinates(TriList* triList, bool includeFrame);
393 
394 private:
395  class TriangleCoordinatesVisitor;
396  class TriangleCircumcentreVisitor;
397 
398 public:
407  std::unique_ptr<geom::MultiLineString> getEdges(const geom::GeometryFactory& geomFact);
408 
419  std::unique_ptr<geom::GeometryCollection> getTriangles(const geom::GeometryFactory& geomFact);
420 
433  std::unique_ptr<geom::GeometryCollection> getVoronoiDiagram(const geom::GeometryFactory& geomFact);
434 
446  std::unique_ptr<geom::MultiLineString> getVoronoiDiagramEdges(const geom::GeometryFactory& geomFact);
447 
459  std::vector<std::unique_ptr<geom::Geometry>> getVoronoiCellPolygons(const geom::GeometryFactory& geomFact);
460 
472  std::vector<std::unique_ptr<geom::Geometry>> getVoronoiCellEdges(const geom::GeometryFactory& geomFact);
473 
487  std::unique_ptr<QuadEdgeSubdivision::QuadEdgeList> getVertexUniqueEdges(bool includeFrame);
488 
500  std::unique_ptr<geom::Geometry> getVoronoiCellPolygon(const QuadEdge* qe, const geom::GeometryFactory& geomFact);
501 
513  std::unique_ptr<geom::Geometry> getVoronoiCellEdge(const QuadEdge* qe, const geom::GeometryFactory& geomFact);
514 
515 };
516 
517 } //namespace geos.triangulate.quadedge
518 } //namespace geos.triangulate
519 } //namespace goes
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:256
An interface for algorithms which process the triangles in a QuadEdgeSubdivision. ...
Definition: TriangleVisitor.h:33
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:240
Coordinate is the lightweight class used to store coordinates.
Definition: Coordinate.h:216
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:65
std::deque< QuadEdgeQuartet > & getEdges()
Gets the collection of base QuadEdges (one for every pair of vertices which is connected).
Definition: QuadEdgeSubdivision.h:160
A class that contains the QuadEdges representing a planar subdivision that models a triangulation...
Definition: QuadEdgeSubdivision.h:83
Basic namespace for all GEOS functionalities.
Definition: Angle.h:25
const geom::Envelope & getEnvelope() const
Gets the envelope of the Subdivision (including the frame).
Definition: QuadEdgeSubdivision.h:148
void setLocator(std::unique_ptr< QuadEdgeLocator > p_locator)
Sets the QuadEdgeLocator to use for locating containing triangles in this subdivision.
Definition: QuadEdgeSubdivision.h:173
A class that represents the edge data structure which implements the quadedge algebra.
Definition: QuadEdge.h:53
double getTolerance() const
Gets the vertex-equality tolerance value used in this subdivision.
Definition: QuadEdgeSubdivision.h:137