[發(fā)明專(zhuān)利]基于劣弧演化的點(diǎn)到隱式曲線距離計(jì)算方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201310542392.X
• 申請(qǐng)日: 2013-10-30
• 公開(kāi)（公告）號(hào): CN103559400B
• 公開(kāi)（公告）日: 2017-06-16
• 發(fā)明（設(shè)計(jì)）人: 胡明曉;吳文國(guó);謝祖明;張新瑤
• 申請(qǐng)（專(zhuān)利權(quán)）人: 溫州大學(xué)
• 主分類(lèi)號(hào): G06F19/00
• 分類(lèi)號(hào): G06F19/00
• 代理公司: 暫無(wú)信息
• 代理人: 暫無(wú)信息

1.一種用于電子計(jì)算機(jī)的二維平面內(nèi)的點(diǎn)p₀到隱式曲線距離的數(shù)值計(jì)算方法，其中隱式曲線為某有界區(qū)域Ω上有定義且方向?qū)?shù)有界的二元函數(shù)f(x，y)依其零值集確定的單分支平面曲線，其特征在于包含如下步驟：尋找一個(gè)函數(shù)值f(p)與f(p₀)異號(hào)或等于零的初始點(diǎn)p，此時(shí)以p₀為圓心、以||p₀-p||為半徑的圓必與隱式曲線相交；置內(nèi)半徑為0，外半徑為||p₀-p||；再取中值半徑為內(nèi)半徑與外半徑之平均值，然后判斷以p₀為圓心、以中值半徑為半徑的圓與隱式曲線是否相交，若相交，外半徑下調(diào)為中值半徑，若不相交，內(nèi)半徑上調(diào)為中值半徑；再取中值半徑、判斷相交性、調(diào)整內(nèi)半徑或外半徑，如此反復(fù)，直至外半徑與內(nèi)半徑之差小于容許誤差，返回內(nèi)半徑與外半徑之平均值作為點(diǎn)p₀到所述隱式曲線的距離；其中判斷圓與隱式曲線是否相交的方法包含如下步驟：

(1)取最小的正整數(shù)n，使圓周2ⁿ等分后每段圓弧長(zhǎng)小于容許誤差，圓周等分后依次分布的等分點(diǎn)為q₀，q₁，......，

(2)置初始值i＝0，初始劣弧集A＝{[0，2ⁿ]}，劣弧集是圓上函數(shù)值可能與f(p₀)異號(hào)的圓弧的集合，其元素形如[s，t]，其中s、t分別是圓弧兩端的等分點(diǎn)標(biāo)號(hào)，[s，t]表示由等分點(diǎn)q_s，q_s+1，……，q_t連成的圓弧，初始劣弧集只有一個(gè)從q₀連到的單個(gè)圓弧，其實(shí)為整個(gè)圓周；

(3)將i的n位二進(jìn)制數(shù)表示b₁b₂……b_n逆序，得到二進(jìn)制數(shù)b_n……b₂b₁，其表示的整數(shù)為j；

(4)若q_j不落在劣弧集A的任一圓弧內(nèi)，跳至步驟(7)；

(5)計(jì)算f(q_j)，若該函數(shù)值與f(p₀)異號(hào)，結(jié)束判斷，返回結(jié)果為“圓與隱式曲線相交”，否則，進(jìn)行劣弧演化，即根據(jù)f(q_j)值與方向?qū)?shù)上界M排除f(q)肯定與f(p₀)同號(hào)的等分點(diǎn)q，對(duì)A中的圓弧進(jìn)行刪除、收縮和分裂處理，縮小劣弧集的覆蓋范圍；

(6)若劣弧集結(jié)束判斷算法，返回結(jié)果為“圓與隱式曲線不相交”；

(7)置i為i+1，若i＝2ⁿ，結(jié)束判斷算法，返回結(jié)果為“圓與隱式曲線不相交”，否則轉(zhuǎn)至步驟(3)。

2.如權(quán)利要求1所述的數(shù)值計(jì)算方法，其特征在于，其中判斷圓與隱式曲線是否相交的步驟(5)中的劣弧演化包含如下步驟：

①若|f(q_j)|＞2Mr，置結(jié)束；

其中：

r為圓的半徑；

M為f(x，y)的方向?qū)?shù)的上界，即

$M=\underset{\mathrm{\Ω}}{\max }\left|\right|\▿f(x,y)\left|\right|=\underset{\mathrm{\Ω}}{\max }\left|\right|(\frac{\∂f(x,y)}{\∂x},\frac{\∂f(x,y)}{\∂y})\left|\right|\<+\mathrm{\∞};$

②計(jì)算

③計(jì)算其中表示取下整數(shù)，當(dāng)j-k≤i≤j+k時(shí)f(q_i)必與f(p₀)同號(hào)，即得2k+1個(gè)同號(hào)等分點(diǎn)；

④若j＝0，直接將圓弧[0，2ⁿ]收縮為[k+1，2ⁿ-k-1]，否則，對(duì)劣弧集A的每個(gè)圓弧[s，t]，分如下五種情形分別作演化處理：

(a)j-k＞t或j+k＜s：保持[s，t]不變；

(b)j+k≥t≥j-k＞s：[s，t]收縮為[s，j-k-1]；

(c)t＞j+k≥s≥j-k：[s，t]收縮為[j+k+1，t]；

(d)j+k≥t≥s≥j-k：將[s，t]從A中刪除；

(e)t＞j+k≥j-k＞s：[s，t]分裂為[s，j-k-1]和[j+k+1，t]兩個(gè)圓弧；

⑤結(jié)束。