假设你有一个带有2个点(称为a和b)的二维平面,它由x整数和每个点的y整数表示.
如何确定a和b定义的线段上是否有另一个点c？
我最常使用python,但任何语言的示例都会有所帮助.
检查(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
这是我如何做到的:
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)
检查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
这是另一种方法:
让我们假设两个点是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之间(平凡检查)
段的长度并不重要,因此不需要使用平方根,应该避免使用,因为我们可能会失去一些精度.
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)
京公网安备 11010802040832号 | 京ICP备19059560号-6 