如何确定线段上两个点之间的点？

Question

假设你有一个带有2个点(称为a和b)的二维平面,它由x整数和每个点的y整数表示.

如何确定a和b定义的线段上是否有另一个点c？

我最常使用python,但任何语言的示例都会有所帮助.

Answer 1

检查(ba)和(ca)的叉积是否为0,如Darius Bacon告诉你的那样,a,b和c点是否对齐.

但是,如果你想知道c是否在a和b之间,你还必须检查(ba)和(ca)的点积是正的并且小于 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

Answer 2

这是我如何做到的:

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)

Answer 3

检查b-a和的叉积c-a是否为0:表示所有点都是共线的.如果是,检查c坐标是否在a's和b's之间.请使用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 在Beautiful Code中的章节涵盖了共线性测试功能的设计空间 - 有用的背景.文森特的回答有助于改善这一点.Hayes建议只测试x或y坐标中的一个; 原来代码代替了.andif a.x != b.x else

Answer 4

这是另一种方法:

• 让我们假设两个点是A(x1,y1)和B(x2,y2)
• 通过这些点的直线方程是(x-x1)/(y-y1)=(x2-x1)/(y2-y1)..(只是等于斜率)

如果出现以下情况,C点(x3,y3)将位于A和B之间:

• x3,y3满足上述等式.
• x3位于x1和x2之间,y3位于y1和y2之间(平凡检查)

Answer 5

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

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)

Answer 6

您可以使用楔积和点积：

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

Answer 7

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

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

这是因为存在三种可能性：

• 3个点形成三角形 => ac+bc > ab
• 它们共线且c在ab线段之外 => ac+bc > ab
• 它们共线且c在ab线段内 => ac+bc = ab

Answer 8

这是一种不同的方法，用 C++ 给出代码。给定两个点 l1 和 l2，将它们之间的线段表示为很简单

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;
}