QGIS API Documentation 3.41.0-Master (181b2f43d8e)
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
56
58 QgsDualEdgeTriangulation( int nop );
60 void addLine( const QVector< QgsPoint > &points, QgsInterpolator::SourceType lineType ) override;
61 int addPoint( const QgsPoint &p ) override;
63 void performConsistencyTest() override;
65 bool calcNormal( double x, double y, QgsPoint &result SIP_OUT ) override;
66 bool calcPoint( double x, double y, QgsPoint &result SIP_OUT ) override;
68 //virtual void draw(QPainter* p, double xlowleft, double ylowleft, double xupright, double yupright, double width, double height) const;
70 QgsPoint *point( int i ) const override;
71 int oppositePoint( int p1, int p2 ) override;
72 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;
73 bool triangleVertices( double x, double y, QgsPoint &p1 SIP_OUT, QgsPoint &p2 SIP_OUT, QgsPoint &p3 SIP_OUT ) override;
74 QList<int> surroundingTriangles( int pointno ) override;
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; }
84 int pointsCount() const override;
88 void setTriangleInterpolator( TriangleInterpolator *interpolator ) override;
90 void eliminateHorizontalTriangles() override;
92 void ruppertRefinement() override;
94 bool pointInside( double x, double y ) override;
96 bool swapEdge( double x, double y ) override;
98 QList<int> pointsAroundEdge( double x, double y ) override;
99
100 bool saveTriangulation( QgsFeatureSink *sink, QgsFeedback *feedback = nullptr ) const override;
101
102 virtual QgsMesh triangulationToMesh( QgsFeedback *feedback = nullptr ) const override;
103
104 private:
106 double mXMax = 0;
108 double mXMin = 0;
110 double mYMax = 0;
112 double mYMin = 0;
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;
122 TriangleInterpolator *mTriangleInterpolator = nullptr;
126 unsigned int insertEdge( int dual, int next, int point, bool mbreak, bool forced );
128 int insertForcedSegment( int p1, int p2, QgsInterpolator::SourceType segmentType );
130 static const int MAX_BASE_ITERATIONS = 300000;
132 int baseEdgeOfPoint( int point );
133
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 );
175 int mDimension = -1;
176
177 int firstEdgeOutSide();
178
179 void removeLastPoint();
180
181
182 friend class TestQgsInterpolator;
183};
184
185#ifndef SIP_RUN
186
188{
189 mPointVector.reserve( DEFAULT_STORAGE_FOR_POINTS );
190 mHalfEdge.reserve( DEFAULT_STORAGE_FOR_HALF_EDGES );
191}
192
194{
195 mPointVector.reserve( nop );
196 mHalfEdge.reserve( nop );
197}
198
200{
201 return mPointVector.count();
202}
203
205{
206 if ( i < 0 || i >= mPointVector.count() )
207 return nullptr;
208
209 return mPointVector.at( i );
210}
211
212inline bool QgsDualEdgeTriangulation::halfEdgeBBoxTest( int edge, double xlowleft, double ylowleft, double xupright, double yupright ) const
213{
214 return (
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 )
223 );
224}
225
226#endif
227#endif
228
229
230
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(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.
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.