boostorg / boostorg/geometry

hausdorff is not symmetric - that should be added to the documentation

Open
#1,171 2 comments 0 reactions 0 assignees View on GitHub
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.