多边形构建三角形

TT_123456789 2020-08-03 13:34:42 1358

本篇文章将介绍怎样将一个多边形剖分成三角形,写这篇博客的背景是由于我想要利用OpenGL ES绘制面,但是OpenGL ES没有给出由多边形构建面的功能,因此为了绘制面,必须将多边形划分成三角形,以下是过程,由于查询的资料较多,中间出现讲解错误的地方,还请各位指正。

1.向量点乘

a=(x0,y0),b=(x1,y1)

a▪b=x0x1+y0y1=abcosθ θ为向量a,b的夹角

2.向量叉乘

axb=x0y2-x1y1=k

叉乘具有如下意义

a,b向量构成的平行四边形的面积。
②如果k>0时,那么a正旋转到b的角度为<180°,如果k<0,那么a正旋转到b的角度为>180°,如果k=0 那么a,b向量平行。

正旋:

平面坐标系中,坐标轴,x轴朝y轴方向旋转90°和y轴重合的方向视为正旋转。(通俗的来讲就是x轴旋转到y轴只需要旋转90°,那么这个旋转就是正旋转),如下图所示

3.简单几何图形的凸角、凹角
在简单几何图形中,在构成这个几何图形的所有点中寻找一个X坐标或者Y坐标最大的点,该点一定是凸角,如下图所示,C点一定是凸角。

简单几何体找出所有凹凸:

根据结论1,我们得知C为凸角,那么向量BC→叉乘CD→,得到一个值为k。

则得到结论,k>0时,所有叉乘积>0的为凸角,反之为凹角。k<0时,所有叉乘积<0的为凸角,反之为凹角。注意当顺时针计算时K<0为凸角,K>0时为凹角。

以上图为例:

BC→叉乘CD→ = k ,这里计算出来应该为k<0;

CD→叉乘DA→ = v ,如图所示,很明显D点对应的角是个凸角,那么v<0。(这里用图来佐证推测v<0,实际上求出来的v一定是<0,且可以通过<0的结果得到D点对应的角一定是个凸角)。

4.判断点是否在三角行内部
判断三点是否在三角形内有三种方法:面积法、重心法、同向法;前面两种方法都比较简单,这里选择同向法进行讲解。

定义:平面上的三点P1(x1,y1),P2(x2,y2),P3(x3,y3)的面积量:S(P1,P2,P3)=|y1 y2 y3|= (x1-x3)(y2-y3)-(y1-y3)(x2-x3),即向量P1P3叉乘P2P3
当P1P2P3逆时针时S为正的,当P1P2P3顺时针时S为负的。
令矢量的起点为A,终点为B,判断的点为C,
如果S(A,B,C)为正数,则C在矢量AB的左侧;
如果S(A,B,C)为负数,则C在矢量AB的右侧;
如果S(A,B,C)为0,则C在直线AB上。

假设点P位于三角形内,会有这样一个规律,当我们沿着ABCA的方向在三条边上行走时,你会发现点P始终位于边AB,BC和CA的右侧。我们就利用这一点,但是如何判断一个点在线段的左侧还是右侧呢?我们可以从另一个角度来思考,当选定线段AB时,点C位于AB的右侧,同理选定BC时,点A位于BC的右侧,最后选定CA时,点B位于CA的右侧,所以当选择某一条边时,我们只需验证点P与该边所对的点在同一侧即可。问题又来了,如何判断两个点在某条线段的同一侧呢?可以通过上面的面积量实现,计算S(A,B,P)、S(B,C,P)、S(C,A,P)是否同时为正或者为负。

5.多边形三角化
对凸多边形的三角化(没有凹角的多边形叫做凸多边形)
选择凸多边形的任意一点为起点,将当前点与该点的前面和后面一点构成三角形,然后将得到的三角形保存起来
删除当前点,形成新的多边形
重复以上步骤,直到只剩三个点
步骤如下图所示:

2.凹多边形的三角化
(1)求出所有角的凹凸性。

(2)选取其中一个凹角,然后凹角所在点,和前两点或后两点,形成一个三角形 。如果这个图形中剩余的点(三点除外的点),有任意一个点在这个三角形的内部,则证明是错误的分割,换一个凹角重复(2)操作。反之,把这3个点构成的三角形保存到三角形数组中,删除连续3点中,中间点(凹角旁边一定是凸角,所以删除的就是凸角点)。

(3)重复(1)(2)操作直到点只剩3个时终止,并且把这三个点构成一个三角形,保存到三角形数组中。

原文链接:https://blog.csdn.net/yuanheng19930119/article/details/88055949

推荐阅读:

声明:本文内容由易百纳平台入驻作者撰写,文章观点仅代表作者本人,不代表易百纳立场。如有内容侵权或者其他问题,请联系本站进行删除。
红包 点赞 收藏 评论 打赏
评论
0个
内容存在敏感词
手气红包
    易百纳技术社区暂无数据
相关专栏
置顶时间设置
结束时间
删除原因
  • 广告/SPAM
  • 恶意灌水
  • 违规内容
  • 文不对题
  • 重复发帖
打赏作者
易百纳技术社区
TT_123456789
您的支持将鼓励我继续创作!
打赏金额:
¥1易百纳技术社区
¥5易百纳技术社区
¥10易百纳技术社区
¥50易百纳技术社区
¥100易百纳技术社区
支付方式:
微信支付
支付宝支付
易百纳技术社区微信支付
易百纳技术社区
打赏成功!

感谢您的打赏,如若您也想被打赏,可前往 发表专栏 哦~

举报反馈

举报类型

  • 内容涉黄/赌/毒
  • 内容侵权/抄袭
  • 政治相关
  • 涉嫌广告
  • 侮辱谩骂
  • 其他

详细说明

审核成功

发布时间设置
发布时间:
是否关联周任务-专栏模块

审核失败

失败原因
备注
拼手气红包 红包规则
祝福语
恭喜发财,大吉大利!
红包金额
红包最小金额不能低于5元
红包数量
红包数量范围10~50个
余额支付
当前余额:
可前往问答、专栏板块获取收益 去获取
取 消 确 定

小包子的红包

恭喜发财,大吉大利

已领取20/40,共1.6元 红包规则

    易百纳技术社区