DualEdgeTriangulation.h

Go to the documentation of this file.

/***************************************************************************
                          DualEdgeTriangulation.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 <QVector>
#include <QList>
#include <QSet>
#include <QColor>
#include <QFile>
#include <QTextStream>
#include <QMessageBox>
#include <QBuffer>
#include <QStringList>
#include <QCursor>

#include <cfloat>

#include "qgis_sip.h"
#include "qgis_analysis.h"
#include "qgspoint.h"

#include "Triangulation.h"
#include "HalfEdge.h"

#define SIP_NO_FILE

class ANALYSIS_EXPORT DualEdgeTriangulation: public Triangulation
{
  public:
    DualEdgeTriangulation();
    DualEdgeTriangulation( int nop, Triangulation *decorator );
    ~DualEdgeTriangulation() override;
    void setDecorator( Triangulation *d ) {mDecorator = d;}
    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, Vector3D *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 *getPoint( int i ) const override;
    int getOppositePoint( int p1, int p2 ) override;
    bool getTriangle( 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 ) SIP_PYNAME( getTriangleVertices ) override;
    bool getTriangle( double x, double y, QgsPoint &p1 SIP_OUT, QgsPoint &p2 SIP_OUT, QgsPoint &p3 SIP_OUT ) override;
    QList<int> getSurroundingTriangles( int pointno ) override;
    double getXMax() const override { return xMax; }
    double getXMin() const override { return xMin; }
    double getYMax() const override { return yMax; }
    double getYMin() const override { return yMin; }
    int getNumberOfPoints() const override;
    void setForcedCrossBehavior( Triangulation::ForcedCrossBehavior b ) override;
    void setEdgeColor( int r, int g, int b ) override;
    void setForcedEdgeColor( int r, int g, int b ) override;
    void setBreakEdgeColor( int r, int g, int b ) override;
    void setTriangleInterpolator( TriangleInterpolator *interpolator ) override;
    void eliminateHorizontalTriangles() override;
    void ruppertRefinement() override;
    bool pointInside( double x, double y ) override;
    //bool readFromTAFF(QString fileName);
    //bool saveToTAFF(QString fileName) const;
    bool swapEdge( double x, double y ) override;
    QList<int> *getPointsAroundEdge( double x, double y ) override;

    bool saveTriangulation( QgsFeatureSink *sink, QgsFeedback *feedback = nullptr ) const override;

  protected:
    double xMax = 0;
    double xMin = 0;
    double yMax = 0;
    double yMin = 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;
    Triangulation::ForcedCrossBehavior mForcedCrossBehavior = Triangulation::DeleteFirst;
    QColor mEdgeColor;
    QColor mForcedEdgeColor;
    QColor mBreakEdgeColor;
    Triangulation *mDecorator = nullptr;
    unsigned int insertEdge( int dual, int next, int point, bool mbreak, bool forced );
    int insertForcedSegment( int p1, int p2, QgsInterpolator::SourceType segmentType );
    //const static double leftOfTresh=0.00001;
    static const int MAX_BASE_ITERATIONS = 300000;
    int baseEdgeOfPoint( int point );
    int baseEdgeOfTriangle( const QgsPoint &point );
    bool checkSwap( unsigned int edge, unsigned int recursiveDeep );
    void doSwap( unsigned int edge, unsigned int recursiveDeep );
    void doOnlySwap( unsigned int edge );
    unsigned int mEdgeInside = 0;
    unsigned int mEdgeOutside = 0;
    unsigned int mEdgeWithPoint = 0;
    unsigned int mUnstableEdge = 0;
    int mTwiceInsPoint = 0;
    bool swapPossible( unsigned int edge );
    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 );

    friend class TestQgsInterpolator;
};

#ifndef SIP_RUN

inline DualEdgeTriangulation::DualEdgeTriangulation()
  : mEdgeColor( 0, 255, 0 )
  , mForcedEdgeColor( 0, 0, 255 )
  , mBreakEdgeColor( 100, 100, 0 )
  , mDecorator( this )
{
  mPointVector.reserve( DEFAULT_STORAGE_FOR_POINTS );
  mHalfEdge.reserve( DEFAULT_STORAGE_FOR_HALF_EDGES );
}

inline DualEdgeTriangulation::DualEdgeTriangulation( int nop, Triangulation *decorator )
  : mEdgeColor( 0, 255, 0 )
  , mForcedEdgeColor( 0, 0, 255 )
  , mBreakEdgeColor( 100, 100, 0 )
  , mDecorator( decorator ? decorator : this )
{
  mPointVector.reserve( nop );
  mHalfEdge.reserve( nop );
}

inline int DualEdgeTriangulation::getNumberOfPoints() const
{
  return mPointVector.count();
}

inline QgsPoint *DualEdgeTriangulation::getPoint( int i ) const
{
  if ( i < 0 || i >= mPointVector.count() )
    return nullptr;

  return mPointVector.at( i );
}

inline bool DualEdgeTriangulation::halfEdgeBBoxTest( int edge, double xlowleft, double ylowleft, double xupright, double yupright ) const
{
  return (
           ( getPoint( mHalfEdge[edge]->getPoint() )->x() >= xlowleft &&
             getPoint( mHalfEdge[edge]->getPoint() )->x() <= xupright &&
             getPoint( mHalfEdge[edge]->getPoint() )->y() >= ylowleft &&
             getPoint( mHalfEdge[edge]->getPoint() )->y() <= yupright ) ||
           ( getPoint( mHalfEdge[mHalfEdge[edge]->getDual()]->getPoint() )->x() >= xlowleft &&
             getPoint( mHalfEdge[mHalfEdge[edge]->getDual()]->getPoint() )->x() <= xupright &&
             getPoint( mHalfEdge[mHalfEdge[edge]->getDual()]->getPoint() )->y() >= ylowleft &&
             getPoint( mHalfEdge[mHalfEdge[edge]->getDual()]->getPoint() )->y() <= yupright )
         );
}

#endif
#endif