四面体交点

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 theorem ，我知道如果Rg（A）=Rg（A | B），这个系统允许解，其中Rg代表rank。为了确保这种平等性得到尊重，那么Det（A | B）=0，其中Det代表determinant。因为在我的例子中，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行存储了a, b, c中对应于两个四面体的四个平面的ax + by + cz + d <= 0，列向量d1和d2存储了常数ied。还要注意A1.X是矩阵乘法

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

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

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

请注意，如果解算器返回inf，则表示不存在满足上述约束的X。如果解算器返回0（这是常量目标函数的值），则表示至少有一个X满足约束

您可以为此使用cvxpy库。这是一个不错的tutorial。另外cvxpy库与numpy很好地结合

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