使用計算幾何學求多段線之交點

李 垚，夏富洲，劉富奎

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

在進行CAD的二次開發過程中，經常需要計算任意兩條多段線之間的交點，然而多段線之間有可能有連續的交點，即某些區段是完全重合的，這時需要計算這個連續區間的2個端點坐標(射線重合只有1個交點)，另外也有可能是離散的交點。需要把這些連續的交點和離散的交點，用程序計算并保存下來。

1 多段線的數值表示

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

1.1 圓弧

1.1.1圓弧的數據存儲

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

1.1.2圓弧的相關參數求取

(1)求圓弧的半徑

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

由圓的參數方程有：

x1=a+rcosφ

(1)

y1=b+rsinφ

(2)

x2=a+rcos(φ+θ)

(3)

y2b+rsin(φ+θ)

(4)

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

θ=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)

聯立式(7)式(8)得到

λ=-0.5

(9)

1.2 線型對象

1.2.1線段的數據存儲

1.2.2射線的數據存儲

2 求交點

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

該方程為一個關于s的一個一元二次方程：

以上獲得的只是線段和圓的交點坐標，在一條多段線里只有線段或者圓弧，是沒有圓的。因此要進一步根據圓弧端點和線段的關系去取舍點。

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

(1)線段和圓O沒有一個交點，如線段m1與圓O的位置關系。

(2)線段和圓O實線部分有1個交點，如線段m2與圓O的位置關系。

(3)線段和圓O實線部分有2個交點，如線段m3與圓O的位置關系。

(4)線段和圓O的實線部分虛線部分各有1個交點，如線段m4與圓O的位置關系。

(5)線段和圓O的虛線部分有2個交點，如線段m5與圓O的位置關系。

(6)線段和圓O的虛線部分有1個交點，如線段m6與圓O的位置關系。

圖1 圓弧和線段的交點

對于任意一個在圓O實線部分上的點，需滿足以下條件：

通過以上2種情況能夠將線段與圓弧的交點成功篩選出來。

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

3 工程應用

實際在AutoCAD二次開發的計算機語言中有求交點的函數，這個函數的求交點結果不是很穩定，有的情況即使有交點，也無法計算出結果，有的情況計算出來的點存在多個一樣的情況，另外該函數在求交點時，必須是AutoCAD的dwg文件中的兩條已經存在的多段線。本文所提到的多段線求交點的方法，恰好能夠彌補以上不足。

智能識別樁號點，在堤防的平面線繪制過程中，能夠將橫斷面圖設計線的特征點準確的繪制到平面圖中。但是每兩個樁號線之間都是用線段直接連接，如圖4所示中的擬生成線。為了讓平面圖中的設計線能夠符合地形，需要對平面線進行調整。目前已經開發出一套軟件，可以根據地形先調整好一條平面線，如圖4中的被模仿線(m0)，然后其余線條可以根據被模仿線的形狀和走勢自動生成。這中間就會產生一個問題：怎樣保持擬生成線(m1、m2、m3)在樁號線上的位置不變，同時樁號線與樁號線之間的線段能夠根據被模仿線的形狀和走勢智能調整。上面介紹的求交點的方法能夠解決這一問題，具體算法：

第一步被模仿線和樁號線1、2求交點，將這些點標記為不可改變點，分別記為pt1、pt2。

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

第三步擬生成線和樁號線1、2求交點，將這些點標記為不可改變點，分別記為pt3、pt4。

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

最后通過對被摸仿線線型的模仿，圖4中的擬生成線，最后轉變成如圖5所示的生成線，程序的模仿線的效果還是不錯的。通常堤防設計過程中有7條線需要繪制。現在使用此程序，只需繪制其中一條線，其余6條線能夠智能生成，效率相當于提高3～5倍。

圖4 多段線被模仿前

圖5 多段線被模仿后

4 結論

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