DualEdgeTriangulation class

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

Reference

Base classes

class Triangulation: Interface for Triangulation classes.

Public functions

void addLine(const QVector<QgsPoint>& points, QgsInterpolator::SourceType lineType) override: Adds a line (e.g.
auto addPoint(const QgsPoint& point) -> int override: Adds a point to the triangulation.
auto calcNormal(double x, double y, Vector3D* result) -> bool override: Calculates the normal at a point on the surface.
auto calcPoint(double x, double y, QgsPoint& result) -> bool override: Calculates x-, y and z-value of the point on the surface and assigns it to 'result'.
void eliminateHorizontalTriangles() override: Eliminates the horizontal triangles by swapping or by insertion of new points.
auto getNumberOfPoints() const -> int override: Returns the number of points.
auto getOppositePoint(int p1, int p2) -> int override: Returns the number of the point opposite to the triangle points p1, p2 (which have to be on a halfedge).
auto getPoint(int i) const -> QgsPoint* override: Draws the points, edges and the forced lines.
auto getPointsAroundEdge(double x, double y) -> QList<int>* override: 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.
auto getSurroundingTriangles(int pointno) -> QList<int> override: Returns a pointer to a value list with the information of the triangles surrounding (counterclockwise) a point.
auto getTriangle(double x, double y, QgsPoint& p1, int& n1, QgsPoint& p2, int& n2, QgsPoint& p3, int& n3) -> bool override: 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'.
auto getTriangle(double x, double y, QgsPoint& p1, QgsPoint& p2, QgsPoint& p3) -> bool override: Finds out, in which triangle the point with coordinates x and y is and assigns the points at the vertices to 'p1', 'p2' and 'p3.
auto getXMax() const -> double override: Returns the largest x-coordinate value of the bounding box.
auto getXMin() const -> double override: Returns the smallest x-coordinate value of the bounding box.
auto getYMax() const -> double override: Returns the largest y-coordinate value of the bounding box.
auto getYMin() const -> double override: Returns the smallest x-coordinate value of the bounding box.
void performConsistencyTest() override: Performs a consistency check, remove this later.
auto pointInside(double x, double y) -> bool override: Returns true, if the point with coordinates x and y is inside the convex hull and false otherwise.
void ruppertRefinement() override: Adds points to make the triangles better shaped (algorithm of ruppert)
auto saveTriangulation(QgsFeatureSink* sink, QgsFeedback* feedback = nullptr) const -> bool override: Saves the triangulation features to a feature sink.
void setBreakEdgeColor(int r, int g, int b) override: Sets the color of the breaklines.
void setEdgeColor(int r, int g, int b) override: Sets the color of the normal edges.
void setForcedCrossBehavior(Triangulation::ForcedCrossBehavior b) override: Sets the behavior of the triangulation in case of crossing forced lines.
void setForcedEdgeColor(int r, int g, int b) override: Sets the color of the forced edges.
void setTriangleInterpolator(TriangleInterpolator* interpolator) override: Sets an interpolator object.
auto swapEdge(double x, double y) -> bool override: Reads the dual edge structure of a taff file.

Protected functions

auto baseEdgeOfPoint(int point) -> int: Returns the number of an edge which points to the point with number 'point' or -1 if there is an error.
auto baseEdgeOfTriangle(const QgsPoint& point) -> int: 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 occurred (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.
auto checkSwap(unsigned int edge, unsigned int recursiveDeep) -> bool: Checks, if 'edge' has to be swapped because of the empty circle criterion. If so, doSwap(...) is called.
void doOnlySwap(unsigned int edge): Swaps 'edge' and does no recursiv testing.
void doSwap(unsigned int edge, unsigned int recursiveDeep): Swaps 'edge' and test recursively for other swaps (delaunay criterion)
auto edgeOnConvexHull(int edge) -> bool: Returns true, if a half edge is on the convex hull and false otherwise.
void evaluateInfluenceRegion(QgsPoint* point, int edge, QSet<int>& set): 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.
auto halfEdgeBBoxTest(int edge, double xlowleft, double ylowleft, double xupright, double yupright) const -> bool: 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.
auto insertEdge(int dual, int next, int point, bool mbreak, bool forced) -> unsigned int: Inserts an edge and makes sure, everything is OK with the storage of the edge. The number of the HalfEdge is returned.
auto insertForcedSegment(int p1, int p2, QgsInterpolator::SourceType segmentType) -> int: 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.
auto splitHalfEdge(int edge, float position) -> int: 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.
auto swapMinAngle(int edge) const -> double: Calculates the minimum angle, which would be present, if the specified halfedge would be swapped.
auto swapPossible(unsigned int edge) -> bool: 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. '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.

Protected static variables

static const unsigned int DEFAULT_STORAGE_FOR_HALF_EDGES: Default value for the number of storable HalfEdges at the beginning.
static const unsigned int DEFAULT_STORAGE_FOR_POINTS: Default value for the number of storable points at the beginning.
static const int MAX_BASE_ITERATIONS: Threshold for the leftOfTest to handle numerical instabilities.

Protected variables

QColor mBreakEdgeColor: Color to paint the breaklines.
Triangulation* mDecorator: Pointer to the decorator using this triangulation. It it is used directly, mDecorator equals this.
QColor mEdgeColor: Color to paint the normal edges.
unsigned int mEdgeInside: Number of an edge which does not point to the virtual point. It continuously updated for a fast search.
unsigned int mEdgeOutside: 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.
unsigned int mEdgeWithPoint: If an inserted point is exactly on an existing edge, 'baseEdgeOfTriangle' returns -20 and sets the variable 'mEdgeWithPoint'.
Triangulation::ForcedCrossBehavior mForcedCrossBehavior: Member to store the behavior in case of crossing forced segments.
QColor mForcedEdgeColor: Color to paint the forced edges.
QVector<HalfEdge*> mHalfEdge: Stores pointers to the HalfEdges.
QVector<QgsPoint*> 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.

Function documentation

void DualEdgeTriangulation::addLine(const QVector<QgsPoint>& points, QgsInterpolator::SourceType lineType) override

Adds a line (e.g.

a break-, structure- or an isoline) to the triangulation, by specifying a list of source points.

int DualEdgeTriangulation::addPoint(const QgsPoint& point) override

Adds a point to the triangulation.

The point should have a z-value matching the value to interpolate.

bool DualEdgeTriangulation::calcPoint(double x, double y, QgsPoint& result) override

Calculates x-, y and z-value of the point on the surface and assigns it to 'result'.

Returns true in case of success and flase in case of failure

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

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

Returns -1 if point is a virtual point. Returns -10 if point crosses over edges.

QgsPoint* DualEdgeTriangulation::getPoint(int i) const override

Draws the points, edges and the forced lines.

Returns a pointer to the point with number i

QList<int> DualEdgeTriangulation::getSurroundingTriangles(int pointno) override

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. Any virtual point needs to have the number -1

bool DualEdgeTriangulation::saveTriangulation(QgsFeatureSink* sink, QgsFeedback* feedback = nullptr) const override

Saves the triangulation features to a feature sink.

Returns	true in case of success

The sink must be setup to accept LineString features, with fields matching those returned by triangulationFields().

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

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)

Variable documentation

static const int DualEdgeTriangulation::MAX_BASE_ITERATIONS 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