How can you determine a point is between two other points on a line segment?

Let's say you have a two dimensional plane with 2 points (called a and b) on it represented by an x integer and a y integer for each point.

How can you determine if another point c is on the line segment defined by a and b?

I use python most, but examples in any language would be helpful.

154524 次浏览
小开

检查 b-a和 c-a的交叉积是否为 0: 这意味着所有的点是共线的。如果是，检查 c的坐标是否在 a和 b之间。使用 x 或 y 坐标，只要 a和 b在该轴上是分开的(或者它们在两者上是相同的)。

def is_on(a, b, c):
"Return true iff point c intersects the line segment from a to b."
# (or the degenerate case that all 3 points are coincident)
return (collinear(a, b, c)
and (within(a.x, c.x, b.x) if a.x != b.x else
within(a.y, c.y, b.y)))


def collinear(a, b, c):
"Return true iff a, b, and c all lie on the same line."
return (b.x - a.x) * (c.y - a.y) == (c.x - a.x) * (b.y - a.y)


def within(p, q, r):
"Return true iff q is between p and r (inclusive)."
return p <= q <= r or r <= q <= p

这个答案曾经是三个更新的混乱。他们提供的有价值的信息: Brian Hayes 在 美丽的密码中的 第二章涵盖了共线性测试函数的设计空间——有用的背景。Vincent's answer帮助改进了这个。Hayes 建议只测试 x 或 y 坐标中的一个; 最初代码使用 and代替 if a.x != b.x else。

(这是用整数或有理数进行精确算术编码的; 如果传入的是浮点数，就会出现舍入误差问题。我甚至不确定在浮点坐标系中定义2-d 点之间的关系的好方法是什么。)

小开
最佳答案

检查(b-a)和(c-a)的 交叉积是否为0，就像 Darius Bacon 告诉你的那样，告诉你 a、 b 和 c 是否对齐。

但是，如果你想知道 c 是否在 a 和 b 之间，你还必须检查(b-a)和(c-a)的 dot product是否是 确定，是否是 更少比 a 和 b 之间距离的平方。

在未经优化的伪代码中:

def isBetween(a, b, c):
crossproduct = (c.y - a.y) * (b.x - a.x) - (c.x - a.x) * (b.y - a.y)


# compare versus epsilon for floating point values, or != 0 if using integers
if abs(crossproduct) > epsilon:
return False


dotproduct = (c.x - a.x) * (b.x - a.x) + (c.y - a.y)*(b.y - a.y)
if dotproduct < 0:
return False


squaredlengthba = (b.x - a.x)*(b.x - a.x) + (b.y - a.y)*(b.y - a.y)
if dotproduct > squaredlengthba:
return False


return True
小开

(c-a)和(b-a)之间的标量乘积必须等于它们长度的乘积(这意味着向量(c-a)和(b-a)对齐并且方向相同)。此外，(c-a)的长度必须小于或等于(b-a)的长度。伪代码:

# epsilon = small constant


def isBetween(a, b, c):
lengthca2  = (c.x - a.x)*(c.x - a.x) + (c.y - a.y)*(c.y - a.y)
lengthba2  = (b.x - a.x)*(b.x - a.x) + (b.y - a.y)*(b.y - a.y)
if lengthca2 > lengthba2: return False
dotproduct = (c.x - a.x)*(b.x - a.x) + (c.y - a.y)*(b.y - a.y)
if dotproduct < 0.0: return False
if abs(dotproduct*dotproduct - lengthca2*lengthba2) > epsilon: return False
return True
小开

还有一种方法:

  • 假设这两个点是 A (x1，y1)和 B (x2，y2)
  • 通过这些点的直线的方程式是(x-x1)/(y-y1) = (x2-x1)/(y2-y1) . . (只是对斜率进行等值)

Point C (x3,y3) will lie between A & B if:

  • X3，y3满足上述方程。
  • X3在 x1和 x2之间，y3在 y1和 y2之间(简单检查)
小开

使用更加几何的方法，计算以下距离:

ab = sqrt((a.x-b.x)**2 + (a.y-b.y)**2)
ac = sqrt((a.x-c.x)**2 + (a.y-c.y)**2)
bc = sqrt((b.x-c.x)**2 + (b.y-c.y)**2)

测试 ac+bc是否等于 AB:

is_on_segment = abs(ac + bc - ab) < EPSILON

这是因为有三种可能性:

  • 这三个点构成一个三角形 = > Ac + bc > ab
  • 它们是共线的，C在 AB区段之外 = > Ac + bc > ab
  • 它们是共线的，c在 AB区段内 = > C + bc = ab
小开

我是这么做的:

def distance(a,b):
return sqrt((a.x - b.x)**2 + (a.y - b.y)**2)


def is_between(a,c,b):
return distance(a,c) + distance(c,b) == distance(a,b)
小开

我在学校是这么做的，我忘了为什么这不是个好主意。

编辑:

@Darius Bacon: 引用了一本“美丽代码”的书 which contains an explanation why the belowed code is not a good idea.

#!/usr/bin/env python
from __future__ import division


epsilon = 1e-6


class Point:
def __init__(self, x, y):
self.x, self.y = x, y


class LineSegment:
"""
>>> ls = LineSegment(Point(0,0), Point(2,4))
>>> Point(1, 2) in ls
True
>>> Point(.5, 1) in ls
True
>>> Point(.5, 1.1) in ls
False
>>> Point(-1, -2) in ls
False
>>> Point(.1, 0.20000001) in ls
True
>>> Point(.1, 0.2001) in ls
False
>>> ls = LineSegment(Point(1, 1), Point(3, 5))
>>> Point(2, 3) in ls
True
>>> Point(1.5, 2) in ls
True
>>> Point(0, -1) in ls
False
>>> ls = LineSegment(Point(1, 2), Point(1, 10))
>>> Point(1, 6) in ls
True
>>> Point(1, 1) in ls
False
>>> Point(2, 6) in ls
False
>>> ls = LineSegment(Point(-1, 10), Point(5, 10))
>>> Point(3, 10) in ls
True
>>> Point(6, 10) in ls
False
>>> Point(5, 10) in ls
True
>>> Point(3, 11) in ls
False
"""
def __init__(self, a, b):
if a.x > b.x:
a, b = b, a
(self.x0, self.y0, self.x1, self.y1) = (a.x, a.y, b.x, b.y)
self.slope = (self.y1 - self.y0) / (self.x1 - self.x0) if self.x1 != self.x0 else None


def __contains__(self, c):
return (self.x0 <= c.x <= self.x1 and
min(self.y0, self.y1) <= c.y <= max(self.y0, self.y1) and
(not self.slope or -epsilon < (c.y - self.y(c.x)) < epsilon))


def y(self, x):
return self.slope * (x - self.x0) + self.y0


if __name__ == '__main__':
import  doctest
doctest.testmod()
小开

段的长度并不重要，因此使用平方根是不必要的，应该避免，因为我们可能会失去一些精度。

class Point:
def __init__(self, x, y):
self.x = x
self.y = y


class Segment:
def __init__(self, a, b):
self.a = a
self.b = b


def is_between(self, c):
# Check if slope of a to c is the same as a to b ;
# that is, when moving from a.x to c.x, c.y must be proportionally
# increased than it takes to get from a.x to b.x .


# Then, c.x must be between a.x and b.x, and c.y must be between a.y and b.y.
# => c is after a and before b, or the opposite
# that is, the absolute value of cmp(a, b) + cmp(b, c) is either 0 ( 1 + -1 )
#    or 1 ( c == a or c == b)


a, b = self.a, self.b


return ((b.x - a.x) * (c.y - a.y) == (c.x - a.x) * (b.y - a.y) and
abs(cmp(a.x, c.x) + cmp(b.x, c.x)) <= 1 and
abs(cmp(a.y, c.y) + cmp(b.y, c.y)) <= 1)

一些随机使用的例子:

a = Point(0,0)
b = Point(50,100)
c = Point(25,50)
d = Point(0,8)


print Segment(a,b).is_between(c)
print Segment(a,b).is_between(d)
小开

好的，很多人提到线性代数(矢量的交叉乘积) ，这在实空间(即连续或浮点)中有效，但问题特别指出，这两个点被表示为 整数，因此交叉乘积不是正确的解，尽管它可以给出近似解。

正确的解决方案是在两个点之间使用 Bresenham's Line Algorithm，并查看第三个点是否是直线上的一个点。如果这些点距离足够远，以至于计算算法是不可执行的(如果是这样的话，它必须非常大) ，我相信你可以四处挖掘并找到优化。

小开

如何只是确保斜率是相同的，点之间的其他？

given points (x1, y1) and (x2, y2) ( with x2 > x1) and candidate point (a,b)

如果(b-y1)/(a-x1) = (y2-y2)/(x2-x1)和 x1 < a < x2

Then (a,b) must be on line between (x1,y1) and (x2, y2)

小开

线段上的任何点(一，b)(其中 一和 b是载体)可以表示为两个载体 一和 b的 线性组合:

换句话说，如果 c位于线段(一，b)上:

c = ma + (1 - m)b, where 0 <= m <= 1

求解 我，我们得到:

m = (c.x - b.x)/(a.x - b.x) = (c.y - b.y)/(a.y - b.y)

So, our test becomes (in Python):

def is_on(a, b, c):
"""Is c on the line segment ab?"""


def _is_zero( val ):
return -epsilon < val < epsilon


x1 = a.x - b.x
x2 = c.x - b.x
y1 = a.y - b.y
y2 = c.y - b.y


if _is_zero(x1) and _is_zero(y1):
# a and b are the same point:
# so check that c is the same as a and b
return _is_zero(x2) and _is_zero(y2)


if _is_zero(x1):
# a and b are on same vertical line
m2 = y2 * 1.0 / y1
return _is_zero(x2) and 0 <= m2 <= 1
elif _is_zero(y1):
# a and b are on same horizontal line
m1 = x2 * 1.0 / x1
return _is_zero(y2) and 0 <= m1 <= 1
else:
m1 = x2 * 1.0 / x1
if m1 < 0 or m1 > 1:
return False
m2 = y2 * 1.0 / y1
return _is_zero(m2 - m1)
小开

c# 来自 http://www.faqs.org/faqs/graphics/algorithms-faq/ - > 实验对象1.02: 我如何找到从一个点到一条线的距离？

Boolean Contains(PointF from, PointF to, PointF pt, double epsilon)
{


double segmentLengthSqr = (to.X - from.X) * (to.X - from.X) + (to.Y - from.Y) * (to.Y - from.Y);
double r = ((pt.X - from.X) * (to.X - from.X) + (pt.Y - from.Y) * (to.Y - from.Y)) / segmentLengthSqr;
if(r<0 || r>1) return false;
double sl = ((from.Y - pt.Y) * (to.X - from.X) - (from.X - pt.X) * (to.Y - from.Y)) / System.Math.Sqrt(segmentLengthSqr);
return -epsilon <= sl && sl <= epsilon;
}
小开

我需要在 html5画布中使用 javascript 来检测用户光标是否超过或接近某一行。所以我把达利斯 · 培根给出的答案改成了咖啡台词:

is_on = (a,b,c) ->
# "Return true if point c intersects the line segment from a to b."
# (or the degenerate case that all 3 points are coincident)
return (collinear(a,b,c) and withincheck(a,b,c))


withincheck = (a,b,c) ->
if a[0] != b[0]
within(a[0],c[0],b[0])
else
within(a[1],c[1],b[1])


collinear = (a,b,c) ->
# "Return true if a, b, and c all lie on the same line."
((b[0]-a[0])*(c[1]-a[1]) < (c[0]-a[0])*(b[1]-a[1]) + 1000) and ((b[0]-a[0])*(c[1]-a[1]) > (c[0]-a[0])*(b[1]-a[1]) - 1000)


within = (p,q,r) ->
# "Return true if q is between p and r (inclusive)."
p <= q <= r or r <= q <= p
小开

Here's a different way to go about it, with code given in C++. Given two points, l1 and l2 it's trivial to express the line segment between them as

l1 + A(l2 - l1)

其中0 < = A < = 1。这就是线的向量表示，如果你对这个问题感兴趣的话。我们可以把 x 和 y 分量分开，给出:

x = l1.x + A(l2.x - l1.x)
y = l1.y + A(l2.y - l1.y)

取一个点(x，y) ，将它的 x 和 y 分量替换成这两个表达式来求 A。如果两个表达式中 A 的解相等且0 < = A < = 1，则点在直线上。因为求解 A 需要除法，所以有些特殊情况需要处理，以便在线段是水平或垂直的时候停止除零。最后的解决办法如下:

// Vec2 is a simple x/y struct - it could very well be named Point for this use


bool isBetween(double a, double b, double c) {
// return if c is between a and b
double larger = (a >= b) ? a : b;
double smaller = (a != larger) ? a : b;


return c <= larger && c >= smaller;
}


bool pointOnLine(Vec2<double> p, Vec2<double> l1, Vec2<double> l2) {
if(l2.x - l1.x == 0) return isBetween(l1.y, l2.y, p.y); // vertical line
if(l2.y - l1.y == 0) return isBetween(l1.x, l2.x, p.x); // horizontal line


double Ax = (p.x - l1.x) / (l2.x - l1.x);
double Ay = (p.y - l1.y) / (l2.y - l1.y);


// We want Ax == Ay, so check if the difference is very small (floating
// point comparison is fun!)


return fabs(Ax - Ay) < 0.000001 && Ax >= 0.0 && Ax <= 1.0;
}
小开

下面是一些我用过的 Java 代码:

boolean liesOnSegment(Coordinate a, Coordinate b, Coordinate c) {
        

double dotProduct = (c.x - a.x) * (c.x - b.x) + (c.y - a.y) * (c.y - b.y);
return (dotProduct < 0);
}
小开

C # 中使用 Vector2D 类的一个答案

public static bool IsOnSegment(this Segment2D @this, Point2D c, double tolerance)
{
var distanceSquared = tolerance*tolerance;
// Start of segment to test point vector
var v = new Vector2D( @this.P0, c ).To3D();
// Segment vector
var s = new Vector2D( @this.P0, @this.P1 ).To3D();
// Dot product of s
var ss = s*s;
// k is the scalar we multiply s by to get the projection of c onto s
// where we assume s is an infinte line
var k = v*s/ss;
// Convert our tolerance to the units of the scalar quanity k
var kd = tolerance / Math.Sqrt( ss );
// Check that the projection is within the bounds
if (k <= -kd || k >= (1+kd))
{
return false;
}
// Find the projection point
var p = k*s;
// Find the vector between test point and it's projection
var vp = (v - p);
// Check the distance is within tolerance.
return vp * vp < distanceSquared;
}

请注意

s * s

是 c # 中段向量通过运算符重载的点积

The key is taking advantage of the projection of the point onto the infinite line and observing that the scalar quantity of the projection tells us trivially if the projection is on the segment or not. We can adjust the bounds of the scalar quantity to use a fuzzy tolerance.

如果投影在界内，我们只需测试从点到投影的距离是否在界内。

相对于交叉产品方法的好处是，公差具有有意义的价值。

小开

你可以使用楔形和点积:

def dot(v,w): return v.x*w.x + v.y*w.y
def wedge(v,w): return v.x*w.y - v.y*w.x


def is_between(a,b,c):
v = a - b
w = b - c
return wedge(v,w) == 0 and dot(v,w) > 0
小开

这是我在 Unity 中使用 C # 的解决方案。

private bool _isPointOnLine( Vector2 ptLineStart, Vector2 ptLineEnd, Vector2 ptPoint )
{
bool bRes = false;
if((Mathf.Approximately(ptPoint.x, ptLineStart.x) || Mathf.Approximately(ptPoint.x, ptLineEnd.x)))
{
if(ptPoint.y > ptLineStart.y && ptPoint.y < ptLineEnd.y)
{
bRes = true;
}
}
else if((Mathf.Approximately(ptPoint.y, ptLineStart.y) || Mathf.Approximately(ptPoint.y, ptLineEnd.y)))
{
if(ptPoint.x > ptLineStart.x && ptPoint.x < ptLineEnd.x)
{
bRes = true;
}
}
return bRes;
}
小开

C# version of Jules' answer:

public static double CalcDistanceBetween2Points(double x1, double y1, double x2, double y2)
{
return Math.Sqrt(Math.Pow (x1-x2, 2) + Math.Pow (y1-y2, 2));
}


public static bool PointLinesOnLine (double x, double y, double x1, double y1, double x2, double y2, double allowedDistanceDifference)
{
double dist1 = CalcDistanceBetween2Points(x, y, x1, y1);
double dist2 = CalcDistanceBetween2Points(x, y, x2, y2);
double dist3 = CalcDistanceBetween2Points(x1, y1, x2, y2);
return Math.Abs(dist3 - (dist1 + dist2)) <= allowedDistanceDifference;
}
小开

你可以用点坐标来解线段的线方程，你会知道那个点是否在线上，然后检查线段的边界，知道它是在线段的内部还是外部。你可以应用一些阈值，因为它在空间的某个地方，很可能是由一个浮点值定义的，所以你不能达到精确的阈值。 Php 中的例子

function getLineDefinition($p1=array(0,0), $p2=array(0,0)){
    

$k = ($p1[1]-$p2[1])/($p1[0]-$p2[0]);
$q = $p1[1]-$k*$p1[0];
    

return array($k, $q);
    

}


function isPointOnLineSegment($line=array(array(0,0),array(0,0)), $pt=array(0,0)){
    

// GET THE LINE DEFINITION y = k.x + q AS array(k, q)
$def = getLineDefinition($line[0], $line[1]);
    

// use the line definition to find y for the x of your point
$y = $def[0]*$pt[0]+$def[1];


$yMin = min($line[0][1], $line[1][1]);
$yMax = max($line[0][1], $line[1][1]);


// exclude y values that are outside this segments bounds
if($y>$yMax || $y<$yMin) return false;
    

// calculate the difference of your points y value from the reference value calculated from lines definition
// in ideal cases this would equal 0 but we are dealing with floating point values so we need some threshold value not to lose results
// this is up to you to fine tune
$diff = abs($pt[1]-$y);
    

$thr = 0.000001;
    

return $diff<=$thr;
    

}
小开

您也可以使用非常方便的 scikit-spatial 图书馆。

例如，您可以创建一个由 a和 b两个点定义的 Line对象:

>>> point_a = [0, 0]
>>> point_b = [1, 0]


>>> line = Line.from_points(point_a, point_b)

then you can use the side_point method of the Line class to check whether point c lies on line or not.

>>> line.side_point([0.5, 0])
0

如果输出为 0，那么点 c位于 line上。


提交答案