QGIS API Documentation  3.21.0-Master (56b4176581)
qgsdualedgetriangulation.h
Go to the documentation of this file.
1 /**************************************************************************
2  QgsDualEdgeTriangulation.h - description
3  -------------------
4  copyright : (C) 2004 by Marco Hugentobler
5  email : [email protected]
6  ***************************************************************************/
7 
8 /***************************************************************************
9  * *
10  * This program is free software; you can redistribute it and/or modify *
11  * it under the terms of the GNU General Public License as published by *
12  * the Free Software Foundation; either version 2 of the License, or *
13  * (at your option) any later version. *
14  * *
15  ***************************************************************************/
16 
17 #ifndef DUALEDGETRIANGULATION_H
18 #define DUALEDGETRIANGULATION_H
19 
20 #include <QVector>
21 #include <QList>
22 #include <QSet>
23 #include <QColor>
24 #include <QFile>
25 #include <QTextStream>
26 #include <QMessageBox>
27 #include <QBuffer>
28 #include <QStringList>
29 #include <QCursor>
30 
31 #include <cfloat>
32 
33 #include "qgis_sip.h"
34 #include "qgis_analysis.h"
35 #include "qgspoint.h"
36 
37 #include "qgstriangulation.h"
38 #include "HalfEdge.h"
39 
40 #define SIP_NO_FILE
41 
49 class ANALYSIS_EXPORT QgsDualEdgeTriangulation: public QgsTriangulation
50 {
51  public:
54  QgsDualEdgeTriangulation( int nop );
55  ~QgsDualEdgeTriangulation() override;
56  void addLine( const QVector< QgsPoint > &points, QgsInterpolator::SourceType lineType ) override;
57  int addPoint( const QgsPoint &p ) override;
59  void performConsistencyTest() override;
61  bool calcNormal( double x, double y, QgsPoint &result SIP_OUT ) override;
62  bool calcPoint( double x, double y, QgsPoint &result SIP_OUT ) override;
64  //virtual void draw(QPainter* p, double xlowleft, double ylowleft, double xupright, double yupright, double width, double height) const;
66  QgsPoint *point( int i ) const override;
67  int oppositePoint( int p1, int p2 ) override;
68  bool triangleVertices( double x, double y, QgsPoint &p1 SIP_OUT, int &n1 SIP_OUT, QgsPoint &p2 SIP_OUT, int &n2 SIP_OUT, QgsPoint &p3 SIP_OUT, int &n3 SIP_OUT ) override;
69  bool triangleVertices( double x, double y, QgsPoint &p1 SIP_OUT, QgsPoint &p2 SIP_OUT, QgsPoint &p3 SIP_OUT ) override;
70  QList<int> surroundingTriangles( int pointno ) override;
72  double xMax() const override { return mXMax; }
74  double xMin() const override { return mXMin; }
76  double yMax() const override { return mYMax; }
78  double yMin() const override { return mYMin; }
80  int pointsCount() const override;
84  void setTriangleInterpolator( TriangleInterpolator *interpolator ) override;
86  void eliminateHorizontalTriangles() override;
88  void ruppertRefinement() override;
90  bool pointInside( double x, double y ) override;
92  bool swapEdge( double x, double y ) override;
94  QList<int> pointsAroundEdge( double x, double y ) override;
95 
96  bool saveTriangulation( QgsFeatureSink *sink, QgsFeedback *feedback = nullptr ) const override;
97 
98  virtual QgsMesh triangulationToMesh( QgsFeedback *feedback = nullptr ) const override;
99 
100  private:
102  double mXMax = 0;
104  double mXMin = 0;
106  double mYMax = 0;
108  double mYMin = 0;
110  static const unsigned int DEFAULT_STORAGE_FOR_POINTS = 100000;
112  QVector<QgsPoint *> mPointVector;
114  static const unsigned int DEFAULT_STORAGE_FOR_HALF_EDGES = 300006;
116  QVector<HalfEdge *> mHalfEdge;
118  TriangleInterpolator *mTriangleInterpolator = nullptr;
122  unsigned int insertEdge( int dual, int next, int point, bool mbreak, bool forced );
124  int insertForcedSegment( int p1, int p2, QgsInterpolator::SourceType segmentType );
126  static const int MAX_BASE_ITERATIONS = 300000;
128  int baseEdgeOfPoint( int point );
129 
137  int baseEdgeOfTriangle( const QgsPoint &point );
139  bool checkSwapRecursively( unsigned int edge, unsigned int recursiveDeep );
141  bool isEdgeNeedSwap( unsigned int edge ) const;
143  void doSwapRecursively( unsigned int edge, unsigned int recursiveDeep );
145  void doOnlySwap( unsigned int edge );
147  unsigned int mEdgeInside = 0;
149  int mEdgeOutside = -1;
151  unsigned int mEdgeWithPoint = 0;
153  unsigned int mUnstableEdge = 0;
155  int mTwiceInsPoint = 0;
157  bool swapPossible( unsigned int edge ) const;
159  void triangulatePolygon( QList<int> *poly, QList<int> *free, int mainedge );
161  bool halfEdgeBBoxTest( int edge, double xlowleft, double ylowleft, double xupright, double yupright ) const;
163  double swapMinAngle( int edge ) const;
165  int splitHalfEdge( int edge, float position );
167  bool edgeOnConvexHull( int edge );
169  void evaluateInfluenceRegion( QgsPoint *point, int edge, QSet<int> &set );
171  int mDimension = -1;
172 
173  int firstEdgeOutSide();
174 
175  void removeLastPoint();
176 
177 
178  friend class TestQgsInterpolator;
179 };
180 
181 #ifndef SIP_RUN
182 
184 {
185  mPointVector.reserve( DEFAULT_STORAGE_FOR_POINTS );
186  mHalfEdge.reserve( DEFAULT_STORAGE_FOR_HALF_EDGES );
187 }
188 
190 {
191  mPointVector.reserve( nop );
192  mHalfEdge.reserve( nop );
193 }
194 
196 {
197  return mPointVector.count();
198 }
199 
201 {
202  if ( i < 0 || i >= mPointVector.count() )
203  return nullptr;
204 
205  return mPointVector.at( i );
206 }
207 
208 inline bool QgsDualEdgeTriangulation::halfEdgeBBoxTest( int edge, double xlowleft, double ylowleft, double xupright, double yupright ) const
209 {
210  return (
211  ( point( mHalfEdge[edge]->getPoint() )->x() >= xlowleft &&
212  point( mHalfEdge[edge]->getPoint() )->x() <= xupright &&
213  point( mHalfEdge[edge]->getPoint() )->y() >= ylowleft &&
214  point( mHalfEdge[edge]->getPoint() )->y() <= yupright ) ||
215  ( point( mHalfEdge[mHalfEdge[edge]->getDual()]->getPoint() )->x() >= xlowleft &&
216  point( mHalfEdge[mHalfEdge[edge]->getDual()]->getPoint() )->x() <= xupright &&
217  point( mHalfEdge[mHalfEdge[edge]->getDual()]->getPoint() )->y() >= ylowleft &&
218  point( mHalfEdge[mHalfEdge[edge]->getDual()]->getPoint() )->y() <= yupright )
219  );
220 }
221 
222 #endif
223 #endif
224 
225 
226 
DualEdgeTriangulation is an implementation of a triangulation class based on the dual edge data struc...
QgsPoint * point(int i) const override
Draws the points, edges and the forced lines.
double yMax() const override
Returns the largest y-coordinate value of the bounding box.
int pointsCount() const override
Returns the number of points.
double xMax() const override
Returns the largest x-coordinate value of the bounding box.
double xMin() const override
Returns the smallest x-coordinate value of the bounding box.
double yMin() const override
Returns the smallest x-coordinate value of the bounding box.
An interface for objects which accept features via addFeature(s) methods.
Base class for feedback objects to be used for cancellation of something running in a worker thread.
Definition: qgsfeedback.h:45
SourceType
Describes the type of input data.
Point geometry type, with support for z-dimension and m-values.
Definition: qgspoint.h:49
Interface for Triangulation classes.
virtual QgsPoint * point(int i) const =0
Returns a pointer to the point with number i.
virtual bool calcNormal(double x, double y, QgsPoint &result)=0
Calculates the normal at a point on the surface and assigns it to 'result'.
virtual QgsMesh triangulationToMesh(QgsFeedback *feedback=nullptr) const =0
Returns a QgsMesh corresponding to the triangulation.
virtual void eliminateHorizontalTriangles()=0
Eliminates the horizontal triangles by swapping.
virtual void performConsistencyTest()=0
Performs a consistency check, remove this later.
virtual void ruppertRefinement()=0
Adds points to make the triangles better shaped (algorithm of ruppert)
virtual int pointsCount() const =0
Returns the number of points.
virtual QList< int > surroundingTriangles(int pointno)=0
Returns a value list with the information of the triangles surrounding (counterclockwise) a point.
ForcedCrossBehavior
Enumeration describing the behavior, if two forced lines cross.
@ DeleteFirst
The status of the first inserted forced line is reset to that of a normal edge (so that the second in...
virtual bool saveTriangulation(QgsFeatureSink *sink, QgsFeedback *feedback=nullptr) const =0
Saves the triangulation features to a feature sink.
virtual void addLine(const QgsPointSequence &points, QgsInterpolator::SourceType lineType)=0
Adds a line (e.g.
virtual bool calcPoint(double x, double y, QgsPoint &result)=0
Calculates x-, y and z-value of the point on the surface and assigns it to 'result'.
virtual int oppositePoint(int p1, int p2)=0
Returns the number of the point opposite to the triangle points p1, p2 (which have to be on a halfedg...
virtual int addPoint(const QgsPoint &point)=0
Adds a point to the triangulation.
virtual bool swapEdge(double x, double y)=0
Reads the content of a taff-file.
virtual QList< int > pointsAroundEdge(double x, double y)=0
Returns a value list with the numbers of the four points, which would be affected by an edge swap.
virtual void setTriangleInterpolator(TriangleInterpolator *interpolator)=0
Sets an interpolator object.
virtual bool triangleVertices(double x, double y, QgsPoint &p1, int &n1, QgsPoint &p2, int &n2, QgsPoint &p3, int &n3)=0
Finds out in which triangle the point with coordinates x and y is and assigns the numbers of the vert...
virtual void setForcedCrossBehavior(QgsTriangulation::ForcedCrossBehavior b)=0
Draws the points, edges and the forced lines.
virtual bool pointInside(double x, double y)=0
Returns true, if the point with coordinates x and y is inside the convex hull and false otherwise.
This is an interface for interpolator classes for triangulations.
#define SIP_OUT
Definition: qgis_sip.h:58
Mesh - vertices, edges and faces.