17#ifndef DUALEDGETRIANGULATION_H
18#define DUALEDGETRIANGULATION_H
34#include "qgis_analysis.h"
76 double xMax()
const override {
return mXMax; }
78 double xMin()
const override {
return mXMin; }
80 double yMax()
const override {
return mYMax; }
82 double yMin()
const override {
return mYMin; }
96 bool swapEdge(
double x,
double y )
override;
114 static const unsigned int DEFAULT_STORAGE_FOR_POINTS = 100000;
116 QVector<QgsPoint *> mPointVector;
118 static const unsigned int DEFAULT_STORAGE_FOR_HALF_EDGES = 300006;
120 QVector<HalfEdge *> mHalfEdge;
126 unsigned int insertEdge(
int dual,
int next,
int point,
bool mbreak,
bool forced );
130 static const int MAX_BASE_ITERATIONS = 300000;
132 int baseEdgeOfPoint(
int point );
141 int baseEdgeOfTriangle(
const QgsPoint &point );
143 bool checkSwapRecursively(
unsigned int edge,
unsigned int recursiveDeep );
145 bool isEdgeNeedSwap(
unsigned int edge )
const;
147 void doSwapRecursively(
unsigned int edge,
unsigned int recursiveDeep );
149 void doOnlySwap(
unsigned int edge );
151 unsigned int mEdgeInside = 0;
153 int mEdgeOutside = -1;
155 unsigned int mEdgeWithPoint = 0;
157 unsigned int mUnstableEdge = 0;
159 int mTwiceInsPoint = 0;
161 bool swapPossible(
unsigned int edge )
const;
163 void triangulatePolygon( QList<int> *poly, QList<int> *free,
int mainedge );
165 bool halfEdgeBBoxTest(
int edge,
double xlowleft,
double ylowleft,
double xupright,
double yupright )
const;
167 double swapMinAngle(
int edge )
const;
169 int splitHalfEdge(
int edge,
float position );
171 bool edgeOnConvexHull(
int edge );
173 void evaluateInfluenceRegion(
QgsPoint *point,
int edge, QSet<int> &set );
177 int firstEdgeOutSide();
179 void removeLastPoint();
182 friend class TestQgsInterpolator;
189 mPointVector.reserve( DEFAULT_STORAGE_FOR_POINTS );
190 mHalfEdge.reserve( DEFAULT_STORAGE_FOR_HALF_EDGES );
195 mPointVector.reserve( nop );
196 mHalfEdge.reserve( nop );
201 return mPointVector.count();
206 if ( i < 0 || i >= mPointVector.count() )
209 return mPointVector.at( i );
212inline bool QgsDualEdgeTriangulation::halfEdgeBBoxTest(
int edge,
double xlowleft,
double ylowleft,
double xupright,
double yupright )
const
215 (
point( mHalfEdge[edge]->getPoint() )->x() >= xlowleft &&
216 point( mHalfEdge[edge]->getPoint() )->x() <= xupright &&
217 point( mHalfEdge[edge]->getPoint() )->y() >= ylowleft &&
218 point( mHalfEdge[edge]->getPoint() )->y() <= yupright ) ||
219 (
point( mHalfEdge[mHalfEdge[edge]->getDual()]->getPoint() )->x() >= xlowleft &&
220 point( mHalfEdge[mHalfEdge[edge]->getDual()]->getPoint() )->x() <= xupright &&
221 point( mHalfEdge[mHalfEdge[edge]->getDual()]->getPoint() )->y() >= ylowleft &&
222 point( mHalfEdge[mHalfEdge[edge]->getDual()]->getPoint() )->y() <= yupright )
DualEdgeTriangulation is an implementation of a triangulation class based on the dual edge data struc...
QgsPoint * point(int i) const override
Draws the points, edges and the forced lines.
double yMax() const override
Returns the largest y-coordinate value of the bounding box.
int pointsCount() const override
Returns the number of points.
double xMax() const override
Returns the largest x-coordinate value of the bounding box.
double xMin() const override
Returns the smallest x-coordinate value of the bounding box.
double yMin() const override
Returns the smallest x-coordinate value of the bounding box.
QgsDualEdgeTriangulation()
QgsDualEdgeTriangulation & operator=(const QgsDualEdgeTriangulation &other)=delete
QgsDualEdgeTriangulation(const QgsDualEdgeTriangulation &)=delete
An interface for objects which accept features via addFeature(s) methods.
Base class for feedback objects to be used for cancellation of something running in a worker thread.
SourceType
Describes the type of input data.
Point geometry type, with support for z-dimension and m-values.
Interface for Triangulation classes.
virtual bool calcNormal(double x, double y, QgsPoint &result)=0
Calculates the normal at a point on the surface and assigns it to 'result'.
virtual QgsMesh triangulationToMesh(QgsFeedback *feedback=nullptr) const =0
Returns a QgsMesh corresponding to the triangulation.
virtual void eliminateHorizontalTriangles()=0
Eliminates the horizontal triangles by swapping.
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)
virtual int pointsCount() const =0
Returns the number of points.
ForcedCrossBehavior
Enumeration describing the behavior, if two forced lines cross.
@ DeleteFirst
The status of the first inserted forced line is reset to that of a normal edge (so that the second in...
virtual bool saveTriangulation(QgsFeatureSink *sink, QgsFeedback *feedback=nullptr) const =0
Saves the triangulation features to a feature sink.
virtual QgsPoint * point(int i) const =0
Returns a pointer to the point with number i.
virtual void addLine(const QgsPointSequence &points, QgsInterpolator::SourceType lineType)=0
Adds a line (e.g.
virtual QList< int > pointsAroundEdge(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 bool calcPoint(double x, double y, QgsPoint &result)=0
Calculates x-, y and z-value of the point on the surface and assigns it to 'result'.
virtual int oppositePoint(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...
virtual int addPoint(const QgsPoint &point)=0
Adds a point to the triangulation.
virtual bool swapEdge(double x, double y)=0
Reads the content of a taff-file.
virtual void setTriangleInterpolator(TriangleInterpolator *interpolator)=0
Sets an interpolator object.
virtual bool triangleVertices(double x, double y, QgsPoint &p1, int &n1, QgsPoint &p2, int &n2, QgsPoint &p3, int &n3)=0
Finds out in which triangle the point with coordinates x and y is and assigns the numbers of the vert...
virtual QList< int > surroundingTriangles(int pointno)=0
Returns a value list with the information of the triangles surrounding (counterclockwise) a point.
virtual void setForcedCrossBehavior(QgsTriangulation::ForcedCrossBehavior b)=0
Draws the points, edges and the forced lines.
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.
This is an interface for interpolator classes for triangulations.
Mesh - vertices, edges and faces.