QGIS API Documentation 3.36.0-Maidenhead (09951dc0acf)
Loading...
Searching...
No Matches
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:
53
58
60 QgsDualEdgeTriangulation( int nop );
62 void addLine( const QVector< QgsPoint > &points, QgsInterpolator::SourceType lineType ) override;
63 int addPoint( const QgsPoint &p ) override;
65 void performConsistencyTest() override;
67 bool calcNormal( double x, double y, QgsPoint &result SIP_OUT ) override;
68 bool calcPoint( double x, double y, QgsPoint &result SIP_OUT ) override;
70 //virtual void draw(QPainter* p, double xlowleft, double ylowleft, double xupright, double yupright, double width, double height) const;
72 QgsPoint *point( int i ) const override;
73 int oppositePoint( int p1, int p2 ) override;
74 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;
75 bool triangleVertices( double x, double y, QgsPoint &p1 SIP_OUT, QgsPoint &p2 SIP_OUT, QgsPoint &p3 SIP_OUT ) override;
76 QList<int> surroundingTriangles( int pointno ) override;
78 double xMax() const override { return mXMax; }
80 double xMin() const override { return mXMin; }
82 double yMax() const override { return mYMax; }
84 double yMin() const override { return mYMin; }
86 int pointsCount() const override;
90 void setTriangleInterpolator( TriangleInterpolator *interpolator ) override;
92 void eliminateHorizontalTriangles() override;
94 void ruppertRefinement() override;
96 bool pointInside( double x, double y ) override;
98 bool swapEdge( double x, double y ) override;
100 QList<int> pointsAroundEdge( double x, double y ) override;
101
102 bool saveTriangulation( QgsFeatureSink *sink, QgsFeedback *feedback = nullptr ) const override;
103
104 virtual QgsMesh triangulationToMesh( QgsFeedback *feedback = nullptr ) const override;
105
106 private:
108 double mXMax = 0;
110 double mXMin = 0;
112 double mYMax = 0;
114 double mYMin = 0;
116 static const unsigned int DEFAULT_STORAGE_FOR_POINTS = 100000;
118 QVector<QgsPoint *> mPointVector;
120 static const unsigned int DEFAULT_STORAGE_FOR_HALF_EDGES = 300006;
122 QVector<HalfEdge *> mHalfEdge;
124 TriangleInterpolator *mTriangleInterpolator = nullptr;
128 unsigned int insertEdge( int dual, int next, int point, bool mbreak, bool forced );
130 int insertForcedSegment( int p1, int p2, QgsInterpolator::SourceType segmentType );
132 static const int MAX_BASE_ITERATIONS = 300000;
134 int baseEdgeOfPoint( int point );
135
143 int baseEdgeOfTriangle( const QgsPoint &point );
145 bool checkSwapRecursively( unsigned int edge, unsigned int recursiveDeep );
147 bool isEdgeNeedSwap( unsigned int edge ) const;
149 void doSwapRecursively( unsigned int edge, unsigned int recursiveDeep );
151 void doOnlySwap( unsigned int edge );
153 unsigned int mEdgeInside = 0;
155 int mEdgeOutside = -1;
157 unsigned int mEdgeWithPoint = 0;
159 unsigned int mUnstableEdge = 0;
161 int mTwiceInsPoint = 0;
163 bool swapPossible( unsigned int edge ) const;
165 void triangulatePolygon( QList<int> *poly, QList<int> *free, int mainedge );
167 bool halfEdgeBBoxTest( int edge, double xlowleft, double ylowleft, double xupright, double yupright ) const;
169 double swapMinAngle( int edge ) const;
171 int splitHalfEdge( int edge, float position );
173 bool edgeOnConvexHull( int edge );
175 void evaluateInfluenceRegion( QgsPoint *point, int edge, QSet<int> &set );
177 int mDimension = -1;
178
179 int firstEdgeOutSide();
180
181 void removeLastPoint();
182
183
184 friend class TestQgsInterpolator;
185};
186
187#ifndef SIP_RUN
188
190{
191 mPointVector.reserve( DEFAULT_STORAGE_FOR_POINTS );
192 mHalfEdge.reserve( DEFAULT_STORAGE_FOR_HALF_EDGES );
193}
194
196{
197 mPointVector.reserve( nop );
198 mHalfEdge.reserve( nop );
199}
200
202{
203 return mPointVector.count();
204}
205
207{
208 if ( i < 0 || i >= mPointVector.count() )
209 return nullptr;
210
211 return mPointVector.at( i );
212}
213
214inline bool QgsDualEdgeTriangulation::halfEdgeBBoxTest( int edge, double xlowleft, double ylowleft, double xupright, double yupright ) const
215{
216 return (
217 ( point( mHalfEdge[edge]->getPoint() )->x() >= xlowleft &&
218 point( mHalfEdge[edge]->getPoint() )->x() <= xupright &&
219 point( mHalfEdge[edge]->getPoint() )->y() >= ylowleft &&
220 point( mHalfEdge[edge]->getPoint() )->y() <= yupright ) ||
221 ( point( mHalfEdge[mHalfEdge[edge]->getDual()]->getPoint() )->x() >= xlowleft &&
222 point( mHalfEdge[mHalfEdge[edge]->getDual()]->getPoint() )->x() <= xupright &&
223 point( mHalfEdge[mHalfEdge[edge]->getDual()]->getPoint() )->y() >= ylowleft &&
224 point( mHalfEdge[mHalfEdge[edge]->getDual()]->getPoint() )->y() <= yupright )
225 );
226}
227
228#endif
229#endif
230
231
232
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 & operator=(const QgsDualEdgeTriangulation &other)=delete
QgsDualEdgeTriangulation cannot be copied.
QgsDualEdgeTriangulation(const QgsDualEdgeTriangulation &)=delete
QgsDualEdgeTriangulation cannot be copied.
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:44
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.