algorithm - 3D 凸非平面多边形的线段相交

Question

我正在尝试找到一种合适的最佳算法来确定线段是否与 3D 凸非平面多边形相交。我现在能想到的最好办法是画一条线，将非平面多边形分成两半，确定线段是位于分割线的右侧还是左侧，然后继续分割，直到我可以确定交点。其背后的原因是我可以计算给定点所在的 3d 球形 voronoi 图的哪个区域。但是，找到解决方案的时间可能取决于我的行拆分的 float 分辨率。

图表

非平面多边形示例

在这个例子中，我将在蓝色点和单位球体的中心之间绘制一条线段(在 voronoi 计算之后添加，它们不是用于计算图表的点)。然后，我需要找出该线段与哪个多边形相交，以确定它位于哪个区域。

Answer 1

这可以用坐标几何来解决。

首先，将多边形分成三角形。例如，如果多边形是 ABCDE，请考虑三角形 ABC、ACD 和 ADE。在您的问题中，线段与多边形相交当且仅当它与至少一个三角形相交时。我们将通过以下方式检查线段是否与三角形相交。

设三角形为 KLM，线段为 UV。包含 KLM 的平面方程的形式为 ax+by+cz+d=0，包含 UV 的直线的方程形式为 (x-x_0)/e = (y-y_0)/f = ( z-z_0)/克。通过同时求解这些方程，我们可以得到直线和平面交点的坐标P=(x,y,z)。

一旦找到 P，我们需要确保它同时位于 UV 和 KLM 上。当且仅当从 P 到 U 和 V 的距离之和等于 UV 的长度时，前者为真。对于后者，检查P和KLM的边(即PKL、PLM和PMK)形成的三角形的面积是否等于KLM的面积。