判断平面多边形的凹凸性

2024-03-01 08:08
文章标签 多边形 判断 平面 凹凸

本文主要是介绍判断平面多边形的凹凸性,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

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

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;}
 

以上两种判断多边形凹凸性的方法来自于《3D数学基础图形与游戏开发》一书,并由自己编程实现。

这篇关于判断平面多边形的凹凸性的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/761745

相关文章

Go语言中nil判断的注意事项(最新推荐)

《Go语言中nil判断的注意事项(最新推荐)》本文给大家介绍Go语言中nil判断的注意事项,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1.接口变量的特殊行为2.nil的合法类型3.nil值的实用行为4.自定义类型与nil5.反射判断nil6.函数返回的

python判断文件是否存在常用的几种方式

《python判断文件是否存在常用的几种方式》在Python中我们在读写文件之前,首先要做的事情就是判断文件是否存在,否则很容易发生错误的情况,:本文主要介绍python判断文件是否存在常用的几种... 目录1. 使用 os.path.exists()2. 使用 os.path.isfile()3. 使用

Go语言如何判断两张图片的相似度

《Go语言如何判断两张图片的相似度》这篇文章主要为大家详细介绍了Go语言如何中实现判断两张图片的相似度的两种方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 在介绍技术细节前,我们先来看看图片对比在哪些场景下可以用得到:图片去重:自动删除重复图片,为存储空间"瘦身"。想象你是一个

Python如何判断字符串中是否包含特殊字符并替换

《Python如何判断字符串中是否包含特殊字符并替换》这篇文章主要为大家详细介绍了如何使用Python实现判断字符串中是否包含特殊字符并使用空字符串替换掉,文中的示例代码讲解详细,感兴趣的小伙伴可以了... 目录python判断字符串中是否包含特殊字符方法一:使用正则表达式方法二:手动检查特定字符Pytho

判断PyTorch是GPU版还是CPU版的方法小结

《判断PyTorch是GPU版还是CPU版的方法小结》PyTorch作为当前最流行的深度学习框架之一,支持在CPU和GPU(NVIDIACUDA)上运行,所以对于深度学习开发者来说,正确识别PyTor... 目录前言为什么需要区分GPU和CPU版本?性能差异硬件要求如何检查PyTorch版本?方法1:使用命

Python如何精准判断某个进程是否在运行

《Python如何精准判断某个进程是否在运行》这篇文章主要为大家详细介绍了Python如何精准判断某个进程是否在运行,本文为大家整理了3种方法并进行了对比,有需要的小伙伴可以跟随小编一起学习一下... 目录一、为什么需要判断进程是否存在二、方法1:用psutil库(推荐)三、方法2:用os.system调用

Python实现特殊字符判断并去掉非字母和数字的特殊字符

《Python实现特殊字符判断并去掉非字母和数字的特殊字符》在Python中,可以通过多种方法来判断字符串中是否包含非字母、数字的特殊字符,并将这些特殊字符去掉,本文为大家整理了一些常用的,希望对大家... 目录1. 使用正则表达式判断字符串中是否包含特殊字符去掉字符串中的特殊字符2. 使用 str.isa

Python中判断对象是否为空的方法

《Python中判断对象是否为空的方法》在Python开发中,判断对象是否为“空”是高频操作,但看似简单的需求却暗藏玄机,从None到空容器,从零值到自定义对象的“假值”状态,不同场景下的“空”需要精... 目录一、python中的“空”值体系二、精准判定方法对比三、常见误区解析四、进阶处理技巧五、性能优化

C++实现回文串判断的两种高效方法

《C++实现回文串判断的两种高效方法》文章介绍了两种判断回文串的方法:解法一通过创建新字符串来处理,解法二在原字符串上直接筛选判断,两种方法都使用了双指针法,文中通过代码示例讲解的非常详细,需要的朋友... 目录一、问题描述示例二、解法一:将字母数字连接到新的 string思路代码实现代码解释复杂度分析三、

Java判断多个时间段是否重合的方法小结

《Java判断多个时间段是否重合的方法小结》这篇文章主要为大家详细介绍了Java中判断多个时间段是否重合的方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录判断多个时间段是否有间隔判断时间段集合是否与某时间段重合判断多个时间段是否有间隔实体类内容public class D