如何判断一个点是否在一条线的右侧或左侧
我有一组点。我想将它们分成2个不同的集合。为此,我选择两个点(a和b)并在它们之间绘制一条虚线。现在我想把这一行中的所有点都放在一个集合中,并且这些行中的所有点都放在另一个集合中。如何判断一个点是否在一条线的右侧或左侧
我该如何判断任何给定的点z无论是在左边还是在右边?我试图计算a-z-b –之间的角度,右侧的角度小于180°,左侧的角度大于180°–但由于ArcCos的定义,计算的角度始终小于180°。是否有计算角度大于180°的公式(或任何其他公式可选择右侧或左侧)?
使用矢量(AB,AM)
的行列式,其中M(X,Y)
是查询点的符号:
position = sign((Bx - Ax) * (Y - Ay) - (By - Ay) * (X - Ax))
它是0
就行,和+1
在一侧,-1
在另一侧。
+1不错,有一件事要注意:舍入错误可能是一个问题,当点很接近线。 *大多数情况下不会造成问题,但它会不时地咬人。 – 2009-10-13 14:18:53
太棒了!这是一个很好的,没有窦,arccos等:) 舍入误差在这里不是一个问题,因为我使用算法中的分离来计算点集的凸包并在它们周围绘制折线。如果一个点位于船体外面,这不是什么大问题。 – Aaginor 2009-10-13 14:53:37
如果您发现自己处于这个测试的舍入错误导致您遇到问题的情况,您将需要查看Jon Shewchuk的“用于计算几何的快速鲁棒谓词”。 – 2009-10-13 15:13:45
使用equation of the lineab,获取与要排序的点在同一个y坐标线上的x坐标。
- 如果point的x> line的x,则该点位于该行的右侧。
- 如果点的 x <行的x,该点在该行的左侧。
- 如果点的x ==线的x,该点在线上。
这是错误的,因为正如你可以从Aaginor对第一个答案的评论中看到的那样,我们不想知道该点是在DIRECTED线AB的左侧还是右侧,即如果你站在A上,朝着B方向看,是在你的左边还是在右边? – dionyziz 2011-09-04 12:18:43
@dionyziz - 咦?我的回答并没有通过AB给线路分配“方向”。我的答案假设“左”是corrdinate系统的-x方向。接受的答案选择定义一个*向量* AB,并使用交叉乘积定义左边。原始问题没有说明“左”是什么意思。 – mbeckish 2011-09-06 19:29:46
注意:如果您使用这种方法(而不是交叉产品被批准为答案),请注意在线接近水平线时存在缺陷。数学错误增加,并且如果完全水平,则命中无穷。解决方案是使用两个点之间具有较大三角形的轴。 (或者也许更小的三角洲..这是我的头顶。) – ToolmakerSteve 2013-07-10 05:20:33
你看看
| x2-x1 x3-x1 |
| y2-y1 y3-y1 |
行列式这将利好点一侧的(上线本身分零)的标志,而在其他阴性。
矢量(y1 - y2, x2 - x1)
与线垂直,并且始终指向右侧(或者如果平面方向与我的平面方向不同,则总是指向左侧)。
然后,您可以计算该向量的点积和(x3 - x1, y3 - y1)
,以确定该点是否与垂直向量(点积>0
)位于该线的同一侧。
尝试这个代码,其利用一个cross product的:
public bool isLeft(Point a, Point b, Point c){
return ((b.X - a.X)*(c.Y - a.Y) - (b.Y - a.Y)*(c.X - a.X)) > 0;
}
凡一个 =行点1; b =第2行; c =指向检查。
如果公式等于0,则这些点是共线的。
如果该行是水平的,那么如果该点位于该行之上,则返回true。
首先检查,如果你有一条垂直线:
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)
然后,创建使用点斜式线的公式:y - y1 = m*(x-x1) + y1
。为了我的解释,将其简化为斜截式(在您的算法中不需要):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
失败:垂直线的斜率计算无效。无尽的如果/其他的东西。不知道这是OP的左/右意味着什么 - 如果这样看着它旋转90度将削减一半的代码,因为“上方”是正确的或左边的。 – phkahler 2010-08-11 18:57:23
这个答案有几个问题。垂直线导致除以零。更糟糕的是,它失败了,因为它不担心线的斜率是正值还是负值。 – 2010-08-12 03:36:34
@phkahler,修复了垂直线问题。绝对不是一个忘记一个测试用例的失败,但是要感谢这些客气的话。 “如果/其他”是解释数学理论; OP的问题中没有提到编程。 @woodchips,修复了垂直线问题。斜率是变量m;我确实检查它是正面还是负面。 – maksim 2010-08-12 22:46:13
基本上,我认为有一个解决方案,它是非常容易和简单的,对于任何给定的多边形,可以说包括四个顶点(P1,P2,P3 ,p4),在多边形中找到两个极端相对的顶点,换句话说,找到例如最左上角的顶点(可以说是p1)以及位于最右下角(可以说)的相反顶点。因此,考虑到您的测试点C(x,y),现在您必须在C与p1和C以及p4之间进行双重检查:如果cx> p1x AND cy> p1y ==>意味着C较低并且到的P1 下 右如果CX < P2X和cy < P2Y ==>表示C是上和向左P4
结论的,C是在矩形内。
谢谢:)
(1)回答与问题不同的问题吗?听起来像是“边界框”测试,当一个矩形与两个轴对齐时。 (2)更详细地:对4点之间的可能关系进行假设。例如,取一个矩形,并将其旋转45度,以便获得一颗钻石。钻石中没有“左上角的点”。最左边的点不是最顶部或最底部。当然,4分可以形成更奇怪的形状。例如,3个点可能在一个方向上很远,而另一个方向上的4个点可能很远。继续尝试! – ToolmakerSteve 2013-07-10 05:28:11
我在Java中实现这一点,并(下面源)跑一个单元测试。上述解决方案均不起作用。这段代码通过了单元测试。如果有人发现未通过单元测试,请告诉我。
代码:NOTE: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;
}
这里的单元测试:
@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));
}
假设点(AX,AY)(BX,BY)和(CX,CY),你需要计算:
( Bx-Ax)*(Cy-Ay) - (By-Ay)*(Cx-Ax)
如果点C位于由点A和点B形成的线上并且将具有不同签署取决于一方。这是哪一边取决于(x,y)坐标的方向,但可以将A,B和C的测试值插入此公式中,以确定负值是左侧还是右侧。
这基本上是接受的答案的副本? – bummzack 2013-03-19 13:53:31
非常感谢您的回应......这是非常有益的..保持伟大的工作:) - 1投票从我:D – 2013-06-25 08:10:16
@ AVB的答案红宝石
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)
最后,与其他跨产品基础的解决方案,该解决方案返回一个布尔值,并且不会给出共线性的第三个结果。但它会给出一个有意义的结果,例如:
(is-left? [[1 1] [3 1]] [10 1])
false
右或左定义如何? A)从P1到P2或B)在平面上的线的左侧或右侧。 – phkahler 2010-08-11 18:58:59
为了说明问题的第二部分,您可以使用atan2()而不是acos()来计算正确的角度。但是,Eric Bainville指出,使用交叉产品是最好的解决方案。 – dionyziz 2011-09-04 12:20:39
下面的许多解决方案都不起作用,因为如果您交换点a和b(我们用来定义我们的线的点),它们会给出相反的答案。我在Clojure中给出了一个解决方案,在将它们与第三点进行比较之前,首先按照字典顺序排列这两点。 – Purplejacket 2015-02-23 00:28:29