3D 凸非平面多边形的线段相交
Line Segment Intersection of a 3D Convex Non-Planar Polygon
我正在尝试找到一种合适的最佳算法来确定线段是否与 3D 凸非平面多边形相交。我现在能想到的最好办法是画一条线，将非平面多边形分成两半，确定线段是位于分割线的右侧还是左侧，然后继续分割，直到我可以确定交点。其背后的原因是我可以计算给定点所在的 3d 球形 voronoi 图的哪个区域。但是，找到解决方案的时间可能取决于我的行拆分的浮动分辨率。
图表
非平面多边形示例
在这个例子中，我将在蓝色点和单位球体的中心之间绘制一条线段（在 voronoi 计算之后添加，它们不是用于计算图表的点）。然后，我需要找出线段与哪个多边形相交，以确定它位于哪个区域。
这个可以用坐标几何来解决
首先，将多边形分成三角形。例如，如果多边形是 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的面积。
我正在尝试找到一种合适的最佳算法来确定线段是否与 3D 凸非平面多边形相交。我现在能想到的最好办法是画一条线，将非平面多边形分成两半，确定线段是位于分割线的右侧还是左侧，然后继续分割，直到我可以确定交点。其背后的原因是我可以计算给定点所在的 3d 球形 voronoi 图的哪个区域。但是，找到解决方案的时间可能取决于我的行拆分的浮动分辨率。
图表
非平面多边形示例
在这个例子中，我将在蓝色点和单位球体的中心之间绘制一条线段（在 voronoi 计算之后添加，它们不是用于计算图表的点）。然后，我需要找出线段与哪个多边形相交，以确定它位于哪个区域。
这个可以用坐标几何来解决
首先，将多边形分成三角形。例如，如果多边形是 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的面积。