四面体交点

Question

我希望尽可能清楚。我试图实现一个函数，给出两个四面体，检查它们是否相交。我正在使用python，我使用的唯一库是NumPy。为了描述一个四面体，我使用它的4个顶点，每个顶点用坐标x，y，z来描述。

vertex = [x, y, z]

tetrahedra = [vertex 1,vertex 2,vertex 3,vertex 4]

这就是我想用的理由：

• 四面体只不过是一个由不等式定义的区域。
• 这些不等式由含有四面体面的平面描述。
• 所以给出两个四面体的不等式，并把它们放在一个系统中，如果这个系统允许一个解，那么就有一个交点。

这是我的职责：

def IsInterpenetrated(self, tetrahedra):
    A= []
    B= []
    sol= 0
    for tr in [self, tetrahedra]:
        print("Plane of tetrahedra")
        vertexList = tr.vertices
        i=0
        while i<4:
            if handedness(vertexList)>0:
                n= numpy.cross(vertexList[1].coords - vertexList[0].coords, vertexList[2].coords - vertexList[0].coords)
            else:
                n= numpy.cross(vertexList[2].coords - vertexList[0].coords, vertexList[1].coords - vertexList[0].coords)
            
            p0= vertexList[0].coords
            d= -(n[0]*p0[0] + n[1]*p0[1] + n[2]*p0[2])
            
            print("normal: ", n , end="      ")
            print("termine noto: ",(d))

            if len(A) > 3:
                j=0
                while j<=3:
                    if numpy.all(-n == A[j]) and -d == B[j]:
                        sol = 1
                    j= j+1

            A.append(n)
            B.append(d)

            p0= vertexList[0]
            vertexList[0] = vertexList[1]
            vertexList[1] = vertexList[2]
            vertexList[2] = vertexList[3]
            vertexList[3] = p0

            i=i+1

    A= numpy.array(A)
    B= numpy.array(B)
    print("\n")

    print("Disequazioni:\n")
    i=0
    for n in A:
        print("({0})x + ({1})y + ({2})z + ({3}) > 0".format(n[0],n[1],n[2],B[i]))
        i=i+1
    print("\n")

    x = cvxpy.Variable(3)
    prob = cvxpy.Problem(cvxpy.Minimize(0),[A @ x + B >= 0])
    prob.solve()
    if prob.value == 0 and sol != 1:
        return 1
    return 0

在这种情况下，我用cvxpy解决了不等式系统，并证明了两个四面体具有共同面的特殊情况。我想知道你是否认为下面的推理是正确的，以避免处理不平等系统。每一个识别四面体面的平面都属于平行面束族，其描述方式如下: ax + by + cz +k=0，其中k是表示平面在空间中的确切位置的术语。然后我可以用以下的方式来描述四面体：

System:
a'x + b'y + c'z = k '
a "x + b" y + c "z = k"
a '"x + b'" y + c '"z = k'"
a "" x + b "" y + c "" z = k ""

对于k>d，其中d是识别面部的平面的已知项。多亏了Rouché-Capelli定理，我知道如果Rg (A) = Rg (A = B)其中Rg代表排名，那么这个系统可以接受解决方案。为了确保这个相等性得到尊重，那么Det (A _因为在我的例子中，B由变量组成：

(k ', k ", k"', ......, kᵐ)

然后，若要使Det (A = B) =0，我必须求解这个计算所建立的方程。在对两个四面体进行了这个推理之后，我发现自己有两个方程，其中有3个未知数。每个四面体一个。通过将这两个方程放入一个系统中，我必须看到k的值是否允许解。如果系统尊重k的值，那么我就有交集，否则没有。我不知道这是否可行，但我更愿意分享我的想法，以便一起讨论。

提前谢谢。

Answer 1

为什么不用你所拥有的平面不等式来构造一个凸优化问题，或者精确地说是一个可行性问题？假设这两个四面体可以表示为A1.X + d1 <= 0和A2.X + d2 <= 0，其中A1和A2的4行存储与ax + by + cz + d <= 0中的两个四面体对应的四个平面的a, b, c，列向量d1和d2存储常数，即d。同时也注意到A1.X是矩阵乘法。

将(x, y, z)表示为向量X。

现在，基本上您希望解决X的可行性问题，如下所示：

minimize 0
subject to A1.X + d1 <= 0
           A2.X + d2 <= 0

注意，如果求解器返回inf，这意味着不存在满足上述约束的X。如果求解器返回0 (这是常数目标函数的值)，这意味着至少有一个满足约束条件的X。

为此，您可以使用cvxpy库。这是一个不错的教程。此外，cvxpy库与numpy很相配。

我不认为解方程，会在这种情况下起作用，因为四面体基本上是由四个线性不等式组成的。所以你必须求解inequalities，才能在它们的交集区域找到一个解。