Computation of Hausdorff distance between planar curves

DOI：10.7511/dllgxb201402005

 作者 单位 曹利新,董雷,曹京京

为克服传统的针对平面曲线间Hausdorff距离4种情况需分别求解不同非线性方程组的缺点,分两个步骤计算平面曲线间的Hausdorff距离．首先将曲线 A进行离散化处理,并计算各离散点到曲线B的最小距离,从中选择若干个距离较大,且满足曲线A上相邻点到曲线B 的距离呈“小大小”的点对作为近似解；然后根据各点对处曲线的特点,判断该点附近可能存在4种类型点的哪一种,建立相应的优化模型并进行局部寻优,选择优化结果中最大的距离值作为两平面曲线间的单向Hausdorff距离．该法将平面曲线间Hausdorff距离的计算转化为点到曲线的最小距离计算,计算过程简单有效．两个数值算例验证了该方法的正确性．

The difficulty of computing the Hausdorff distance(HD) between planar curves lies in solving different nonlinear equations for four kinds of special cases which are encountered in this computing process. To simplify the process of calculation, a two-step method for computing the HD between planar curves is proposed. The first step of the method is sampling the curve A , and calculating the minimum distance between each discrete point on the curve A and the curve B . Then, selecting several points from the discrete points as the approximate solutions, which correspond to the larger minimum distance and the minimum distances of each point together with its adjacent two points obeying the ′small-large-small′ order. The second step is identifying which case the approximate solution belongs to according to the shape and position of the curves, establishing corresponding optimization model and finding the local optimal solution. Comparing these local optimal solutions, the final directed HD with the largest minimum distance will be acquired. By using this method, the computing process of the HD between planar curves can be converted into the computation of the minimum distance between a point and a curve, which can improve the computational efficiency and stability of the algorithm. The feasibility of the algorithm has been verified by two numerical examples.