ganggouren
在实际工程中，常常需要确定平面内三角形和直线相交情况，并确定交点。这种情况在实际中有广泛的应用场景，比如二维有限元后处理中计算任意一切面的应力、应变以及位移，在三维点云后处理、地形三角网处理中求三维地形的某一竖直切面。熟悉计算机图形学的读者可能已经能想到，计算机图形学经常需要考虑空间直线和空间三角形相交的情况，但是经过研究表明三维求交点的情况不便于直接应用于二维相交的情况。
本文将介绍一种计算平面内三角形与直线相交的算法。
1、问题的简化
任何一条直线都会将平面分割成为两部分，如果以逆时针方向为正向，对于不在直线上的点，必然落在直线的内侧或外侧（三角形所在的一侧称为内侧）。如下图所示，对于任意一个三角形来说，组成三角形的三条直线将平面分割成了7个部分，任何一个不在三角形边上的点都会落在这7个区域中的一个。在计算机中不存在无限长的直线，线段都是由其两个端点定义。对于有限长度的线段，其与三角形的关系就相对比较复杂，其可能整体存在于一个、两个或者三个区域中，但不可能存在于超过四个区域中。如果要求线段与三角形相交，则线段必须要通过至少两个区域。
如果我们继续沿着以上的思路来考虑这个问题，问题将会变得过于复杂而难以求解，原因主要有以下两点：
1，线段有限长度的；
2.在得知线段两个端点所在区域后并不能直接的得出线段与三角形边是否相交，还需进一步的讨论。所以我们需要对问题做一个简化。
对于问题1，在后文中我们将考虑无限长的线段（即线段的两个端点都在三角形不同边的外侧）。对于问题2，我们改变问题的主要考虑对象，从以三角形为主要研究对象变成以直线PQ作为主要研究对象，分别考虑三角形三个顶点与直线的相对位置关系。如果三角形某条边的两个顶点在直线的同一侧，则这条边与直线不相交。如果这条边的两点在直线的两侧，则这条边与直线相交。如果三角形的三个顶点都在直线的同一侧，则三角形与直线不相交。
2、直线与三角形相交算法具体内容
根据上文的分析，研究直线与三角形相交的基础是判断两点是否在直线的同一侧。根据向量叉乘的定义，可知向量的叉乘可以很方便的判断点与直线的相对位置关系。如下图所示，v1-v2为一直线，分别计算v1-v2向量与v1-Q的叉乘以及v1-v2与v1-P的叉乘，如果这两个叉乘结果同号，则P、Q在直线的同一侧，如果异号，则P、Q在直线的异侧。
相关的代码见下
有了上面的基础，就可以进一步的研究直线与三角形相交的问题。首先计算三角形任意两个点相对于直线的关系。
如下图所示，若三角形的三个顶点v1, v2, v0都在直线pq的同一侧，则三角形与直线不相交，具体的算法即为，v1,v2 在PQ的同一侧，同时v1,v0在PQ的同一侧。
（2）三角形有一个顶点在直线上，如下图所示。具体可以分为两种类型，v1,v2在PQ的一侧，但是v0在PQ上，如左图；v0在PQ上，v1,v2在PQ的两侧，如右图。
（3）最后一种情况就是，PQ与三角形的两条边相交，这里即为v0-v1在PQ的两侧，v0-v2在PQ的两侧，这种情况可以直接计算出两个交点。
3、算法的应用
我们得出一个三角形与直线交点的求解算法之后，我们就可以很容易的算出三角形与三角网格的交点。这里提供一个非常直接的思路，通过遍历网格的所有三角形，求出每个三角形与直线的交点。当然，这个算法对于三角形数量不多的三角形网格是比较适用的，但是对于三角形数量很多的网格，本算法的效率就比较低了。
参考文献
[1]Stephen R. Marschner. Fundamentals of Computer Graphics 4th Edition.
[2]https://stackoverflow.com/questions/50218139/fast-test-to-see-if-a-2d-line-segment-intersects-a-triangle-in-python
[3]https://zhuanlan.zhihu.com/p/73686686
我们非解构一直关注建筑艺术与结构技术的有机融合。我们在做好设计的同时，一直关注数字化、智能化等前沿技术在建筑设计行业中的运用，这些年一直在坚持探索和实践。
非常欢迎优秀的你来加入我们，一起来跨界，做一名推动行业发展的斜杠青年。
这几年，对参数化设计感兴趣的朋友越来越多，我们的参数化设计交流群也已经发展到了5群，欢迎更多的朋友加入，相互交流学习。
添加我们“转自：非解构-公众号”微信，
加入参数化设计交流群。
不了解我们的可以来补课了
