[發明專利]一種計算兩條參數曲線間的Hausdorff距離的方法

無效

• 申請號: 201210373972.6
• 申請日: 2012-10-05
• 公開（公告）號: CN103049593A
• 公開（公告）日: 2013-04-17
• 發明（設計）人: 李英明;姜華;曹鳳蓮
• 申請（專利權）人: 李英明
• 主分類號: G06F17/50
• 分類號: G06F17/50
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發明涉及計算機輔助設計領域和模式識別領域，特別涉及一種計算兩條參數曲線間的Hausdorff距離的方法。?

背景技術

隨著計算機輔助設計越來越多的應用到產品設計中，計算機輔助設計技術的發展也帶來了新的需求，曲線間的匹配程度和度量通常采用Hausdorff距離，然而，Hausdorff距離的計算卻相當困難，并且通常相當費時，它的研究也只局限在某些特定的場合下。目前的研究有對兩條平面曲線的Hausdorff距離；圓錐曲線與參數有理Bézier曲線間近似Hausdorff誤差的方法，兩條二維或三維空間中曲線間近似Hausdorff距離的算法的研究卻很少。為了提高Hausdorff距離的計算效率，減少計算時間，研究計算兩條二維或三維空間中曲線間近似Hausdorff距離的方法具有重要的意義。?

Hausdorff距離定義如下：?

給定兩條參數曲線P(s)，Q(t)，t₀≤t≤t₁，假設兩條參數曲線的末端端點重合，即：?P_s(s)≠0，Q_t(t)≠0，P(s0)=?Q(t₀)且P(s₁)=?Q(t₁)?

則這兩條曲線間的Hausdorff距離定義如下：

發明內容

本發明要解決的技術問題是提供一種計算兩條參數曲線間的Hausdorff距離的方法，算法效率高，速度快，計算精度可控，滿足實用要求。?

一種計算兩條參數曲線間的Hausdorff距離的方法，其實施步驟如下：?

第一步證明了兩條曲線間的Hausdorff距離一定會在這兩條曲線的偏導曲線的交點上達到

1）Hausdorff距離的定義及幾何意義

給定兩條參數曲線P(s)，Q(t)，t₀≤t≤t₁，假設兩條參數曲線的末端端點重合，即：?

P_s(s)≠0，Q_t(t)≠0，P(s₀)=?Q(t₀)且P(s₁)=?Q(t₁)

則這兩條曲線間的Hausdorff距離如下：

.?(1)

為了計算它們之間的Hausdorff距離，定義一個兩條曲線間距離函數的平方項的映射

讓，假設

所以是函數的一個局部極值點，即,對于任意s,s₀≤s≤s₁，可以得到在s-t平面內的一條曲線f_t(s,t)=0，這條曲線上的任一點滿足：?

另一條曲線f_s(s,t)=0上的任一點使得：

兩條曲線f_s(s,t)=0以及f_t(s,t)=0的幾何意義，即：?

???????????,????????????

??????????????????????

對于兩條正則參數曲線P(s)以及Q(t)，有兩個原因使得

f_s(s,t)=0，即：