Add QgsCurve::indexOf to retrieve index of a specified QgsPoint

within the curve
qgis · Apr 27, 2021 · 729792d · 729792d
1 parent 6f8af4d
commit 729792d
Show file tree

Hide file tree

Showing 12 changed files with 190 additions and 0 deletions.
diff --git a/python/core/auto_generated/geometry/qgscircularstring.sip.in b/python/core/auto_generated/geometry/qgscircularstring.sip.in
@@ -87,6 +87,7 @@ to ``p2`` will be used (i.e. winding the other way around the circle).
 
     virtual int numPoints() const /HoldGIL/;
 
+    int indexOf( const QgsPoint &point ) const final;
 
     QgsPoint pointN( int i ) const /HoldGIL/;
 %Docstring

diff --git a/python/core/auto_generated/geometry/qgscompoundcurve.sip.in b/python/core/auto_generated/geometry/qgscompoundcurve.sip.in
@@ -67,6 +67,7 @@ Compound curve geometry type
 
     virtual bool isValid( QString &error /Out/, int flags = 0 ) const;
 
+    int indexOf( const QgsPoint &point ) const final;
 
     virtual QgsLineString *curveToLine( double tolerance = M_PI_2 / 90, SegmentationToleranceType toleranceType = MaximumAngle ) const /Factory/;
 

diff --git a/python/core/auto_generated/geometry/qgscurve.sip.in b/python/core/auto_generated/geometry/qgscurve.sip.in
@@ -142,6 +142,23 @@ Returns the point and vertex id of a point within the curve.
          - type: will be set to the vertex type of the node
 %End
 
+    virtual int indexOf( const QgsPoint &point ) const = 0;
+%Docstring
+Returns the index of the first vertex matching the given ``point``, or -1 if a matching
+vertex is not found.
+
+.. note::
+
+   If the curve has m or z values then the search ``point`` must have exactly matching
+   m and z values in order to be matched against the curve's vertices.
+
+.. note::
+
+   This method only matches against segment vertices, not curve vertices.
+
+.. versionadded:: 3.20
+%End
+
     virtual QgsCurve *reversed() const = 0 /Factory/;
 %Docstring
 Returns a reversed copy of the curve, where the direction of the curve has been flipped.

diff --git a/python/core/auto_generated/geometry/qgslinestring.sip.in b/python/core/auto_generated/geometry/qgslinestring.sip.in
@@ -416,6 +416,7 @@ segment in the line.
 
     virtual bool isEmpty() const /HoldGIL/;
 
+    int indexOf( const QgsPoint &point ) const final;
     virtual bool isValid( QString &error /Out/, int flags = 0 ) const;
 
     virtual QgsLineString *snappedToGrid( double hSpacing, double vSpacing, double dSpacing = 0, double mSpacing = 0 ) const /Factory/;

diff --git a/src/core/geometry/qgscircularstring.cpp b/src/core/geometry/qgscircularstring.cpp
@@ -529,6 +529,46 @@ int QgsCircularString::numPoints() const
   return std::min( mX.size(), mY.size() );
 }
 
+int QgsCircularString::indexOf( const QgsPoint &point ) const
+{
+  const int size = mX.size();
+  if ( size == 0 )
+    return -1;
+
+  const double *x = mX.constData();
+  const double *y = mY.constData();
+  const bool useZ = is3D();
+  const bool useM = isMeasure();
+  const double *z = useZ ? mZ.constData() : nullptr;
+  const double *m = useM ? mM.constData() : nullptr;
+
+  for ( int i = 0; i < size; i += 2 )
+  {
+    if ( qgsDoubleNear( *x, point.x() )
+         && qgsDoubleNear( *y, point.y() )
+         && ( !useZ || qgsDoubleNear( *z, point.z() ) )
+         && ( !useM || qgsDoubleNear( *m, point.m() ) ) )
+      return i;
+
+    // we skip over curve points!
+    x++;
+    x++;
+    y++;
+    y++;
+    if ( useZ )
+    {
+      z++;
+      z++;
+    }
+    if ( useM )
+    {
+      m++;
+      m++;
+    }
+  }
+  return -1;
+}
+
 QgsPoint QgsCircularString::pointN( int i ) const
 {
   if ( i < 0 || std::min( mX.size(), mY.size() ) <= i )

diff --git a/src/core/geometry/qgscircularstring.h b/src/core/geometry/qgscircularstring.h
@@ -84,6 +84,7 @@ class CORE_EXPORT QgsCircularString: public QgsCurve
     bool isEmpty() const override SIP_HOLDGIL;
     bool isValid( QString &error SIP_OUT, int flags = 0 ) const override;
     int numPoints() const override SIP_HOLDGIL;
+    int indexOf( const QgsPoint &point ) const final;
 
     /**
      * Returns the point at index i within the circular string.

diff --git a/src/core/geometry/qgscompoundcurve.cpp b/src/core/geometry/qgscompoundcurve.cpp
@@ -405,6 +405,21 @@ bool QgsCompoundCurve::isValid( QString &error, int flags ) const
   return QgsCurve::isValid( error, flags );
 }
 
+int QgsCompoundCurve::indexOf( const QgsPoint &point ) const
+{
+  int curveStart = 0;
+  for ( const QgsCurve *curve : mCurves )
+  {
+    const int curveIndex = curve->indexOf( point );
+    if ( curveIndex >= 0 )
+      return curveStart + curveIndex;
+    // subtract 1 here, because the next curve will start with the same
+    // vertex as this curve ended at
+    curveStart += curve->numPoints() - 1;
+  }
+  return -1;
+}
+
 QgsLineString *QgsCompoundCurve::curveToLine( double tolerance, SegmentationToleranceType toleranceType ) const
 {
   QgsLineString *line = new QgsLineString();

diff --git a/src/core/geometry/qgscompoundcurve.h b/src/core/geometry/qgscompoundcurve.h
@@ -61,6 +61,7 @@ class CORE_EXPORT QgsCompoundCurve: public QgsCurve
     int numPoints() const override SIP_HOLDGIL;
     bool isEmpty() const override SIP_HOLDGIL;
     bool isValid( QString &error SIP_OUT, int flags = 0 ) const override;
+    int indexOf( const QgsPoint &point ) const final;
 
     /**
      * Returns a new line string geometry corresponding to a segmentized approximation

diff --git a/src/core/geometry/qgscurve.h b/src/core/geometry/qgscurve.h
@@ -142,6 +142,18 @@ class CORE_EXPORT QgsCurve: public QgsAbstractGeometry
      */
     virtual bool pointAt( int node, QgsPoint &point SIP_OUT, QgsVertexId::VertexType &type SIP_OUT ) const = 0;
 
+    /**
+     * Returns the index of the first vertex matching the given \a point, or -1 if a matching
+     * vertex is not found.
+     *
+     * \note If the curve has m or z values then the search \a point must have exactly matching
+     * m and z values in order to be matched against the curve's vertices.
+     * \note This method only matches against segment vertices, not curve vertices.
+     *
+     * \since QGIS 3.20
+     */
+    virtual int indexOf( const QgsPoint &point ) const = 0;
+
     /**
      * Returns a reversed copy of the curve, where the direction of the curve has been flipped.
      * \since QGIS 2.14

diff --git a/src/core/geometry/qgslinestring.cpp b/src/core/geometry/qgslinestring.cpp
@@ -312,6 +312,37 @@ bool QgsLineString::isEmpty() const
   return mX.isEmpty();
 }
 
+int QgsLineString::indexOf( const QgsPoint &point ) const
+{
+  const int size = mX.size();
+  if ( size == 0 )
+    return -1;
+
+  const double *x = mX.constData();
+  const double *y = mY.constData();
+  const bool useZ = is3D();
+  const bool useM = isMeasure();
+  const double *z = useZ ? mZ.constData() : nullptr;
+  const double *m = useM ? mM.constData() : nullptr;
+
+  for ( int i = 0; i < size; ++i )
+  {
+    if ( qgsDoubleNear( *x, point.x() )
+         && qgsDoubleNear( *y, point.y() )
+         && ( !useZ || qgsDoubleNear( *z, point.z() ) )
+         && ( !useM || qgsDoubleNear( *m, point.m() ) ) )
+      return i;
+
+    x++;
+    y++;
+    if ( useZ )
+      z++;
+    if ( useM )
+      m++;
+  }
+  return -1;
+}
+
 bool QgsLineString::isValid( QString &error, int flags ) const
 {
   if ( !isEmpty() && ( numPoints() < 2 ) )

diff --git a/src/core/geometry/qgslinestring.h b/src/core/geometry/qgslinestring.h
@@ -587,6 +587,7 @@ class CORE_EXPORT QgsLineString: public QgsCurve
     QgsLineString *clone() const override SIP_FACTORY;
     void clear() override;
     bool isEmpty() const override SIP_HOLDGIL;
+    int indexOf( const QgsPoint &point ) const final;
     bool isValid( QString &error SIP_OUT, int flags = 0 ) const override;
     QgsLineString *snappedToGrid( double hSpacing, double vSpacing, double dSpacing = 0, double mSpacing = 0 ) const override SIP_FACTORY;
     bool removeDuplicateNodes( double epsilon = 4 * std::numeric_limits<double>::epsilon(), bool useZValues = false ) override;

diff --git a/tests/src/core/testqgsgeometry.cpp b/tests/src/core/testqgsgeometry.cpp
@@ -140,6 +140,9 @@ class TestQgsGeometry : public QObject
     void multiPolygon();
     void geometryCollection();
 
+    void curveIndexOf_data();
+    void curveIndexOf();
+
     void fromQgsPointXY();
     void fromQPoint();
     void fromQPolygonF();
@@ -16882,6 +16885,72 @@ void TestQgsGeometry::geometryCollection()
   QVERIFY( !transformCollect2.transform( &failTransformer ) );
 }
 
+void TestQgsGeometry::curveIndexOf_data()
+{
+  QTest::addColumn<QString>( "curve" );
+  QTest::addColumn<QString>( "point" );
+  QTest::addColumn<int>( "expected" );
+
+  QTest::newRow( "linestring empty" ) << QStringLiteral( "LINESTRING()" ) << QStringLiteral( "Point( 1 2 )" ) << -1;
+  QTest::newRow( "linestring one point no match" ) << QStringLiteral( "LINESTRING( 1 3 )" ) << QStringLiteral( "Point( 1 2 )" ) << -1;
+  QTest::newRow( "linestring one point match" ) << QStringLiteral( "LINESTRING( 1 2 )" ) << QStringLiteral( "Point( 1 2 )" ) << 0;
+  QTest::newRow( "linestring match 0" ) << QStringLiteral( "LINESTRING( 1 2, 2 3, 3 4)" ) << QStringLiteral( "Point( 1 2 )" ) << 0;
+  QTest::newRow( "linestring match 1" ) << QStringLiteral( "LINESTRING( 1 2, 2 3, 3 4)" ) << QStringLiteral( "Point( 2 3 )" ) << 1;
+  QTest::newRow( "linestring match 2" ) << QStringLiteral( "LINESTRING( 1 2, 2 3, 3 4)" ) << QStringLiteral( "Point( 3 4 )" ) << 2;
+  QTest::newRow( "linestring no match" ) << QStringLiteral( "LINESTRING( 1 2, 2 3, 3 4)" ) << QStringLiteral( "Point( 3 3 )" ) << -1;
+  QTest::newRow( "linestringz no match" ) << QStringLiteral( "LINESTRINGZ( 1 2 11, 2 3 12, 3 4 13)" ) << QStringLiteral( "PointZ( 2 3 11)" ) << -1;
+  QTest::newRow( "linestringz match" ) << QStringLiteral( "LINESTRINGZ( 1 2 11, 2 3 12, 3 4 13)" ) << QStringLiteral( "PointZ( 2 3 12)" ) << 1;
+  QTest::newRow( "linestringm no match" ) << QStringLiteral( "LINESTRINGM( 1 2 11, 2 3 12, 3 4 13)" ) << QStringLiteral( "PointM( 2 3 11)" ) << -1;
+  QTest::newRow( "linestringm match" ) << QStringLiteral( "LINESTRINGM( 1 2 11, 2 3 12, 3 4 13)" ) << QStringLiteral( "PointM( 2 3 12)" ) << 1;
+  QTest::newRow( "linestringzm no match z" ) << QStringLiteral( "LINESTRINGZM( 1 2 11 21, 2 3 12 22, 3 4 13 23)" ) << QStringLiteral( "PointM( 2 3 11 22)" ) << -1;
+  QTest::newRow( "linestringzm no match m" ) << QStringLiteral( "LINESTRINGZM( 1 2 11 21, 2 3 12 22, 3 4 13 23)" ) << QStringLiteral( "PointM( 2 3 12 23)" ) << -1;
+  QTest::newRow( "linestringzm match" ) << QStringLiteral( "LINESTRINGZM( 1 2 11 21, 2 3 12 22, 3 4 13 23)" ) << QStringLiteral( "PointZM( 2 3 12 22)" ) << 1;
+
+  QTest::newRow( "circularstring empty" ) << QStringLiteral( "CIRCULARSTRING()" ) << QStringLiteral( "Point( 1 2 )" ) << -1;
+  QTest::newRow( "circularstring match 0" ) << QStringLiteral( "CIRCULARSTRING( 1 2, 2 3, 3 4)" ) << QStringLiteral( "Point( 1 2 )" ) << 0;
+  // should not match -- we only consider segment points, not curve points
+  QTest::newRow( "circularstring match 1" ) << QStringLiteral( "CIRCULARSTRING( 1 2, 2 3, 3 4)" ) << QStringLiteral( "Point( 2 3 )" ) << -1;
+  QTest::newRow( "circularstring match 2" ) << QStringLiteral( "CIRCULARSTRING( 1 2, 2 3, 3 4)" ) << QStringLiteral( "Point( 3 4 )" ) << 2;
+  QTest::newRow( "circularstring no match" ) << QStringLiteral( "CIRCULARSTRING( 1 2, 2 3, 3 4)" ) << QStringLiteral( "Point( 3 3 )" ) << -1;
+  QTest::newRow( "circularstringz no match" ) << QStringLiteral( "CIRCULARSTRINGZ( 1 2 11, 2 3 12, 3 4 13)" ) << QStringLiteral( "PointZ( 3 4 12)" ) << -1;
+  QTest::newRow( "circularstringz match" ) << QStringLiteral( "CIRCULARSTRINGZ( 1 2 11, 2 3 12, 3 4 13)" ) << QStringLiteral( "PointZ( 3 4 13)" ) << 2;
+  QTest::newRow( "circularstringm no match" ) << QStringLiteral( "CIRCULARSTRINGM( 1 2 11, 2 3 12, 3 4 13)" ) << QStringLiteral( "PointM( 3 4 12)" ) << -1;
+  QTest::newRow( "circularstringm match" ) << QStringLiteral( "CIRCULARSTRINGM( 1 2 11, 2 3 12, 3 4 13)" ) << QStringLiteral( "PointM( 3 4 13)" ) << 2;
+  QTest::newRow( "circularstringzm no match z" ) << QStringLiteral( "CIRCULARSTRINGZM( 1 2 11 21, 2 3 12 22, 3 4 13 23)" ) << QStringLiteral( "PointM( 3 4 14 23)" ) << -1;
+  QTest::newRow( "circularstringzm no match m" ) << QStringLiteral( "CIRCULARSTRINGZM( 1 2 11 21, 2 3 12 22, 3 4 13 23)" ) << QStringLiteral( "PointM( 3 4 13 24)" ) << -1;
+  QTest::newRow( "circularstringzm match" ) << QStringLiteral( "CIRCULARSTRINGZM( 1 2 11 21, 2 3 12 22, 3 4 13 23)" ) << QStringLiteral( "PointZM( 3 4 13 23)" ) << 2;
+
+  QTest::newRow( "compound curve empty" ) << QStringLiteral( "COMPOUNDCURVE()" ) << QStringLiteral( "Point( 1 2 )" ) << -1;
+  QTest::newRow( "compound curve no match" ) << QStringLiteral( "COMPOUNDCURVE((1 1, 2 3, 3 4),(3 4, 5 6, 7 8))" ) << QStringLiteral( "Point( 1 21 )" ) << -1;
+  QTest::newRow( "compound curve match 0" ) << QStringLiteral( "COMPOUNDCURVE((1 1, 2 3, 3 4),(3 4, 5 6, 7 8))" ) << QStringLiteral( "Point( 1 1 )" ) << 0;
+  QTest::newRow( "compound curve match 1" ) << QStringLiteral( "COMPOUNDCURVE((1 1, 2 3, 3 4),(3 4, 5 6, 7 8))" ) << QStringLiteral( "Point( 2 3 )" ) << 1;
+  QTest::newRow( "compound curve match 2" ) << QStringLiteral( "COMPOUNDCURVE((1 1, 2 3, 3 4),(3 4, 5 6, 7 8))" ) << QStringLiteral( "Point( 3 4 )" ) << 2;
+  QTest::newRow( "compound curve match 3" ) << QStringLiteral( "COMPOUNDCURVE((1 1, 2 3, 3 4),(3 4, 5 6, 7 8))" ) << QStringLiteral( "Point( 5 6 )" ) << 3;
+  QTest::newRow( "compound curve match 4" ) << QStringLiteral( "COMPOUNDCURVE((1 1, 2 3, 3 4),(3 4, 5 6, 7 8))" ) << QStringLiteral( "Point( 7 8 )" ) << 4;
+  QTest::newRow( "compound curve match 5" ) << QStringLiteral( "COMPOUNDCURVE((1 1, 2 3, 3 4),(3 4, 5 6, 7 8),(7 8, 9 10))" ) << QStringLiteral( "Point( 9 10 )" ) << 5;
+  QTest::newRow( "compound curve circular string match" ) << QStringLiteral( "COMPOUNDCURVE((1 1, 2 3, 3 4),CIRCULARSTRING(3 4, 5 6, 7 8))" ) << QStringLiteral( "Point( 7 8 )" ) << 4;
+  QTest::newRow( "compound curve circular string no match" ) << QStringLiteral( "COMPOUNDCURVE((1 1, 2 3, 3 4),CIRCULARSTRING(3 4, 5 6, 7 8))" ) << QStringLiteral( "Point( 5 6 )" ) << -1;
+  QTest::newRow( "compound curve z match" ) << QStringLiteral( "COMPOUNDCURVEZ((1 1 11, 2 3 12, 3 4 13),(3 4 13, 5 6 14, 7 8 15))" ) << QStringLiteral( "PointZ( 7 8 15)" ) << 4;
+  QTest::newRow( "compound curve z nomatch" ) << QStringLiteral( "COMPOUNDCURVEZ((1 1 11, 2 3 12, 3 4 13),(3 4 13, 5 6 14, 7 8 15))" ) << QStringLiteral( "PointZ( 7 8 16)" ) << -1;
+  QTest::newRow( "compound curve m match" ) << QStringLiteral( "COMPOUNDCURVEM((1 1 11, 2 3 12, 3 4 13),(3 4 13, 5 6 14, 7 8 15))" ) << QStringLiteral( "PointM( 7 8 15)" ) << 4;
+  QTest::newRow( "compound curve m nomatch" ) << QStringLiteral( "COMPOUNDCURVEM((1 1 11, 2 3 12, 3 4 13),(3 4 13, 5 6 14, 7 8 15))" ) << QStringLiteral( "PointM( 7 8 16)" ) << -1;
+  QTest::newRow( "compound curve zm match" ) << QStringLiteral( "COMPOUNDCURVEZM((1 1 11 22, 2 3 12 23, 3 4 13 24),(3 4 13 24, 5 6 14 25, 7 8 15 26))" ) << QStringLiteral( "PointZM( 7 8 15 26)" ) << 4;
+  QTest::newRow( "compound curve zm nomatch z" ) << QStringLiteral( "COMPOUNDCURVEZM((1 1 11 22, 2 3 12 23, 3 4 13 24),(3 4 13 24, 5 6 14 25, 7 8 15 26))" ) << QStringLiteral( "PointZM( 7 8 16 26)" ) << -1;
+  QTest::newRow( "compound curve zm nomatch m" ) << QStringLiteral( "COMPOUNDCURVEZM((1 1 11 22, 2 3 12 23, 3 4 13 24),(3 4 13 24, 5 6 14 25, 7 8 15 26))" ) << QStringLiteral( "PointZM( 7 8 15 27)" ) << -1;
+}
+
+void TestQgsGeometry::curveIndexOf()
+{
+  QFETCH( QString, curve );
+  QFETCH( QString, point );
+  QFETCH( int, expected );
+
+  QgsGeometry g = QgsGeometry::fromWkt( curve );
+  QgsPoint p;
+  p.fromWkt( point );
+  QCOMPARE( qgsgeometry_cast< const QgsCurve * >( g.constGet() )->indexOf( p ), expected );
+}
+
 void TestQgsGeometry::fromQgsPointXY()
 {
   QgsPointXY point( 1.0, 2.0 );