QGIS API Documentation  2.5.0-Master
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties 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.
Triangulation::forcedCrossBehaviour mForcedCrossBehaviour
Member to store the behaviour in case of crossing forced segments.
QVector< Point3D * > mPointVector
Stores pointers to all points in the triangulations (including the points contained in the lines) ...
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.
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.
int mTwiceInsPoint
If a point has been inserted twice, its number is stored in this member.
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.
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.
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.
virtual double getYMin() const
Returns the smallest x-coordinate value of the bounding box.
unsigned int mUnstableEdge
If an instability occurs in 'baseEdgeOfTriangle', mUnstableEdge is set to the value of the current ed...
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...
static const unsigned int mDefaultStorageForPoints
Default value for the number of storable points at the beginning.
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.
double yMax
Y-coordinate of the upper right corner of the bounding box.
void setDecorator(Triangulation *d)
virtual double getYMax() const
Returns the largest y-coordinate value of the bounding box.
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 Point3D * getPoint(unsigned int i) const
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:28
QColor mBreakEdgeColor
Color to paint the breaklines.
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...
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.
unsigned int mEdgeInside
Number of an edge which does not point to the virtual point.
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 '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.
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.
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.
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.
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...
unsigned int mEdgeOutside
Number of an edge on the outside of the convex hull.
virtual void setTriangleInterpolator(TriangleInterpolator *interpolator)=0
Sets an interpolator object.