fr.ign.cogit.geoxygene.distance

Class Frechet

Object

Frechet

public class Frechet
extends Object

A class to compute the Fréchet distance.

Author:

Julien Perret

Constructor Summary

Constructors

Constructor and Description
Frechet()

Method Summary

Modifier and Type	Method and Description
static double[]	boundary(IDirectPosition p, IDirectPosition q1, IDirectPosition q2, double r) Compute one side of a free space diagram cell.
static DirectPosition[]	circleLineIntersect(double x1, double y1, double x2, double y2, double cx, double cy, double cr) Points d'intersection entre une droite définie par 2 points (x1,y1);(x2,y2) et un cercle de centre (cx,cy) et de rayon cr.
static double	discreteFrechet(ILineString p, ILineString q) Discrete Fréchet distance.
static double	discreteFrechetWithProjection(ILineString p, ILineString q) Discrete Fréchet distance.
static double	distance(double x1, double y1, double x2, double y2)
static double[]	freeCellEllipse(IDirectPosition p1, IDirectPosition p2, IDirectPosition q1, IDirectPosition q2) Compute the free space cell as an ellipse intersecting the unit square.
static IPolygon[][]	freeSpaceDiagram(IDirectPositionList p, IDirectPositionList q, double sigma)
static double[][][][]	fsdCalculation(IDirectPositionList p, IDirectPositionList q, double sigma)
static double	partialFrechet(ILineString p, ILineString q)
static int	pointOnSegment(double x1, double y1, double x2, double y2, double x3, double y3)

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

Frechet

public Frechet()

Method Detail

discreteFrechet

public static double discreteFrechet(ILineString p,
                                     ILineString q)

Discrete Fréchet distance.

Complexity O(pq).

Eiter, Thomas; Mannila, Heikki (1994), Computing discrete Fréchet distance, Tech. Report CD-TR 94/64, Christian Doppler Laboratory for Expert Systems, TU Vienna, Austria.

Parameters:

p - linestring

q - linestring

Returns:

the discrete Fréchet distance between the 2 input polygonal curves

discreteFrechetWithProjection

public static double discreteFrechetWithProjection(ILineString p,
                                                   ILineString q)

Discrete Fréchet distance. This method reproject the points from each curve to the other (only to the closest projection). This still has to be tested.

Complexity O(pq).

Eiter, Thomas; Mannila, Heikki (1994), Computing discrete Fréchet distance, Tech. Report CD-TR 94/64, Christian Doppler Laboratory for Expert Systems, TU Vienna, Austria.

Parameters:

p - linestring

q - linestring

Returns:

the discrete Fréchet distance between the 2 input polygonal curves

partialFrechet

public static double partialFrechet(ILineString p,
                                    ILineString q)

freeCellEllipse

public static double[] freeCellEllipse(IDirectPosition p1,
                                       IDirectPosition p2,
                                       IDirectPosition q1,
                                       IDirectPosition q2)

Compute the free space cell as an ellipse intersecting the unit square.
Its inequation is giver by Ax² + Bxy + Cy² + Dx + Ey + F < epsilon² Reference Frechet Distance on Convex Polyhedron

Parameters:

p1 -

p2 -

q1 -

q2 -

Returns:

freeSpaceDiagram

public static IPolygon[][] freeSpaceDiagram(IDirectPositionList p,
                                            IDirectPositionList q,
                                            double sigma)

fsdCalculation

public static double[][][][] fsdCalculation(IDirectPositionList p,
                                            IDirectPositionList q,
                                            double sigma)

boundary

public static double[] boundary(IDirectPosition p,
                                IDirectPosition q1,
                                IDirectPosition q2,
                                double r)

Compute one side of a free space diagram cell. In other words, we compute the intersection of the segment [q1;q2] with a circle of radius r and centered in p;

Parameters:

p - the center of the circle

q1 - point of the segment

q2 - point of the segment

r - radius

Returns:

circleLineIntersect

public static DirectPosition[] circleLineIntersect(double x1,
                                                   double y1,
                                                   double x2,
                                                   double y2,
                                                   double cx,
                                                   double cy,
                                                   double cr)

Points d'intersection entre une droite définie par 2 points (x1,y1);(x2,y2) et un cercle de centre (cx,cy) et de rayon cr.

Parameters:

x1 -

y1 -

x2 -

y2 -

cx -

cy -

cr -

Returns:

pointOnSegment

public static int pointOnSegment(double x1,
                                 double y1,
                                 double x2,
                                 double y2,
                                 double x3,
                                 double y3)

distance

public static double distance(double x1,
                              double y1,
                              double x2,
                              double y2)