“凸”字形單調多邊形三角剖分算法的研究

劉 燕

（赤峰學院 計算機科學與技術系，內蒙古 赤峰 024000）

“凸”字形單調多邊形三角剖分算法的研究

劉 燕

（赤峰學院 計算機科學與技術系，內蒙古 赤峰 024000）

單調多邊形的三角剖分是計算幾何的一個重要分支，其中嚴格單調多邊形的三角剖分已有了線性時間算法，但該算法對于一般單調多邊形還不能給出正確的剖分.本文對嚴格單調多邊形三角剖分算法進行了詳細分析，給出了一般單調多邊形的三角剖分算法.

對角線；單調多邊形；三角剖分

1 引言

計算幾何研究的任務是如何處理通過各種途徑獲得的幾何信息，給出最優(yōu)的處理幾何信息的方法.而多邊形正是許多真實物體外形的一種既方便又精確的描述工具，并且在計算上很容易實現(xiàn).它的應用包括自動符號識別中單個符號的形狀，機器人運動時要避免的障礙物的形狀等.但是通常多邊形又是相當復雜的，因此經(jīng)常需要將它們看成是由簡單的部分組成，這就是劃分多邊形的問題.例如對真實圖像進行抽象和二值化后，再進行三角剖分，通過和標準圖像的匹配，用于外觀檢測和篩選等[1].可見多邊形的三角剖分是計算幾何的一個重要分支，隨著計算機在圖形圖像處理方面的廣泛應用，對多邊形的三角剖分及其對偶圖的研究與應用，越來越受到重視.

2 簡單多邊形三角剖分的重要概念[2]

簡單多邊形：設平面上n個點p1,p2,…,pn按循環(huán)排序方法逆時針排列，p1在pn之后，有設e1=p1p2,e2=p2p3,…,en=pnp1是連接各點的n條線段，則這些線段界限一個多邊形，并且滿足：

①循環(huán)排序中相鄰線段對的交點是兩者之間的公共單頂點：ei∩ei+1=pi+1；

②不相鄰的線段不相交，ei∩ej=覫，j≠i+1；i=1,2,…,n；en+1=e1，pn+1=p1.

（2）鏈：是一條折線，記作：L=，其中 p={p1,p2,…,i=1,2,…}是頂點集，e={e1,e2,…,i=1,2,…}是邊集.

（3）單調：若對于任一正交于鏈L的直線L'，有L'交L是空集或是一個點，或是一段線段，即至多只交于一個連通的部分，稱鏈L關于直線L`是單調的.如果L'與L只交于一點或不交，則稱鏈L關于直線L`為嚴格單調.

（4）對角線：P 是多邊形，pi、pj∈P，若 pipj∈P，則稱pi、pj彼此可視的.若pipj與多邊形的邊界只交于兩個頂點，則稱pi、pj是清晰可視的.清晰可視的兩頂點之間的線段，稱為多邊形的對角線.

（5）凸頂點：對于多邊形任意三個連續(xù)的頂點pi,pi+1,pi+2,若pipi+2是對角線，則角pi+1稱為凸角，頂點pi+1稱為凸頂點.

（6）三角剖分：多邊形三角剖分是指：對于任意簡單的多邊形，連接其所有的對角線，將多邊形劃分為若干個三角形平鋪的集合.

3 簡單多邊形的三角剖算法分析

簡單多邊形的三角剖分方法一般是先經(jīng)過修剪歧點[2]，將其變?yōu)閲栏駟握{多邊形，再按Y坐標由低到高劃分為左右兩條嚴格單調的鏈Ll與Lr，進而對嚴格單調多邊形進行三角剖分，嚴格單調多邊形三角剖分的算法概要在文獻[3]、[4]中有詳細的敘述，算法的基本特點為：

（1）p不在凹鏈上，以p為基點將凹鏈中的點由下向上去掉三角形，直到p進入凹鏈為止.

（2）p在凹鏈上，以p為基點將凹鏈中的點由上向下去掉三角形，直到p進入凹鏈為止.

（3）對于當前處理的頂點p，當無對角線輸出時，才進入凹鏈，可見凹鏈中的頂點除頭頂點以外，必然屬于同一條多邊形的分支鏈，且是凹的或平的.

為了討論問題方便起見，本文所用的坐標系為水平向右為x軸，豎直向下為y軸.將上述算法應用于下面的圖1，如果在list中，y值相同的頂點，右鏈處于優(yōu)先的位置，即list={p1,p3,p4,p2,…}，輸出對角線為dlist={p4p1,p4p2,…}，可以給出正確的三角剖分；如果左鏈處于優(yōu)先的位置，即list={p1,p2,p3,p4,…}；則輸出對 dlist={p3p2,p4p2, …}，由于 p2、p3、p4三點在同一水平線上，則p2p3不是正確的對角線.可見此時不會給出正確的三角剖分.

圖1

對于圖2而，如果在list中，y值相同的頂點，左鏈處于優(yōu)先的位置，即list={p1,p2,p3,p4,p5,p6,…}，凹鏈中頂點為vchain={p1,p2,p3,p4}，p=p5時 ，按原算法依此輸出對角線為 dlist= {p5p2,p5p3,p5p4,…}，顯然由于 p2、p5不在同一條水平線上，p5p2是正確的對角線，p3、p5雖然共線，但卻是左右兩鏈中所有同一條水平線上離的最近的點，因而也是正確的對角線，p4、p5也是水平共線的兩點，但由于中間有點p3，因而p5p4不是正確的對角線.可見此時也不會給出正確的三角剖分.如果在list中，y值相同的頂點，右鏈處于優(yōu)先的位置，則先輸出對角線p5p2后，就與圖1相似了，同樣不會給出正確的三角剖分.

圖2

圖3和圖1的情況也相似，右鏈優(yōu)先時可以給出正確的三角剖分，左鏈優(yōu)先時不會給出正確的三角剖分.出現(xiàn)錯誤的原因是上述三個多邊形不是嚴格單調的，它們在水平方向上有多個點共線，構成一個連通的區(qū)域，使得由原算法輸出的對角線與多邊形的邊重和，不符合計算幾何中對角線的定義.由此得出如下兩點結論：

圖3

（1）上述算法不適用一般單調多邊形的三角剖分，問題均出在p不在凹鏈上的情況下.

（2）單調多邊形的三角剖分算法的正確與否和多邊形頂點進入list鏈中時,左、右兩鏈中y值相同的頂點誰優(yōu)先有關.

在下面分析一般單調多邊形的三角剖分算法時，約定在list中，y值相同的頂點，以左鏈優(yōu)先.根據(jù)原算法思想，如果p在凹鏈vchain上，則無須判斷沿x軸方向頂點有無共線，若x（凹鏈中的尾頂點）是嚴格凸頂點的，連p和凹鏈的倒數(shù)第二個頂點，去掉三角形；否則p進凹鏈.原算法在這一部分不用做改動.下面重點討論p不在凹鏈上的情況.

對圖2而言，當p=p5不在凹鏈上，按原算法輸出對角線 p5p2，p5p3以后，凹鏈中頂點集為vchain={p3,p4}，由于 p3、p4、p5 在水平方向共線，p3在中間，按愿算法輸出的對角線p4p5是不正確的.可見，當p不在凹鏈上時，算法必須先判斷p與凹鏈中的第二個頂點是否沿水平方向共線，若不共線，則可按原算法輸出對角線；否則必須對共線的頂點做特殊處理后才能輸出正確的對角線.

對圖3而言，當p=p5不在凹鏈上，按原算法輸出對角線p5p2，凹鏈中頂點集為vchain={p2,p3,p4}，若原算法還應輸出對角線 p5p3，p5p4，由于 p3、p4、p5、p6在水平方向共線，p3、p6在中間，顯然按愿算法輸出的對角線p5p3、p5p4是不正確的.同樣必須對共線的頂點做特殊處理后才能輸出正確的對角線.本文解決上述問題的方法如下：

（1）由于在list中，y值相同的頂點，以左鏈優(yōu)先，所以當凹鏈屬左鏈時（以凹鏈中尾頂點原屬的鏈為準），當前待處理的頂點p不在凹鏈上，才會出現(xiàn)圖2、圖3的情況；此時能否正確輸出對角線，要看頂點p、w（凹鏈中的第二個頂點）和s(p在list中的后繼)三者間的位置關系.當凹鏈屬右鏈時，當前待處理的頂點p不在凹鏈上，那么p是左鏈上的頂點，它必然在凹鏈以下，原算法不會輸出錯誤的對角線.

（2）由于處于同一水平線上的點分別屬于不同的單調鏈，當凹鏈屬左鏈而頂點p為右鏈時，只有分屬于兩個鏈中且離的最近的兩點之間才有一條正確的對角線，而其他點的對角線，要么是和水平線以上的點相連，即和凹鏈中的頭頂點相連；要么是和水平線以下的點相連，這些點仍在list鏈中.

（3）當凹鏈中的所有點都處于同一水平線上時，由于簡單多邊形的特點，這些點不能沿x軸往復分布，只能沿某一方向分布，所以，必須將就這些點重新沿x軸方向排序.

（4）當凹鏈中的點處于同一水平線且分別屬于不同的單調鏈時，對于后續(xù)處理的某個頂點p而言，它必然有時在凹鏈上，有時又不在凹鏈上，即有時要刪除凹鏈的頭頂點，有時又要刪除凹鏈的尾頂點，這將會導致錯誤.為此，在對凹鏈中的共線點排序的同時，還必須把所有的點改為和p點處于同一鏈中.

將上述四點應用于圖2，當p=p5時，刪除頭頂點p1后，由于p6.x>p5.x，此時因為p3、p5之間有正確對角線，可輸出對角線p5p3并刪除頭頂點p2，此時凹鏈vchain={p3,p4,}已變成平的，然后將凹鏈沿x軸排序，并改變頂點所屬的鏈，這樣將導致p5、p6依此進入凹鏈中，凹鏈vchain={p3,p4,p5,p6}，當p=p7時，再輸出對角線{p7p3,p7p5,p7p6}.對于圖3，當p=p5時，由于p5.x

4 一般單調多邊形的三角剖分算法

約定：h：vchain中的頭頂點；p當前待處理的頂點；s：p 在 list中的后繼；x：vchain 中的尾頂點；w：vchain中的第二個頂點或倒數(shù)第二個頂點；flag：頂點的鏈屬性，L表示左鏈，R表示右鏈；

輸入：單調多邊形的兩條鏈Ll、Lr；沿y軸將左、右兩鏈的頂點合并為頂點表vlist，并約定當兩鏈中的頂點y坐標相同時，以左鏈優(yōu)先.

輸出：對角線表dlist；

由于當p點在凹鏈時，原算法不需要修改，下面僅給出p不在凹鏈上的部分算法：[1、頂點排序]

沿y軸將左、右兩鏈的頂點合并為頂點表vlist，并約定當兩鏈中的頂點y坐標相同時，以左鏈優(yōu)先.

[3.3重復剖分]若p不是vlist中的最小頂點或凹鏈中有兩個以上頂點，做3.1或3.2；否則算法結束.

運用上述算法對圖4進行剖分如下：

左鏈L={p2,p3,p4,p7,p8,p11}；右鏈 R={p1,p5,p6,p9,p10,p12}；

vlist={p2,p1,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12}；

dlist={p3p1,p5p3,p7p3,p7p5,p7p6,p8p6,p10p6,p10p8,p11p10}；

圖4

5 算法的時間復雜性分析

該算法和原算法相比更加通用，更加高效，且易于實現(xiàn).對所有頂點排序，時間復雜性[5]可達o(n)；初始化時間復雜性可達o(1)，剖分時，每個頂點進出凹鏈最多為一次，所以時間復雜性最多為o(n)，如有同一水平線上的頂需排序，時間復雜性可達o(n).所以總的時間復雜性上界為o(n)，下界為o(n2).本算法已在V.B6.0上實現(xiàn).

〔1〕楊平，林意.一種三角剖分算法實現(xiàn)圖形的匹配.計算機工程與應用，2003（8）.

〔2〕Zhou Peide，An algorithm for partitioning polygons into convex parts.Journal Beijing Institute of Technology,1997,6(4):363-368.

〔3〕周培德.計算幾何—算法分析與設計.清華大學出版社，2000.

〔4〕廖士中.計算幾何講義.遼寧師范大學，1999.

〔5〕嚴蔚敏.數(shù)據(jù)結構.清華大學出版社，1996.

TP393

A

1673-260X（2010）01-0025-03

內蒙古自治區(qū)高等院校科研項目基金資助（NJzy08153）