Polyline Hausdorff

Pure python code to compute the Hausdorff distance between two polylines.

What is the Hausdorff distance between two polylines?

The Hausdorff distance between polylines is the length of the largest gap between them. It may be expressed more formally as the maximum minimum distance, i.e. the maximum of d(a→B) and d(b→A) for all points a and b on polylines A and B respectively.

How does this code differ from SciPy/Shapely?

The SciPy and Shapely libraries do not compute the true Hausdorff distances between polylines.

• SciPy's directed Hausdorff distance function computes the Hausdorff distance between two point sets. If given two polylines, it will compute the maximum distance between a vertex on one polyline and the nearest vertex on the other polyline.
• Shapely's Hausdorff distance function is not well documented, but our experiments have shown that it actually calculates the maximum minimum distance between a vertex on one polyline and any point on the other polyline.
• In contrast, the Polyline Hausdorff function computes the true Hausdorff distance, which is the maximum minimum distance between any point on one polyline and any point on the other polyline.

The following figure illustrates the difference between the SciPy, Shapely and Polyline Hausdorff distances:

How do I use the code?

Basic usage is illustrated in the file, illustration.py.

How does it work?

The code follows the general algorithm described in:

J.F. Hangouët (1995). Computation of the Hausdorff distance between plane vector polylines. Proceedings of the International Symposium on Computer-Assistated Cartography (AutoCarto XII).

The algorithm has been updated in several ways to ensure robustness and improve computational efficiency. Details on these improvements are currently being prepared for publication.

Current Status (updated Apr 2024)

This is still a working process. The code is functional but has not been cleaned, organized and documented so usage is not recommended except for research purposes.

Robustness

The code has been tested on several cases including coincident, overlapping and perpendicular line segments with random transformations to catch problems involving floating point precision arithmetic. It appears to be robust but further testing is warranted for production-level usage. C

Computational Efficiency

Computational efficiency has been improved with a "three-circle-filter" and is usually subquadratic but approaches cubic running time in the very unlikely worst case scenario.

Code Testing

Test functions are included for all subsidiary functions as well as the main function. To perform additional tests, add coordinates for pairs of polyines you wish to test to the case function in test_utils.py and then run test_polyline_hausdroff.py.

Who created this?

This code is being developed by Dr. Barry Kronenfeld at Eastern Illinois University with support from the USGS. However this repository has not been approved or endorsed by EIU or the USGS.

Much of the code for the Hausdorff distance calculation was developed by students in the Spring 2021 section of GEO 4910: GIS Programming at Eastern Illinois University. Team members are:

• Luke Jansen
• Tanner Jones
• Farouk Olaitan
• Megshi Thakur

Is this free to use?

Yes, it is licensed with the open source MIT License. If you find this useful, acknowledgement would be appreciated.