hausdorff is not symmetric - that should be added to the documentation
- Dominant language
- C++
- Stars
- 517
- Forks
- 232
- PR merge metrics
- No merged PRs in 30d
Description
The Hausdorff algorithm is not symmetrical and can give unexpected results.
SEE COMMENTS BELOW - we should fix the documentation.
Minimal case:
```
#include
namespace bg = boost::geometry;
template
double fixed_hausdorff(const Geometry& geometry1, const Geometry& geometry2)
{
return std::max(bg::discrete_hausdorff_distance(geometry1, geometry2),
bg::discrete_hausdorff_distance(geometry2, geometry1));
}
template
void test_case(Geometry const& p, Geometry const& q)
{
std::cout
<< "Frechet: " << boost::geometry::discrete_frechet_distance(p, q)
<< " Hausdorff: " << boost::geometry::discrete_hausdorff_distance(p, q)
<< " Hausdorff (q/p): " << boost::geometry::discrete_hausdorff_distance(q, p)
<< " Fixed Hausdorff: " << fixed_hausdorff(p, q)
<< std::endl;
}
int main()
{
using coordinate_type = double;
using point = boost::geometry::model::d2::point_xy;
using linestring = boost::geometry::model::linestring;
// Two lines consistently 0.1 apart
std::string const simplex1 = "LINESTRING(1.0 1.0, 2.0 1.0)";
std::string const simplex2 = "LINESTRING(1.0 1.1, 2.0 1.1)";
// With extra point in between
std::string const simplex3 = "LINESTRING(1.0 1.1, 1.5 1.1,2.0 1.1)";
// With a "spike"
std::string const simplex4 = "LINESTRING(1.0 1.1, 1.49 1.1, 1.5 2.5, 1.51 1.1, 2.0 1.1)";
test_case(bg::from_wkt(simplex1), bg::from_wkt(simplex2));
test_case(bg::from_wkt(simplex1), bg::from_wkt(simplex3));
test_case(bg::from_wkt(simplex1), bg::from_wkt(simplex4));
return 0;
}
```
It reports:
```
Frechet: 0.1 Hausdorff: 0.1 Hausdorff (q/p): 0.1 Fixed Hausdorff: 0.1
Frechet: 0.509902 Hausdorff: 0.1 Hausdorff (q/p): 0.509902 Fixed Hausdorff: 0.509902
Frechet: 1.58114 Hausdorff: 0.1 Hausdorff (q/p): 1.58114 Fixed Hausdorff: 1.58114
```
and you can see it is wrong. I verified it with another (non open source) version of Hausdorff and that gives the same result as here labeled as `Fixed` (also for other testcases).
The `fixed_hausdorff` presented here is probably not optimized. I only tested for linestrings.
The correct version is equal to Frechet, for these testcases (for others, obviously, it's not).
Contributor guide
Assessment
This issue has not been assessed yet.