基本介紹
- 中文名：凹多邊形
- 外文名：Concave Polygon
- 定義：內角中至少有一個優角的多邊形
- 屬於：幾何圖形
- 分類：數學
- 性質：至少一個鈍角
定義,示例,性質,判斷,
定義
凹多邊形（Concave Polygon）可以有以下三種定義方式：
凹多邊形- 至少有一個優角（Reflexive Angle）的多邊形。（例如上圖中，∠CDE>180°）
- 把一個各邊不自交的多邊形任意一邊向兩方無限延長成為一直線，如果多邊形的所有邊中只要有一條邊向兩方無限延長成為一直線時，其他各邊不在此直線的同旁（如上圖左），那么這個多邊形就叫做凹多邊形。
示例
性質
- 平面上，不可能存在凹三角形。
- 凹多邊形的內角和的解，應該通過（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;
}
