2018-12-21 Frechet 距离

Frechet 距离是衡量数字曲线距离的一种距离。从直观的意义来看，也可以称之为狗绳距离。

示意图

线状要素是离散的数字曲线，计算算法的大体思路用一个公式表示即为

计算公式
这里用的是递归的方法，因此效率问题比较大，后期应当考虑更替为迭代的形式。

def culculateFrechetDis(line1,line2):
    n = len(line1)
    m = len(line2)
   disNMX=0.0
    if n > 1 and m > 1:
        disNM = euclidDis(line1[n-1],line2[m-1])
        disN_1M=culculateFrechetDis(line1[:n-1],line2)
        disNM_1=culculateFrechetDis(line1,line2[:m-1])
        if disNM >= disN_1M and disNM >= disNM_1:
            return disNM
        elif disN_1M <= disNM_1:
            disNMX = disN_1M
        else: 
            disNMX = disNM_1
        if disNMX > disNM:
            return disNM
        else :
            return disNMX
    if n == 1 and m > 1:
        disNM = euclidDis(line1[n-1],line2[m-1])
        disNM_1=culculateFrechetDis(line1,line2[:m-1])
        if disNM >= disNM_1:
            return disNM
        else:
            return disNM_1
    if m == 1 and n > 1:
        disNM = euclidDis(line1[n-1],line2[m-1])
        disN_1M=culculateFrechetDis(line1[:n-1],line2)
        if disNM >= disN_1M:
            return disNM
        else :
            return disN_1M    
    if m == 1 and n == 1:
        return euclidDis(line1[n-1],line2[m-1])
#  欧式距离
def euclidDis(point1,point2):
    return math.sqrt( ((point1[0]-point2[0])**2)+((point1[1]-point2[1])**2)) 

line1=[[1,1], [2,1], [2,2]] line2=[[2,2], [0,1], [2,4]] 计算距离为 2