我正在 R 中寻找一种算法来将凸多面体与线段相交。我在这里找到了几篇关于飞机上堆栈交换的帖子，但我想知道这种算法是否存在于更高维度。我的谷歌搜索并没有真正产生很多答案。
线段由凸多面体内部的点和外部的点组成。 R 中是否有可用的算法可以在维度 N
最佳答案
对于计算几何中的问题，维度 d > 3 通常也可能是 d 任意的。如果您将多面体作为相交半空间的集合，那么可能唯一明智的做法是将线段与每个分离超平面相交(通过求解 d 线性方程组)并取最接近该点的交点里面。
如果您只有多面体的顶点，甚至只有一组顶点的凸闭合是多面体，那么给定 R 库的最简单方法可能是线性规划。 (可以想象，您可以使用算法计算面以找到高维凸包，但它们可能有 Theta(n^floor(d/2))，其中 n 是顶点数。)我不熟悉 R 中的 LP 求解器，所以我会用数学方法写下程序。翻译应该不会太难。令 p_0 为外部点，p_1 为内部点，v_i 为 i 第 p_0 alpha_0 + p_1 alpha_1 点，定义多面体。
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
交点由点 ojit_code 定义(除非程序不可行，在这种情况下没有交点)。
关于r - 算法相交多面体和半线，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/25399417/