QGIS API Documentation  3.10.0-A Coruña (6c816b4204)
DualEdgeTriangulation.h
Go to the documentation of this file.
1 /***************************************************************************
2  DualEdgeTriangulation.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 "Triangulation.h"
38 #include "HalfEdge.h"
39 
40 #define SIP_NO_FILE
41 
47 class ANALYSIS_EXPORT DualEdgeTriangulation: public Triangulation
48 {
49  public:
51  DualEdgeTriangulation( int nop, Triangulation *decorator );
52  ~DualEdgeTriangulation() override;
53  void setDecorator( Triangulation *d ) {mDecorator = d;}
54  void addLine( const QVector< QgsPoint > &points, QgsInterpolator::SourceType lineType ) override;
55  int addPoint( const QgsPoint &p ) override;
57  void performConsistencyTest() override;
59  bool calcNormal( double x, double y, Vector3D *result SIP_OUT ) override;
60  bool calcPoint( double x, double y, QgsPoint &result SIP_OUT ) override;
62  //virtual void draw(QPainter* p, double xlowleft, double ylowleft, double xupright, double yupright, double width, double height) const;
64  QgsPoint *getPoint( int i ) const override;
65  int getOppositePoint( int p1, int p2 ) override;
66  bool getTriangle( 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 ) SIP_PYNAME( getTriangleVertices ) override;
67  bool getTriangle( double x, double y, QgsPoint &p1 SIP_OUT, QgsPoint &p2 SIP_OUT, QgsPoint &p3 SIP_OUT ) override;
68  QList<int> getSurroundingTriangles( int pointno ) override;
70  double getXMax() const override { return xMax; }
72  double getXMin() const override { return xMin; }
74  double getYMax() const override { return yMax; }
76  double getYMin() const override { return yMin; }
78  int getNumberOfPoints() const override;
82  void setEdgeColor( int r, int g, int b ) override;
84  void setForcedEdgeColor( int r, int g, int b ) override;
86  void setBreakEdgeColor( int r, int g, int b ) override;
88  void setTriangleInterpolator( TriangleInterpolator *interpolator ) override;
90  void eliminateHorizontalTriangles() override;
92  void ruppertRefinement() override;
94  bool pointInside( double x, double y ) override;
96  //bool readFromTAFF(QString fileName);
98  //bool saveToTAFF(QString fileName) const;
100  bool swapEdge( double x, double y ) override;
102  QList<int> *getPointsAroundEdge( double x, double y ) override;
103 
104  bool saveTriangulation( QgsFeatureSink *sink, QgsFeedback *feedback = nullptr ) const override;
105 
106  protected:
108  double xMax = 0;
110  double xMin = 0;
112  double yMax = 0;
114  double yMin = 0;
116  static const unsigned int DEFAULT_STORAGE_FOR_POINTS = 100000;
118  QVector<QgsPoint *> mPointVector;
120  static const unsigned int DEFAULT_STORAGE_FOR_HALF_EDGES = 300006;
122  QVector<HalfEdge *> mHalfEdge;
124  TriangleInterpolator *mTriangleInterpolator = nullptr;
128  QColor mEdgeColor;
134  Triangulation *mDecorator = nullptr;
136  unsigned int insertEdge( int dual, int next, int point, bool mbreak, bool forced );
138  int insertForcedSegment( int p1, int p2, QgsInterpolator::SourceType segmentType );
140  //const static double leftOfTresh=0.00001;
142  static const int MAX_BASE_ITERATIONS = 300000;
144  int baseEdgeOfPoint( int point );
146  int baseEdgeOfTriangle( const QgsPoint &point );
148  bool checkSwap( unsigned int edge, unsigned int recursiveDeep );
150  void doSwap( unsigned int edge, unsigned int recursiveDeep );
152  void doOnlySwap( unsigned int edge );
154  unsigned int mEdgeInside = 0;
156  unsigned int mEdgeOutside = 0;
158  unsigned int mEdgeWithPoint = 0;
160  unsigned int mUnstableEdge = 0;
162  int mTwiceInsPoint = 0;
164  bool swapPossible( unsigned int edge );
166  void triangulatePolygon( QList<int> *poly, QList<int> *free, int mainedge );
168  bool halfEdgeBBoxTest( int edge, double xlowleft, double ylowleft, double xupright, double yupright ) const;
170  double swapMinAngle( int edge ) const;
172  int splitHalfEdge( int edge, float position );
174  bool edgeOnConvexHull( int edge );
176  void evaluateInfluenceRegion( QgsPoint *point, int edge, QSet<int> &set );
177 
178  friend class TestQgsInterpolator;
179 };
180 
181 #ifndef SIP_RUN
182 
184  : mEdgeColor( 0, 255, 0 )
185  , mForcedEdgeColor( 0, 0, 255 )
186  , mBreakEdgeColor( 100, 100, 0 )
187  , mDecorator( this )
188 {
191 }
192 
194  : mEdgeColor( 0, 255, 0 )
195  , mForcedEdgeColor( 0, 0, 255 )
196  , mBreakEdgeColor( 100, 100, 0 )
197  , mDecorator( decorator ? decorator : this )
198 {
199  mPointVector.reserve( nop );
200  mHalfEdge.reserve( nop );
201 }
202 
204 {
205  return mPointVector.count();
206 }
207 
209 {
210  if ( i < 0 || i >= mPointVector.count() )
211  return nullptr;
212 
213  return mPointVector.at( i );
214 }
215 
216 inline bool DualEdgeTriangulation::halfEdgeBBoxTest( int edge, double xlowleft, double ylowleft, double xupright, double yupright ) const
217 {
218  return (
219  ( getPoint( mHalfEdge[edge]->getPoint() )->x() >= xlowleft &&
220  getPoint( mHalfEdge[edge]->getPoint() )->x() <= xupright &&
221  getPoint( mHalfEdge[edge]->getPoint() )->y() >= ylowleft &&
222  getPoint( mHalfEdge[edge]->getPoint() )->y() <= yupright ) ||
223  ( getPoint( mHalfEdge[mHalfEdge[edge]->getDual()]->getPoint() )->x() >= xlowleft &&
224  getPoint( mHalfEdge[mHalfEdge[edge]->getDual()]->getPoint() )->x() <= xupright &&
225  getPoint( mHalfEdge[mHalfEdge[edge]->getDual()]->getPoint() )->y() >= ylowleft &&
226  getPoint( mHalfEdge[mHalfEdge[edge]->getDual()]->getPoint() )->y() <= yupright )
227  );
228 }
229 
230 #endif
231 #endif
232 
233 
234 
Triangulation * mDecorator
Pointer to the decorator using this triangulation. It it is used directly, mDecorator equals this...
static const unsigned int DEFAULT_STORAGE_FOR_HALF_EDGES
Default value for the number of storable HalfEdges at the beginning.
virtual bool swapEdge(double x, double y)=0
Reads the content of a taff-file.
virtual void setBreakEdgeColor(int r, int g, int b)=0
Sets the color of the breaklines.
The status of the first inserted forced line is reset to that of a normal edge (so that the second in...
Definition: Triangulation.h:45
virtual void setEdgeColor(int r, int g, int b)=0
Sets the color of the normal edges.
An interface for objects which accept features via addFeature(s) methods.
QgsPoint * getPoint(int i) const override
Draws the points, edges and the forced lines.
bool halfEdgeBBoxTest(int edge, double xlowleft, double ylowleft, double xupright, double yupright) const
Tests, if the bounding box of the halfedge with index i intersects the specified bounding box...
int getNumberOfPoints() const override
Returns the number of points.
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)
SourceType
Describes the type of input data.
DualEdgeTriangulation is an implementation of a triangulation class based on the dual edge data struc...
QVector< HalfEdge * > mHalfEdge
Stores pointers to the HalfEdges.
Base class for feedback objects to be used for cancellation of something running in a worker thread...
Definition: qgsfeedback.h:44
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...
virtual QgsPoint * getPoint(int i) const =0
Returns a pointer to the point with number i. Any virtual points must have the number -1...
Class Vector3D represents a 3D-Vector, capable to store x-,y- and z-coordinates in double values...
Definition: Vector3D.h:33
virtual bool saveTriangulation(QgsFeatureSink *sink, QgsFeedback *feedback=nullptr) const =0
Saves the triangulation features to a feature sink.
This is an interface for interpolator classes for triangulations.
double getXMax() const override
Returns the largest x-coordinate value of the bounding box.
void setDecorator(Triangulation *d)
QColor mForcedEdgeColor
Color to paint the forced edges.
virtual int getNumberOfPoints() const =0
Returns the number of points.
virtual void setForcedEdgeColor(int r, int g, int b)=0
Sets the color of the forced edges.
virtual bool getTriangle(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...
Interface for Triangulation classes.
Definition: Triangulation.h:38
QColor mBreakEdgeColor
Color to paint the breaklines.
Point geometry type, with support for z-dimension and m-values.
Definition: qgspoint.h:37
double getXMin() const override
Returns the smallest x-coordinate value of the bounding box.
virtual int addPoint(const QgsPoint &point)=0
Adds a point to the triangulation.
virtual bool calcNormal(double x, double y, Vector3D *result)=0
Calculates the normal at a point on the surface and assigns it to &#39;result&#39;.
virtual QList< int > getSurroundingTriangles(int pointno)=0
Returns a pointer to a value list with the information of the triangles surrounding (counterclockwise...
virtual QList< int > * getPointsAroundEdge(double x, double y)=0
Returns a value list with the numbers of the four points, which would be affected by an edge swap...
#define SIP_OUT
Definition: qgis_sip.h:58
double getYMin() const override
Returns the smallest x-coordinate value of the bounding box.
virtual void setForcedCrossBehavior(Triangulation::ForcedCrossBehavior b)=0
Draws the points, edges and the forced lines.
QVector< QgsPoint * > mPointVector
Stores pointers to all points in the triangulations (including the points contained in the lines) ...
static const unsigned int DEFAULT_STORAGE_FOR_POINTS
Default value for the number of storable points at the beginning.
double getYMax() const override
Returns the largest y-coordinate value of the bounding box.
virtual void addLine(const QVector< QgsPoint > &points, QgsInterpolator::SourceType lineType)=0
Adds a line (e.g.
virtual void eliminateHorizontalTriangles()=0
Eliminates the horizontal triangles by swapping.
QColor mEdgeColor
Color to paint the normal edges.
virtual int getOppositePoint(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...
ForcedCrossBehavior
Enumeration describing the behavior, if two forced lines cross.
Definition: Triangulation.h:42
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 &#39;result&#39;.
#define SIP_PYNAME(name)
Definition: qgis_sip.h:81
virtual void setTriangleInterpolator(TriangleInterpolator *interpolator)=0
Sets an interpolator object.