凹多边形

凹多边形

目录导航
  • 定义
  • 示例
  • 性质
  • 判断

凹多边形(Concave Polygon)可以有以下三种定义方式:

凹多边形凹多边形

  • 至少有一个(Reflexive Angle)的多边形。(例如上图中,∠CDE>180°)[1]
  • 把一个各边不自交的多边形任意一边向两方无限延长成为一直线,如果多边形的所有边中只要有一条边向两方无限延长成为一直线时,其他各边不在此直线的同旁(如上图左),那么这个多边形就叫做凹多边形。[2]
  • 凹多边形的是一个内部为凸集的简单多边形.简单多边形的下列性质与其凸性等价:1、一个内角大于180度。2、存在两个顶点间的线段位于多边形的外部。3、多边形内存在两个点,其连线不全部在多边形内部。[3]

五角星四角星八角星六角形等都是凹多边形:例如,正六角星中,有一个240°的角。[2]

  • 平面上,不可能存在凹三角形。[2]
  • 凹多边形的内角和的解,应该通过(n-2)180°来计算。实际上是把大于平角的角划分为两个角,使得任意一个凹N多边形,都可分画为N-2个三角形,因此凹多边形的内角和,也适用(N-2)180°这个公式。不可以沿着一条边的延长线切割凹多边形。[3]
  • 平面上,凹多边形与边数相同的凸多边形的内角和相等。[1]

对于平面多边形的三角化处理也是计算机图形学里面的一个领域,最近由于项目的需要,需要对平面多边形进行剖分,特此对其作了些研究。

在对平面多边形进行处理的时候,很多时候需要知道多边形的凹凸性,本文介绍两种方法来进行平面多边形凹凸性的判定,文章后面会给出示例代码。

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;

}

相关百科
返回顶部
产品求购 求购