qgsdualedgetriangulation.h

Go to the documentation of this file.

/**************************************************************************
                          QgsDualEdgeTriangulation.h  -  description
                             -------------------
    copyright            : (C) 2004 by Marco Hugentobler
    email                : [email protected]
 ***************************************************************************/
 
/***************************************************************************
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 ***************************************************************************/
 
#ifndef DUALEDGETRIANGULATION_H
#define DUALEDGETRIANGULATION_H
 
#include <cfloat>
 
#include "HalfEdge.h"
#include "qgis_analysis.h"
#include "qgis_sip.h"
#include "qgspoint.h"
#include "qgstriangulation.h"
 
#include <QBuffer>
#include <QColor>
#include <QCursor>
#include <QFile>
#include <QList>
#include <QMessageBox>
#include <QSet>
#include <QStringList>
#include <QTextStream>
#include <QVector>
 
#define SIP_NO_FILE

class ANALYSIS_EXPORT QgsDualEdgeTriangulation : public QgsTriangulation
{
  public:
    QgsDualEdgeTriangulation();
 
    QgsDualEdgeTriangulation( const QgsDualEdgeTriangulation & ) = delete;
    QgsDualEdgeTriangulation &operator=( const QgsDualEdgeTriangulation &other ) = delete;

    QgsDualEdgeTriangulation( int nop );
    ~QgsDualEdgeTriangulation() override;
    void addLine( const QVector<QgsPoint> &points, QgsInterpolator::SourceType lineType ) override;
    int addPoint( const QgsPoint &p ) override;
    void performConsistencyTest() override;
    bool calcNormal( double x, double y, QgsPoint &result SIP_OUT ) override;
    bool calcPoint( double x, double y, QgsPoint &result SIP_OUT ) override;
    //virtual void draw(QPainter* p, double xlowleft, double ylowleft, double xupright, double yupright, double width, double height) const;
    QgsPoint *point( int i ) const override;
    int oppositePoint( int p1, int p2 ) override;
    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;
    bool triangleVertices( double x, double y, QgsPoint &p1 SIP_OUT, QgsPoint &p2 SIP_OUT, QgsPoint &p3 SIP_OUT ) override;
    QList<int> surroundingTriangles( int pointno ) override;
    double xMax() const override { return mXMax; }
    double xMin() const override { return mXMin; }
    double yMax() const override { return mYMax; }
    double yMin() const override { return mYMin; }
    int pointsCount() const override;
    void setForcedCrossBehavior( QgsTriangulation::ForcedCrossBehavior b ) override;
    void setTriangleInterpolator( TriangleInterpolator *interpolator ) override;
    void eliminateHorizontalTriangles() override;
    void ruppertRefinement() override;
    bool pointInside( double x, double y ) override;
    bool swapEdge( double x, double y ) override;
    QList<int> pointsAroundEdge( double x, double y ) override;
 
    bool saveTriangulation( QgsFeatureSink *sink, QgsFeedback *feedback = nullptr ) const override;
 
    QgsMesh triangulationToMesh( QgsFeedback *feedback = nullptr ) const override;
 
  private:
    double mXMax = 0;
    double mXMin = 0;
    double mYMax = 0;
    double mYMin = 0;
    static const unsigned int DEFAULT_STORAGE_FOR_POINTS = 100000;
    QVector<QgsPoint *> mPointVector;
    static const unsigned int DEFAULT_STORAGE_FOR_HALF_EDGES = 300006;
    QVector<HalfEdge *> mHalfEdge;
    TriangleInterpolator *mTriangleInterpolator = nullptr;
    QgsTriangulation::ForcedCrossBehavior mForcedCrossBehavior = QgsTriangulation::ForcedCrossBehavior::DeleteFirst;
    unsigned int insertEdge( int dual, int next, int point, bool mbreak, bool forced );
    int insertForcedSegment( int p1, int p2, QgsInterpolator::SourceType segmentType );
    static const int MAX_BASE_ITERATIONS = 300000;
    int baseEdgeOfPoint( int point );

    int baseEdgeOfTriangle( const QgsPoint &point );
    bool checkSwapRecursively( unsigned int edge, unsigned int recursiveDeep );
    bool isEdgeNeedSwap( unsigned int edge ) const;
    void doSwapRecursively( unsigned int edge, unsigned int recursiveDeep );
    void doOnlySwap( unsigned int edge );
    unsigned int mEdgeInside = 0;
    int mEdgeOutside = -1;
    unsigned int mEdgeWithPoint = 0;
    unsigned int mUnstableEdge = 0;
    int mTwiceInsPoint = 0;
    bool swapPossible( unsigned int edge ) const;
    void triangulatePolygon( QList<int> *poly, QList<int> *free, int mainedge );
    bool halfEdgeBBoxTest( int edge, double xlowleft, double ylowleft, double xupright, double yupright ) const;
    double swapMinAngle( int edge ) const;
    int splitHalfEdge( int edge, float position );
    bool edgeOnConvexHull( int edge );
    void evaluateInfluenceRegion( QgsPoint *point, int edge, QSet<int> &set );
    int mDimension = -1;
 
    int firstEdgeOutSide();
 
    void removeLastPoint();
 
 
    friend class TestQgsInterpolator;
};
 
#ifndef SIP_RUN
 
inline QgsDualEdgeTriangulation::QgsDualEdgeTriangulation()
{
  mPointVector.reserve( DEFAULT_STORAGE_FOR_POINTS );
  mHalfEdge.reserve( DEFAULT_STORAGE_FOR_HALF_EDGES );
}
 
inline QgsDualEdgeTriangulation::QgsDualEdgeTriangulation( int nop )
{
  mPointVector.reserve( nop );
  mHalfEdge.reserve( nop );
}
 
inline int QgsDualEdgeTriangulation::pointsCount() const
{
  return mPointVector.count();
}
 
inline QgsPoint *QgsDualEdgeTriangulation::point( int i ) const
{
  if ( i < 0 || i >= mPointVector.count() )
    return nullptr;
 
  return mPointVector.at( i );
}
 
inline bool QgsDualEdgeTriangulation::halfEdgeBBoxTest( int edge, double xlowleft, double ylowleft, double xupright, double yupright ) const
{
  return (
    ( point( mHalfEdge[edge]->getPoint() )->x() >= xlowleft && point( mHalfEdge[edge]->getPoint() )->x() <= xupright && point( mHalfEdge[edge]->getPoint() )->y() >= ylowleft && point( mHalfEdge[edge]->getPoint() )->y() <= yupright ) || ( point( mHalfEdge[mHalfEdge[edge]->getDual()]->getPoint() )->x() >= xlowleft && point( mHalfEdge[mHalfEdge[edge]->getDual()]->getPoint() )->x() <= xupright && point( mHalfEdge[mHalfEdge[edge]->getDual()]->getPoint() )->y() >= ylowleft && point( mHalfEdge[mHalfEdge[edge]->getDual()]->getPoint() )->y() <= yupright )
  );
}
 
#endif
#endif