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

#include <DualEdgeTriangulation.h>

Inheritance diagram for DualEdgeTriangulation:

Collaboration diagram for DualEdgeTriangulation:

Public Member Functions
	DualEdgeTriangulation ()
	DualEdgeTriangulation (int nop, Triangulation *decorator)
virtual	~DualEdgeTriangulation ()
void	addLine (Line3D *line, bool breakline)
	Adds a line (e.g.
int	addPoint (Point3D *p)
	Adds a point to the triangulation and returns the number of this point in case of success or -100 in case of failure.
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.
void	eliminateHorizontalTriangles ()
	Eliminates the horizontal triangles by swapping or by insertion of new points.
virtual int	getNumberOfPoints () const
	Returns the number of points.
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 Point3D *	getPoint (unsigned int i) const
	draws the points, edges and the forced lines
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.
QList< int > *	getSurroundingTriangles (int pointno)
	Returns a pointer to a value list with the information of the triangles surrounding (counterclockwise) a point.
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.
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 void	performConsistencyTest ()
	Performs a consistency check, remove this later.
bool	pointInside (double x, double y)
	Returns true, if the point with coordinates x and y is inside the convex hull and false otherwise.
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	ruppertRefinement ()
	Adds points to make the triangles better shaped (algorithm of ruppert)
virtual bool	saveAsShapefile (const QString &fileName) const
	Saves the triangulation as a (line) shapefile.
virtual void	setBreakEdgeColor (int r, int g, int b)
	Sets the color of the breaklines.
void	setDecorator (Triangulation *d)
virtual void	setEdgeColor (int r, int g, int b)
	Sets the color of the normal edges.
virtual void	setForcedCrossBehaviour (Triangulation::forcedCrossBehaviour b)
	Sets the behaviour of the triangulation in case of crossing forced lines.
virtual void	setForcedEdgeColor (int r, int g, int b)
	Sets the color of the forced edges.
void	setTriangleInterpolator (TriangleInterpolator *interpolator)
	Sets an interpolator object.
virtual bool	swapEdge (double x, double y)
	Reads the dual edge structure of a taff file.
Protected Member Functions
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	doOnlySwap (unsigned int edge)
	Swaps 'edge' and does no recursiv testing.
void	doSwap (unsigned int edge)
	Swaps 'edge' and test recursively for other swaps (delaunay criterion)
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.
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	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	splitHalfEdge (int edge, float position)
	Inserts a new point on the halfedge with number 'edge'.
double	swapMinAngle (int edge) const
	Calculates the minimum angle, which would be present, if the specified halfedge would be swapped.
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.
Protected Attributes
QColor	mBreakEdgeColor
	Color to paint the breaklines.
Triangulation *	mDecorator
	Pointer to the decorator using this triangulation.
QColor	mEdgeColor
	Color to paint the normal edges.
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'.
Triangulation::forcedCrossBehaviour	mForcedCrossBehaviour
	Member to store the behaviour in case of crossing forced segments.
QColor	mForcedEdgeColor
	Color to paint the forced edges.
QVector< HalfEdge * >	mHalfEdge
	Stores pointers to the HalfEdges.
QVector< Point3D * >	mPointVector
	Stores pointers to all points in the triangulations (including the points contained in the lines)
TriangleInterpolator *	mTriangleInterpolator
	Association to an interpolator object.
int	mTwiceInsPoint
	If a point has been inserted twice, its number is stored in this member.
unsigned int	mUnstableEdge
	If an instability occurs in 'baseEdgeOfTriangle', mUnstableEdge is set to the value of the current edge.
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.
Static Protected Attributes
static const unsigned int	mDefaultStorageForHalfEdges = 300006
	Default value for the number of storable HalfEdges at the beginning.
static const unsigned int	mDefaultStorageForPoints = 100000
	Default value for the number of storable points at the beginning.
static const int	nBaseOfRuns = 300000
	Threshold for the leftOfTest to handle numerical instabilities.

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]

Definition at line 183 of file DualEdgeTriangulation.h.

References mDefaultStorageForHalfEdges, mDefaultStorageForPoints, mHalfEdge, and mPointVector.

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]`

Adds a line (e.g.

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 [inline, virtual]

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 [inline, virtual]

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<int>* 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<int>* 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 [inline, virtual]

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 [inline, virtual]

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 [inline, virtual]

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 [inline, virtual]

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 `[inline, protected]`

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