geos::algorithm::distance::DiscreteFrechetDistance Class Reference

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>

Collaboration diagram for geos::algorithm::distance::DiscreteFrechetDistance:

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)

Private Member Functions
geom::Coordinate	getSegementAt (const geom::CoordinateSequence &seq, size_t index)
PointPairDistance &	getFrecheDistance (std::vector< std::vector< PointPairDistance > > &ca, size_t i, size_t j, const geom::CoordinateSequence &p, const geom::CoordinateSequence &q)
void	compute (const geom::Geometry &discreteGeom, const geom::Geometry &geom)
	DiscreteFrechetDistance (const DiscreteFrechetDistance &other)=delete
DiscreteFrechetDistance &	operator= (const DiscreteFrechetDistance &rhs)=delete

Private Attributes
const geom::Geometry &	g0
const geom::Geometry &	g1
PointPairDistance	ptDist
double	densifyFrac
	Value of 0.0 indicates that no densification should take place. More...

Detailed Description

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

Definition at line 106 of file DiscreteFrechetDistance.h.

Constructor & Destructor Documentation

geos::algorithm::distance::DiscreteFrechetDistance::DiscreteFrechetDistance ( const geom::Geometry &  p_g0, const geom::Geometry &  p_g1  )

inline

Definition at line 115 of file DiscreteFrechetDistance.h.

geos::algorithm::distance::DiscreteFrechetDistance::DiscreteFrechetDistance ( const DiscreteFrechetDistance &  other )

privatedelete

Member Function Documentation

void geos::algorithm::distance::DiscreteFrechetDistance::compute ( const geom::Geometry &  discreteGeom, const geom::Geometry &  geom  )

private

static double geos::algorithm::distance::DiscreteFrechetDistance::distance ( const geom::Geometry &  g0, const geom::Geometry &  g1  )

static

static double geos::algorithm::distance::DiscreteFrechetDistance::distance ( const geom::Geometry &  g0, const geom::Geometry &  g1, double  densifyFrac  )

static

double geos::algorithm::distance::DiscreteFrechetDistance::distance ( )

inline

Definition at line 144 of file DiscreteFrechetDistance.h.

const std::array<geom::Coordinate, 2> geos::algorithm::distance::DiscreteFrechetDistance::getCoordinates ( ) const

inline

Definition at line 151 of file DiscreteFrechetDistance.h.

PointPairDistance& geos::algorithm::distance::DiscreteFrechetDistance::getFrecheDistance ( std::vector< std::vector< PointPairDistance > > &  ca, size_t  i, size_t  j, const geom::CoordinateSequence &  p, const geom::CoordinateSequence &  q  )

private

geom::Coordinate geos::algorithm::distance::DiscreteFrechetDistance::getSegementAt ( const geom::CoordinateSequence &  seq, size_t  index  )

private

DiscreteFrechetDistance& geos::algorithm::distance::DiscreteFrechetDistance::operator= ( const DiscreteFrechetDistance &  rhs )

privatedelete

void geos::algorithm::distance::DiscreteFrechetDistance::setDensifyFraction ( double  dFrac )

inline

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

Parameters

dFrac

Definition at line 133 of file DiscreteFrechetDistance.h.

Member Data Documentation

double geos::algorithm::distance::DiscreteFrechetDistance::densifyFrac

private

Value of 0.0 indicates that no densification should take place.

Definition at line 171 of file DiscreteFrechetDistance.h.

const geom::Geometry& geos::algorithm::distance::DiscreteFrechetDistance::g0

private

Definition at line 164 of file DiscreteFrechetDistance.h.

const geom::Geometry& geos::algorithm::distance::DiscreteFrechetDistance::g1

private

Definition at line 166 of file DiscreteFrechetDistance.h.

PointPairDistance geos::algorithm::distance::DiscreteFrechetDistance::ptDist

private

Definition at line 168 of file DiscreteFrechetDistance.h.

---

The documentation for this class was generated from the following file:

• DiscreteFrechetDistance.h