检查4D线段和4D凸多面体的交集

Question

我有两个4D形状:一个由两个三角形组成的多面体，每个边都连接到另一个三角形上的对应边(假设是三角柱，但不一定是直的)和一条线段。

我不需要知道它们在哪里相交，只需要知道它们是否相交。我怎么才能检查这个？

Answer 1

您的凸多面体由方程ax+by+cz+dw+e = 0的多个超平面分隔。考虑多面体内部的一个点，您可以调整标志，以便所有内部点验证所有超平面的ax+by+cz+dw+e ≥ 0。

现在，线段将具有如下参数方程

x = (1-t)x'+tx''
y = (1-t)y'+ty''
z = (1-t)z'+tz''
w = (1-t)w'+tw''

你可以找到线P'P''与每个超平面的交点。您将丢弃那些使t不在[0,1]中的超平面，并丢弃那些不在其他超平面的正面中的超平面。如果找到某个交点，则多面体和线段确实相交。