四面体的交点

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 是表示平面在 space 上的确切位置的项。那么我可以用下面的方式来描述这个四面体：

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 ""

with k > d 其中 d 是识别面部的平面的已知项。感谢Rouché-Capelli theorem I know that this system admits solution if Rg (A) = Rg (A | B) where Rg stands for rank. To ensure that this equality is respected then Det (A | B) = 0 where Det stands for 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 存储常数，即 d。还要注意 A1.X 是矩阵乘法。

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

现在基本上你想像这样解决 X 的可行性问题：

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

请注意，如果求解器returns inf，则意味着不存在满足上述约束的X。如果求解器 returns 0（这是常量 objective 函数的值），则意味着至少有一个 X 满足约束。

您可以为此使用 cvxpy 库。这是一个不错的 tutorial。此外 cvxpy 库与 numpy.

相得益彰

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

四面体的交点

Intersection of tetrahedra

python

geometry

linear-algebra

linear-programming