凹多边形（Concave Polygon）指如果把一个多边形的所有边中，有一条边向两方无限
延长成为一
直线时，其他各边不都在此直线的同旁，那么这个
多边形就叫做凹多边形，其
内角中至少有一个
优角。
定义
凹多边形（Concave Polygon）可以有以下三种定义方式：
示例
五角星、四角星、
八角星、六角形等都是凹多边形：例如，正
六角星中，有一个240°的角。
性质
判断
对于平面多边形的三角化处理也是计算机图形学里面的一个领域，最近由于项目的需要，需要对平面多边形进行剖分，特此对其作了些研究。
在对平面多边形进行处理的时候，很多时候需要知道多边形的凹凸性，本文介绍两种方法来进行平面多边形凹凸性的判定，文章后面会给出示例代码。
1、使用角度和判断凹凸性
我们知道，任意n个顶点的凸多边形可以分解成(n-2)个三角形，一个三角形的内角和是180°，所有三角形的内角和是(n-2)*180°，这一点，对于凸多边形或者凹多边形来说都是一样的，但是对于一个凸多边形来说，不存在内角大于外角，而凹多边形则会存在。
因此，将多边形每个顶点处较小的角（内角或外角）相加，凸多边形得到(n-2)*180°,而凹多边形则小于它。至于如何判断小角，我们可以使用几何工具---向量点乘。我们知道，向
量点乘可以用来等价求两个向量的夹角，它的值（即角）总是以较短的弧度来度量的。
以下是代码的示例：
bool IsHollow(std::vector
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
& IsHollow_Vec(std::vector curveloopPoints)const{
//假设传进来的顶点数组都是按照顺时针或者逆时针遍历的，且没有重复点
//使用法向量判断凹凸性，检测多边形上是否有凸点，每个顶点的转向都应该一致，若不一致则为凹点
std::vector
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;
}