使用計(jì)算幾何學(xué)求多段線之交點(diǎn)

李 垚，夏富洲，劉富奎

(1.安徽省水利水電勘測(cè)設(shè)計(jì)院，安徽 合肥 230000；2.武漢大學(xué)水利水電學(xué)院，湖北 武漢 430072；3.中山市水利水電勘測(cè)設(shè)計(jì)咨詢有限公司，廣東 中山 528400)

在進(jìn)行CAD的二次開(kāi)發(fā)過(guò)程中，經(jīng)常需要計(jì)算任意兩條多段線之間的交點(diǎn)，然而多段線之間有可能有連續(xù)的交點(diǎn)，即某些區(qū)段是完全重合的，這時(shí)需要計(jì)算這個(gè)連續(xù)區(qū)間的2個(gè)端點(diǎn)坐標(biāo)(射線重合只有1個(gè)交點(diǎn))，另外也有可能是離散的交點(diǎn)。需要把這些連續(xù)的交點(diǎn)和離散的交點(diǎn)，用程序計(jì)算并保存下來(lái)。

1 多段線的數(shù)值表示

多段線的數(shù)值表示就是把一條多段線的幾何信息用數(shù)字信息來(lái)表示。通常情況下，一條多段線是由線段和圓弧組成。考慮2種特殊情況，一種是當(dāng)起始點(diǎn)終止點(diǎn)2個(gè)端點(diǎn)完全重合，并且凸度為0的情況。凸度概念，在AutoCAD里是把圓心角的四分之一的正切值(tan(θ/4))作為凸度，由于圓心角的取值范圍為(-2π，2π)，所以凸度的取值范圍(-1，1)，凸度的取值區(qū)間為開(kāi)區(qū)間，因?yàn)楫?dāng)凸度接近-1或者1時(shí)，圓弧接近為一個(gè)圓形，當(dāng)凸度為0時(shí)起始點(diǎn)終止點(diǎn)2個(gè)端點(diǎn)完全重合在同一直線上。另外一種是當(dāng)起始點(diǎn)終止點(diǎn)2個(gè)端點(diǎn)完全重合，凸度不為0的情況。這2種情況在DXF文件中只可能出現(xiàn)在一條多段線的首端和尾端。下面把多段線的幾何信息描述成數(shù)字信息。

1.1 圓弧

1.1.1圓弧的數(shù)據(jù)存儲(chǔ)

圓的標(biāo)準(zhǔn)方程為(x-a)2+(y-b)2=r2里面有3個(gè)參數(shù)，即圓心的x坐標(biāo)，y坐標(biāo)以及圓的半徑。表示一個(gè)圓弧，需要有圓弧的起始點(diǎn)(x1，y1)、終止點(diǎn)(x2，y2)、凸度d。為方便交點(diǎn)的計(jì)算，同時(shí)準(zhǔn)確表示一段圓弧需要有8個(gè)參數(shù)。可以用一個(gè)3×3的數(shù)組來(lái)存儲(chǔ)圓弧的信息，這樣還多出一個(gè)存儲(chǔ)單元，可以把起始點(diǎn)和終止點(diǎn)的長(zhǎng)度m存儲(chǔ)到這個(gè)單元里。數(shù)據(jù)的存儲(chǔ)如下：

1.1.2圓弧的相關(guān)參數(shù)求取

(1)求圓弧的半徑

已知DXF文件提供了圓弧的起始點(diǎn)P1(x1，y1)、終止點(diǎn)P2(x2，y2)、凸度d共5個(gè)參數(shù)，以這5個(gè)參數(shù)推導(dǎo)出圓弧的圓心坐標(biāo)及圓弧的半徑。

由圓的參數(shù)方程有：

x1=a+rcosφ

(1)

y1=b+rsinφ

(2)

x2=a+rcos(φ+θ)

(3)

y2b+rsin(φ+θ)

(4)

由凸度的定義得到圓心角的計(jì)算公式：

θ=4tan-1d

(5)

(式1-式2)2+(式3-式4)2得：

(x1-x2)2+(y1-y2)2=2r2-2r2cosφcos(φ+θ)-2r2sinφsin(φ+θ)=2r2-2r2cosθ

則

(6)

(2)求圓弧的圓心

(7)

(8)

聯(lián)立式(7)式(8)得到

λ=-0.5

(9)

1.2 線型對(duì)象

1.2.1線段的數(shù)據(jù)存儲(chǔ)

1.2.2射線的數(shù)據(jù)存儲(chǔ)

2 求交點(diǎn)

由于多段線是由線段、圓弧組成，當(dāng)考慮多段線的端點(diǎn)沿其切線方向的射線時(shí)，多段線之間的交點(diǎn)最多會(huì)出現(xiàn)6種情況(線段和線段、圓弧與圓弧、射線和射線、線段和圓弧、線段和射線、射線和圓弧之間的交點(diǎn))，下面主要對(duì)圓弧與線段情況的交點(diǎn)計(jì)算方法進(jìn)行討論，其余5種情況和這種情況類似。

該方程為一個(gè)關(guān)于s的一個(gè)一元二次方程：

以上獲得的只是線段和圓的交點(diǎn)坐標(biāo)，在一條多段線里只有線段或者圓弧，是沒(méi)有圓的。因此要進(jìn)一步根據(jù)圓弧端點(diǎn)和線段的關(guān)系去取舍點(diǎn)。

如圖多段線ABCD是由2條線段和一條圓弧組成。線段和多段線ABCD的位置關(guān)系主要可以分成6種情況進(jìn)行考慮。如圖1所示。

(1)線段和圓O沒(méi)有一個(gè)交點(diǎn)，如線段m1與圓O的位置關(guān)系。

(2)線段和圓O實(shí)線部分有1個(gè)交點(diǎn)，如線段m2與圓O的位置關(guān)系。

(3)線段和圓O實(shí)線部分有2個(gè)交點(diǎn)，如線段m3與圓O的位置關(guān)系。

(4)線段和圓O的實(shí)線部分虛線部分各有1個(gè)交點(diǎn)，如線段m4與圓O的位置關(guān)系。

(5)線段和圓O的虛線部分有2個(gè)交點(diǎn)，如線段m5與圓O的位置關(guān)系。

(6)線段和圓O的虛線部分有1個(gè)交點(diǎn)，如線段m6與圓O的位置關(guān)系。

圖1 圓弧和線段的交點(diǎn)

對(duì)于任意一個(gè)在圓O實(shí)線部分上的點(diǎn)，需滿足以下條件：

通過(guò)以上2種情況能夠?qū)⒕€段與圓弧的交點(diǎn)成功篩選出來(lái)。

圖2 凸度大于0圖3 凸度小于0

3 工程應(yīng)用

實(shí)際在AutoCAD二次開(kāi)發(fā)的計(jì)算機(jī)語(yǔ)言中有求交點(diǎn)的函數(shù)，這個(gè)函數(shù)的求交點(diǎn)結(jié)果不是很穩(wěn)定，有的情況即使有交點(diǎn)，也無(wú)法計(jì)算出結(jié)果，有的情況計(jì)算出來(lái)的點(diǎn)存在多個(gè)一樣的情況，另外該函數(shù)在求交點(diǎn)時(shí)，必須是AutoCAD的dwg文件中的兩條已經(jīng)存在的多段線。本文所提到的多段線求交點(diǎn)的方法，恰好能夠彌補(bǔ)以上不足。

智能識(shí)別樁號(hào)點(diǎn)，在堤防的平面線繪制過(guò)程中，能夠?qū)M斷面圖設(shè)計(jì)線的特征點(diǎn)準(zhǔn)確的繪制到平面圖中。但是每?jī)蓚€(gè)樁號(hào)線之間都是用線段直接連接，如圖4所示中的擬生成線。為了讓平面圖中的設(shè)計(jì)線能夠符合地形，需要對(duì)平面線進(jìn)行調(diào)整。目前已經(jīng)開(kāi)發(fā)出一套軟件，可以根據(jù)地形先調(diào)整好一條平面線，如圖4中的被模仿線(m0)，然后其余線條可以根據(jù)被模仿線的形狀和走勢(shì)自動(dòng)生成。這中間就會(huì)產(chǎn)生一個(gè)問(wèn)題：怎樣保持?jǐn)M生成線(m1、m2、m3)在樁號(hào)線上的位置不變，同時(shí)樁號(hào)線與樁號(hào)線之間的線段能夠根據(jù)被模仿線的形狀和走勢(shì)智能調(diào)整。上面介紹的求交點(diǎn)的方法能夠解決這一問(wèn)題，具體算法：

第一步被模仿線和樁號(hào)線1、2求交點(diǎn)，將這些點(diǎn)標(biāo)記為不可改變點(diǎn)，分別記為pt1、pt2。

第二步把pt1、pt2在被模仿線上之間的一系列點(diǎn)點(diǎn)ptn截取下來(lái)，并記下其凸度、法線方向向量等線型特征。

第三步擬生成線和樁號(hào)線1、2求交點(diǎn)，將這些點(diǎn)標(biāo)記為不可改變點(diǎn)，分別記為pt3、pt4。

第四步根據(jù)第二步獲得的線性特征，在pt3、pt4之間，把線型自動(dòng)智能生成。

最后通過(guò)對(duì)被摸仿線線型的模仿，圖4中的擬生成線，最后轉(zhuǎn)變成如圖5所示的生成線，程序的模仿線的效果還是不錯(cuò)的。通常堤防設(shè)計(jì)過(guò)程中有7條線需要繪制。現(xiàn)在使用此程序，只需繪制其中一條線，其余6條線能夠智能生成，效率相當(dāng)于提高3～5倍。

圖4 多段線被模仿前

圖5 多段線被模仿后

4 結(jié)論

本程序使用Lisp語(yǔ)言編制而成，測(cè)試時(shí)，使用2條都有10段的多段線，執(zhí)行500次循環(huán)運(yùn)算，花費(fèi)時(shí)間7.29秒，平均每次花費(fèi)時(shí)間0.015s，同時(shí)計(jì)算結(jié)果比較理想。求交點(diǎn)程序在CAD的二次開(kāi)發(fā)中需要經(jīng)常用到，然而AutoCAD提供的函數(shù)只能在2條多段線都存在于AutoCAD模型空間中的情況下才能進(jìn)行求交點(diǎn)計(jì)算，有時(shí)候甚至無(wú)法求出多段線的交點(diǎn)。本文提出了使用計(jì)算幾何學(xué)計(jì)算交點(diǎn)的具體方法，并編制了計(jì)算機(jī)程序。在堤防平面圖設(shè)計(jì)過(guò)程中需要智能識(shí)別樁號(hào)位置的點(diǎn)，本程序的成功編制很好的解決了這個(gè)問(wèn)題。本文介紹的應(yīng)用程序已經(jīng)在《無(wú)為縣五千畝至萬(wàn)畝圩口除險(xiǎn)加固工程(Ⅱ期)》《2015年度攔路港堤防除險(xiǎn)加固工程》《巢湖流域牛屯河防洪治理工程》等項(xiàng)目中得到很好的應(yīng)用。。