Блог

Предположим, у меня есть два тетраэдра, и это координаты вершин. Они не могут иметь частей друг внутри друга, и их расстояние всегда будет больше 0. Как рассчитать минимальное расстояние между ними?

Мой подход, который мне не очень понравился, потому что у меня возникли проблемы с представлением линейных уравнений в коде:

• Для каждого тетраэдра вычислите 6 линейных уравнений, по одному для каждого ребра.
• Они вычисляют расстояние между точками тетраэдров A до линейных уравнений тетраэдров B. Сохраните эти 24 (6 ребер, 4 вершины) расстояния в списке.
• Сделайте то же самое другим способом.
• Найдите минимум между рассчитанными 48 расстояниями

Существует ли какой-либо алгоритм для определения минимального расстояния между 3D-объектами, учитывая его координаты? Я считаю, что описанная выше процедура решает проблему, но писать все уравнения очень утомительно

Вот мой простой подход. Если у нас есть точки тетраэдра в массивах t1 и t2, мы инициируем минимальное расстояние до расстояния между любыми двумя вершинами в тетраэдре A и тетраэдре B. Мы перебираем все грани в A и B и и определяем функции face_p_1(альфа, бета), которые мы используем, чтобы получить любую точку на этой грани, сканируя параметры альфа и бета в диапазоне [0,1]. И, наконец, мы минимизируем расстояние (используя scipy) между всеми точками в каждой паре граней в A и B.

 from matplotlib import pyplot as plt
from mpl_toolkits.mplot3d.art3d import Poly3DCollection, Line3DCollection
import numpy as np
import itertools
from scipy.optimize import minimize

def mindist (t1,t2):
    dmin=np.linalg.norm(t1[0]-t2[0])
    p0=t1[0]
    p1=t2[0]

    for face_t1 in itertools.combinations([0,1, 2, 3], 3):
        for face_t2 in itertools.combinations([0,1, 2, 3], 3):
            pts_f_t1=t1[list(face_t1)]
            pts_f_t2=t2[list(face_t2)]

            def face_p_1(alpha1,beta1):
                v1=pts_f_t1[1]-pts_f_t1[0]
                v2=pts_f_t1[2]-pts_f_t1[1]
                return(pts_f_t1[0] (v1*alpha1 v2*alpha1*beta1))

            def face_p_2(alpha2,beta2):
                v1=pts_f_t2[1]-pts_f_t2[0]
                v2=pts_f_t2[2]-pts_f_t2[1]
                return(pts_f_t2[0] (v1*alpha2 v2*alpha2*beta2))

            def fpdist(a):
                alpha1,beta1,alpha2,beta2=a
                return(np.linalg.norm(face_p_1(alpha1,beta1)-face_p_2(alpha2,beta2)))

            res=minimize(fpdist,[0.5,0.5,0.5,0.5],bounds=[(0,1),(0,1),(0,1),(0,1)])
            if( res["fun"] < dmin):
                dmin=res["fun"]
                p0=face_p_1(*(res["x"][[0,1]]))
                p1=face_p_2(*(res["x"][[2,3]]))
    return dmin,p0,p1

    
def plot_tetrahedron(v,ax):
    ax.scatter3D(v[:, 0], v[:, 1], v[:, 2])
    verts = [ [v[0],v[1],v[2]], [v[0],v[1],v[3]], [v[0],v[2],v[3]] , [v[1],v[2],v[3]]  ]
    ax.add_collection3d(Poly3DCollection(verts, 
     facecolors='cyan', linewidths=1, edgecolors='r', alpha=.25))
 

Вот несколько тестов с графиками

 fig = plt.figure()
ax = fig.add_subplot(111, projection='3d')

t1=np.array([[ 0.5,  0.5, -0.2],[ 0.6, -0.1, -0.2],[-0.2,  0.6, -0.1],[ 0. ,  0. ,  0.6]])
t2=np.array([[0.6 , 0.65, 0.55],[1.4 , 0.75, 0.55],[0.6 , 1.45, 0.65],[0.8 , 0.85, 1.35]])

dmin,p1,p2=mindist (t1,t2)

plot_tetrahedron(t1,ax)
plot_tetrahedron(t2,ax)

ax.plot(*(array([ p1 , p2 ]).T), c='k')
 

еще один случай

 t1=np.array([[-0.15 , -0.225, -0.075],[-0.05 , -0.825, -0.775],[-0.85 , -0.125, -0.675],[-0.65 , -0.725,  0.025]])
t2=np.array([[0.6 , 0.65, 0.55],[1.4 , 0.75, 0.55],[0.6 , 1.45, 0.65],[0.8 , 0.85, 1.35]])


t1=np.array([[-0.15 , -0.225, -0.075],[-0.05 , -0.825, -0.775],[-0.85 , -0.125, -0.675],[-0.65 , -0.725,  0.025]])
t2=np.array([[0.6 , 0.65, 0.55],[1.4 , 0.75, 0.55],[0.6 , 1.45, 0.65],[0.8 , 0.85, 1.35]])
 

 t1=np.array([[0.1, 0.1, 0.1],[0.9, 0.2, 0.1],[0.1, 0.9, 0.2],[0.3, 0.3, 0.9]])
t2=np.array([[0.6 , 0.65, 0.55],[1.4 , 0.75, 0.55],[0.6 , 1.45, 0.65],[0.8 , 0.85, 1.35]])
 

и корпус с двумя параллельными гранями

 t1=np.array([[-1 , 0, 0],[1 , 0, 0],[0 , sqrt(2), 0],[0 , sqrt(2)/3, sqrt(2)]])
t2=np.array([[-1 , 0, -1],[1 , 0, -1],[0 , sqrt(2), -1],[0 , sqrt(2)/3, -sqrt(2)-1]])