离散弗雷歇Frechet距离 C/C++

离散弗雷歇（Frechet）距离的计算，参考了前人（http://download.csdn.net/download/deltapan/4364154）的代码，并实现了自底向上的动态规划来减少递归时栈的使用，尤其是当曲线数据点比较多时。

// FrechetDist.cpp : Defines the entry point for the console application.
//

#include “stdafx.h“

#include 

typedef struct _sPoint
{
	float x;
	float y;
}sPoint;	

#define max（ab） （（（a）>（b））?（a）:（b））

float dis（sPoint *p1 sPoint* p2 int i int j）
{
	return sqrt（pow（p1[i].x-p2[j].x2） + pow（p1[i].y-p2[j].y2））;
}

float min3（float f1 float f2 float f3）
{
	float minf = （f1 < f2）? f1 : f2;
	minf = （minf < f3）? minf : f3;
	return minf;
}


float Cal（sPoint* p1 sPoint *p2float** ca int i int j）
{
	if（ca[i][j] > -1.0）
	{
		return ca[i][j];
	}
	else if（i == 0 && j == 0）
	{
		ca[i][j] = dis（p1p200）;
	}
	else if（i > 0 && j == 0）
	{
		ca[i][j] = max（Cal（p1p2cai-10）dis（p1p2i0））;
	}
	else if（i == 0 && j > 0）
	{
		ca[i][j] = max（Cal（p1p2ca0j-1）dis（p1p20j））;
	}
	else if（i > 0 && j > 0）
	{
		ca[i][j] = max（min3（ Cal（p1p2cai-1j） Cal（p1p2cai-1j-1） Cal（p1p2caij-1） ） dis（p1p2ij））;
	}
	else
	{
		ca[i][j] = 0xFFFFFFFF;
	}

	return ca[i][j];

}


float calcFrechet（sPoint *p1 int p sPoint* p2 int q）
{
	// init ca[p][q]
	float **ca = new float*[p];
	for（int i = 0 ; i < p ; i++）
	{
		ca[i] = new float[q];
	}

	for（int i = 0 ; i < p ; i++）
	{
		for（int j = 0 ; j < q ; j++）
		{
			ca[i][j] = -1.0;
		}
	}

	float r=Cal（p1p2cap-1q-1）;


	for （int i=0; i	{
		for