算法：多面体与半直线的交集

Question

我正在寻找一个在 R 中用于与线段相交的凸多面体算法。我在这里找到了几篇关于平面中的帖子，但我想知道是否存在在更高维度中的算法。我的谷歌搜索并没有产生太多答案。

该线段由凸多面体内部的一个点和凸多面体外部的一个点组成。在 N<=10 的情况下，R 中是否有可用的算法来实现此功能？或者，是否有人知道一个参考资料，以便我可以自己实现算法？是否有有关查找多面体和交集的复杂性的信息？

- MrOperator

---

我认为你应该在你的问题中用“多面体”代替“多边形”，以明确你想要一个非二维的解决方案。https://en.wikipedia.org/wiki/Polytope - Spacedman

将多边形改为多面体。 - MrOperator

快速搜索建议使用CRAN-hitandrun、geozoo以及几个Github存档。 - Carl Witthoft

Answer 1

对于计算几何中的问题，维度d>3通常可以视为任意维度d。如果您将多面体表示为相交半空间的集合，则可能唯一明智的做法是将线段与每个分离超平面相交（通过解决一组d线性方程），并取最靠近内部点的交点。

如果您只有多面体的顶点，甚至只有一个凸包为多面体的顶点集，则在R的库中给出的最简单方法可能是线性规划。（可以想象，您可以使用查找高维凸包的算法来计算面，但其中可能有Theta(n^floor(d/2))个面，其中n是顶点数。）我不熟悉R中的LP求解器，因此我将以数学方式编写程序。它不应该太难翻译。让p_0是外部点，p_1是内部点，v_i是定义多面体的第i个点。

maximize alpha_0
subject to

for 1 <= j <= d,
    p_0[j] alpha_0 + p_1[j] alpha_1 - sum_{1 <= i <= n} v_i[j] beta_i = 0
alpha_0 + alpha_1 = 1
sum_{1 <= i <= n} beta_i = 1

alpha_0 >= 0
alpha_1 >= 0
for 1 <= i <= n,
    beta_i >= 0

交点由点 p_0 alpha_0 + p_1 alpha_1 定义（除非程序无法实现，否则不存在交点）。

- David Eisenstat