平面图形原理总结（3）：多边形相交

前言

继续总结关于图形学的问题，这次总结下多边行的相交问题，同样可以自行阅读参考文献了解，以下是本人的自行总结内容。

参考文献:《计算机图形学——用OpenGL实现(第2版)》 清华大学出版社

平面直线与多边形相交

首先要说明一个定义——外法向量，指的是多边形的边指向多边形外部的法向量。要想确立多边形每条边的外法向量，简单的方法就是顺时针记录多边形的顶点集合$P_i$，对应边的集合$E_i=P_{i+1}-P_i$，边的外法向量集合$E_i^{\perp }$便是$E_i$的逆时针法向量
具体步骤便是，依次对多边形的每一条边做直线与线段的相交检测（具体请参考前面的章节平面图形原理总结（1）：直线相交）

平面线段与多边形相交

步骤大致与直线与多边形相交的方法相似，可用两直线相交的方法，但是要记录下所有线段所在直线与多边形边所在直线的相交点的t值，同时要区分入点与出点。出入点区分方法是用线段的向量$n$与多边形边的外法向量$E_i^{\perp }$做点乘：
若$n\cdot E_i^{\perp }<0$，则为入点；
若$n\cdot E_i^{\perp }>0$，则为出点；
若$n\cdot E_i^{\perp }=0$，则线段与多边行的边平行（考虑重合问题）；
取入点所有记录t与0的最大值，出点所有记录t与1的最小值；
若存在$0\le t\le 1$，则线段与多边形相交。

平面多边形与多边形相交

以上述线段与多边形相交为单元步骤，对多边形的每一条边做与另一多边形的相交判断，即可得到多边形与多边形的相交检测。

平面圆与多边形相交

具体步骤便是，依次对多边形的每一条边做圆与线段的相交检测（具体请参考前面的章节平面图形原理总结（2）：点与直线）

补充：凸多边形的投影法相交检测

具体步骤为：检测图形对多边形每条边的法向量形成的坐标系做投影，若其中一边的检测中，存在图形的投影与多边形自身的投影范围没有重合部分，则图形与多边形不相交；反之，则相交。
注意：投影法只适用于凸多边形，凹多边形不适用。
【投影法没有参考书籍中记载，具体描述，可自行上网查找】

最后

以上就是笨笨舞蹈为你收集整理的平面图形原理总结（3）：多边形相交的全部内容，希望文章能够帮你解决平面图形原理总结（3）：多边形相交所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。