Skip to content

Commit

Permalink
Browse files Browse the repository at this point in the history
Merge pull request #5089 from nyalldawson/hausdorff
Expose GEOS Hausdorff distance calculations to QgsGeometry, add expression function
  • Loading branch information
nyalldawson committed Aug 31, 2017
2 parents 4810c73 + c2f8a82 commit 133d58f
Show file tree
Hide file tree
Showing 9 changed files with 418 additions and 80 deletions.
48 changes: 45 additions & 3 deletions python/core/geometry/qgsgeometry.sip
Expand Up @@ -241,6 +241,47 @@ Returns true if WKB of the geometry is of WKBMulti* type
:rtype: float
%End

double hausdorffDistance( const QgsGeometry &geom ) const;
%Docstring
Returns the Hausdorff distance between this geometry and ``geom``. This is basically a measure of how similar or dissimilar 2 geometries are.

This algorithm is an approximation to the standard Hausdorff distance. This approximation is exact or close enough for a large
subset of useful cases. Examples of these are:

- computing distance between Linestrings that are roughly parallel to each other,
and roughly equal in length. This occurs in matching linear networks.
- Testing similarity of geometries.

If the default approximate provided by this method is insufficient, use hausdorffDistanceDensify() instead.

In case of error -1 will be returned.

.. versionadded:: 3.0
.. seealso:: hausdorffDistanceDensify()
:rtype: float
%End

double hausdorffDistanceDensify( const QgsGeometry &geom, double densifyFraction ) const;
%Docstring
Returns the Hausdorff distance between this geometry and ``geom``. This is basically a measure of how similar or dissimilar 2 geometries are.

This function accepts a ``densifyFraction`` argument. The function performs a segment
densification before computing the discrete Hausdorff distance. The ``densifyFraction`` 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.

This method can be used when the default approximation provided by hausdorffDistance()
is not sufficient. Decreasing the ``densifyFraction`` parameter will make the
distance returned approach the true Hausdorff distance for the geometries.

In case of error -1 will be returned.

.. versionadded:: 3.0
.. seealso:: hausdorffDistance()
:rtype: float
%End

QgsPointXY closestVertex( const QgsPointXY &point, int &atVertex /Out/, int &beforeVertex /Out/, int &afterVertex /Out/, double &sqrDist /Out/ ) const;
%Docstring
:rtype: QgsPointXY
Expand Down Expand Up @@ -1251,10 +1292,11 @@ Returns an extruded version of this geometry.
:rtype: int
%End

QString error() const;
QString lastError() const;
%Docstring
Returns an error string referring to an error that was produced
when this geometry was created.
Returns an error string referring to the last error encountered
either when this geometry was created or when an operation
was performed on the geometry.

.. versionadded:: 3.0
:rtype: str
Expand Down
12 changes: 12 additions & 0 deletions resources/function_help/json/hausdorff_distance
@@ -0,0 +1,12 @@
{
"name": "hausdorff_distance",
"type": "function",
"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.",
"arguments": [ {"arg":"geometry a","description":"a geometry"},
{"arg":"geometry b","description":"a geometry"},
{"arg":"densify_fraction","description":"densify fraction amount", "optional":true}],
"examples": [ { "expression":"hausdorff_distance( geometry1:= geom_from_wkt('LINESTRING (0 0, 2 1)'),geometry2:=geom_from_wkt('LINESTRING (0 0, 2 0)'))", "returns":"2"},
{ "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"},
{ "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"}
]
}
28 changes: 27 additions & 1 deletion src/core/expression/qgsexpressionfunction.cpp
Expand Up @@ -53,6 +53,7 @@ QVariant QgsExpressionFunction::run( QgsExpressionNode::NodeList *args, const Qg
QVariantList argValues;
if ( args )
{
int arg = 0;
Q_FOREACH ( QgsExpressionNode *n, args->list() )
{
QVariant v;
Expand All @@ -65,10 +66,12 @@ QVariant QgsExpressionFunction::run( QgsExpressionNode::NodeList *args, const Qg
{
v = n->eval( parent, context );
ENSURE_NO_EVAL_ERROR;
if ( QgsExpressionUtils::isNull( v ) && !handlesNull() )
bool defaultParamIsNull = mParameterList.count() > arg && mParameterList.at( arg ).optional() && !mParameterList.at( arg ).defaultValue().isValid();
if ( QgsExpressionUtils::isNull( v ) && !defaultParamIsNull && !handlesNull() )
return QVariant(); // all "normal" functions return NULL, when any QgsExpressionFunction::Parameter is NULL (so coalesce is abnormal)
}
argValues.append( v );
arg++;
}
}

Expand Down Expand Up @@ -2574,6 +2577,27 @@ static QVariant fcnDistance( const QVariantList &values, const QgsExpressionCont
QgsGeometry sGeom = QgsExpressionUtils::getGeometry( values.at( 1 ), parent );
return QVariant( fGeom.distance( sGeom ) );
}

static QVariant fcnHausdorffDistance( const QVariantList &values, const QgsExpressionContext *, QgsExpression *parent )
{
QgsGeometry g1 = QgsExpressionUtils::getGeometry( values.at( 0 ), parent );
QgsGeometry g2 = QgsExpressionUtils::getGeometry( values.at( 1 ), parent );

double res = -1;
if ( values.length() == 3 && values.at( 2 ).isValid() )
{
double densify = QgsExpressionUtils::getDoubleValue( values.at( 2 ), parent );
densify = qBound( 0.0, densify, 1.0 );
res = g1.hausdorffDistanceDensify( g2, densify );
}
else
{
res = g1.hausdorffDistance( g2 );
}

return res > -1 ? QVariant( res ) : QVariant();
}

static QVariant fcnIntersection( const QVariantList &values, const QgsExpressionContext *, QgsExpression *parent )
{
QgsGeometry fGeom = QgsExpressionUtils::getGeometry( values.at( 0 ), parent );
Expand Down Expand Up @@ -4113,6 +4137,8 @@ const QList<QgsExpressionFunction *> &QgsExpression::Functions()
<< new QgsStaticExpressionFunction( QStringLiteral( "convex_hull" ), 1, fcnConvexHull, QStringLiteral( "GeometryGroup" ), QString(), false, QSet<QString>(), false, QStringList() << QStringLiteral( "convexHull" ) )
<< new QgsStaticExpressionFunction( QStringLiteral( "difference" ), 2, fcnDifference, QStringLiteral( "GeometryGroup" ) )
<< new QgsStaticExpressionFunction( QStringLiteral( "distance" ), 2, fcnDistance, QStringLiteral( "GeometryGroup" ) )
<< new QgsStaticExpressionFunction( QStringLiteral( "hausdorff_distance" ), QgsExpressionFunction::ParameterList() << QgsExpressionFunction::Parameter( QStringLiteral( "geometry1" ) ) << QgsExpressionFunction::Parameter( QStringLiteral( "geometry2" ) )
<< QgsExpressionFunction::Parameter( QStringLiteral( "densify_fraction" ), true ), fcnHausdorffDistance, QStringLiteral( "GeometryGroup" ) )
<< new QgsStaticExpressionFunction( QStringLiteral( "intersection" ), 2, fcnIntersection, QStringLiteral( "GeometryGroup" ) )
<< new QgsStaticExpressionFunction( QStringLiteral( "sym_difference" ), 2, fcnSymDifference, QStringLiteral( "GeometryGroup" ), QString(), false, QSet<QString>(), false, QStringList() << QStringLiteral( "symDifference" ) )
<< new QgsStaticExpressionFunction( QStringLiteral( "combine" ), 2, fcnCombine, QStringLiteral( "GeometryGroup" ) )
Expand Down

0 comments on commit 133d58f

Please sign in to comment.