#include <DualEdgeTriangulation.h>
Public Member Functions | |
DualEdgeTriangulation () | |
DualEdgeTriangulation (int nop, Triangulation *decorator) | |
virtual | ~DualEdgeTriangulation () |
void | setDecorator (Triangulation *d) |
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 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 Point3D * | getPoint (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. | |
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, std::set< 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. | |
TriangleInterpolator * | mTriangleInterpolator |
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. | |
Triangulation * | mDecorator |
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. |
Definition at line 40 of file DualEdgeTriangulation.h.
DualEdgeTriangulation::DualEdgeTriangulation | ( | ) | [inline] |
Definition at line 184 of file DualEdgeTriangulation.h.
References mDefaultStorageForHalfEdges, mDefaultStorageForPoints, mHalfEdge, and mPointVector.
DualEdgeTriangulation::DualEdgeTriangulation | ( | int | nop, | |
Triangulation * | decorator | |||
) | [inline] |
Definition at line 190 of file DualEdgeTriangulation.h.
References mDecorator, mHalfEdge, and mPointVector.
virtual DualEdgeTriangulation::~DualEdgeTriangulation | ( | ) | [virtual] |
void DualEdgeTriangulation::setDecorator | ( | Triangulation * | d | ) | [inline] |
Definition at line 46 of file DualEdgeTriangulation.h.
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.
virtual void DualEdgeTriangulation::performConsistencyTest | ( | ) | [virtual] |
virtual bool DualEdgeTriangulation::calcNormal | ( | double | x, | |
double | y, | |||
Vector3D * | result | |||
) | [virtual] |
virtual bool DualEdgeTriangulation::calcPoint | ( | double | x, | |
double | y, | |||
Point3D * | result | |||
) | [virtual] |
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 225 of file DualEdgeTriangulation.h.
References mPointVector.
Referenced by halfEdgeBBoxTest().
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.
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'.
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.
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.
double DualEdgeTriangulation::getXMax | ( | ) | const [inline, virtual] |
Returns the largest x-coordinate value of the bounding box.
Implements Triangulation.
Definition at line 200 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 205 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 210 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 215 of file DualEdgeTriangulation.h.
References yMin.
int DualEdgeTriangulation::getNumberOfPoints | ( | ) | const [inline, virtual] |
Returns the number of points.
Implements Triangulation.
Definition at line 220 of file DualEdgeTriangulation.h.
References mPointVector.
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::setForcedCrossBehaviour | ( | Triangulation::forcedCrossBehaviour | b | ) | [virtual] |
virtual void DualEdgeTriangulation::setEdgeColor | ( | int | r, | |
int | g, | |||
int | b | |||
) | [virtual] |
virtual void DualEdgeTriangulation::setForcedEdgeColor | ( | int | r, | |
int | g, | |||
int | b | |||
) | [virtual] |
virtual void DualEdgeTriangulation::setBreakEdgeColor | ( | int | r, | |
int | g, | |||
int | b | |||
) | [virtual] |
void DualEdgeTriangulation::setTriangleInterpolator | ( | TriangleInterpolator * | interpolator | ) | [virtual] |
void DualEdgeTriangulation::eliminateHorizontalTriangles | ( | ) | [virtual] |
Eliminates the horizontal triangles by swapping or by insertion of new points.
Implements Triangulation.
virtual void DualEdgeTriangulation::ruppertRefinement | ( | ) | [virtual] |
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.
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 fileSwaps the edge which is closest to the point with x and y coordinates (if this is possible)
Implements Triangulation.
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.
virtual bool DualEdgeTriangulation::saveAsShapefile | ( | const QString & | fileName | ) | const [virtual] |
Saves the triangulation as a (line) shapefile.
Implements Triangulation.
Referenced by QgsTINInterpolator::initialize().
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
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
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::doSwap | ( | unsigned int | edge | ) | [protected] |
Swaps 'edge' and test recursively for other swaps (delaunay criterion).
void DualEdgeTriangulation::doOnlySwap | ( | unsigned int | edge | ) | [protected] |
Swaps 'edge' and does no recursiv testing.
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
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 230 of file DualEdgeTriangulation.h.
References getPoint(), and mHalfEdge.
double DualEdgeTriangulation::swapMinAngle | ( | int | edge | ) | const [protected] |
Calculates the minimum angle, which would be present, if the specified halfedge would be swapped.
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
bool DualEdgeTriangulation::edgeOnConvexHull | ( | int | edge | ) | [protected] |
Returns true, if a half edge is on the convex hull and false otherwise.
void DualEdgeTriangulation::evaluateInfluenceRegion | ( | Point3D * | point, | |
int | edge, | |||
std::set< 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
double DualEdgeTriangulation::xMax [protected] |
X-coordinate of the upper right corner of the bounding box.
Definition at line 113 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 115 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 117 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 119 of file DualEdgeTriangulation.h.
Referenced by getYMin().
const unsigned int DualEdgeTriangulation::mDefaultStorageForPoints = 100000 [static, protected] |
Default value for the number of storable points at the beginning.
Definition at line 121 of file DualEdgeTriangulation.h.
Referenced by DualEdgeTriangulation().
QVector<Point3D*> DualEdgeTriangulation::mPointVector [protected] |
Stores pointers to all points in the triangulations (including the points contained in the lines).
Definition at line 123 of file DualEdgeTriangulation.h.
Referenced by DualEdgeTriangulation(), getNumberOfPoints(), and getPoint().
const unsigned int DualEdgeTriangulation::mDefaultStorageForHalfEdges = 300006 [static, protected] |
Default value for the number of storable HalfEdges at the beginning.
Definition at line 125 of file DualEdgeTriangulation.h.
Referenced by DualEdgeTriangulation().
QVector<HalfEdge*> DualEdgeTriangulation::mHalfEdge [protected] |
Stores pointers to the HalfEdges.
Definition at line 127 of file DualEdgeTriangulation.h.
Referenced by DualEdgeTriangulation(), and halfEdgeBBoxTest().
Member to store the behaviour in case of crossing forced segments.
Definition at line 131 of file DualEdgeTriangulation.h.
QColor DualEdgeTriangulation::mEdgeColor [protected] |
QColor DualEdgeTriangulation::mForcedEdgeColor [protected] |
QColor DualEdgeTriangulation::mBreakEdgeColor [protected] |
Triangulation* DualEdgeTriangulation::mDecorator [protected] |
Pointer to the decorator using this triangulation.
It it is used directly, mDecorator equals this
Definition at line 139 of file DualEdgeTriangulation.h.
Referenced by DualEdgeTriangulation().
const int DualEdgeTriangulation::nBaseOfRuns = 300000 [static, protected] |
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 147 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 159 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 161 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 163 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 165 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 167 of file DualEdgeTriangulation.h.