GEOS
3.9.0dev

An algorithm for computing a distance metric which is an approximation to the Frechet Distance based on a discretization of the input geom::Geometry. More...
#include <DiscreteFrechetDistance.h>
Public Member Functions  
DiscreteFrechetDistance (const geom::Geometry &p_g0, const geom::Geometry &p_g1)  
void  setDensifyFraction (double dFrac) 
double  distance () 
const std::array < geom::Coordinate, 2 >  getCoordinates () const 
Static Public Member Functions  
static double  distance (const geom::Geometry &g0, const geom::Geometry &g1) 
static double  distance (const geom::Geometry &g0, const geom::Geometry &g1, double densifyFrac) 
An algorithm for computing a distance metric which is an approximation to the Frechet Distance based on a discretization of the input geom::Geometry.
The algorithm computes the Frechet distance restricted to discrete points for one of the geometries. The points can be either the vertices of the geometries (the default), or the geometries with line segments densified by a given fraction. Also determines two points of the Geometries which are separated by the computed distance.
This algorithm is an approximation to the standard Frechet distance. Specifically,
for all geometries a, b: DFD(a, b) >= FD(a, b)
The approximation can be made as close as needed by densifying the input geometries. In the limit, this value will approach the true Frechet distance:
DFD(A, B, densifyFactor) > FD(A, B) as densifyFactor > 0.0
The default approximation is exact or close enough for a large subset of useful cases.
The difference between DFD and FD is bounded by the length of the longest edge of the polygonal curves.
Fréchet distance sweep continuously along their respective curves and the direction of curves is significant. This makes a better measure of similarity than Hausdorff distance.
An example showing how different DHD and DFD are:
A = LINESTRING (0 0, 50 200, 100 0, 150 200, 200 0) B = LINESTRING (0 200, 200 150, 0 100, 200 50, 0 0) B' = LINESTRING (0 0, 200 50, 0 100, 200 150, 0 200)
DHD(A, B) = DHD(A, B') = 48.5071250072666 DFD(A, B) = 200 DFD(A, B') = 282.842712474619

inline 
Sets the fraction by which to densify each segment. Each segment will be (virtually) split into a number of equallength subsegments, whose fraction of the total length is closest to the given fraction.
dFrac 