QGIS API Documentation  2.99.0-Master (d55fa22)
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 <QProgressDialog>
34 #include <QCursor>
35 #include "qgis_analysis.h"
36 
39 class ANALYSIS_EXPORT DualEdgeTriangulation: public Triangulation
40 {
41  public:
43  DualEdgeTriangulation( int nop, Triangulation *decorator );
44  virtual ~DualEdgeTriangulation();
45  void setDecorator( Triangulation *d ) {mDecorator = d;}
47  void addLine( Line3D *line, bool breakline ) override;
49  int addPoint( Point3D *p ) override;
51  virtual void performConsistencyTest() override;
53  virtual bool calcNormal( double x, double y, Vector3D *result ) override;
55  virtual bool calcPoint( double x, double y, Point3D *result ) override;
57  //virtual void draw(QPainter* p, double xlowleft, double ylowleft, double xupright, double yupright, double width, double height) const;
59  virtual Point3D *getPoint( unsigned int i ) const override;
61  int getOppositePoint( int p1, int p2 ) override;
64  virtual bool getTriangle( double x, double y, Point3D *p1, int *n1, Point3D *p2, int *n2, Point3D *p3, int *n3 ) override SIP_SKIP;
66  virtual bool getTriangle( double x, double y, Point3D *p1, Point3D *p2, Point3D *p3 ) override;
68  QList<int> *getSurroundingTriangles( int pointno ) override;
70  virtual double getXMax() const override { return xMax; }
72  virtual double getXMin() const override { return xMin; }
74  virtual double getYMax() const override { return yMax; }
76  virtual double getYMin() const override { return yMin; }
78  virtual int getNumberOfPoints() const override;
82  virtual void setEdgeColor( int r, int g, int b ) override;
84  virtual void setForcedEdgeColor( int r, int g, int b ) override;
86  virtual void setBreakEdgeColor( int r, int g, int b ) override;
88  void setTriangleInterpolator( TriangleInterpolator *interpolator ) override;
90  void eliminateHorizontalTriangles() override;
92  virtual void ruppertRefinement() override;
94  bool pointInside( double x, double y ) override;
96  //bool readFromTAFF(QString fileName);
98  //bool saveToTAFF(QString fileName) const;
100  virtual bool swapEdge( double x, double y ) override;
102  virtual QList<int> *getPointsAroundEdge( double x, double y ) override;
103 
106  virtual bool saveAsShapefile( const QString &fileName ) const override;
107 
108  protected:
110  double xMax;
112  double xMin;
114  double yMax;
116  double yMin;
118  static const unsigned int DEFAULT_STORAGE_FOR_POINTS = 100000;
120  QVector<Point3D *> mPointVector;
122  static const unsigned int DEFAULT_STORAGE_FOR_HALF_EDGES = 300006;
124  QVector<HalfEdge *> mHalfEdge;
126  TriangleInterpolator *mTriangleInterpolator = nullptr;
130  QColor mEdgeColor;
136  Triangulation *mDecorator = nullptr;
138  unsigned int insertEdge( int dual, int next, int point, bool mbreak, bool forced );
140  int insertForcedSegment( int p1, int p2, bool breakline );
142  //const static double leftOfTresh=0.00001;
144  static const int MAX_BASE_ITERATIONS = 300000;
146  int baseEdgeOfPoint( int point );
148  int baseEdgeOfTriangle( Point3D *point );
150  bool checkSwap( unsigned int edge, unsigned int recursiveDeep );
152  void doSwap( unsigned int edge, unsigned int recursiveDeep );
154  void doOnlySwap( unsigned int edge );
156  unsigned int mEdgeInside;
158  unsigned int mEdgeOutside;
160  unsigned int mEdgeWithPoint;
162  unsigned int mUnstableEdge;
166  bool swapPossible( unsigned int edge );
168  void triangulatePolygon( QList<int> *poly, QList<int> *free, int mainedge );
170  bool halfEdgeBBoxTest( int edge, double xlowleft, double ylowleft, double xupright, double yupright ) const;
172  double swapMinAngle( int edge ) const;
174  int splitHalfEdge( int edge, float position );
176  bool edgeOnConvexHull( int edge );
178  void evaluateInfluenceRegion( Point3D *point, int edge, QSet<int> &set );
179 };
180 
182  : xMax( 0 )
183  , xMin( 0 )
184  , yMax( 0 )
185  , yMin( 0 )
186  , mTriangleInterpolator( nullptr )
187  , mForcedCrossBehavior( Triangulation::DeleteFirst )
188  , mEdgeColor( 0, 255, 0 )
189  , mForcedEdgeColor( 0, 0, 255 )
190  , mBreakEdgeColor( 100, 100, 0 )
191  , mDecorator( this )
192  , mEdgeInside( 0 )
193  , mEdgeOutside( 0 )
194  , mEdgeWithPoint( 0 )
195  , mUnstableEdge( 0 )
196  , mTwiceInsPoint( 0 )
197 {
200 }
201 
203  : xMax( 0 )
204  , xMin( 0 )
205  , yMax( 0 )
206  , yMin( 0 )
207  , mTriangleInterpolator( nullptr )
209  , mEdgeColor( 0, 255, 0 )
210  , mForcedEdgeColor( 0, 0, 255 )
211  , mBreakEdgeColor( 100, 100, 0 )
212  , mDecorator( decorator ? decorator : this )
213  , mEdgeInside( 0 )
214  , mEdgeOutside( 0 )
215  , mEdgeWithPoint( 0 )
216  , mUnstableEdge( 0 )
217  , mTwiceInsPoint( 0 )
218 {
219  mPointVector.reserve( nop );
220  mHalfEdge.reserve( nop );
221 }
222 
224 {
225  return mPointVector.count();
226 }
227 
228 inline Point3D *DualEdgeTriangulation::getPoint( unsigned int i ) const
229 {
230  return mPointVector.at( i );
231 }
232 
233 inline bool DualEdgeTriangulation::halfEdgeBBoxTest( int edge, double xlowleft, double ylowleft, double xupright, double yupright ) const
234 {
235  return (
236  ( getPoint( mHalfEdge[edge]->getPoint() )->getX() >= xlowleft &&
237  getPoint( mHalfEdge[edge]->getPoint() )->getX() <= xupright &&
238  getPoint( mHalfEdge[edge]->getPoint() )->getY() >= ylowleft &&
239  getPoint( mHalfEdge[edge]->getPoint() )->getY() <= yupright ) ||
240  ( getPoint( mHalfEdge[mHalfEdge[edge]->getDual()]->getPoint() )->getX() >= xlowleft &&
241  getPoint( mHalfEdge[mHalfEdge[edge]->getDual()]->getPoint() )->getX() <= xupright &&
242  getPoint( mHalfEdge[mHalfEdge[edge]->getDual()]->getPoint() )->getY() >= ylowleft &&
243  getPoint( mHalfEdge[mHalfEdge[edge]->getDual()]->getPoint() )->getY() <= yupright )
244  );
245 }
246 
247 #endif
248 
249 
250 
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 int addPoint(Point3D *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:37
virtual void setEdgeColor(int r, int g, int b)=0
Sets the color of the normal edges.
int mTwiceInsPoint
If a point has been inserted twice, its number is stored in this member.
virtual bool calcPoint(double x, double y, Point3D *result)=0
Calculates x-, y and z-value of the point on the surface and assigns it to &#39;result&#39;.
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 bool saveAsShapefile(const QString &fileName) const =0
Saves the triangulation as a (line) shapefile.
double yMin
Y-coordinate of the lower left corner of the bounding box.
virtual 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)
This class represents a line.
Definition: Line3D.h:25
double xMax
X-coordinate of the upper right corner of the bounding box.
unsigned int mUnstableEdge
If an instability occurs in &#39;baseEdgeOfTriangle&#39;, mUnstableEdge is set to the value of the current ed...
DualEdgeTriangulation is an implementation of a triangulation class based on the dual edge data struc...
QVector< HalfEdge * > mHalfEdge
Stores pointers to the HalfEdges.
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...
Point3D is a class to represent a three dimensional point.
Definition: Point3D.h:25
Class Vector3D represents a 3D-Vector, capable to store x-,y- and z-coordinates in double values...
Definition: Vector3D.h:29
virtual double getYMax() const override
Returns the largest y-coordinate value of the bounding box.
This is an interface for interpolator classes for triangulations.
#define SIP_SKIP
Definition: qgis_sip.h:87
double yMax
Y-coordinate of the upper right corner of the bounding box.
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.
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 Point3D * getPoint(unsigned int i) const override
Draws the points, edges and the forced lines.
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:30
QColor mBreakEdgeColor
Color to paint the breaklines.
unsigned int mEdgeWithPoint
If an inserted point is exactly on an existing edge, &#39;baseEdgeOfTriangle&#39; returns -20 and sets the va...
virtual double getXMin() const override
Returns the smallest x-coordinate value of the bounding box.
Triangulation::ForcedCrossBehavior mForcedCrossBehavior
Member to store the behavior in case of crossing forced segments.
unsigned int mEdgeInside
Number of an edge which does not point to the virtual point. It continuously updated for a fast searc...
TriangleInterpolator * mTriangleInterpolator
Association to an interpolator object.
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 bool getTriangle(double x, double y, Point3D *p1, int *n1, Point3D *p2, int *n2, Point3D *p3, int *n3)=0
Finds out in which triangle the point with coordinates x and y is and assigns the numbers of the vert...
QVector< Point3D * > mPointVector
Stores pointers to all points in the triangulations (including the points contained in the lines) ...
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...
virtual void setForcedCrossBehavior(Triangulation::ForcedCrossBehavior b)=0
Draws the points, edges and the forced lines.
static const unsigned int DEFAULT_STORAGE_FOR_POINTS
Default value for the number of storable points at the beginning.
virtual void eliminateHorizontalTriangles()=0
Eliminates the horizontal triangles by swapping.
QColor mEdgeColor
Color to paint the normal edges.
virtual Point3D * getPoint(unsigned int i) const =0
Returns a pointer to the point with number i. Any virtual points must have the number -1...
double xMin
X-coordinate of the lower left corner of the bounding box.
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:34
unsigned int mEdgeOutside
Number of an edge on the outside of the convex hull. It is updated in method &#39;baseEdgeOfTriangle&#39; to ...
virtual void setTriangleInterpolator(TriangleInterpolator *interpolator)=0
Sets an interpolator object.