我试图找到一个适当的最佳算法，用于确定线段是否与3D凸非平面多边形相交 . 我现在能想到的最好的是绘制一条线，将非平面多边形分成两半，确定线段是否位于分割线的右侧或左侧，然后继续分割直到我可以确定交叉点 . 其背后的原因是，我可以确定给定点所在的3d球面voronoi图的哪个区域 . 但是，找到解决方案的时间可能取决于我的行拆分的浮点分辨率 .
Diagram
Non-Planar Polygon Example
在这个例子中，我将绘制蓝点和单位球体中心之间的线段（在voronoi计算之后添加，它们不是用于计算图表的点） . 然后，我需要弄清楚线段与哪个多边形相交，以确定它所在的区域 .
1 回答
这可以通过坐标几何来解决 .
首先，将多边形划分为三角形 . 例如，如果多边形是ABCDE，则考虑三角形ABC，ACD和ADE . 在您的问题中，当且仅当它与至少一个三角形相交时，线段与多边形相交 . 我们将检查线段是否以下列方式与三角形相交 .
设三角形为KLM，线段为UV . 包含KLM的平面的方程将是由cz d = 0形式的ax，而包含UV的线的方程将是（x-x_0）/ e =（y-y_0）/ f =（z-z_0）的形式）/G . 通过同时求解这些方程，我们可以找到线与平面的交点的坐标P =（x，y，z） .
一旦找到P，我们需要确保它位于UV和KLM上 . 如果从P到U和V的距离之和等于UV的长度，则前者是真的 . 对于后者，检查由P形成的三角形区域和KLM的边缘（即PKL，PLM和PMK）是否加起来为KLM区域 .