support also mesh elements with >4 vertices

qgis · Jan 23, 2019 · af2501e · af2501e
1 parent 928a559
commit af2501e
Show file tree

Hide file tree

Showing 4 changed files with 143 additions and 25 deletions.
diff --git a/src/core/mesh/qgstriangularmesh.cpp b/src/core/mesh/qgstriangularmesh.cpp
@@ -108,6 +108,26 @@ static void ENP_centroid( const QPolygonF &pX, double &cx, double &cy )
   cy /= ( 6.0 * signedArea );
 }
 
+void QgsTriangularMesh::triangulate( const QgsMeshFace &face, int nativeIndex )
+{
+  int vertexCount = face.size();
+  if ( vertexCount < 3 )
+    return;
+
+  while ( vertexCount > 3 )
+  {
+    // clip one ear from last 2 and first vertex
+    const QgsMeshFace ear = { face[vertexCount - 2], face[vertexCount - 1], face[0] };
+    mTriangularMesh.faces.push_back( ear );
+    mTrianglesToNativeFaces.push_back( nativeIndex );
+    --vertexCount;
+  }
+
+  const QgsMeshFace triangle = { face[1], face[2], face[0] };
+  mTriangularMesh.faces.push_back( triangle );
+  mTrianglesToNativeFaces.push_back( nativeIndex );
+}
+
 void QgsTriangularMesh::update( QgsMesh *nativeMesh, QgsRenderContext *context )
 {
   Q_ASSERT( nativeMesh );
@@ -159,31 +179,7 @@ void QgsTriangularMesh::update( QgsMesh *nativeMesh, QgsRenderContext *context )
   for ( int i = 0; i < nativeMesh->faces.size(); ++i )
   {
     const QgsMeshFace &face = nativeMesh->faces.at( i ) ;
-    if ( face.size() == 3 )
-    {
-      // triangle
-      mTriangularMesh.faces.push_back( face );
-      mTrianglesToNativeFaces.push_back( i );
-    }
-    else if ( face.size() == 4 )
-    {
-      // quad
-      QgsMeshFace face1;
-      face1.push_back( face[0] );
-      face1.push_back( face[1] );
-      face1.push_back( face[2] );
-
-      mTriangularMesh.faces.push_back( face1 );
-      mTrianglesToNativeFaces.push_back( i );
-
-      QgsMeshFace face2;
-      face2.push_back( face[0] );
-      face2.push_back( face[2] );
-      face2.push_back( face[3] );
-
-      mTriangularMesh.faces.push_back( face2 );
-      mTrianglesToNativeFaces.push_back( i );
-    }
+    triangulate( face, i );
   }
 
   // CALCULATE CENTROIDS

diff --git a/src/core/mesh/qgstriangularmesh.h b/src/core/mesh/qgstriangularmesh.h
@@ -129,6 +129,19 @@ class CORE_EXPORT QgsTriangularMesh
     QList<int> faceIndexesForRectangle( const QgsRectangle &rectangle ) const ;
 
   private:
+
+    /**
+     * Triangulates native face to triangles
+     *
+     * Triangulation does not create any new vertices and uses
+     * "Ear clipping method". Number of vertices in face is usually
+     * less than 10 and the faces are usually convex and without holes
+     *
+     * Skips the input face if it is not possible to triangulate
+     * with the given algorithm (e.g. only 2 vertices, polygon with holes)
+     */
+    void triangulate( const QgsMeshFace &face, int nativeIndex );
+
     // vertices: map CRS; 0-N ... native vertices, N+1 - len ... extra vertices
     // faces are derived triangles
     QgsMesh mTriangularMesh;
@@ -139,6 +152,8 @@ class CORE_EXPORT QgsTriangularMesh
 
     QgsSpatialIndex mSpatialIndex;
     QgsCoordinateTransform mCoordinateTransform; //coordinate transform used to convert native mesh vertices to map vertices
+
+    friend class TestQgsTriangularMesh;
 };
 
 namespace QgsMeshUtils

diff --git a/tests/src/core/CMakeLists.txt b/tests/src/core/CMakeLists.txt
@@ -200,6 +200,7 @@ SET(TESTS
  testqgssymbol.cpp
  testqgstaskmanager.cpp
  testqgstracer.cpp
+ testqgstriangularmesh.cpp
  testqgsfontutils.cpp
  testqgsvector.cpp
  testqgsvectordataprovider.cpp

diff --git a/tests/src/core/testqgstriangularmesh.cpp b/tests/src/core/testqgstriangularmesh.cpp
@@ -0,0 +1,106 @@
+/***************************************************************************
+                         testqgstriangularmesh.cpp
+                         -------------------------
+    begin                : January 2019
+    copyright            : (C) 2019 by Peter Petrik
+    email                : zilolv at gmail dot com
+ ***************************************************************************/
+
+/***************************************************************************
+ *                                                                         *
+ *   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.                                   *
+ *                                                                         *
+ ***************************************************************************/
+
+#include "qgstest.h"
+#include <QObject>
+#include <QString>
+
+//qgis includes...
+#include "qgstriangularmesh.h"
+#include "qgsapplication.h"
+#include "qgsproject.h"
+
+/**
+ * \ingroup UnitTests
+ * This is a unit test for a triangular mesh
+ */
+class TestQgsTriangularMesh : public QObject
+{
+    Q_OBJECT
+
+  public:
+    TestQgsTriangularMesh() = default;
+
+  private slots:
+    void initTestCase();// will be called before the first testfunction is executed.
+    void cleanupTestCase();// will be called after the last testfunction was executed.
+    void init() {} // will be called before each testfunction is executed.
+    void cleanup() {} // will be called after every testfunction.
+
+    void test_triangulate();
+};
+
+
+void TestQgsTriangularMesh::initTestCase()
+{
+  // init QGIS's paths - true means that all path will be inited from prefix
+  QgsApplication::init();
+  QgsApplication::initQgis();
+  QgsApplication::showSettings();
+}
+
+void TestQgsTriangularMesh::cleanupTestCase()
+{
+  QgsApplication::exitQgis();
+}
+
+void TestQgsTriangularMesh::test_triangulate()
+{
+  {
+    QgsTriangularMesh mesh;
+    QgsMeshFace point = { 1 };
+    mesh.triangulate( point, 0 );
+    QCOMPARE( 0, mesh.mTriangularMesh.faces.size() );
+  }
+
+  {
+    QgsTriangularMesh mesh;
+    QgsMeshFace line = { 1, 2 };
+    mesh.triangulate( line, 0 );
+    QCOMPARE( 0, mesh.mTriangularMesh.faces.size() );
+  }
+
+  {
+    QgsTriangularMesh mesh;
+    QgsMeshFace triangle = { 1, 2, 3 };
+    mesh.triangulate( triangle, 0 );
+    QCOMPARE( 1, mesh.mTriangularMesh.faces.size() );
+    QgsMeshFace firstTriangle = {2, 3, 1};
+    QCOMPARE( firstTriangle, mesh.mTriangularMesh.faces[0] );
+  }
+
+  {
+    QgsTriangularMesh mesh;
+    QgsMeshFace quad = { 1, 2, 3, 4 };
+    mesh.triangulate( quad, 0 );
+    QCOMPARE( 2, mesh.mTriangularMesh.faces.size() );
+    QgsMeshFace firstTriangle = {3, 4, 1};
+    QCOMPARE( firstTriangle, mesh.mTriangularMesh.faces[0] );
+    QgsMeshFace secondTriangle = {2, 3, 1};
+    QCOMPARE( secondTriangle, mesh.mTriangularMesh.faces[1] );
+  }
+
+  {
+    QgsTriangularMesh mesh;
+    QgsMeshFace poly = { 1, 2, 3, 4, 5, 6, 7 };
+    mesh.triangulate( poly, 0 );
+    QCOMPARE( 5, mesh.mTriangularMesh.faces.size() );
+  }
+}
+
+QGSTEST_MAIN( TestQgsTriangularMesh )
+#include "testqgstriangularmesh.moc"