工程計算機圖形學第四部分圖形處理辦法基本算法

主要內(nèi)容多邊形的方向及頂點的凸凹性判斷點在多邊形內(nèi)外判斷曲線數(shù)據(jù)壓縮算法

1浙江大學工程及計算機圖學所4.1多邊形的方向及頂點的凸凹性判斷 1.基本概念凸凹性的定義

如圖所示。如果與Pi(i=1,2,…，n)相關(guān)聯(lián)的兩條邊Pi-1

Pi與Pi

Pi+1所夾的角小于或等于π，則稱頂點Pi是凸的，否則稱頂點Pi

是凹的。2圖4-1-1圖4-1-2浙江大學工程及計算機圖學所拓撲變化的概念作為點集的幾何圖形，如果在變換時正逆兩方面的兩圖形都是單值而且連續(xù)對應，則這種對應稱為拓撲映射，相應的幾何變換稱為拓撲變換圓的拓撲映射圖4-1-3半圓的拓撲映射圖4-1-43浙江大學工程及計算機圖學所4.1多邊形的方向及頂點的凸凹性判斷 2.經(jīng)典算法介紹（1）凸凹性判斷經(jīng)典算法

4圖4-1-5浙江大學工程及計算機圖學所4.1多邊形的方向及頂點的凸凹性判斷（2）方向性判斷經(jīng)典算法--有向面積法如果sp>0，則多邊形頂點以逆時針方向連接；如果sp<0，則多邊形頂點以順時針方向連接；如果sp=0，則多邊形所有頂點共線，這與簡單多邊形的定義相矛盾，因此可以不予考慮。5圖4-1-6浙江大學工程及計算機圖學所4.1多邊形的方向及頂點的凸凹性判斷（3）方向性判斷快速算法規(guī)則1：多邊形方向與同構(gòu)凸多邊形方向相同規(guī)則2：多邊形方向與凸點的方向相同？6圖4-1-7圖4-1-8浙江大學工程及計算機圖學所4.1多邊形的方向及頂點的凸凹性判斷（4）方向性判斷新思路7圖4-1-9浙江大學工程及計算機圖學所4.1多邊形的方向及頂點的凸凹性判斷8圖4-1-10浙江大學工程及計算機圖學所4.1多邊形的方向及頂點的凸凹性判斷（3）方向性判斷新思路XXXi-1≥XXXi+1，頂點為凸頂點XXXi-1<XXXi+1，頂點為凸頂點9圖4-1-11浙江大學工程及計算機圖學所4.1多邊形的方向及頂點的凸凹性判斷實質(zhì)上與叉乘法等效10圖4-1-12浙江大學工程及計算機圖學所4.2點在多邊形內(nèi)外判斷1.叉積判斷法點在凸多邊形內(nèi)的充要條件是叉積Vi×Vi+1（i=1,2,…n）的符號相同。叉積判斷法僅適用于凸多邊形2.夾角之和檢驗法若則點在多邊形內(nèi)；若則點在多邊形外11圖4-1-13浙江大學工程及計算機圖學所4.2點在多邊形內(nèi)外判斷3.交點計數(shù)檢驗法

當多邊形是凹多邊形，甚至還帶孔時，可采用交點計數(shù)檢驗法判斷點是否在多邊形內(nèi)。具體做法是從判斷點P0作一射線至無窮遠，然后求射線與多邊形的交點，若交點個數(shù)為奇數(shù)，則點在多邊形內(nèi)，否則點在多邊形外特殊情況：若共享頂點的兩邊在射線的同一側(cè)，則交點計數(shù)加2，否則加1。具體計數(shù)時，當一條邊的兩端點y值都大于y0，即邊處于射線上方時，計數(shù)加1，否則不加12圖4-1-14圖4-1-15浙江大學工程及計算機圖學所4.3曲線數(shù)據(jù)壓縮算法命題：點數(shù)多、局部分布密集、整體分布情況復雜等特征的曲線壓縮、簡化；要求盡可能保持特征13圖4-1-16浙江大學工程及計算機圖學所Douglas-Peucker算法步驟一：確定閥值ε。步驟二：先連接第一個和最后一個邊界網(wǎng)格頂點，計算這對基準頂點對之間的點到基準線的距離。如果有一個及一個以上的點到基準線的距離大于ε，將距離基準線最遠的點記為第n個點，刪除基準線，并將第一個點和第n個點記為基準頂點對，將第n個點和最后一個點記為基準頂點對；如果所有點到基準線的距離都小于等于ε，刪除基準頂點之間的所有點，只保留基準頂點對作為基準頂點對之間曲線的控制頂點。步驟三：重復將步驟二中得到的基準頂點對進行步驟二的計算，直到所有點到他們的基準線的距離都小于等于ε。144.