QGIS API Documentation  2.0.1-Dufour
DualEdgeTriangulation Class Reference

DualEdgeTriangulation is an implementation of a triangulation class based on the dual edge data structure. More...

`#include <DualEdgeTriangulation.h>`

Inheritance diagram for DualEdgeTriangulation: [legend]
Collaboration diagram for DualEdgeTriangulation: [legend]

## Public Member Functions

DualEdgeTriangulation ()
DualEdgeTriangulation (int nop, Triangulation *decorator)
virtual ~DualEdgeTriangulation ()
void setDecorator (Triangulation *d)
void addLine (Line3D *line, bool breakline)
Adds a point to the triangulation and returns the number of this point in case of success or -100 in case of failure.
virtual void performConsistencyTest ()
Performs a consistency check, remove this later.
virtual bool calcNormal (double x, double y, Vector3D *result)
Calculates the normal at a point on the surface.
virtual bool calcPoint (double x, double y, Point3D *result)
Calculates x-, y and z-value of the point on the surface.
virtual Point3DgetPoint (unsigned int i) const
draws the points, edges and the forced lines
int getOppositePoint (int p1, int p2)
Returns the number of the point opposite to the triangle points p1, p2 (which have to be on a halfedge)
virtual bool getTriangle (double x, double y, Point3D *p1, int *n1, Point3D *p2, int *n2, Point3D *p3, int *n3)
Finds out, in which triangle the point with coordinates x and y is and assigns the numbers of the vertices to 'n1', 'n2' and 'n3' and the vertices to 'p1', 'p2' and 'p3'.
virtual bool getTriangle (double x, double y, Point3D *p1, Point3D *p2, Point3D *p3)
Finds out, in which triangle the point with coordinates x and y is and assigns addresses to the points at the vertices to 'p1', 'p2' and 'p3.
QList< int > * getSurroundingTriangles (int pointno)
Returns a pointer to a value list with the information of the triangles surrounding (counterclockwise) a point.
virtual double getXMax () const
Returns the largest x-coordinate value of the bounding box.
virtual double getXMin () const
Returns the smallest x-coordinate value of the bounding box.
virtual double getYMax () const
Returns the largest y-coordinate value of the bounding box.
virtual double getYMin () const
Returns the smallest x-coordinate value of the bounding box.
virtual int getNumberOfPoints () const
Returns the number of points.
void removeLine (int i)
Removes the line with number i from the triangulation.
void removePoint (int i)
Removes the point with the number i from the triangulation.
virtual void setForcedCrossBehaviour (Triangulation::forcedCrossBehaviour b)
Sets the behaviour of the triangulation in case of crossing forced lines.
virtual void setEdgeColor (int r, int g, int b)
Sets the color of the normal edges.
virtual void setForcedEdgeColor (int r, int g, int b)
Sets the color of the forced edges.
virtual void setBreakEdgeColor (int r, int g, int b)
Sets the color of the breaklines.
void setTriangleInterpolator (TriangleInterpolator *interpolator)
Sets an interpolator object.
void eliminateHorizontalTriangles ()
Eliminates the horizontal triangles by swapping or by insertion of new points.
virtual void ruppertRefinement ()
Adds points to make the triangles better shaped (algorithm of ruppert)
bool pointInside (double x, double y)
Returns true, if the point with coordinates x and y is inside the convex hull and false otherwise.
virtual bool swapEdge (double x, double y)
Reads the dual edge structure of a taff file.
virtual QList< int > * getPointsAroundEdge (double x, double y)
Returns a value list with the numbers of the four points, which would be affected by an edge swap.
virtual bool saveAsShapefile (const QString &fileName) const
Saves the triangulation as a (line) shapefile. Public Member Functions inherited from Triangulation
virtual ~Triangulation ()

## Protected Member Functions

unsigned int insertEdge (int dual, int next, int point, bool mbreak, bool forced)
inserts an edge and makes sure, everything is ok with the storage of the edge.
int insertForcedSegment (int p1, int p2, bool breakline)
inserts a forced segment between the points with the numbers p1 and p2 into the triangulation and returns the number of a HalfEdge belonging to this forced edge or -100 in case of failure
int baseEdgeOfPoint (int point)
Returns the number of an edge which points to the point with number 'point' or -1 if there is an error.
int baseEdgeOfTriangle (Point3D *point)
returns the number of a HalfEdge from a triangle in which 'point' is in.
bool checkSwap (unsigned int edge)
Checks, if 'edge' has to be swapped because of the empty circle criterion.
void doSwap (unsigned int edge)
Swaps 'edge' and test recursively for other swaps (delaunay criterion)
void doOnlySwap (unsigned int edge)
Swaps 'edge' and does no recursiv testing.
bool swapPossible (unsigned int edge)
Returns true, if it is possible to swap an edge, otherwise false(concave quad or edge on (or outside) the convex hull)
void triangulatePolygon (QList< int > *poly, QList< int > *free, int mainedge)
divides a polygon in a triangle and two polygons and calls itself recursively for these two polygons.
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.
double swapMinAngle (int edge) const
Calculates the minimum angle, which would be present, if the specified halfedge would be swapped.
int splitHalfEdge (int edge, float position)
Inserts a new point on the halfedge with number 'edge'.
bool edgeOnConvexHull (int edge)
Returns true, if a half edge is on the convex hull and false otherwise.
void evaluateInfluenceRegion (Point3D *point, int edge, QSet< int > &set)
Function needed for the ruppert algorithm.

## Protected Attributes

double xMax
X-coordinate of the upper right corner of the bounding box.
double xMin
X-coordinate of the lower left corner of the bounding box.
double yMax
Y-coordinate of the upper right corner of the bounding box.
double yMin
Y-coordinate of the lower left corner of the bounding box.
QVector< Point3D * > mPointVector
Stores pointers to all points in the triangulations (including the points contained in the lines)
QVector< HalfEdge * > mHalfEdge
Stores pointers to the HalfEdges.
TriangleInterpolatormTriangleInterpolator
Association to an interpolator object.
Triangulation::forcedCrossBehaviour mForcedCrossBehaviour
Member to store the behaviour in case of crossing forced segments.
QColor mEdgeColor
Color to paint the normal edges.
QColor mForcedEdgeColor
Color to paint the forced edges.
QColor mBreakEdgeColor
Color to paint the breaklines.
TriangulationmDecorator
Pointer to the decorator using this triangulation.
unsigned int mEdgeInside
Number of an edge which does not point to the virtual point.
unsigned int mEdgeOutside
Number of an edge on the outside of the convex hull.
unsigned int mEdgeWithPoint
If an inserted point is exactly on an existing edge, 'baseEdgeOfTriangle' returns -20 and sets the variable 'mEdgeWithPoint'.
unsigned int mUnstableEdge
If an instability occurs in 'baseEdgeOfTriangle', mUnstableEdge is set to the value of the current edge.
int mTwiceInsPoint
If a point has been inserted twice, its number is stored in this member.

## Static Protected Attributes

static const unsigned int mDefaultStorageForPoints = 100000
Default value for the number of storable points at the beginning.
static const unsigned int mDefaultStorageForHalfEdges = 300006
Default value for the number of storable HalfEdges at the beginning.
static const int nBaseOfRuns = 300000
Threshold for the leftOfTest to handle numerical instabilities. Public Types inherited from Triangulation
enum  forcedCrossBehaviour { SnappingType_VERTICE, DELETE_FIRST, INSERT_VERTICE }
Enumeration describing the behaviour, if two forced lines cross. More...

## Detailed Description

DualEdgeTriangulation is an implementation of a triangulation class based on the dual edge data structure.

Definition at line 38 of file DualEdgeTriangulation.h.

## Constructor & Destructor Documentation

 DualEdgeTriangulation::DualEdgeTriangulation ( )
inline
 DualEdgeTriangulation::DualEdgeTriangulation ( int nop, Triangulation * decorator )
inline

Definition at line 189 of file DualEdgeTriangulation.h.

References mDecorator, mHalfEdge, and mPointVector.

 virtual DualEdgeTriangulation::~DualEdgeTriangulation ( )
virtual

## Member Function Documentation

 void DualEdgeTriangulation::addLine ( Line3D * line, bool breakline )
virtual

a break-, structure- or an isoline) to the triangulation. The class takes ownership of the line object and its points

Implements Triangulation.

 int DualEdgeTriangulation::addPoint ( Point3D * p )
virtual

Adds a point to the triangulation and returns the number of this point in case of success or -100 in case of failure.

Implements Triangulation.

 int DualEdgeTriangulation::baseEdgeOfPoint ( int point )
protected

Returns the number of an edge which points to the point with number 'point' or -1 if there is an error.

 int DualEdgeTriangulation::baseEdgeOfTriangle ( Point3D * point )
protected

returns the number of a HalfEdge from a triangle in which 'point' is in.

If the number -10 is returned, this means, that 'point' is outside the convex hull. If -5 is returned, then numerical problems with the leftOfTest occured (and the value of the possible edge is stored in the variable 'mUnstableEdge'. -20 means, that the inserted point is exactly on an edge (the number is stored in the variable 'mEdgeWithPoint'). -25 means, that the point is already in the triangulation (the number of the point is stored in the member 'mTwiceInsPoint'. If -100 is returned, this means that something else went wrong

 virtual bool DualEdgeTriangulation::calcNormal ( double x, double y, Vector3D * result )
virtual

Calculates the normal at a point on the surface.

Implements Triangulation.

 virtual bool DualEdgeTriangulation::calcPoint ( double x, double y, Point3D * result )
virtual

Calculates x-, y and z-value of the point on the surface.

Implements Triangulation.

 bool DualEdgeTriangulation::checkSwap ( unsigned int edge )
protected

Checks, if 'edge' has to be swapped because of the empty circle criterion.

If so, doSwap(...) is called.

 void DualEdgeTriangulation::doOnlySwap ( unsigned int edge )
protected

Swaps 'edge' and does no recursiv testing.

 void DualEdgeTriangulation::doSwap ( unsigned int edge )
protected

Swaps 'edge' and test recursively for other swaps (delaunay criterion)

 bool DualEdgeTriangulation::edgeOnConvexHull ( int edge )
protected

Returns true, if a half edge is on the convex hull and false otherwise.

 void DualEdgeTriangulation::eliminateHorizontalTriangles ( )
virtual

Eliminates the horizontal triangles by swapping or by insertion of new points.

Implements Triangulation.

 void DualEdgeTriangulation::evaluateInfluenceRegion ( Point3D * point, int edge, QSet< int > & set )
protected

Function needed for the ruppert algorithm.

Tests, if point is in the circle through both endpoints of edge and the endpoint of edge->dual->next->point. If so, the function calls itself recursively for edge->next and edge->next->next. Stops, if it finds a forced edge or a convex hull edge

 int DualEdgeTriangulation::getNumberOfPoints ( ) const
inlinevirtual

Returns the number of points.

Implements Triangulation.

Definition at line 219 of file DualEdgeTriangulation.h.

References mPointVector.

 int DualEdgeTriangulation::getOppositePoint ( int p1, int p2 )
virtual

Returns the number of the point opposite to the triangle points p1, p2 (which have to be on a halfedge)

Implements Triangulation.

 Point3D * DualEdgeTriangulation::getPoint ( unsigned int i ) const
inlinevirtual

draws the points, edges and the forced lines

Returns a pointer to the point with number i

Implements Triangulation.

Definition at line 224 of file DualEdgeTriangulation.h.

References mPointVector.

Referenced by halfEdgeBBoxTest().

 virtual QList* DualEdgeTriangulation::getPointsAroundEdge ( double x, double y )
virtual

Returns a value list with the numbers of the four points, which would be affected by an edge swap.

This function is e.g. needed by NormVecDecorator to know the points, for which the normals have to be recalculated. The returned ValueList has to be deleted by the code which calls the method

Implements Triangulation.

 QList* DualEdgeTriangulation::getSurroundingTriangles ( int pointno )
virtual

Returns a pointer to a value list with the information of the triangles surrounding (counterclockwise) a point.

Four integer values describe a triangle, the first three are the number of the half edges of the triangle and the fourth is -10, if the third (and most counterclockwise) edge is a breakline, and -20 otherwise. The value list has to be deleted by the code which called the method

Implements Triangulation.

 virtual bool DualEdgeTriangulation::getTriangle ( double x, double y, Point3D * p1, int * n1, Point3D * p2, int * n2, Point3D * p3, int * n3 )
virtual

Finds out, in which triangle the point with coordinates x and y is and assigns the numbers of the vertices to 'n1', 'n2' and 'n3' and the vertices to 'p1', 'p2' and 'p3'.

Note
not available in python bindings

Implements Triangulation.

 virtual bool DualEdgeTriangulation::getTriangle ( double x, double y, Point3D * p1, Point3D * p2, Point3D * p3 )
virtual

Finds out, in which triangle the point with coordinates x and y is and assigns addresses to the points at the vertices to 'p1', 'p2' and 'p3.

Implements Triangulation.

 double DualEdgeTriangulation::getXMax ( ) const
inlinevirtual

Returns the largest x-coordinate value of the bounding box.

Implements Triangulation.

Definition at line 199 of file DualEdgeTriangulation.h.

References xMax.

 double DualEdgeTriangulation::getXMin ( ) const
inlinevirtual

Returns the smallest x-coordinate value of the bounding box.

Implements Triangulation.

Definition at line 204 of file DualEdgeTriangulation.h.

References xMin.

 double DualEdgeTriangulation::getYMax ( ) const
inlinevirtual

Returns the largest y-coordinate value of the bounding box.

Implements Triangulation.

Definition at line 209 of file DualEdgeTriangulation.h.

References yMax.

 double DualEdgeTriangulation::getYMin ( ) const
inlinevirtual

Returns the smallest x-coordinate value of the bounding box.

Implements Triangulation.

Definition at line 214 of file DualEdgeTriangulation.h.

References yMin.

 bool DualEdgeTriangulation::halfEdgeBBoxTest ( int edge, double xlowleft, double ylowleft, double xupright, double yupright ) const
inlineprotected

Tests, if the bounding box of the halfedge with index i intersects the specified bounding box.

The main purpose for this method is the drawing of the triangulation

Definition at line 229 of file DualEdgeTriangulation.h.

References getPoint(), and mHalfEdge.

 unsigned int DualEdgeTriangulation::insertEdge ( int dual, int next, int point, bool mbreak, bool forced )
protected

inserts an edge and makes sure, everything is ok with the storage of the edge.

The number of the HalfEdge is returned

 int DualEdgeTriangulation::insertForcedSegment ( int p1, int p2, bool breakline )
protected

inserts a forced segment between the points with the numbers p1 and p2 into the triangulation and returns the number of a HalfEdge belonging to this forced edge or -100 in case of failure

 virtual void DualEdgeTriangulation::performConsistencyTest ( )
virtual

Performs a consistency check, remove this later.

Implements Triangulation.

 bool DualEdgeTriangulation::pointInside ( double x, double y )
virtual

Returns true, if the point with coordinates x and y is inside the convex hull and false otherwise.

Implements Triangulation.

 void DualEdgeTriangulation::removeLine ( int i )

Removes the line with number i from the triangulation.

 void DualEdgeTriangulation::removePoint ( int i )

Removes the point with the number i from the triangulation.

 virtual void DualEdgeTriangulation::ruppertRefinement ( )
virtual

Adds points to make the triangles better shaped (algorithm of ruppert)

Implements Triangulation.

 virtual bool DualEdgeTriangulation::saveAsShapefile ( const QString & fileName ) const
virtual

Saves the triangulation as a (line) shapefile.

Returns
true in case of success

Implements Triangulation.

Referenced by QgsTINInterpolator::initialize().

 virtual void DualEdgeTriangulation::setBreakEdgeColor ( int r, int g, int b )
virtual

Sets the color of the breaklines.

Implements Triangulation.

 void DualEdgeTriangulation::setDecorator ( Triangulation * d )
inline

Definition at line 44 of file DualEdgeTriangulation.h.

 virtual void DualEdgeTriangulation::setEdgeColor ( int r, int g, int b )
virtual

Sets the color of the normal edges.

Implements Triangulation.

 virtual void DualEdgeTriangulation::setForcedCrossBehaviour ( Triangulation::forcedCrossBehaviour b )
virtual

Sets the behaviour of the triangulation in case of crossing forced lines.

Implements Triangulation.

 virtual void DualEdgeTriangulation::setForcedEdgeColor ( int r, int g, int b )
virtual

Sets the color of the forced edges.

Implements Triangulation.

 void DualEdgeTriangulation::setTriangleInterpolator ( TriangleInterpolator * interpolator )
virtual

Sets an interpolator object.

Implements Triangulation.

 int DualEdgeTriangulation::splitHalfEdge ( int edge, float position )
protected

Inserts a new point on the halfedge with number 'edge'.

The position can have a value from 0 to 1 (e.g. 0.5 would be in the middle). The return value is the number of the new inserted point. tin is the triangulation, which should be used to calculate the elevation of the inserted point

 virtual bool DualEdgeTriangulation::swapEdge ( double x, double y )
virtual

Reads the dual edge structure of a taff file.

Saves the dual edge structure to a taff file Swaps the edge which is closest to the point with x and y coordinates (if this is possible)

Implements Triangulation.

 double DualEdgeTriangulation::swapMinAngle ( int edge ) const
protected

Calculates the minimum angle, which would be present, if the specified halfedge would be swapped.

 bool DualEdgeTriangulation::swapPossible ( unsigned int edge )
protected

Returns true, if it is possible to swap an edge, otherwise false(concave quad or edge on (or outside) the convex hull)

 void DualEdgeTriangulation::triangulatePolygon ( QList< int > * poly, QList< int > * free, int mainedge )
protected

divides a polygon in a triangle and two polygons and calls itself recursively for these two polygons.

'poly' is a pointer to a list with the numbers of the edges of the polygon, 'free' is a pointer to a list of free halfedges, and 'mainedge' is the number of the edge, towards which the new triangle is inserted. Mainedge has to be the same as poly->begin(), otherwise the recursion does not work

## Member Data Documentation

 QColor DualEdgeTriangulation::mBreakEdgeColor
protected

Color to paint the breaklines.

Definition at line 136 of file DualEdgeTriangulation.h.

 Triangulation* DualEdgeTriangulation::mDecorator
protected

Pointer to the decorator using this triangulation.

It it is used directly, mDecorator equals this

Definition at line 138 of file DualEdgeTriangulation.h.

Referenced by DualEdgeTriangulation().

 const unsigned int DualEdgeTriangulation::mDefaultStorageForHalfEdges = 300006
staticprotected

Default value for the number of storable HalfEdges at the beginning.

Definition at line 124 of file DualEdgeTriangulation.h.

Referenced by DualEdgeTriangulation().

 const unsigned int DualEdgeTriangulation::mDefaultStorageForPoints = 100000
staticprotected

Default value for the number of storable points at the beginning.

Definition at line 120 of file DualEdgeTriangulation.h.

Referenced by DualEdgeTriangulation().

 QColor DualEdgeTriangulation::mEdgeColor
protected

Color to paint the normal edges.

Definition at line 132 of file DualEdgeTriangulation.h.

 unsigned int DualEdgeTriangulation::mEdgeInside
protected

Number of an edge which does not point to the virtual point.

It continuously updated for a fast search

Definition at line 158 of file DualEdgeTriangulation.h.

 unsigned int DualEdgeTriangulation::mEdgeOutside
protected

Number of an edge on the outside of the convex hull.

It is updated in method 'baseEdgeOfTriangle' to enable insertion of points outside the convex hull

Definition at line 160 of file DualEdgeTriangulation.h.

 unsigned int DualEdgeTriangulation::mEdgeWithPoint
protected

If an inserted point is exactly on an existing edge, 'baseEdgeOfTriangle' returns -20 and sets the variable 'mEdgeWithPoint'.

Definition at line 162 of file DualEdgeTriangulation.h.

 Triangulation::forcedCrossBehaviour DualEdgeTriangulation::mForcedCrossBehaviour
protected

Member to store the behaviour in case of crossing forced segments.

Definition at line 130 of file DualEdgeTriangulation.h.

 QColor DualEdgeTriangulation::mForcedEdgeColor
protected

Color to paint the forced edges.

Definition at line 134 of file DualEdgeTriangulation.h.

 QVector DualEdgeTriangulation::mHalfEdge
protected

Stores pointers to the HalfEdges.

Definition at line 126 of file DualEdgeTriangulation.h.

Referenced by DualEdgeTriangulation(), and halfEdgeBBoxTest().

 QVector DualEdgeTriangulation::mPointVector
protected

Stores pointers to all points in the triangulations (including the points contained in the lines)

Definition at line 122 of file DualEdgeTriangulation.h.

Referenced by DualEdgeTriangulation(), getNumberOfPoints(), and getPoint().

 TriangleInterpolator* DualEdgeTriangulation::mTriangleInterpolator
protected

Association to an interpolator object.

Definition at line 128 of file DualEdgeTriangulation.h.

 int DualEdgeTriangulation::mTwiceInsPoint
protected

If a point has been inserted twice, its number is stored in this member.

Definition at line 166 of file DualEdgeTriangulation.h.

 unsigned int DualEdgeTriangulation::mUnstableEdge
protected

If an instability occurs in 'baseEdgeOfTriangle', mUnstableEdge is set to the value of the current edge.

Definition at line 164 of file DualEdgeTriangulation.h.

 const int DualEdgeTriangulation::nBaseOfRuns = 300000
staticprotected

Threshold for the leftOfTest to handle numerical instabilities.

Security to prevent endless loops in 'baseEdgeOfTriangle'. It there are more iteration then this number, the point will not be inserted

Definition at line 146 of file DualEdgeTriangulation.h.

 double DualEdgeTriangulation::xMax
protected

X-coordinate of the upper right corner of the bounding box.

Definition at line 112 of file DualEdgeTriangulation.h.

Referenced by getXMax().

 double DualEdgeTriangulation::xMin
protected

X-coordinate of the lower left corner of the bounding box.

Definition at line 114 of file DualEdgeTriangulation.h.

Referenced by getXMin().

 double DualEdgeTriangulation::yMax
protected

Y-coordinate of the upper right corner of the bounding box.

Definition at line 116 of file DualEdgeTriangulation.h.

Referenced by getYMax().

 double DualEdgeTriangulation::yMin
protected

Y-coordinate of the lower left corner of the bounding box.

Definition at line 118 of file DualEdgeTriangulation.h.

Referenced by getYMin().

The documentation for this class was generated from the following file: