Skip to content

Instantly share code, notes, and snippets.

@jackgris
Created April 15, 2014 17:35
Show Gist options
  • Save jackgris/10750896 to your computer and use it in GitHub Desktop.
Save jackgris/10750896 to your computer and use it in GitHub Desktop.
Hausdorff distance, calculating similar polygons
/**
* This method will be used to calculate the Hausdorff distance
*
* @param distanceMax this is the value of the maximum distance to compare
* @param routeOne this is one of the routes to compare
* @param routeTwo this is one of the routes to compare
* @return returns true if the value of the maximum distance is not exceeded, false otherwise
*/
public boolean distanceHausdorff(final int distanceMax, LinkedList<Posicion> routeOne,
LinkedList<Posicion> routeTwo) {
int maxDistAB = distanceCalc(routeOne, routeTwo);
int maxDistBA = distanceCalc(routeTwo, routeOne);
int maxDist = Math.max(maxDistAB, maxDistBA);
return Math.sqrt((double)maxDist) < distanceMax;
}
/*
* This method is a helper to calculate the distance
*/
private int distanceCalc(final LinkedList<Posicion> a, final LinkedList<Posicion> b)
{
int maxDistAB = 0;
for (Posicion posicionOne : a){
int minB = 1000000;
for (Posicion posicionTwo : b){
int dx = (posicionOne.getX() - posicionTwo.getX());
int dy = (posicionOne.getY() - posicionTwo.getY());
int tmpDist = dx*dx + dy*dy;
if (tmpDist < minB){
minB = tmpDist;
}
if ( tmpDist == 0 ){
break; // can't be better than 0
}
}
maxDistAB += minB;
}
return maxDistAB;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////// COMMENTS ////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Need these imports
import java.util.LinkedList;
// The classe Posicion is a simple POJO, for example
public class Posicion {
private int x;
private int y;
Posicion(){
this.x = 0;
this.y = 0;
}
Posicion(int x, int y){
this.x = x;
this.y = y;
}
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment