HausdorffSimilarityMeasure.java
/*
* Copyright (c) 2016 Vivid Solutions.
*
* All rights reserved. This program and the accompanying materials
* are made available under the terms of the Eclipse Public License 2.0
* and Eclipse Distribution License v. 1.0 which accompanies this distribution.
* The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
* and the Eclipse Distribution License is available at
*
* http://www.eclipse.org/org/documents/edl-v10.php.
*/
package org.locationtech.jts.algorithm.match;
import org.locationtech.jts.algorithm.distance.DiscreteHausdorffDistance;
import org.locationtech.jts.geom.Envelope;
import org.locationtech.jts.geom.Geometry;
/**
* Measures the degree of similarity between two {@link Geometry}s
* using the Hausdorff distance metric.
* The measure is normalized to lie in the range [0, 1].
* Higher measures indicate a great degree of similarity.
* <p>
* The measure is computed by computing the Hausdorff distance
* between the input geometries, and then normalizing
* this by dividing it by the diagonal distance across
* the envelope of the combined geometries.
*
* @author mbdavis
*
*/
public class HausdorffSimilarityMeasure
implements SimilarityMeasure
{
/*
public static double measure(Geometry a, Geometry b)
{
HausdorffSimilarityMeasure gv = new HausdorffSimilarityMeasure(a, b);
return gv.measure();
}
*/
public HausdorffSimilarityMeasure()
{
}
/*
* Densify a small amount to increase accuracy of Hausdorff distance
*/
private static final double DENSIFY_FRACTION = 0.25;
public double measure(Geometry g1, Geometry g2)
{
double distance = DiscreteHausdorffDistance.distance(g1, g2, DENSIFY_FRACTION);
if (distance == 0d) return 1d;
Envelope env = new Envelope(g1.getEnvelopeInternal());
env.expandToInclude(g2.getEnvelopeInternal());
double envSize = diagonalSize(env);
// normalize so that more similarity produces a measure closer to 1
double measure = 1 - distance / envSize;
//System.out.println("Hausdorff distance = " + distance + ", measure = " + measure);
return measure;
}
public static double diagonalSize(Envelope env)
{
if (env.isNull()) return 0.0;
double width = env.getWidth();
double hgt = env.getHeight();
return Math.sqrt(width * width + hgt * hgt);
}
}