如何判断一个点是在一条线的右边还是左边
我有一套要点。 我想把它们分成两个不同的集合。 要做到这一点，我select了两个点（ a和b ），并在它们之间画一条想象的线。 现在我想把这一行中的所有点都放在一个集合中，而那些在这一行中正确的点集合在另一个集合中。
我怎么能告诉任何给定的点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) x和y 。 下面是一些伪代码，详细说明会发生什么情况：
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
