QGIS API Documentation  2.99.0-Master (ae4d26a)
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 "Triangulation.h"
21 #include "qgis_sip.h"
22 #include "HalfEdge.h"
23 #include <QVector>
24 #include <QList>
25 #include <QSet>
26 #include <QColor>
27 #include <QFile>
28 #include <QTextStream>
29 #include <QMessageBox>
30 #include <cfloat>
31 #include <QBuffer>
32 #include <QStringList>
33 #include <QCursor>
34 #include "qgis_analysis.h"
35 
36 #define SIP_NO_FILE
37 
43 class ANALYSIS_EXPORT DualEdgeTriangulation: public Triangulation
44 {
45  public:
47  DualEdgeTriangulation( int nop, Triangulation *decorator );
48  virtual ~DualEdgeTriangulation();
49  void setDecorator( Triangulation *d ) {mDecorator = d;}
51  void addLine( Line3D *line SIP_TRANSFER, bool breakline ) override;
53  int addPoint( QgsPoint *p SIP_TRANSFER ) override;
55  virtual void performConsistencyTest() override;
57  virtual bool calcNormal( double x, double y, Vector3D *result SIP_OUT ) override;
59  virtual bool calcPoint( double x, double y, QgsPoint *result SIP_OUT ) override;
61  //virtual void draw(QPainter* p, double xlowleft, double ylowleft, double xupright, double yupright, double width, double height) const;
63  virtual QgsPoint *getPoint( unsigned int i ) const override;
65  int getOppositePoint( int p1, int p2 ) override;
67  virtual 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;
69  virtual bool getTriangle( double x, double y, QgsPoint *p1 SIP_OUT, QgsPoint *p2 SIP_OUT, QgsPoint *p3 SIP_OUT ) override;
71  QList<int> *getSurroundingTriangles( int pointno ) override;
73  virtual double getXMax() const override { return xMax; }
75  virtual double getXMin() const override { return xMin; }
77  virtual double getYMax() const override { return yMax; }
79  virtual double getYMin() const override { return yMin; }
81  virtual int getNumberOfPoints() const override;
85  virtual void setEdgeColor( int r, int g, int b ) override;
87  virtual void setForcedEdgeColor( int r, int g, int b ) override;
89  virtual void setBreakEdgeColor( int r, int g, int b ) override;
91  void setTriangleInterpolator( TriangleInterpolator *interpolator ) override;
93  void eliminateHorizontalTriangles() override;
95  virtual void ruppertRefinement() override;
97  bool pointInside( double x, double y ) override;
99  //bool readFromTAFF(QString fileName);
101  //bool saveToTAFF(QString fileName) const;
103  virtual bool swapEdge( double x, double y ) override;
105  virtual QList<int> *getPointsAroundEdge( double x, double y ) override;
106 
107  virtual bool saveTriangulation( QgsFeatureSink *sink, QgsFeedback *feedback = nullptr ) const override;
108 
109  protected:
111  double xMax = 0;
113  double xMin = 0;
115  double yMax = 0;
117  double yMin = 0;
119  static const unsigned int DEFAULT_STORAGE_FOR_POINTS = 100000;
121  QVector<QgsPoint *> mPointVector;
123  static const unsigned int DEFAULT_STORAGE_FOR_HALF_EDGES = 300006;
125  QVector<HalfEdge *> mHalfEdge;
127  TriangleInterpolator *mTriangleInterpolator = nullptr;
131  QColor mEdgeColor;
137  Triangulation *mDecorator = nullptr;
139  unsigned int insertEdge( int dual, int next, int point, bool mbreak, bool forced );
141  int insertForcedSegment( int p1, int p2, bool breakline );
143  //const static double leftOfTresh=0.00001;
145  static const int MAX_BASE_ITERATIONS = 300000;
147  int baseEdgeOfPoint( int point );
149  int baseEdgeOfTriangle( QgsPoint *point );
151  bool checkSwap( unsigned int edge, unsigned int recursiveDeep );
153  void doSwap( unsigned int edge, unsigned int recursiveDeep );
155  void doOnlySwap( unsigned int edge );
157  unsigned int mEdgeInside = 0;
159  unsigned int mEdgeOutside = 0;
161  unsigned int mEdgeWithPoint = 0;
163  unsigned int mUnstableEdge = 0;
165  int mTwiceInsPoint = 0;
167  bool swapPossible( unsigned int edge );
169  void triangulatePolygon( QList<int> *poly, QList<int> *free, int mainedge );
171  bool halfEdgeBBoxTest( int edge, double xlowleft, double ylowleft, double xupright, double yupright ) const;
173  double swapMinAngle( int edge ) const;
175  int splitHalfEdge( int edge, float position );
177  bool edgeOnConvexHull( int edge );
179  void evaluateInfluenceRegion( QgsPoint *point, int edge, QSet<int> &set );
180 };
181 
182 #ifndef SIP_RUN
183 
185  : mEdgeColor( 0, 255, 0 )
186  , mForcedEdgeColor( 0, 0, 255 )
187  , mBreakEdgeColor( 100, 100, 0 )
188  , mDecorator( this )
189 {
192 }
193 
195  : mEdgeColor( 0, 255, 0 )
196  , mForcedEdgeColor( 0, 0, 255 )
197  , mBreakEdgeColor( 100, 100, 0 )
198  , mDecorator( decorator ? decorator : this )
199 {
200  mPointVector.reserve( nop );
201  mHalfEdge.reserve( nop );
202 }
203 
205 {
206  return mPointVector.count();
207 }
208 
209 inline QgsPoint *DualEdgeTriangulation::getPoint( unsigned int i ) const
210 {
211  return mPointVector.at( i );
212 }
213 
214 inline bool DualEdgeTriangulation::halfEdgeBBoxTest( int edge, double xlowleft, double ylowleft, double xupright, double yupright ) const
215 {
216  return (
217  ( getPoint( mHalfEdge[edge]->getPoint() )->x() >= xlowleft &&
218  getPoint( mHalfEdge[edge]->getPoint() )->x() <= xupright &&
219  getPoint( mHalfEdge[edge]->getPoint() )->y() >= ylowleft &&
220  getPoint( mHalfEdge[edge]->getPoint() )->y() <= yupright ) ||
221  ( getPoint( mHalfEdge[mHalfEdge[edge]->getDual()]->getPoint() )->x() >= xlowleft &&
222  getPoint( mHalfEdge[mHalfEdge[edge]->getDual()]->getPoint() )->x() <= xupright &&
223  getPoint( mHalfEdge[mHalfEdge[edge]->getDual()]->getPoint() )->y() >= ylowleft &&
224  getPoint( mHalfEdge[mHalfEdge[edge]->getDual()]->getPoint() )->y() <= yupright )
225  );
226 }
227 
228 #endif
229 #endif
230 
231 
232 
Triangulation * mDecorator
Pointer to the decorator using this triangulation. It it is used directly, mDecorator equals this...
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;.
static const unsigned int DEFAULT_STORAGE_FOR_HALF_EDGES
Default value for the number of storable HalfEdges at the beginning.
virtual int addPoint(QgsPoint *p)=0
Adds a point to the triangulation Ownership is transferred to this class.
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.
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...
virtual int getNumberOfPoints() const override
Returns the number of points.
virtual void performConsistencyTest()=0
Performs a consistency check, remove this later.
virtual QgsPoint * getPoint(unsigned int i) const =0
Returns a pointer to the point with number i. Any virtual points must have the number -1...
virtual void ruppertRefinement()=0
Adds points to make the triangles better shaped (algorithm of ruppert)
This class represents a line.
Definition: Line3D.h:31
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 cancelation 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...
Class Vector3D represents a 3D-Vector, capable to store x-,y- and z-coordinates in double values...
Definition: Vector3D.h:33
virtual double getYMax() const override
Returns the largest y-coordinate value of the bounding box.
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.
void setDecorator(Triangulation *d)
virtual QList< int > * getSurroundingTriangles(int pointno)=0
Returns a pointer to a value list with the information of the triangles surrounding (counterclockwise...
QColor mForcedEdgeColor
Color to paint the forced edges.
#define SIP_TRANSFER
Definition: qgis_sip.h:36
virtual double getYMin() const override
Returns the smallest x-coordinate value of the bounding box.
virtual double getXMax() const override
Returns the largest x-coordinate value of the bounding box.
virtual int getNumberOfPoints() const =0
Returns the number of points.
virtual void addLine(Line3D *line, bool breakline)=0
Adds a line (e.g.
virtual void setForcedEdgeColor(int r, int g, int b)=0
Sets the color of the forced edges.
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
virtual double getXMin() const override
Returns the smallest x-coordinate value of the bounding box.
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 > * 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:51
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.
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...
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 QgsPoint * getPoint(unsigned int i) const override
Draws the points, edges and the forced lines.
#define SIP_PYNAME(name)
Definition: qgis_sip.h:74
virtual void setTriangleInterpolator(TriangleInterpolator *interpolator)=0
Sets an interpolator object.