Add Visvalingam simplification algorithm

qgis · May 25, 2016 · 7e1d142 · 7e1d142
1 parent 734b8b4
commit 7e1d142
Show file tree

Hide file tree

Showing 9 changed files with 509 additions and 1 deletion.
diff --git a/python/core/qgsmaptopixelgeometrysimplifier.sip b/python/core/qgsmaptopixelgeometrysimplifier.sip
@@ -9,6 +9,7 @@ class QgsMapToPixelSimplifier : QgsAbstractGeometrySimplifier
     {
       Distance    = 0, //!< The simplification uses the distance between points to remove duplicate points
       SnapToGrid  = 1, //!< The simplification uses a grid (similar to ST_SnapToGrid) to remove duplicate points
+      Visvalingam = 2, //!< The simplification gives each point in a line an importance weighting, so that least important points are removed first
     };
 
     QgsMapToPixelSimplifier( int simplifyFlags, double tolerance );

diff --git a/python/core/qgsvectorsimplifymethod.sip b/python/core/qgsvectorsimplifymethod.sip
@@ -34,6 +34,7 @@ class QgsVectorSimplifyMethod
     {
       Distance    = 0, //!< The simplification uses the distance between points to remove duplicate points
       SnapToGrid  = 1, //!< The simplification uses a grid (similar to ST_SnapToGrid) to remove duplicate points
+      Visvalingam = 2, //!< The simplification gives each point in a line an importance weighting, so that least important points are removed first
     };
 
     /** Sets the local simplification algorithm of the vector layer managed */

diff --git a/src/app/qgsoptions.cpp b/src/app/qgsoptions.cpp
@@ -616,6 +616,7 @@ QgsOptions::QgsOptions( QWidget *parent, Qt::WindowFlags fl )
   // Default local simplification algorithm
   mSimplifyAlgorithmComboBox->addItem( tr( "Distance" ), ( int )QgsVectorSimplifyMethod::Distance );
   mSimplifyAlgorithmComboBox->addItem( tr( "SnapToGrid" ), ( int )QgsVectorSimplifyMethod::SnapToGrid );
+  mSimplifyAlgorithmComboBox->addItem( tr( "Visvalingam" ), ( int )QgsVectorSimplifyMethod::Visvalingam );
   mSimplifyAlgorithmComboBox->setCurrentIndex( mSimplifyAlgorithmComboBox->findData( mSettings->value( "/qgis/simplifyAlgorithm", 0 ).toInt() ) );
 
   // Slightly awkard here at the settings value is true to use QImage,

diff --git a/src/app/qgsvectorlayerproperties.cpp b/src/app/qgsvectorlayerproperties.cpp
@@ -442,6 +442,7 @@ void QgsVectorLayerProperties::syncToLayer()
   // Default local simplification algorithm
   mSimplifyAlgorithmComboBox->addItem( tr( "Distance" ), ( int )QgsVectorSimplifyMethod::Distance );
   mSimplifyAlgorithmComboBox->addItem( tr( "SnapToGrid" ), ( int )QgsVectorSimplifyMethod::SnapToGrid );
+  mSimplifyAlgorithmComboBox->addItem( tr( "Visvalingam" ), ( int )QgsVectorSimplifyMethod::Visvalingam );
   mSimplifyAlgorithmComboBox->setCurrentIndex( mSimplifyAlgorithmComboBox->findData(( int )simplifyMethod.simplifyAlgorithm() ) );
 
   QStringList myScalesList = PROJECT_SCALES.split( ',' );

diff --git a/src/core/qgsmaptopixelgeometrysimplifier.cpp b/src/core/qgsmaptopixelgeometrysimplifier.cpp
@@ -44,7 +44,6 @@ float QgsMapToPixelSimplifier::calculateLengthSquared2D( double x1, double y1, d
   return ( vx * vx ) + ( vy * vy );
 }
 
-
 //! Returns whether the points belong to the same grid
 bool QgsMapToPixelSimplifier::equalSnapToGrid( double x1, double y1, double x2, double y2, double gridOriginX, double gridOriginY, float gridInverseSizeXY )
 {
@@ -79,6 +78,32 @@ inline static QgsRectangle calculateBoundingBox( QGis::WkbType wkbType, QgsConst
   return r;
 }
 
+//////////////////////////////////////////////////////////////////////////////////////////////
+// Helper simplification methods for Visvalingam method
+
+// It uses a refactored code of the liblwgeom implementation:
+// https://github.com/postgis/postgis/blob/svn-trunk/liblwgeom/effectivearea.h
+// https://github.com/postgis/postgis/blob/svn-trunk/liblwgeom/effectivearea.c
+
+#define LWDEBUG //
+#define LWDEBUGF //
+#define FP_MAX qMax
+#define FLAGS_GET_Z( flags ) ( ( flags ) & 0x01 )
+#define LW_MSG_MAXLEN 256
+#define lwalloc qgsMalloc
+#define lwfree qgsFree
+#define lwerror qWarning
+
+#include "simplify/effectivearea.h"
+#include "simplify/effectivearea.c"
+
+double* getPoint_internal( const POINTARRAY* inpts, int pointIndex )
+{
+  return inpts->pointlist + ( pointIndex * inpts->dimension );
+}
+
+//////////////////////////////////////////////////////////////////////////////////////////////
+
 //! Generalize the WKB-geometry using the BBOX of the original geometry
 static bool generalizeWkbGeometryByBoundingBox(
   QGis::WkbType wkbType,
@@ -248,6 +273,40 @@ bool QgsMapToPixelSimplifier::simplifyWkbGeometry(
         r.combineExtentWith( x, y );
       }
     }
+    else if ( simplifyAlgorithm == Visvalingam )
+    {
+      map2pixelTol *= map2pixelTol; //-> Use mappixelTol for 'Area' calculations.
+
+      POINTARRAY inpts;
+      inpts.pointlist = ( double* )( const unsigned char* )sourceWkbPtr;
+      inpts.dimension = QGis::wkbDimensions( wkbType );
+      inpts.npoints = numPoints;
+      inpts.flags = 0;
+
+      EFFECTIVE_AREAS* ea;
+      ea = initiate_effectivearea( &inpts );
+
+      int set_area = 0;
+      ptarray_calc_areas( ea, isaLinearRing ? 4 : 2, set_area, map2pixelTol );
+
+      for ( int i = 0; i < numPoints; ++i )
+      {
+        if ( ea->res_arealist[ i ] > map2pixelTol )
+        {
+          double* coord = getPoint_internal( &inpts, i );
+          x = coord[ 0 ];
+          y = coord[ 1 ];
+
+          targetWkbPtr << x << y;
+          lastX = x;
+          lastY = y;
+          numTargetPoints++;
+        }
+      }
+      destroy_effectivearea( ea );
+
+      sourceWkbPtr += numPoints * ( inpts.dimension * sizeof( double ) );
+    }
     else
     {
       map2pixelTol *= map2pixelTol; //-> Use mappixelTol for 'LengthSquare' calculations.

diff --git a/src/core/qgsmaptopixelgeometrysimplifier.h b/src/core/qgsmaptopixelgeometrysimplifier.h
@@ -37,6 +37,7 @@ class CORE_EXPORT QgsMapToPixelSimplifier : public QgsAbstractGeometrySimplifier
     {
       Distance    = 0, //!< The simplification uses the distance between points to remove duplicate points
       SnapToGrid  = 1, //!< The simplification uses a grid (similar to ST_SnapToGrid) to remove duplicate points
+      Visvalingam = 2, //!< The simplification gives each point in a line an importance weighting, so that least important points are removed first
     };
 
     QgsMapToPixelSimplifier( int simplifyFlags, double tolerance, SimplifyAlgorithm simplifyAlgorithm = Distance );

diff --git a/src/core/qgsvectorsimplifymethod.h b/src/core/qgsvectorsimplifymethod.h
@@ -47,6 +47,7 @@ class CORE_EXPORT QgsVectorSimplifyMethod
     {
       Distance    = 0, //!< The simplification uses the distance between points to remove duplicate points
       SnapToGrid  = 1, //!< The simplification uses a grid (similar to ST_SnapToGrid) to remove duplicate points
+      Visvalingam = 2, //!< The simplification gives each point in a line an importance weighting, so that least important points are removed first
     };
 
     /** Sets the local simplification algorithm of the vector layer managed */