点是否在 三角形,凸多边形, 凹多边形,四面体高维单形内的判断

对于三角形的情况, 我们使用有向面积来判断,假设三角形三个点为(x1,y1),(x2,y2), (x3,y3), 需要判断的点为(x,y). 根据向量代数的公式, 已知3点坐标, 判断三角形有向面积为

点是否在 三角形,凸多边形, 凹多边形,四面体高维单形内的判断

有向面积的正负与行列式的排列顺序有关(交换行列式的任意两行, 行列式的正负发生变化)

简单的可以展开为 A0 = (x1y2 – x1y3 – x2y1 + x3y1 + x2y3 - x3y2)/2. 这个判断式子与 叉乘的判断的公式是一模一样的. 可以看出通过有向面积可以统一 <编程之美>中的两种方法, 面积与叉乘的方法在数学本质上是一致的.

 

如何判断一个点在四面体的内部呢? 使用有向体积的概念. 假设四面体的四个顶点的坐标为 (x1,y1,z1), (x2,y2,z2), (x3,y3,z3), (x4,y4,z4).  需要判断的点为(x,y,z). 那么原来四面体的有向体积 为

 

点是否在 三角形,凸多边形, 凹多边形,四面体高维单形内的判断

 

同理剩下的4个有向体积分别为

点是否在 三角形,凸多边形, 凹多边形,四面体高维单形内的判断

点是否在 三角形,凸多边形, 凹多边形,四面体高维单形内的判断

 

判断准则很简单, V0与V1V2V3V4都同向的时候, 则点位于四面体内, 否则位于四面体外.  当Vi = 0 的时候, 则此四面体退化了.