凹多邊形

凹多邊形

凹多邊形(Concave Polygon)指如果把一個多邊形的所有邊中,有一條邊向兩方無限延長成為一直線時,其他各邊不都在此直線的同旁,那么這個多邊形就叫做凹多邊形,其內角中至少有一個鈍角。

定義

凹多邊形(Concave Polygon)可以有以下三種定義方式:

凹多邊形 凹多邊形

•至少有一個優角(Reflexive Angle)的多邊形。(例如上圖中,∠CDE>180°)

•把一個各邊不自交的多邊形任意一邊向兩方無限延長成為一直線,如果多邊形的所有邊中只要有一條邊向兩方無限延長成為一直線時,其他各邊不在此直線的同旁(如上圖左),那么這個多邊形就叫做凹多邊形。

•凹多邊形的是一個內部為非凸集的簡單多邊形.簡單多邊形的下列性質與其凸性等價:1、一個內角大於180度。2、存在兩個頂點間的線段位於多邊形的外部。3、多邊形記憶體在兩個點,其連線不全部在多邊形內部。

示例

五角星四角星八角星六角形等都是凹多邊形:例如,正六角星中,有一個240°的角。

性質

•平面上,不可能存在凹三角形。

•凹多邊形的內角和的解,應該通過(n-2)180°來計算。實際上是把大於平角的角劃分為兩個角,使得任意一個凹N多邊形,都可分畫為N-2個三角形,因此凹多邊形的內角和,也適用(N-2)180°這個公式。不可以沿著一條邊的延長線切割凹多邊形。

•平面上,凹多邊形與邊數相同的凸多邊形的內角和相等。

凹多邊形 凹多邊形

判斷

對於平面多邊形的三角化處理也是計算機圖形學裡面的一個領域,最近由於項目的需要,需要對平面多邊形進行剖分,特此對其作了些研究。

在對平面多邊形進行處理的時候,很多時候需要知道多邊形的凹凸性,本文介紹兩種方法來進行平面多邊形凹凸性的判定,文章後面會給出示例代碼。

1、使用角度和判斷凹凸性

我們知道,任意n個頂點的凸多邊形可以分解成(n-2)個三角形,一個三角形的內角和是180°,所有三角形的內角和是(n-2)*180°,這一點,對於凸多邊形或者凹多邊形來說都是一樣的,但是對於一個凸多邊形來說,不存在內角大於外角,而凹多邊形則會存在。

因此,將多邊形每個頂點處較小的角(內角或外角)相加,凸多邊形得到(n-2)*180°,而凹多邊形則小於它。至於如何判斷小角,我們可以使用幾何工具---向量點乘。我們知道,向

量點乘可以用來等價求兩個向量的夾角,它的值(即角)總是以較短的弧度來度量的。

以下是代碼的示例:

bool IsHollow(std::vector<Position3> curveloopPoints)const

{

//使用角度和判斷凹凸性:凸多邊形的內角和為(n-2)*180°

auto num = curveloopPoints.size();

float angleSum = 0.0;

for (int i = 0; i < num; i++)

{

Vector3 e1;

if (i==0)

{

e1 = curveloopPoints[num - 1] - curveloopPoints[i];

}

else

{

e1 = curveloopPoints[i - 1] - curveloopPoints[i];

}

Vector3 e2;

if (i==num-1)

{

e2 = curveloopPoints[0] - curveloopPoints[i];

}

else

{

e2 = curveloopPoints[i + 1] - curveloopPoints[i];

}

//標準化並計算點乘

e1.normalize(); e2.normalize();

float mdot = e1%e2;

//計算較小值

float theta = acos(mdot);

//加和

angleSum += theta;

}

//計算內角和

float convexAngleSum = float((num - 2))*YZ_PI;

//判斷凹凸性

if (angleSum<(convexAngleSum-(float(num)*0.00001)))

{/*

if (HollowPoints.size()>0)

{*/

//m_IsHollow = true;

//}

return true;//是凹

}

return false;//否則是凸

}

2、使用矢量判斷凹凸性,檢測多邊形的凸點

檢測多邊形上是否有凹點,如果沒有則為凸多邊形。其原理是,凸多邊形的每個頂點的轉向都應該一致,不一致的點 就是凹點。

我們判斷一個頂點的轉向,使用的是另一個幾何工具---向量叉乘。

這裡我們需要平面的法向量,根據法向量來檢測多邊形的每個頂點:

用相鄰的兩個邊向量計算該頂點的法向量,接著用多邊形的法向量和定點的法向量點乘,若點乘值為負(方向相反),則該頂點就是一個凹點。以下即為示例代碼:

const std::vector<Position3>& IsHollow_Vec(std::vector<Position3> curveloopPoints)const

{

//假設傳進來的頂點數組都是按照順時針或者逆時針遍歷的,且沒有重複點

//使用法向量判斷凹凸性,檢測多邊形上是否有凸點,每個頂點的轉向都應該一致,若不一致則為凹點

std::vector<Position3> HollowPoints;

auto num = curveloopPoints.size();

Vector3 HollowNor = (curveloopPoints[num-1] - curveloopPoints[0])* (curveloopPoints[1] - curveloopPoints[0]);

Vector3 Nor;

for (int i = 0; i < num;i++)

{

if (i==0)//第一個點

{

Nor = (curveloopPoints[0] - curveloopPoints[num - 1])* (curveloopPoints[1] - curveloopPoints[0]);

if ((Nor%HollowNor)>0.0)//如果點乘大於0

{

HollowPoints.push_back(curveloopPoints[i]);

}

}

else if (i==num-1)//最後一個點

{

Nor = (curveloopPoints[i] - curveloopPoints[i - 1])* (curveloopPoints[0] - curveloopPoints[i]);

if (((Nor%HollowNor) > 0.0))//如果點乘大於0

{

HollowPoints.push_back(curveloopPoints[i]);

}

}

else//中間點

{

Nor = (curveloopPoints[i] - curveloopPoints[i - 1])* (curveloopPoints[i+1] - curveloopPoints[i]);

if (((Nor%HollowNor) > 0.0))//如果點乘大於0

{

HollowPoints.push_back(curveloopPoints[i]);

}

}

}

return HollowPoints;

}

相關詞條

相關搜尋

熱門詞條

聯絡我們