空间中两条线段之间的最短距离

luyuanhong

luyuanhong

    参看《数学中国》论坛上的帖子：
“空间中一个点到空间中一条线段的最短距离”
http://www.mathchina.com/cgi-bin/topic.cgi?forum=5&topic=3547&show=25
“空间中一个点到空间中一个三角形的最短距离”
http://www.mathchina.com/cgi-bin/topic.cgi?forum=5&topic=3564&show=0
“空间中一条线段到空间中一个三角形的最短距离”
http://www.mathchina.com/cgi-bin/topic.cgi?forum=5&topic=3565
“[求助]如何求空间两个多面体的最短距离”
http://www.mathchina.com/cgi-bin/topic.cgi?forum=5&topic=3511&show=50

wudimary111

方程组会不会无解？

luyuanhong

wudimary111 发表于 2016-12-13 14:35
方程组会不会无解？

这是一次项系数不等于 0 的一次方程，不可能无解。

图老师

luyuanhong 发表于 2008-3-16 17:37
参看《数学中国》论坛上的帖子：
“空间中一个点到空间中一条线段的最短距离”
http://www.mathchina.c ...

这几个问题老陆做的不错，ACM竞赛常考的内容。计算几何。

elim

设空间的二直线的参数方程为 P+tU, Q+tV。
其中 U, V 是直线的方向向量，P，Q 分别是二直线上的点。
若二直线不平行，则所求距离是  |(P-Q)·(U×V)|/|U×V|；
否则所求距离是 |(P-Q)×U)|/|U|

图老师

MATLAB代码：求三维空间任意2直线的最小距离
% Computes the minimum distance between two line segments.
% Usage: Input the start and end x,y,z coordinates for two line segments.
% p1, p2 are [x,y,z] coordinates of first line segment and p3,p4 are for
% second line segment.

% Output: scalar minimum distance between the two segments.

%  Example:
%P1 = [0 0 0];     P2 = [1 0 0];
%  P3 = [0 1 0];     P4 = [1 1 0];
%dist = DistBetween2Segment(P1, P2, P3, P4)
%   dist =
%
%    1
%

function [distance varargout] = DistBetween2Segment(p1, p2, p3, p4)

    u = p1 - p2;
    v = p3 - p4;
    w = p2 - p4;
   
    a = dot(u,u);
    b = dot(u,v);
    c = dot(v,v);
    d = dot(u,w);
    e = dot(v,w);
    D = a*c - b*b;
    sD = D;
    tD = D;
   
    SMALL_NUM = 0.00000001;
   
    % compute the line parameters of the two closest points
    if (D < SMALL_NUM)  % the lines are almost parallel
        sN = 0.0;       % force using point P0 on segment S1
        sD = 1.0;       % to prevent possible division by 0.0 later
        tN = e;
        tD = c;
    else                % get the closest points on the infinite lines
        sN = (b*e - c*d);
        tN = (a*e - b*d);
        if (sN < 0.0)   % sc < 0 => the s=0 edge is visible      
            sN = 0.0;
            tN = e;
            tD = c;
        elseif (sN > sD)% sc > 1 => the s=1 edge is visible
            sN = sD;
            tN = e + b;
            tD = c;
        end
    end
   
    if (tN < 0.0)            % tc < 0 => the t=0 edge is visible
        tN = 0.0;
        % recompute sc for this edge
        if (-d < 0.0)
            sN = 0.0;
        elseif (-d > a)
            sN = sD;
        else
            sN = -d;
            sD = a;
        end
    elseif (tN > tD)       % tc > 1 => the t=1 edge is visible
        tN = tD;
        % recompute sc for this edge
        if ((-d + b) < 0.0)
            sN = 0;
        elseif ((-d + b) > a)
            sN = sD;
        else
            sN = (-d + b);
            sD = a;
        end
    end
   
    % finally do the division to get sc and tc
    if(abs(sN) < SMALL_NUM)
        sc = 0.0;
    else
        sc = sN / sD;
    end
   
    if(abs(tN) < SMALL_NUM)
        tc = 0.0;
    else
        tc = tN / tD;
    end
   
    % get the difference of the two closest points
    dP = w + (sc * u) - (tc * v);  % = S1(sc) - S2(tc)

    distance = norm(dP);
    outV = dP;
   
    varargout(1) = {outV};      % vector connecting the closest points
    varargout(2) = {p2+sc*u};   % Closest point on object 1
    varargout(3) = {p4+tc*v};   % Closest point on object 2
   
end

图老师

MATLAB代码：求三维空间任意2直线的最小距离
% Computes the minimum distance between two line segments.
% Usage: Input the start and end x,y,z coordinates for two line segments.
% p1, p2 are [x,y,z] coordinates of first line segment and p3,p4 are for
% second line segment.

% Output: scalar minimum distance between the two segments.

%  Example:
%P1 = [0 0 0];     P2 = [1 0 0];
%  P3 = [0 1 0];     P4 = [1 1 0];
%dist = DistBetween2Segment(P1, P2, P3, P4)
%   dist =
%
%    1
%

function [distance varargout] = DistBetween2Segment(p1, p2, p3, p4)

    u = p1 - p2;
    v = p3 - p4;
    w = p2 - p4;
   
    a = dot(u,u);
    b = dot(u,v);
    c = dot(v,v);
    d = dot(u,w);
    e = dot(v,w);
    D = a*c - b*b;
    sD = D;
    tD = D;
   
    SMALL_NUM = 0.00000001;
   
    % compute the line parameters of the two closest points
    if (D < SMALL_NUM)  % the lines are almost parallel
        sN = 0.0;       % force using point P0 on segment S1
        sD = 1.0;       % to prevent possible division by 0.0 later
        tN = e;
        tD = c;
    else                % get the closest points on the infinite lines
        sN = (b*e - c*d);
        tN = (a*e - b*d);
        if (sN < 0.0)   % sc < 0 => the s=0 edge is visible      
            sN = 0.0;
            tN = e;
            tD = c;
        elseif (sN > sD)% sc > 1 => the s=1 edge is visible
            sN = sD;
            tN = e + b;
            tD = c;
        end
    end
   
    if (tN < 0.0)            % tc < 0 => the t=0 edge is visible
        tN = 0.0;
        % recompute sc for this edge
        if (-d < 0.0)
            sN = 0.0;
        elseif (-d > a)
            sN = sD;
        else
            sN = -d;
            sD = a;
        end
    elseif (tN > tD)       % tc > 1 => the t=1 edge is visible
        tN = tD;
        % recompute sc for this edge
        if ((-d + b) < 0.0)
            sN = 0;
        elseif ((-d + b) > a)
            sN = sD;
        else
            sN = (-d + b);
            sD = a;
        end
    end
   
    % finally do the division to get sc and tc
    if(abs(sN) < SMALL_NUM)
        sc = 0.0;
    else
        sc = sN / sD;
    end
   
    if(abs(tN) < SMALL_NUM)
        tc = 0.0;
    else
        tc = tN / tD;
    end
   
    % get the difference of the two closest points
    dP = w + (sc * u) - (tc * v);  % = S1(sc) - S2(tc)

    distance = norm(dP);
    outV = dP;
   
    varargout(1) = {outV};      % vector connecting the closest points
    varargout(2) = {p2+sc*u};   % Closest point on object 1
    varargout(3) = {p4+tc*v};   % Closest point on object 2
   
end

denglongshan

等于异面直线的距离？

luyuanhong

denglongshan 发表于 2019-11-27 19:40
等于异面直线的距离？

本题要求的，是空间中两条线段之间的最短距离，

并不是空间中两条直线之间的最短距离。

所以本题不能简单地等同于求异面直线之间的距离。