Skip to content

Commit 133d58f

Browse files
nyalldawsonnyalldawson
authoredAug 31, 2017
Merge pull request #5089 from nyalldawson/hausdorff
Expose GEOS Hausdorff distance calculations to QgsGeometry, add expression function
·
ltr-3_40final-3_0_0
2 parents 4810c73 + c2f8a82 commit 133d58f

File tree

9 files changed

+418
-80
lines changed

9 files changed

+418
-80
lines changed
 

‎python/core/geometry/qgsgeometry.sip

Lines changed: 45 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -241,6 +241,47 @@ Returns true if WKB of the geometry is of WKBMulti* type
241241
:rtype: float
242242
%End
243243

244+
double hausdorffDistance( const QgsGeometry &geom ) const;
245+
%Docstring
246+
Returns the Hausdorff distance between this geometry and ``geom``. This is basically a measure of how similar or dissimilar 2 geometries are.
247+
248+
This algorithm is an approximation to the standard Hausdorff distance. This approximation is exact or close enough for a large
249+
subset of useful cases. Examples of these are:
250+
251+
- computing distance between Linestrings that are roughly parallel to each other,
252+
and roughly equal in length. This occurs in matching linear networks.
253+
- Testing similarity of geometries.
254+
255+
If the default approximate provided by this method is insufficient, use hausdorffDistanceDensify() instead.
256+
257+
In case of error -1 will be returned.
258+
259+
.. versionadded:: 3.0
260+
.. seealso:: hausdorffDistanceDensify()
261+
:rtype: float
262+
%End
263+
264+
double hausdorffDistanceDensify( const QgsGeometry &geom, double densifyFraction ) const;
265+
%Docstring
266+
Returns the Hausdorff distance between this geometry and ``geom``. This is basically a measure of how similar or dissimilar 2 geometries are.
267+
268+
This function accepts a ``densifyFraction`` argument. The function performs a segment
269+
densification before computing the discrete Hausdorff distance. The ``densifyFraction`` parameter
270+
sets the fraction by which to densify each segment. Each segment will be split into a
271+
number of equal-length subsegments, whose fraction of the total length is
272+
closest to the given fraction.
273+
274+
This method can be used when the default approximation provided by hausdorffDistance()
275+
is not sufficient. Decreasing the ``densifyFraction`` parameter will make the
276+
distance returned approach the true Hausdorff distance for the geometries.
277+
278+
In case of error -1 will be returned.
279+
280+
.. versionadded:: 3.0
281+
.. seealso:: hausdorffDistance()
282+
:rtype: float
283+
%End
284+
244285
QgsPointXY closestVertex( const QgsPointXY &point, int &atVertex /Out/, int &beforeVertex /Out/, int &afterVertex /Out/, double &sqrDist /Out/ ) const;
245286
%Docstring
246287
:rtype: QgsPointXY
@@ -1251,10 +1292,11 @@ Returns an extruded version of this geometry.
12511292
:rtype: int
12521293
%End
12531294

1254-
QString error() const;
1295+
QString lastError() const;
12551296
%Docstring
1256-
Returns an error string referring to an error that was produced
1257-
when this geometry was created.
1297+
Returns an error string referring to the last error encountered
1298+
either when this geometry was created or when an operation
1299+
was performed on the geometry.
12581300

12591301
.. versionadded:: 3.0
12601302
:rtype: str

‎resources/function_help/json/hausdorff_distance

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
{
2+
"name": "hausdorff_distance",
3+
"type": "function",
4+
"description": "Returns the Hausdorff distance between two geometries. This is basically a measure of how similar or dissimilar 2 geometries are, with a lower distance indicating more similar geometries.<br>The function can be executed with an optional densify fraction argument. If not specified, an appoximation to the standard Hausdorff distance is used. This approximation is exact or close enough for a large subset of useful cases. Examples of these are:<br><br><li>computing distance between Linestrings that are roughly parallel to each other, and roughly equal in length. This occurs in matching linear networks.</li><li>Testing similarity of geometries.</li><br><br>If the default approximate provided by this method is insufficient, specify the optional densify fraction argument. Specifying this argument performs a segment densification before computing the discrete Hausdorff distance. The parameter sets the fraction by which to densify each segment. Each segment will be split into a number of equal-length subsegments, whose fraction of the total length is closest to the given fraction. Decreasing the densify fraction parameter will make the distance returned approach the true Hausdorff distance for the geometries.",
5+
"arguments": [ {"arg":"geometry a","description":"a geometry"},
6+
{"arg":"geometry b","description":"a geometry"},
7+
{"arg":"densify_fraction","description":"densify fraction amount", "optional":true}],
8+
"examples": [ { "expression":"hausdorff_distance( geometry1:= geom_from_wkt('LINESTRING (0 0, 2 1)'),geometry2:=geom_from_wkt('LINESTRING (0 0, 2 0)'))", "returns":"2"},
9+
{ "expression":"hausdorff_distance( geom_from_wkt('LINESTRING (130 0, 0 0, 0 150)'),geom_from_wkt('LINESTRING (10 10, 10 150, 130 10)'))", "returns":"14.142135623"},
10+
{ "expression":"hausdorff_distance( geom_from_wkt('LINESTRING (130 0, 0 0, 0 150)'),geom_from_wkt('LINESTRING (10 10, 10 150, 130 10)'),0.5)", "returns":"70.0"}
11+
]
12+
}

‎src/core/expression/qgsexpressionfunction.cpp

Lines changed: 27 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -53,6 +53,7 @@ QVariant QgsExpressionFunction::run( QgsExpressionNode::NodeList *args, const Qg
5353
QVariantList argValues;
5454
if ( args )
5555
{
56+
int arg = 0;
5657
Q_FOREACH ( QgsExpressionNode *n, args->list() )
5758
{
5859
QVariant v;
@@ -65,10 +66,12 @@ QVariant QgsExpressionFunction::run( QgsExpressionNode::NodeList *args, const Qg
6566
{
6667
v = n->eval( parent, context );
6768
ENSURE_NO_EVAL_ERROR;
68-
if ( QgsExpressionUtils::isNull( v ) && !handlesNull() )
69+
bool defaultParamIsNull = mParameterList.count() > arg && mParameterList.at( arg ).optional() && !mParameterList.at( arg ).defaultValue().isValid();
70+
if ( QgsExpressionUtils::isNull( v ) && !defaultParamIsNull && !handlesNull() )
6971
return QVariant(); // all "normal" functions return NULL, when any QgsExpressionFunction::Parameter is NULL (so coalesce is abnormal)
7072
}
7173
argValues.append( v );
74+
arg++;
7275
}
7376
}
7477

@@ -2574,6 +2577,27 @@ static QVariant fcnDistance( const QVariantList &values, const QgsExpressionCont
25742577
QgsGeometry sGeom = QgsExpressionUtils::getGeometry( values.at( 1 ), parent );
25752578
return QVariant( fGeom.distance( sGeom ) );
25762579
}
2580+
2581+
static QVariant fcnHausdorffDistance( const QVariantList &values, const QgsExpressionContext *, QgsExpression *parent )
2582+
{
2583+
QgsGeometry g1 = QgsExpressionUtils::getGeometry( values.at( 0 ), parent );
2584+
QgsGeometry g2 = QgsExpressionUtils::getGeometry( values.at( 1 ), parent );
2585+
2586+
double res = -1;
2587+
if ( values.length() == 3 && values.at( 2 ).isValid() )
2588+
{
2589+
double densify = QgsExpressionUtils::getDoubleValue( values.at( 2 ), parent );
2590+
densify = qBound( 0.0, densify, 1.0 );
2591+
res = g1.hausdorffDistanceDensify( g2, densify );
2592+
}
2593+
else
2594+
{
2595+
res = g1.hausdorffDistance( g2 );
2596+
}
2597+
2598+
return res > -1 ? QVariant( res ) : QVariant();
2599+
}
2600+
25772601
static QVariant fcnIntersection( const QVariantList &values, const QgsExpressionContext *, QgsExpression *parent )
25782602
{
25792603
QgsGeometry fGeom = QgsExpressionUtils::getGeometry( values.at( 0 ), parent );
@@ -4113,6 +4137,8 @@ const QList<QgsExpressionFunction *> &QgsExpression::Functions()
41134137
<< new QgsStaticExpressionFunction( QStringLiteral( "convex_hull" ), 1, fcnConvexHull, QStringLiteral( "GeometryGroup" ), QString(), false, QSet<QString>(), false, QStringList() << QStringLiteral( "convexHull" ) )
41144138
<< new QgsStaticExpressionFunction( QStringLiteral( "difference" ), 2, fcnDifference, QStringLiteral( "GeometryGroup" ) )
41154139
<< new QgsStaticExpressionFunction( QStringLiteral( "distance" ), 2, fcnDistance, QStringLiteral( "GeometryGroup" ) )
4140+
<< new QgsStaticExpressionFunction( QStringLiteral( "hausdorff_distance" ), QgsExpressionFunction::ParameterList() << QgsExpressionFunction::Parameter( QStringLiteral( "geometry1" ) ) << QgsExpressionFunction::Parameter( QStringLiteral( "geometry2" ) )
4141+
<< QgsExpressionFunction::Parameter( QStringLiteral( "densify_fraction" ), true ), fcnHausdorffDistance, QStringLiteral( "GeometryGroup" ) )
41164142
<< new QgsStaticExpressionFunction( QStringLiteral( "intersection" ), 2, fcnIntersection, QStringLiteral( "GeometryGroup" ) )
41174143
<< new QgsStaticExpressionFunction( QStringLiteral( "sym_difference" ), 2, fcnSymDifference, QStringLiteral( "GeometryGroup" ), QString(), false, QSet<QString>(), false, QStringList() << QStringLiteral( "symDifference" ) )
41184144
<< new QgsStaticExpressionFunction( QStringLiteral( "combine" ), 2, fcnCombine, QStringLiteral( "GeometryGroup" ) )

‎src/core/geometry/qgsgeometry.cpp

Lines changed: 172 additions & 70 deletions
Large diffs are not rendered by default.

‎src/core/geometry/qgsgeometry.h

Lines changed: 46 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -271,6 +271,45 @@ class CORE_EXPORT QgsGeometry
271271
*/
272272
double distance( const QgsGeometry &geom ) const;
273273

274+
/**
275+
* Returns the Hausdorff distance between this geometry and \a geom. This is basically a measure of how similar or dissimilar 2 geometries are.
276+
*
277+
* This algorithm is an approximation to the standard Hausdorff distance. This approximation is exact or close enough for a large
278+
* subset of useful cases. Examples of these are:
279+
*
280+
* - computing distance between Linestrings that are roughly parallel to each other,
281+
* and roughly equal in length. This occurs in matching linear networks.
282+
* - Testing similarity of geometries.
283+
*
284+
* If the default approximate provided by this method is insufficient, use hausdorffDistanceDensify() instead.
285+
*
286+
* In case of error -1 will be returned.
287+
*
288+
* \since QGIS 3.0
289+
* \see hausdorffDistanceDensify()
290+
*/
291+
double hausdorffDistance( const QgsGeometry &geom ) const;
292+
293+
/**
294+
* Returns the Hausdorff distance between this geometry and \a geom. This is basically a measure of how similar or dissimilar 2 geometries are.
295+
*
296+
* This function accepts a \a densifyFraction argument. The function performs a segment
297+
* densification before computing the discrete Hausdorff distance. The \a densifyFraction parameter
298+
* sets the fraction by which to densify each segment. Each segment will be split into a
299+
* number of equal-length subsegments, whose fraction of the total length is
300+
* closest to the given fraction.
301+
*
302+
* This method can be used when the default approximation provided by hausdorffDistance()
303+
* is not sufficient. Decreasing the \a densifyFraction parameter will make the
304+
* distance returned approach the true Hausdorff distance for the geometries.
305+
*
306+
* In case of error -1 will be returned.
307+
*
308+
* \since QGIS 3.0
309+
* \see hausdorffDistance()
310+
*/
311+
double hausdorffDistanceDensify( const QgsGeometry &geom, double densifyFraction ) const;
312+
274313
/**
275314
* Returns the vertex closest to the given point, the corresponding vertex index, squared distance snap point / target point
276315
* and the indices of the vertices before and after the closest vertex.
@@ -1191,12 +1230,13 @@ class CORE_EXPORT QgsGeometry
11911230
int vertexNrFromVertexId( QgsVertexId i ) const;
11921231

11931232
/**
1194-
* Returns an error string referring to an error that was produced
1195-
* when this geometry was created.
1233+
* Returns an error string referring to the last error encountered
1234+
* either when this geometry was created or when an operation
1235+
* was performed on the geometry.
11961236
*
11971237
* \since QGIS 3.0
11981238
*/
1199-
QString error() const;
1239+
QString lastError() const;
12001240

12011241
/**
12021242
* Return GEOS context handle
@@ -1444,6 +1484,9 @@ class CORE_EXPORT QgsGeometry
14441484

14451485
QgsGeometryPrivate *d; //implicitly shared data pointer
14461486

1487+
//! Last error encountered
1488+
mutable QString mLastError;
1489+
14471490
void detach( bool cloneGeom = true ); //make sure mGeometry only referenced from this instance
14481491

14491492
static void convertToPolyline( const QgsPointSequence &input, QgsPolyline &output );

‎src/core/geometry/qgsgeos.cpp

Lines changed: 47 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -369,19 +369,63 @@ double QgsGeos::distance( const QgsAbstractGeometry *geom, QString *errorMsg ) c
369369
return distance;
370370
}
371371

372-
GEOSGeometry *otherGeosGeom = asGeos( geom, mPrecision );
372+
GEOSGeomScopedPtr otherGeosGeom( asGeos( geom, mPrecision ) );
373373
if ( !otherGeosGeom )
374374
{
375375
return distance;
376376
}
377377

378378
try
379379
{
380-
GEOSDistance_r( geosinit.ctxt, mGeos, otherGeosGeom, &distance );
380+
GEOSDistance_r( geosinit.ctxt, mGeos, otherGeosGeom.get(), &distance );
381381
}
382382
CATCH_GEOS_WITH_ERRMSG( -1.0 )
383383

384-
GEOSGeom_destroy_r( geosinit.ctxt, otherGeosGeom );
384+
return distance;
385+
}
386+
387+
double QgsGeos::hausdorffDistance( const QgsAbstractGeometry *geom, QString *errorMsg ) const
388+
{
389+
double distance = -1.0;
390+
if ( !mGeos )
391+
{
392+
return distance;
393+
}
394+
395+
GEOSGeomScopedPtr otherGeosGeom( asGeos( geom, mPrecision ) );
396+
if ( !otherGeosGeom )
397+
{
398+
return distance;
399+
}
400+
401+
try
402+
{
403+
GEOSHausdorffDistance_r( geosinit.ctxt, mGeos, otherGeosGeom.get(), &distance );
404+
}
405+
CATCH_GEOS_WITH_ERRMSG( -1.0 )
406+
407+
return distance;
408+
}
409+
410+
double QgsGeos::hausdorffDistanceDensify( const QgsAbstractGeometry *geom, double densifyFraction, QString *errorMsg ) const
411+
{
412+
double distance = -1.0;
413+
if ( !mGeos )
414+
{
415+
return distance;
416+
}
417+
418+
GEOSGeomScopedPtr otherGeosGeom( asGeos( geom, mPrecision ) );
419+
if ( !otherGeosGeom )
420+
{
421+
return distance;
422+
}
423+
424+
try
425+
{
426+
GEOSHausdorffDistanceDensify_r( geosinit.ctxt, mGeos, otherGeosGeom.get(), densifyFraction, &distance );
427+
}
428+
CATCH_GEOS_WITH_ERRMSG( -1.0 )
385429

386430
return distance;
387431
}

‎src/core/geometry/qgsgeos.h

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -84,6 +84,42 @@ class CORE_EXPORT QgsGeos: public QgsGeometryEngine
8484
QgsPoint *pointOnSurface( QString *errorMsg = nullptr ) const override;
8585
QgsAbstractGeometry *convexHull( QString *errorMsg = nullptr ) const override;
8686
double distance( const QgsAbstractGeometry *geom, QString *errorMsg = nullptr ) const override;
87+
88+
/**
89+
* Returns the Hausdorff distance between this geometry and \a geom. This is basically a measure of how similar or dissimilar 2 geometries are.
90+
*
91+
* This algorithm is an approximation to the standard Hausdorff distance. This approximation is exact or close enough for a large
92+
* subset of useful cases. Examples of these are:
93+
*
94+
* - computing distance between Linestrings that are roughly parallel to each other,
95+
* and roughly equal in length. This occurs in matching linear networks.
96+
* - Testing similarity of geometries.
97+
*
98+
* If the default approximate provided by this method is insufficient, use hausdorffDistanceDensify() instead.
99+
*
100+
* \since QGIS 3.0
101+
* \see hausdorffDistanceDensify()
102+
*/
103+
double hausdorffDistance( const QgsAbstractGeometry *geom, QString *errorMsg = nullptr ) const;
104+
105+
/**
106+
* Returns the Hausdorff distance between this geometry and \a geom. This is basically a measure of how similar or dissimilar 2 geometries are.
107+
*
108+
* This function accepts a \a densifyFraction argument. The function performs a segment
109+
* densification before computing the discrete Hausdorff distance. The \a densifyFraction parameter
110+
* sets the fraction by which to densify each segment. Each segment will be split into a
111+
* number of equal-length subsegments, whose fraction of the total length is
112+
* closest to the given fraction.
113+
*
114+
* This method can be used when the default approximation provided by hausdorffDistance()
115+
* is not sufficient. Decreasing the \a densifyFraction parameter will make the
116+
* distance returned approach the true Hausdorff distance for the geometries.
117+
*
118+
* \since QGIS 3.0
119+
* \see hausdorffDistance()
120+
*/
121+
double hausdorffDistanceDensify( const QgsAbstractGeometry *geom, double densifyFraction, QString *errorMsg = nullptr ) const;
122+
87123
bool intersects( const QgsAbstractGeometry *geom, QString *errorMsg = nullptr ) const override;
88124
bool touches( const QgsAbstractGeometry *geom, QString *errorMsg = nullptr ) const override;
89125
bool crosses( const QgsAbstractGeometry *geom, QString *errorMsg = nullptr ) const override;

‎tests/src/core/testqgsexpression.cpp

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -872,6 +872,11 @@ class TestQgsExpression: public QObject
872872
QTest::newRow( "smooth point" ) << "geom_to_wkt(smooth(geom_from_wkt('POINT(1 2)'),10))" << false << QVariant( "Point (1 2)" );
873873
QTest::newRow( "smooth line" ) << "geom_to_wkt(smooth(geometry:=geom_from_wkt('LineString(0 0, 5 0, 5 5)'),iterations:=1,offset:=0.2,min_length:=-1,max_angle:=180))" << false << QVariant( "LineString (0 0, 4 0, 5 1, 5 5)" );
874874
QTest::newRow( "transform invalid" ) << "transform(make_point(500,500),'EPSG:4326','EPSG:28356')" << false << QVariant();
875+
QTest::newRow( "hausdorff line to line" ) << " hausdorff_distance( geometry1:= geom_from_wkt('LINESTRING (0 0, 2 1)'),geometry2:=geom_from_wkt('LINESTRING (0 0, 2 0)'))" << false << QVariant( 1.0 );
876+
QTest::newRow( "hausdorff line to line default" ) << " round(hausdorff_distance( geom_from_wkt('LINESTRING (130 0, 0 0, 0 150)'),geom_from_wkt('LINESTRING (10 10, 10 150, 130 10)')))" << false << QVariant( 14 );
877+
QTest::newRow( "hausdorff line to line densify" ) << " round(hausdorff_distance( geom_from_wkt('LINESTRING (130 0, 0 0, 0 150)'),geom_from_wkt('LINESTRING (10 10, 10 150, 130 10)'),0.5))" << false << QVariant( 70 );
878+
QTest::newRow( "hausdorff not geom 1" ) << " hausdorff_distance( 'a',geom_from_wkt('LINESTRING (0 0, 2 0)'))" << true << QVariant();
879+
QTest::newRow( "hausdorff not geom 2" ) << " hausdorff_distance( geom_from_wkt('LINESTRING (0 0, 2 0)'), 'b')" << true << QVariant();
875880

876881
// string functions
877882
QTest::newRow( "lower" ) << "lower('HeLLo')" << false << QVariant( "hello" );

‎tests/src/python/test_qgsgeometry.py

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -4223,6 +4223,34 @@ def testClipped(self):
42234223
self.assertTrue(compareWkt(result, exp, 0.00001),
42244224
"clipped: mismatch Expected:\n{}\nGot:\n{}\n".format(exp, result))
42254225

4226+
def testHausdorff(self):
4227+
tests = [["POLYGON((0 0, 0 2, 1 2, 2 2, 2 0, 0 0))", "POLYGON((0.5 0.5, 0.5 2.5, 1.5 2.5, 2.5 2.5, 2.5 0.5, 0.5 0.5))", 0.707106781186548],
4228+
["LINESTRING (0 0, 2 1)", "LINESTRING (0 0, 2 0)", 1],
4229+
["LINESTRING (0 0, 2 0)", "LINESTRING (0 1, 1 2, 2 1)", 2],
4230+
["LINESTRING (0 0, 2 0)", "MULTIPOINT (0 1, 1 0, 2 1)", 1],
4231+
["LINESTRING (130 0, 0 0, 0 150)", "LINESTRING (10 10, 10 150, 130 10)", 14.142135623730951]
4232+
]
4233+
for t in tests:
4234+
g1 = QgsGeometry.fromWkt(t[0])
4235+
g2 = QgsGeometry.fromWkt(t[1])
4236+
o = g1.hausdorffDistance(g2)
4237+
exp = t[2]
4238+
self.assertAlmostEqual(o, exp, 5,
4239+
"mismatch for {} to {}, expected:\n{}\nGot:\n{}\n".format(t[0], t[1], exp, o))
4240+
4241+
def testHausdorffDensify(self):
4242+
tests = [
4243+
["LINESTRING (130 0, 0 0, 0 150)", "LINESTRING (10 10, 10 150, 130 10)", 0.5, 70.0]
4244+
]
4245+
for t in tests:
4246+
g1 = QgsGeometry.fromWkt(t[0])
4247+
g2 = QgsGeometry.fromWkt(t[1])
4248+
densify = t[2]
4249+
o = g1.hausdorffDistanceDensify(g2, densify)
4250+
exp = t[3]
4251+
self.assertAlmostEqual(o, exp, 5,
4252+
"mismatch for {} to {}, expected:\n{}\nGot:\n{}\n".format(t[0], t[1], exp, o))
4253+
42264254

42274255
if __name__ == '__main__':
42284256
unittest.main()

0 commit comments

Comments
 (0)
Please sign in to comment.