我需要一个基本函数来求点到线段的最短距离。你可以随意用任何你想要的语言来编写解决方案;我可以把它翻译成什么我正在使用(Javascript)。

编辑:线段由两个端点定义。线段AB由两点A (x1,y1)和B (x2,y2)定义。我要求的是这条线段到点C (x3,y3)的距离。我的几何技能生疏了,所以我看到的例子让我很困惑,我很遗憾地承认。


当前回答

特征c++版本的3D线段和点

// Return minimum distance between line segment: head--->tail and point
double MinimumDistance(Eigen::Vector3d head, Eigen::Vector3d tail,Eigen::Vector3d point)
{
    double l2 = std::pow((head - tail).norm(),2);
    if(l2 ==0.0) return (head - point).norm();// head == tail case

    // Consider the line extending the segment, parameterized as head + t (tail - point).
    // We find projection of point onto the line.
    // It falls where t = [(point-head) . (tail-head)] / |tail-head|^2
    // We clamp t from [0,1] to handle points outside the segment head--->tail.

    double t = max(0,min(1,(point-head).dot(tail-head)/l2));
    Eigen::Vector3d projection = head + t*(tail-head);

    return (point - projection).norm();
}

其他回答

对于感兴趣的人,这里是Joshua的Javascript代码到Objective-C的简单转换:

- (double)distanceToPoint:(CGPoint)p fromLineSegmentBetween:(CGPoint)l1 and:(CGPoint)l2
{
    double A = p.x - l1.x;
    double B = p.y - l1.y;
    double C = l2.x - l1.x;
    double D = l2.y - l1.y;

    double dot = A * C + B * D;
    double len_sq = C * C + D * D;
    double param = dot / len_sq;

    double xx, yy;

    if (param < 0 || (l1.x == l2.x && l1.y == l2.y)) {
        xx = l1.x;
        yy = l1.y;
    }
    else if (param > 1) {
        xx = l2.x;
        yy = l2.y;
    }
    else {
        xx = l1.x + param * C;
        yy = l1.y + param * D;
    }

    double dx = p.x - xx;
    double dy = p.y - yy;

    return sqrtf(dx * dx + dy * dy);
}

我需要这个解决方案与MKMapPoint一起工作,所以我将分享它,以防其他人需要它。只是一些小的改变,这将返回米为单位的距离:

- (double)distanceToPoint:(MKMapPoint)p fromLineSegmentBetween:(MKMapPoint)l1 and:(MKMapPoint)l2
{
    double A = p.x - l1.x;
    double B = p.y - l1.y;
    double C = l2.x - l1.x;
    double D = l2.y - l1.y;

    double dot = A * C + B * D;
    double len_sq = C * C + D * D;
    double param = dot / len_sq;

    double xx, yy;

    if (param < 0 || (l1.x == l2.x && l1.y == l2.y)) {
        xx = l1.x;
        yy = l1.y;
    }
    else if (param > 1) {
        xx = l2.x;
        yy = l2.y;
    }
    else {
        xx = l1.x + param * C;
        yy = l1.y + param * D;
    }

    return MKMetersBetweenMapPoints(p, MKMapPointMake(xx, yy));
}

我制作了一个交互式Desmos图来演示如何实现这一点:

https://www.desmos.com/calculator/kswrm8ddum

红点是A点,绿点是B点,C点是蓝色点。 您可以拖动图形中的点来查看值的变化。 左边的值“s”是线段的参数(即s = 0表示点A, s = 1表示点B)。 值“d”是第三点到经过A和B的直线的距离。

编辑:

有趣的小见解:坐标(s, d)是坐标系中第三点C的坐标,AB是单位x轴,单位y轴垂直于AB。

这是Javascript中最简单的完整代码。

(X, y)是目标点(x1, y)到(x2, y)是线段。

更新:修复了评论中0长度的行问题。

function pDistance(x, y, x1, y1, x2, y2) {

  var A = x - x1;
  var B = y - y1;
  var C = x2 - x1;
  var D = y2 - y1;

  var dot = A * C + B * D;
  var len_sq = C * C + D * D;
  var param = -1;
  if (len_sq != 0) //in case of 0 length line
      param = dot / len_sq;

  var xx, yy;

  if (param < 0) {
    xx = x1;
    yy = y1;
  }
  else if (param > 1) {
    xx = x2;
    yy = y2;
  }
  else {
    xx = x1 + param * C;
    yy = y1 + param * D;
  }

  var dx = x - xx;
  var dy = y - yy;
  return Math.sqrt(dx * dx + dy * dy);
}

更新:Kotlin版本

fun getDistance(x: Double, y: Double, x1: Double, y1: Double, x2: Double, y2: Double): Double {
    val a = x - x1
    val b = y - y1
    val c = x2 - x1
    val d = y2 - y1

    val lenSq = c * c + d * d
    val param = if (lenSq != .0) { //in case of 0 length line
        val dot = a * c + b * d
        dot / lenSq
    } else {
        -1.0
    }

    val (xx, yy) = when {
        param < 0 -> x1 to y1
        param > 1 -> x2 to y2
        else -> x1 + param * c to y1 + param * d
    }

    val dx = x - xx
    val dy = y - yy
    return hypot(dx, dy)
}

这是一个基于向量数学的;这个解决方案也适用于更高的维度,并报告交点(在线段上)。

def dist(x1,y1,x2,y2,px,py):
    a = np.array([[x1,y1]]).T
    b = np.array([[x2,y2]]).T
    x = np.array([[px,py]]).T
    tp = (np.dot(x.T, b) - np.dot(a.T, b)) / np.dot(b.T, b)
    tp = tp[0][0]
    tmp = x - (a + tp*b)
    d = np.sqrt(np.dot(tmp.T,tmp)[0][0])
    return d, a+tp*b

x1,y1=2.,2.
x2,y2=5.,5.
px,py=4.,1.

d, inters = dist(x1,y1, x2,y2, px,py)
print (d)
print (inters)

结果是

2.1213203435596424
[[2.5]
 [2.5]]

这里解释了数学

https://brilliant.org/wiki/distance-between-point-and-line/

只是遇到了这个,我想我应该添加一个Lua实现。它假设点以表{x=xVal, y=yVal}给出,直线或线段由包含两个点的表给出(见下面的例子):

function distance( P1, P2 )
    return math.sqrt((P1.x-P2.x)^2 + (P1.y-P2.y)^2)
end

-- Returns false if the point lies beyond the reaches of the segment
function distPointToSegment( line, P )
    if line[1].x == line[2].x and line[1].y == line[2].y then
        print("Error: Not a line!")
        return false
    end

    local d = distance( line[1], line[2] )

    local t = ((P.x - line[1].x)*(line[2].x - line[1].x) + (P.y - line[1].y)*(line[2].y - line[1].y))/(d^2)

    local projection = {}
    projection.x = line[1].x + t*(line[2].x-line[1].x)
    projection.y = line[1].y + t*(line[2].y-line[1].y)

    if t >= 0 and t <= 1 then   -- within line segment?
        return distance( projection, {x=P.x, y=P.y} )
    else
        return false
    end
end

-- Returns value even if point is further down the line (outside segment)
function distPointToLine( line, P )
    if line[1].x == line[2].x and line[1].y == line[2].y then
        print("Error: Not a line!")
        return false
    end

    local d = distance( line[1], line[2] )

    local t = ((P.x - line[1].x)*(line[2].x - line[1].x) + (P.y - line[1].y)*(line[2].y - line[1].y))/(d^2)

    local projection = {}
    projection.x = line[1].x + t*(line[2].x-line[1].x)
    projection.y = line[1].y + t*(line[2].y-line[1].y)

    return distance( projection, {x=P.x, y=P.y} )
end

使用示例:

local P1 = {x = 0, y = 0}
local P2 = {x = 10, y = 10}
local line = { P1, P2 }
local P3 = {x = 7, y = 15}
print(distPointToLine( line, P3 ))  -- prints 5.6568542494924
print(distPointToSegment( line, P3 )) -- prints false