[發(fā)明專利]基于節(jié)點(diǎn)匹配對(duì)的直線段與直線段的自動(dòng)分割方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201710904539.3
• 申請(qǐng)日: 2017-09-29
• 公開(kāi)（公告）號(hào): CN107833234A
• 公開(kāi)（公告）日: 2018-03-23
• 發(fā)明（設(shè)計(jì)）人: 虞昌彬;夏俊;趙志剛;賀彪;李霖;董玉鵬
• 申請(qǐng)（專利權(quán)）人: 浙江大學(xué)寧波理工學(xué)院
• 主分類號(hào): G06T7/162
• 分類號(hào): G06T7/162;G06T11/20
• 代理公司: 寧波市鄞州甬致專利代理事務(wù)所(普通合伙)33228
• 代理人: 李迎春

1.一種基于節(jié)點(diǎn)匹配對(duì)的直線段與直線段的自動(dòng)分割方法，所述方法應(yīng)用于第一直線段與第二直線段的自動(dòng)分割過(guò)程，其特征在于，所述方法包括步驟：

S1、構(gòu)建節(jié)點(diǎn)至直線段的節(jié)點(diǎn)匹配對(duì)的總個(gè)數(shù)；

S2、構(gòu)建第一直線段和第二直線段之間的所有頂點(diǎn)匹配類型；

S3、將第一直線段與第二直線段之間的所有頂點(diǎn)匹配類型進(jìn)行形式化表達(dá)；

S4、確定第一直線段和第二直線段之間所有的頂點(diǎn)匹配類型的實(shí)現(xiàn)方式；

S5、于第一直線段與第二直線段實(shí)交時(shí)計(jì)算交點(diǎn)的坐標(biāo)。

2.根據(jù)權(quán)利要求1所述的基于節(jié)點(diǎn)匹配對(duì)的直線段與直線段的自動(dòng)分割方法，其特征在于，在步驟S1中，判斷第一直線段的兩個(gè)節(jié)點(diǎn)與第二直線段之間、第二直線段的兩個(gè)節(jié)點(diǎn)與第一直線段之間存在的節(jié)點(diǎn)匹配對(duì)的個(gè)數(shù)。

3.根據(jù)權(quán)利要求2所述的基于節(jié)點(diǎn)匹配對(duì)的直線段與直線段的自動(dòng)分割方法，其特征在于，判斷節(jié)點(diǎn)是否存在對(duì)應(yīng)的節(jié)點(diǎn)匹配對(duì)的公式為：

其中，P代表節(jié)點(diǎn)，L代表直線段，ε代表閾值，Pnear(P,L,ε)代表在直線段L上距離節(jié)點(diǎn)P在閾值ε范圍內(nèi)最近的點(diǎn)，distance(P,Pnear)代表點(diǎn)P到點(diǎn)Pnear的距離。

4.根據(jù)權(quán)利要求1所述的基于節(jié)點(diǎn)匹配對(duì)的直線段與直線段的自動(dòng)分割方法中，在步驟S2中，根據(jù)節(jié)點(diǎn)匹配對(duì)的個(gè)數(shù)確定節(jié)點(diǎn)匹配對(duì)的位置，并根據(jù)節(jié)點(diǎn)匹配對(duì)位置確定節(jié)點(diǎn)匹配對(duì)類型。

5.根據(jù)權(quán)利要求1所述的基于節(jié)點(diǎn)匹配對(duì)的直線段與直線段的自動(dòng)分割方法，其特征在于，在步驟S3中，于第一直線段L1和第二直線段L2實(shí)交時(shí)，則需要同時(shí)滿足以下公式：

f(L1)(P3)*f(L1)(P4)＜0

f(L2)(P1)*f(L2)(P2)＜0

其中，P1和P2為第一直線段L1的兩個(gè)端點(diǎn)，P3和P4為第二直線段L2的兩個(gè)端點(diǎn)，f(L1)是第一直線段L1的數(shù)字方程式表達(dá)，f(L2)是第二直線段L2的數(shù)字方程式表達(dá)。

6.根據(jù)權(quán)利要求5所述的基于節(jié)點(diǎn)匹配對(duì)的直線段與直線段的自動(dòng)分割方法，其特征在于，于第一直線段L1與第二直線段L2虛交時(shí)，滿足公式：

于第一直線段L1與第二直線段L2實(shí)交時(shí)，滿足公式：

∧(f(L2)(P1)*f(L2)(P2)＜0)∧(f(L1)(P3)*f(L1)(P4)＜0)

于第一直線段L1與第二直線段L2為接觸與被接觸關(guān)系時(shí)，滿足公式：

于第一直線段L1與第二直線段L2存在部分疊置時(shí)，滿足公式：

于第一直線段L1與第二直線段L2具有公共節(jié)點(diǎn)時(shí)，滿足公式：

于第一直線段L1與第二直線段L2存在包含與被包含關(guān)系時(shí)，滿足公式：

于第一直線段L1與第二直線段L2存在覆蓋與被覆蓋關(guān)系時(shí)，滿足公式：

于第一直線段L1與第二直線段L2存在重合關(guān)系時(shí)，滿足公式：

7.根據(jù)權(quán)利要求1所述的基于節(jié)點(diǎn)匹配對(duì)的直線段與直線段的自動(dòng)分割方法，其特征在于，在步驟S5中，與第一直線段L1和第二直線段L2實(shí)交時(shí)，交點(diǎn)將第一直線段L1分成的兩段的長(zhǎng)度比例為r1，將第二直線段L2分成的兩段的長(zhǎng)度比例為r2：

r1=D1D0]]>

r2=D2D0]]>

其中，

D0=(x2-x1)(y4-y3)-(x4-x3)(y2-y1)=(x2-x1)(x4-x3)(y2-y1)(y4-y3)]]>

D1=(x3-x1)(y4-y3)-(y3-y1)(x4-x3)=(x3-x1)(x4-x3)(y3-y1)(y4-y3)]]>

D2=-(y3-y1)(x2-x1)+(x3-x1)(y2-y1)=(x2-x1)-(x3-x1)(y2-y1)-(y3-y1)]]>

在上述公式中，第一直線段L1由端點(diǎn)(x1,y1)指向端點(diǎn)(x2,y2)，第二直線段L2由端點(diǎn)(x3,y3)指向端點(diǎn)(x4,y4)。