判別簡單多邊形的核為空的快速算法

于存光YU Cun-guang

（黑龍江科技大學，哈爾濱 150022）

（Heilongjiang University of Science and Technology，Harbin 150022，China）

0 引言

簡單多邊形核是計算幾何的核心問題，它在工程設計、計算機圖形學等領域中有廣泛應用。求多邊形核有很多有效算法，對于多邊形無核的研究相對較少，文獻[1]給出了一種判斷簡單多邊形的核是否為空的一個快速算法，但對于多邊形具有連續凹點情形沒有考慮，文獻[2]給出無核多邊形的一種劃分，將多邊形分為多個有核多邊形，也沒有對多邊形無核算法進行深入研究。本算法結合多邊形凹點情況，提出處理連續凹點多邊形無核的平行射線法，給出一種快速判斷多邊形無核算法，并且當多邊形有核時給出多邊形核的一個點。

1 算法思想

由n 個頂點構成多邊形P，頂點記為v1，v2，…vn，沿多邊形頂點順序，按逆時針行走，多邊形P 內部在多邊形左側，這樣的多邊形稱為簡單多邊形，即非相鄰的邊不相交。多邊形的核K 是指其內部任意一點與多邊形邊界一點的連線都在多邊形內部。由于多邊形的凸點在多邊形內是可見的，多邊形核只與凹點有關，所以本算法只處理凹點。

直線可以表示為Ax+By+C=0 的形式，在直線左側記為Ax+By+C≥0，直線右側記為Ax+By+C≤0，這里都包括直線本身。

1.1 線性求交法判斷多邊形無核或求多邊形核一個交點，如果簡單多邊形不是凸多邊形，將多邊形的邊分為三類：①第一類邊，vi是凸點，vi+1是凹點，多邊形核只可能在直線vivi+1左側，即，Ax+By+C≥0。如圖1 所示。②第二類邊，vi+1是凸點，vi是凹點，多邊形核只可能在直線vi+1vi右側，即Ax+By+C≤0。如圖2 所示。③第三類邊，vivi+1都是凹點，多邊形核不可能在直線vivi+1上。如圖3，4 所示。

圖1 第一類邊

圖2 第二類邊

圖3 射線vi-1vi和射線vi+2vi+1不平行有核

圖4 射線vi-1vi和射線vi+2vi+1平行無核

多邊形核是判斷線性不等式圍成凸空間是否為空的問題[3]。這樣只需處理兩類邊在多邊形內是否有交即可。文獻[1]沒有處理連續凹點問題，本算法利用射線平行法迅速判斷出多邊形無核的情況，有核再利用線性求交計算核的一個點。

1.2 射線平行法處理連續凹點多邊形無核，由下面兩種情況推廣：①對于有兩個連續凹點的情況，當射線vi-1vi和射線vi+2vi+1不平行，即相交時，多邊形可能有無核；當射線vi-1vi和射線vi+2vi+1平行或大于平行角，即不相交時，多邊形無核。如圖3，4 所示。②對于有三個連續凹點的情況，當不滿足兩個連續凹點條件時，當射線vi-1vi和射線vi+3vi+2不平行，即相交時，多邊形可能有無核；當射線vi-1vi和射線vi+3vi+2平行或大于平行角，即相交時，多邊形無核。對于多于三個連續凹點情況可由這兩種情況推廣。如圖5，6 所示。

2 算法實現

算法：

輸入 多邊形P 的頂點pi（xi，yi），i=1，2，…n 按逆時針方向排列。

輸出 多邊形P 無核或多邊形核一個點K 坐標。

預處理 確定多邊形P 的凸，凹頂點，并對凹點重新編號（逆時針方向排列），標記連續凹點設為R={r1，r2，…rm}，非連續凹點設為Q={q1，q2，…qk}。

Step1 利用射線平行法判斷R 頂點多邊形無核，輸出多邊形P 無核。

Step2 利用線性求交法，求Q，R 頂點多邊形無核，輸出多邊形P 無核。

Step3 多邊形有核，輸出線性求交的交點pj。

3 結論

本算法利用射線平行法可以迅速判斷多邊形無核情況，然后利用線性求交法處理多邊形第一類邊和第二類邊快速求出多邊形無核或核的一個交點。算法預處理只需要線性次乘法便可確定多邊形P 各頂點的凸凹性，并記住凸凹頂點。Step1 處理至多m 次求平行運算。Step2 判斷qi的第一類邊或第二類邊相交情況需要k 次求交，判斷rj各類邊需要m 次求交，最后還要求與多邊形求交，整個循環需要nmk 次求交。所以本算法求多邊形無核及多邊形核一個交點時間復雜度O(nmk)。

[1]王鉦旋,徐長青,龐云階.判斷簡單多邊形的核是否為空的一個快速算法[J].計算機輔助設計與圖形學學報,2000,12(9):656-659.

[2]汪嘉業，汪衛.簡單多邊形分解成凸多邊形差組合的算法[J].計算機輔助設計與圖形學學報，1992，4(2):22-29.

[3]任世舉，洪炳熔.判定由線性不等式圍成的凸空間是否為空的一個快速算法[J].計算機學報，1998，21(10):896-901.

[4]周培德.計算幾何——算法設計與分析（第二版）[M].清華大學出版社，2001.

[5]陳炳發，錢志鋒，廖文和.簡單多邊形凸凹性的自識別算法[J].計算機輔助設計與圖形學學報，2002，14(3):214-217.

[6]Etzion M,Rappoport A.On Compatible Star Decompositions[J].IEEE Trans-actions on Visualization and Computer Graphics,1997,3(1):87-95.