如何判断一个点是在一条线的右边还是左边

我有一套要点。 我想把它们分成两个不同的集合。 要做到这一点,我select了两个点( ab ),并在它们之间画一条想象的线。 现在我想把这一行中的所有点都放在一个集合中,而那些在这一行中正确的点集合在另一个集合中。

我怎么能告诉任何给定的点z是在左边还是在右边呢? 我试图计算azb之间的angular度 – 小于180的angular度在右侧,在左侧大于180 – 但是由于ArcCos的定义,计算的angular度始终小于180°。 是否有一个公式来计算angular度大于180°(或任何其他公式select正确或左侧)?

使用向量行列式(AB,AM)的符号,其中M(X,Y)是查询点:

 position = sign((Bx - Ax) * (Y - Ay) - (By - Ay) * (X - Ax)) 

在线上是0 ,一边是+1 ,另一边是-1

试试这个使用交叉产品的代码:

 public bool isLeft(Point a, Point b, Point c){ return ((bX - aX)*(cY - aY) - (bY - aY)*(cX - aX)) > 0; } 

其中a =第1行; b =第2行; c =指向检查。

如果公式等于0,则这些点是共线的。

如果这条线是水平的,那么如果点在线之上,则返回true。

你看看行列的标志

 | x2-x1 x3-x1 | | y2-y1 y3-y1 | 

一方面积分为正,另一方为负数(线本身为零点)。

vector(y1 - y2, x2 - x1)垂直于直线,总是指向右(如果平面方向与我的不同,则总是指向左方)。

然后,可以计算该向量的点积和(x3 - x1, y3 - y1)以确定该点是否与垂直向量(点积> 0 )在同一条线上。

我用java实现了这个,并运行了一个unit testing(源代码如下)。 上述解决scheme都不起作用。 这段代码通过了unit testing。 如果有人发现一个unit testing没有通过,请让我知道。

代码:注意:如果两个数字非常接近,那么nearlyEqual(double,double)将返回true。

 /* * @return integer code for which side of the line ab c is on. 1 means * left turn, -1 means right turn. Returns * 0 if all three are on a line */ public static int findSide( double ax, double ay, double bx, double by, double cx, double cy) { if (nearlyEqual(bx-ax,0)) { // vertical line if (cx < bx) { return by > ay ? 1 : -1; } if (cx > bx) { return by > ay ? -1 : 1; } return 0; } if (nearlyEqual(by-ay,0)) { // horizontal line if (cy < by) { return bx > ax ? -1 : 1; } if (cy > by) { return bx > ax ? 1 : -1; } return 0; } double slope = (by - ay) / (bx - ax); double yIntercept = ay - ax * slope; double cSolution = (slope*cx) + yIntercept; if (slope != 0) { if (cy > cSolution) { return bx > ax ? 1 : -1; } if (cy < cSolution) { return bx > ax ? -1 : 1; } return 0; } return 0; } 

这是unit testing:

 @Test public void testFindSide() { assertTrue("1", 1 == Utility.findSide(1, 0, 0, 0, -1, -1)); assertTrue("1.1", 1 == Utility.findSide(25, 0, 0, 0, -1, -14)); assertTrue("1.2", 1 == Utility.findSide(25, 20, 0, 20, -1, 6)); assertTrue("1.3", 1 == Utility.findSide(24, 20, -1, 20, -2, 6)); assertTrue("-1", -1 == Utility.findSide(1, 0, 0, 0, 1, 1)); assertTrue("-1.1", -1 == Utility.findSide(12, 0, 0, 0, 2, 1)); assertTrue("-1.2", -1 == Utility.findSide(-25, 0, 0, 0, -1, -14)); assertTrue("-1.3", -1 == Utility.findSide(1, 0.5, 0, 0, 1, 1)); assertTrue("2.1", -1 == Utility.findSide(0,5, 1,10, 10,20)); assertTrue("2.2", 1 == Utility.findSide(0,9.1, 1,10, 10,20)); assertTrue("2.3", -1 == Utility.findSide(0,5, 1,10, 20,10)); assertTrue("2.4", -1 == Utility.findSide(0,9.1, 1,10, 20,10)); assertTrue("vertical 1", 1 == Utility.findSide(1,1, 1,10, 0,0)); assertTrue("vertical 2", -1 == Utility.findSide(1,10, 1,1, 0,0)); assertTrue("vertical 3", -1 == Utility.findSide(1,1, 1,10, 5,0)); assertTrue("vertical 3", 1 == Utility.findSide(1,10, 1,1, 5,0)); assertTrue("horizontal 1", 1 == Utility.findSide(1,-1, 10,-1, 0,0)); assertTrue("horizontal 2", -1 == Utility.findSide(10,-1, 1,-1, 0,0)); assertTrue("horizontal 3", -1 == Utility.findSide(1,-1, 10,-1, 0,-9)); assertTrue("horizontal 4", 1 == Utility.findSide(10,-1, 1,-1, 0,-9)); assertTrue("positive slope 1", 1 == Utility.findSide(0,0, 10,10, 1,2)); assertTrue("positive slope 2", -1 == Utility.findSide(10,10, 0,0, 1,2)); assertTrue("positive slope 3", -1 == Utility.findSide(0,0, 10,10, 1,0)); assertTrue("positive slope 4", 1 == Utility.findSide(10,10, 0,0, 1,0)); assertTrue("negative slope 1", -1 == Utility.findSide(0,0, -10,10, 1,2)); assertTrue("negative slope 2", -1 == Utility.findSide(0,0, -10,10, 1,2)); assertTrue("negative slope 3", 1 == Utility.findSide(0,0, -10,10, -1,-2)); assertTrue("negative slope 4", -1 == Utility.findSide(-10,10, 0,0, -1,-2)); assertTrue("0", 0 == Utility.findSide(1, 0, 0, 0, -1, 0)); assertTrue("1", 0 == Utility.findSide(0,0, 0, 0, 0, 0)); assertTrue("2", 0 == Utility.findSide(0,0, 0,1, 0,2)); assertTrue("3", 0 == Utility.findSide(0,0, 2,0, 1,0)); assertTrue("4", 0 == Utility.findSide(1, -2, 0, 0, -1, 2)); } 

使用ab 行的公式 ,得到与要sorting的点在同一个y坐标上的行上的x坐标。

  • 如果点的x>线的x,则该点在该线的右侧。
  • 如果点的x <line的x,则该点在该行的左侧。
  • 如果点的x ==线的x,点在线上。

首先检查你是否有一条垂直线:

 if (x2-x1) == 0 if x3 < x2 it's on the left if x3 > x2 it's on the right else it's on the line 

然后,计算斜率: m = (y2-y1)/(x2-x1)

然后,使用点斜率forms创build线的方程: y - y1 = m*(x-x1) + y1 。 为了我的解释,将其简化为斜截式(在您的algorithm中不需要): y = mx+b

现在插入(x3, y3) xy 。 下面是一些伪代码,详细说明会发生什么情况:

 if m > 0 if y3 > m*x3 + b it's on the left else if y3 < m*x3 + b it's on the right else it's on the line else if m < 0 if y3 < m*x3 + b it's on the left if y3 > m*x3+b it's on the right else it's on the line else horizontal line; up to you what you do 

基本上,我认为有一个解决scheme更容易和直接,对于任何给定的多边形,让我们说由四个顶点(p1,p2,p3,p4)组成,在多边形中find两个极点对立的顶点,在另一个字,find例如最左上angular的顶点(可以说是p1)和位于最右下angular的对angular顶点(可以说)。 因此,考虑到你的testing点C(x,y),现在你必须在C和p1和C以及p4之间进行双重检查:

如果cx> p1x AND cy> p1y ==>意味着如果cx <p2x AND cy <p2y ==>则C低于p1 next的右边,意味着C在p4的左上方

结论,C在矩形内。

谢谢 :)

假设点(Ax,Ay)(Bx,By)和(Cx,Cy),你需要计算:

(Bx-Ax)*(Cy-Ay) – (By-Ay)*(Cx-Ax)

如果点C位于由点A和点B组成的线上,这将等于零,并且根据边有不同的符号。 哪一边取决于(x,y)坐标的方向,但是可以将A,B和C的testing值插入此公式中,以确定负值是左侧还是右侧。

@ AVB的答案在ruby

 det = Matrix[ [(x2 - x1), (x3 - x1)], [(y2 - y1), (y3 - y1)] ].determinant 

如果det正面它的上面,如果负面它的下面。 如果是0,那就行了。

这是一个使用Clojure编写的交叉产品逻辑的版本。

 (defn is-left? [line point] (let [[[x1 y1] [x2 y2]] (sort line) [x-pt y-pt] point] (> (* (- x2 x1) (- y-pt y1)) (* (- y2 y1) (- x-pt x1))))) 

用法示例:

 (is-left? [[-3 -1] [3 1]] [0 10]) true 

也就是说,点(0,10)在由(-3,-1)和(3,1)确定的线的左侧。

注意:这个实现解决了其他问题(迄今为止)没有的问题! 在给出确定线路的点时, 命令很重要 。 也就是说,从某种意义上说,这是一个“指引线”。 所以用上面的代码,这个调用也会产生true的结果:

 (is-left? [[3 1] [-3 -1]] [0 10]) true 

这是因为这段代码:

 (sort line) 

最后,与其他基于交叉产品的解决scheme一样,此解决scheme返回一个布尔值,并且不给出共线性的第三个结果。 但它会给出一个有意义的结果,例如:

 (is-left? [[1 1] [3 1]] [10 1]) false