QGIS API Documentation 3.29.0-Master (8c80f25a4f)
qgsdualedgetriangulation.h
Go to the documentation of this file.
1/**************************************************************************
2 QgsDualEdgeTriangulation.h - description
3 -------------------
4 copyright : (C) 2004 by Marco Hugentobler
6 ***************************************************************************/
7
8/***************************************************************************
9 * *
10 * This program is free software; you can redistribute it and/or modify *
11 * it under the terms of the GNU General Public License as published by *
12 * the Free Software Foundation; either version 2 of the License, or *
13 * (at your option) any later version. *
14 * *
15 ***************************************************************************/
16
17#ifndef DUALEDGETRIANGULATION_H
18#define DUALEDGETRIANGULATION_H
19
20#include <QVector>
21#include <QList>
22#include <QSet>
23#include <QColor>
24#include <QFile>
25#include <QTextStream>
26#include <QMessageBox>
27#include <QBuffer>
28#include <QStringList>
29#include <QCursor>
30
31#include <cfloat>
32
33#include "qgis_sip.h"
34#include "qgis_analysis.h"
35#include "qgspoint.h"
36
37#include "qgstriangulation.h"
38#include "HalfEdge.h"
39
40#define SIP_NO_FILE
41
49class ANALYSIS_EXPORT QgsDualEdgeTriangulation: public QgsTriangulation
50{
51 public:
54 QgsDualEdgeTriangulation( int nop );
56 void addLine( const QVector< QgsPoint > &points, QgsInterpolator::SourceType lineType ) override;
57 int addPoint( const QgsPoint &p ) override;
59 void performConsistencyTest() override;
61 bool calcNormal( double x, double y, QgsPoint &result SIP_OUT ) override;
62 bool calcPoint( double x, double y, QgsPoint &result SIP_OUT ) override;
64 //virtual void draw(QPainter* p, double xlowleft, double ylowleft, double xupright, double yupright, double width, double height) const;
66 QgsPoint *point( int i ) const override;
67 int oppositePoint( int p1, int p2 ) override;
68 bool triangleVertices( double x, double y, QgsPoint &p1 SIP_OUT, int &n1 SIP_OUT, QgsPoint &p2 SIP_OUT, int &n2 SIP_OUT, QgsPoint &p3 SIP_OUT, int &n3 SIP_OUT ) override;
69 bool triangleVertices( double x, double y, QgsPoint &p1 SIP_OUT, QgsPoint &p2 SIP_OUT, QgsPoint &p3 SIP_OUT ) override;
70 QList<int> surroundingTriangles( int pointno ) override;
72 double xMax() const override { return mXMax; }
74 double xMin() const override { return mXMin; }
76 double yMax() const override { return mYMax; }
78 double yMin() const override { return mYMin; }
80 int pointsCount() const override;
84 void setTriangleInterpolator( TriangleInterpolator *interpolator ) override;
86 void eliminateHorizontalTriangles() override;
88 void ruppertRefinement() override;
90 bool pointInside( double x, double y ) override;
92 bool swapEdge( double x, double y ) override;
94 QList<int> pointsAroundEdge( double x, double y ) override;
95
96 bool saveTriangulation( QgsFeatureSink *sink, QgsFeedback *feedback = nullptr ) const override;
97
98 virtual QgsMesh triangulationToMesh( QgsFeedback *feedback = nullptr ) const override;
99
100 private:
102 double mXMax = 0;
104 double mXMin = 0;
106 double mYMax = 0;
108 double mYMin = 0;
110 static const unsigned int DEFAULT_STORAGE_FOR_POINTS = 100000;
112 QVector<QgsPoint *> mPointVector;
114 static const unsigned int DEFAULT_STORAGE_FOR_HALF_EDGES = 300006;
116 QVector<HalfEdge *> mHalfEdge;
118 TriangleInterpolator *mTriangleInterpolator = nullptr;
122 unsigned int insertEdge( int dual, int next, int point, bool mbreak, bool forced );
124 int insertForcedSegment( int p1, int p2, QgsInterpolator::SourceType segmentType );
126 static const int MAX_BASE_ITERATIONS = 300000;
128 int baseEdgeOfPoint( int point );
129
137 int baseEdgeOfTriangle( const QgsPoint &point );
139 bool checkSwapRecursively( unsigned int edge, unsigned int recursiveDeep );
141 bool isEdgeNeedSwap( unsigned int edge ) const;
143 void doSwapRecursively( unsigned int edge, unsigned int recursiveDeep );
145 void doOnlySwap( unsigned int edge );
147 unsigned int mEdgeInside = 0;
149 int mEdgeOutside = -1;
151 unsigned int mEdgeWithPoint = 0;
153 unsigned int mUnstableEdge = 0;
155 int mTwiceInsPoint = 0;
157 bool swapPossible( unsigned int edge ) const;
159 void triangulatePolygon( QList<int> *poly, QList<int> *free, int mainedge );
161 bool halfEdgeBBoxTest( int edge, double xlowleft, double ylowleft, double xupright, double yupright ) const;
163 double swapMinAngle( int edge ) const;
165 int splitHalfEdge( int edge, float position );
167 bool edgeOnConvexHull( int edge );
169 void evaluateInfluenceRegion( QgsPoint *point, int edge, QSet<int> &set );
171 int mDimension = -1;
172
173 int firstEdgeOutSide();
174
175 void removeLastPoint();
176
177
178 friend class TestQgsInterpolator;
179};
180
181#ifndef SIP_RUN
182
184{
185 mPointVector.reserve( DEFAULT_STORAGE_FOR_POINTS );
186 mHalfEdge.reserve( DEFAULT_STORAGE_FOR_HALF_EDGES );
187}
188
190{
191 mPointVector.reserve( nop );
192 mHalfEdge.reserve( nop );
193}
194
196{
197 return mPointVector.count();
198}
199
201{
202 if ( i < 0 || i >= mPointVector.count() )
203 return nullptr;
204
205 return mPointVector.at( i );
206}
207
208inline bool QgsDualEdgeTriangulation::halfEdgeBBoxTest( int edge, double xlowleft, double ylowleft, double xupright, double yupright ) const
209{
210 return (
211 ( point( mHalfEdge[edge]->getPoint() )->x() >= xlowleft &&
212 point( mHalfEdge[edge]->getPoint() )->x() <= xupright &&
213 point( mHalfEdge[edge]->getPoint() )->y() >= ylowleft &&
214 point( mHalfEdge[edge]->getPoint() )->y() <= yupright ) ||
215 ( point( mHalfEdge[mHalfEdge[edge]->getDual()]->getPoint() )->x() >= xlowleft &&
216 point( mHalfEdge[mHalfEdge[edge]->getDual()]->getPoint() )->x() <= xupright &&
217 point( mHalfEdge[mHalfEdge[edge]->getDual()]->getPoint() )->y() >= ylowleft &&
218 point( mHalfEdge[mHalfEdge[edge]->getDual()]->getPoint() )->y() <= yupright )
219 );
220}
221
222#endif
223#endif
224
225
226
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.
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.
Definition: qgsfeedback.h:45
SourceType
Describes the type of input data.
Point geometry type, with support for z-dimension and m-values.
Definition: qgspoint.h:49
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.
#define SIP_OUT
Definition: qgis_sip.h:58
Mesh - vertices, edges and faces.