QGIS API Documentation  2.5.0-Master
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
DualEdgeTriangulation.h
Go to the documentation of this file.
1 /***************************************************************************
2  DualEdgeTriangulation.h - description
3  -------------------
4  copyright : (C) 2004 by Marco Hugentobler
5  email : mhugent@geo.unizh.ch
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 "HalfEdge.h"
22 #include <QVector>
23 #include <QList>
24 #include <QSet>
25 #include "MathUtils.h"
26 #include "TriangleInterpolator.h"
27 #include <QColor>
28 #include <QFile>
29 #include <QTextStream>
30 #include <QMessageBox>
31 #include <cfloat>
32 #include <QBuffer>
33 #include <QStringList>
34 #include <QProgressDialog>
35 #include <QCursor>
36 
38 class ANALYSIS_EXPORT DualEdgeTriangulation: public Triangulation
39 {
40  public:
42  DualEdgeTriangulation( int nop, Triangulation* decorator );
43  virtual ~DualEdgeTriangulation();
44  void setDecorator( Triangulation* d ) {mDecorator = d;}
46  void addLine( Line3D* line, bool breakline );
48  int addPoint( Point3D* p );
50  virtual void performConsistencyTest();
52  virtual bool calcNormal( double x, double y, Vector3D* result );
54  virtual bool calcPoint( double x, double y, Point3D* result );
56  //virtual void draw(QPainter* p, double xlowleft, double ylowleft, double xupright, double yupright, double width, double height) const;
58  virtual Point3D* getPoint( unsigned int i ) const;
60  int getOppositePoint( int p1, int p2 );
62  virtual bool getTriangle( double x, double y, Point3D* p1, int* n1, Point3D* p2, int* n2, Point3D* p3, int* n3 );
65  virtual bool getTriangle( double x, double y, Point3D* p1, Point3D* p2, Point3D* p3 );
67  QList<int>* getSurroundingTriangles( int pointno );
69  virtual double getXMax() const;
71  virtual double getXMin() const;
73  virtual double getYMax() const;
75  virtual double getYMin() const;
77  virtual int getNumberOfPoints() const;
79  void removeLine( int i );
81  void removePoint( int i );
85  virtual void setEdgeColor( int r, int g, int b );
87  virtual void setForcedEdgeColor( int r, int g, int b );
89  virtual void setBreakEdgeColor( int r, int g, int b );
91  void setTriangleInterpolator( TriangleInterpolator* interpolator );
95  virtual void ruppertRefinement();
97  bool pointInside( double x, double y );
99  //bool readFromTAFF(QString fileName);
101  //bool saveToTAFF(QString fileName) const;
103  virtual bool swapEdge( double x, double y );
105  virtual QList<int>* getPointsAroundEdge( double x, double y );
108  virtual bool saveAsShapefile( const QString& fileName ) const;
109 
110  protected:
112  double xMax;
114  double xMin;
116  double yMax;
118  double yMin;
120  const static unsigned int mDefaultStorageForPoints = 100000;
122  QVector<Point3D*> mPointVector;
124  const static unsigned int mDefaultStorageForHalfEdges = 300006;
126  QVector<HalfEdge*> mHalfEdge;
132  QColor mEdgeColor;
140  unsigned int insertEdge( int dual, int next, int point, bool mbreak, bool forced );
142  int insertForcedSegment( int p1, int p2, bool breakline );
144  //const static double leftOfTresh=0.00001;
146  const static int nBaseOfRuns = 300000;
148  int baseEdgeOfPoint( int point );
150  int baseEdgeOfTriangle( Point3D* point );
152  bool checkSwap( unsigned int edge, unsigned int recursivDeep );
154  void doSwap( unsigned int edge, unsigned int recursivDeep );
156  void doOnlySwap( unsigned int edge );
158  unsigned int mEdgeInside;
160  unsigned int mEdgeOutside;
162  unsigned int mEdgeWithPoint;
164  unsigned int mUnstableEdge;
168  bool swapPossible( unsigned int edge );
170  void triangulatePolygon( QList<int>* poly, QList<int>* free, int mainedge );
172  bool halfEdgeBBoxTest( int edge, double xlowleft, double ylowleft, double xupright, double yupright ) const;
174  double swapMinAngle( int edge ) const;
176  int splitHalfEdge( int edge, float position );
178  bool edgeOnConvexHull( int edge );
180  void evaluateInfluenceRegion( Point3D* point, int edge, QSet<int> &set );
181 };
182 
183 inline DualEdgeTriangulation::DualEdgeTriangulation() : xMax( 0 ), xMin( 0 ), yMax( 0 ), yMin( 0 ), mTriangleInterpolator( 0 ), mForcedCrossBehaviour( Triangulation::DELETE_FIRST ), mEdgeColor( 0, 255, 0 ), mForcedEdgeColor( 0, 0, 255 ), mBreakEdgeColor( 100, 100, 0 ), mDecorator( this )
184 {
187 }
188 
189 inline DualEdgeTriangulation::DualEdgeTriangulation( int nop, Triangulation* decorator ): xMax( 0 ), xMin( 0 ), yMax( 0 ), yMin( 0 ), mTriangleInterpolator( 0 ), mForcedCrossBehaviour( Triangulation::DELETE_FIRST ), mEdgeColor( 0, 255, 0 ), mForcedEdgeColor( 0, 0, 255 ), mBreakEdgeColor( 100, 100, 0 ), mDecorator( decorator )
190 {
191  mPointVector.reserve( nop );
192  mHalfEdge.reserve( nop );
193  if ( !mDecorator )
194  {
195  mDecorator = this;
196  }
197 }
198 
199 inline double DualEdgeTriangulation::getXMax() const
200 {
201  return xMax;
202 }
203 
204 inline double DualEdgeTriangulation::getXMin() const
205 {
206  return xMin;
207 }
208 
209 inline double DualEdgeTriangulation::getYMax() const
210 {
211  return yMax;
212 }
213 
214 inline double DualEdgeTriangulation::getYMin() const
215 {
216  return yMin;
217 }
218 
220 {
221  return (( int )( mPointVector.count() ) );
222 }
223 
224 inline Point3D* DualEdgeTriangulation::getPoint( unsigned int i ) const
225 {
226  return mPointVector.at( i );
227 }
228 
229 inline bool DualEdgeTriangulation::halfEdgeBBoxTest( int edge, double xlowleft, double ylowleft, double xupright, double yupright ) const
230 {
231  return (( getPoint( mHalfEdge[edge]->getPoint() )->getX() >= xlowleft && getPoint( mHalfEdge[edge]->getPoint() )->getX() <= xupright && getPoint( mHalfEdge[edge]->getPoint() )->getY() >= ylowleft && getPoint( mHalfEdge[edge]->getPoint() )->getY() <= yupright ) || ( getPoint( mHalfEdge[mHalfEdge[edge]->getDual()]->getPoint() )->getX() >= xlowleft && getPoint( mHalfEdge[mHalfEdge[edge]->getDual()]->getPoint() )->getX() <= xupright && getPoint( mHalfEdge[mHalfEdge[edge]->getDual()]->getPoint() )->getY() >= ylowleft && getPoint( mHalfEdge[mHalfEdge[edge]->getDual()]->getPoint() )->getY() <= yupright ) );
232 }
233 
234 #endif
235 
236 
237 
Triangulation * mDecorator
Pointer to the decorator using this triangulation.
Definition: DualEdgeTriangulation.h:138
Triangulation::forcedCrossBehaviour mForcedCrossBehaviour
Member to store the behaviour in case of crossing forced segments.
Definition: DualEdgeTriangulation.h:130
QVector< Point3D * > mPointVector
Stores pointers to all points in the triangulations (including the points contained in the lines) ...
Definition: DualEdgeTriangulation.h:122
virtual int addPoint(Point3D *p)=0
Adds a point to the triangulation.
virtual double getXMax() const
Returns the largest x-coordinate value of the bounding box.
Definition: DualEdgeTriangulation.h:199
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.
virtual double getYMax() const =0
Returns the largest y-coordinate value of the bounding box.
virtual void setEdgeColor(int r, int g, int b)=0
Sets the color of the normal edges.
DualEdgeTriangulation()
Definition: DualEdgeTriangulation.h:183
int mTwiceInsPoint
If a point has been inserted twice, its number is stored in this member.
Definition: DualEdgeTriangulation.h:166
virtual double getXMax() const =0
Returns the largest x-coordinate value of the bounding box.
static const unsigned int mDefaultStorageForHalfEdges
Default value for the number of storable HalfEdges at the beginning.
Definition: DualEdgeTriangulation.h:124
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 'result'.
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.
Definition: DualEdgeTriangulation.h:118
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:24
double xMax
X-coordinate of the upper right corner of the bounding box.
Definition: DualEdgeTriangulation.h:112
virtual double getYMin() const
Returns the smallest x-coordinate value of the bounding box.
Definition: DualEdgeTriangulation.h:214
unsigned int mUnstableEdge
If an instability occurs in 'baseEdgeOfTriangle', mUnstableEdge is set to the value of the current ed...
Definition: DualEdgeTriangulation.h:164
forcedCrossBehaviour
Enumeration describing the behaviour, if two forced lines cross.
Definition: Triangulation.h:32
DualEdgeTriangulation is an implementation of a triangulation class based on the dual edge data struc...
Definition: DualEdgeTriangulation.h:38
static const unsigned int mDefaultStorageForPoints
Default value for the number of storable points at the beginning.
Definition: DualEdgeTriangulation.h:120
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:23
Class Vector3D represents a 3D-Vector, capable to store x-,y- and z-coordinates in double values...
Definition: Vector3D.h:22
This is an interface for interpolator classes for triangulations.
Definition: TriangleInterpolator.h:24
double yMax
Y-coordinate of the upper right corner of the bounding box.
Definition: DualEdgeTriangulation.h:116
void setDecorator(Triangulation *d)
Definition: DualEdgeTriangulation.h:44
virtual double getYMax() const
Returns the largest y-coordinate value of the bounding box.
Definition: DualEdgeTriangulation.h:209
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.
Definition: DualEdgeTriangulation.h:134
virtual Point3D * getPoint(unsigned int i) const
draws the points, edges and the forced lines
Definition: DualEdgeTriangulation.h:224
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:28
QColor mBreakEdgeColor
Color to paint the breaklines.
Definition: DualEdgeTriangulation.h:136
virtual void setForcedCrossBehaviour(Triangulation::forcedCrossBehaviour b)=0
draws the points, edges and the forced lines
unsigned int mEdgeWithPoint
If an inserted point is exactly on an existing edge, 'baseEdgeOfTriangle' returns -20 and sets the va...
Definition: DualEdgeTriangulation.h:162
virtual double getXMin() const =0
Returns the smallest x-coordinate value of the bounding box.
virtual double getXMin() const
Returns the smallest x-coordinate value of the bounding box.
Definition: DualEdgeTriangulation.h:204
unsigned int mEdgeInside
Number of an edge which does not point to the virtual point.
Definition: DualEdgeTriangulation.h:158
TriangleInterpolator * mTriangleInterpolator
Association to an interpolator object.
Definition: DualEdgeTriangulation.h:128
virtual bool calcNormal(double x, double y, Vector3D *result)=0
Calculates the normal at a point on the surface and assigns it to 'result'.
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 ver...
QVector< HalfEdge * > mHalfEdge
Stores pointers to the HalfEdges.
Definition: DualEdgeTriangulation.h:126
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 int getNumberOfPoints() const
Returns the number of points.
Definition: DualEdgeTriangulation.h:219
virtual double getYMin() const =0
Returns the smallest x-coordinate value of the bounding box.
virtual void eliminateHorizontalTriangles()=0
Eliminates the horizontal triangles by swapping.
QColor mEdgeColor
Color to paint the normal edges.
Definition: DualEdgeTriangulation.h:132
virtual Point3D * getPoint(unsigned int i) const =0
Returns a pointer to the point with number i.
double xMin
X-coordinate of the lower left corner of the bounding box.
Definition: DualEdgeTriangulation.h:114
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...
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...
Definition: DualEdgeTriangulation.h:229
unsigned int mEdgeOutside
Number of an edge on the outside of the convex hull.
Definition: DualEdgeTriangulation.h:160
virtual void setTriangleInterpolator(TriangleInterpolator *interpolator)=0
Sets an interpolator object.