计算离散frechet距离
frechetdist的Python项目详细描述
离散fréchet距离
计算 两条曲线。a中两条曲线之间的fréchet距离 度量空间是对曲线之间相似性的度量。 离散FréChET距离可用于近似计算。 两条任意曲线之间的fréchet距离, 作为使用多边形之间精确fréchet距离的替代方法 曲线的近似值或该值的近似值。
这是一个python 3.*算法的实现 在eiter,t.和mannila,h.,1994年。Computing discrete Fréchet distance。技术。 技术大学信息系统系CD-TR 94/64报告 维也纳的。
Function dF(P, Q): real;
input: polygonal curves P = (u1, . . . , up) and Q = (v1, . . . , vq).
return: δdF (P, Q)
ca : array [1..p, 1..q] of real;
function c(i, j): real;
begin
if ca(i, j) > −1 then return ca(i, j)
elsif i = 1 and j = 1 then ca(i, j) := d(u1, v1)
elsif i > 1 and j = 1 then ca(i, j) := max{ c(i − 1, 1), d(ui, v1) }
elsif i = 1 and j > 1 then ca(i, j) := max{ c(1, j − 1), d(u1, vj ) }
elsif i > 1 and j > 1 then ca(i, j) :=
max{ min(c(i − 1, j), c(i − 1, j − 1), c(i, j − 1)), d(ui, vj ) }
else ca(i, j) = ∞
return ca(i, j);
end; /* function c */
begin
for i = 1 to p do for j = 1 to q do ca(i, j) := −1.0;
return c(p, q);
end.
参数
P : Input curve - two dimensional array of points
Q : Input curve - two dimensional array of points
返回
dist: float64
The discrete Frechet distance between curves `P` and `Q`.
示例
>>> from frechetdist import frdist
>>> P=[[1,1], [2,1], [2,2]]
>>> Q=[[2,2], [0,1], [2,4]]
>>> frdist(P,Q)
>>> 2.0
>>> P=[[1,1], [2,1], [2,2]]
>>> Q=[[1,1], [2,1], [2,2]]
>>> frdist(P,Q)
>>> 0