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

我有一套观点。我想把它们分成两组。为此，我选择两个点(一和 B)并在它们之间画一条虚线。现在我要把这条线上的所有点，放在一个集合里，把这条线上的所有点放在另一个集合里。

我如何才能告诉任何给定的点 Z是在左边还是在右边的集合？我尝试计算 A-z-b & nash; 之间的角度小于180的角度在右边，大于180的角度在左边，但是由于 ArcCos 的定义，计算出来的角度总是小于180 ° 。是否有计算大于180 ° 角度的公式(或任何其他选择右边或左边的公式) ？

183756 次浏览
小开
最佳答案

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

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

线上是 0，一边是 +1，另一边是 -1。

小开

使用 直线方程 AB，得到与要排序的点处于相同 y 坐标的直线上的 x 坐标。

  • 如果点是 x > 直线的 x，点就在直线的右边。
  • 如果重点是 X < line 的 x，点在该行的左边。
  • 如果点是 x = = 直线的 x，那么点就在直线上。
小开

你看行列式的符号

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

一边的点为正，另一边为负(直线上的点为零)。

小开

矢量 (y1 - y2, x2 - x1)垂直于直线，并且总是指向右边(或者总是指向左边，如果你的平面方向与我的不同)。

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

小开

尝试使用 交叉积的代码:

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。

现在为 x和 y插入 (x3, y3):

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
小开

基本上，我认为对于任何给定的多边形，有一个更简单直接的解决方案，让我们说由四个顶点(p1，p2，p3，p4)组成，找到多边形中两个极端相反的顶点，换句话说，找到例如最左上角的顶点(比如说 p1)和最右下角的顶点(比如说)。因此，考虑到你的测试点 C (x，y) ，现在你必须在 C 和 p1之间，C 和 p4之间进行双重检查:

如果 cx > p1x AND cy > p1y = = > 表示 C 在 p1的右下方 下一个 如果 cx < p2x AND cy < p2y = = > 意味着 C 在 p4的左上方

结论，C 在矩形内。

谢谢:)

小开

我在 java 中实现了这个并运行了一个单元测试(下面的源代码)。以上的解决方案都不管用。这段代码通过了单元测试。如果有人发现单元测试没有通过，请告诉我。

代码: 注意: 如果两个数字非常接近，则 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 的测试值插入到这个公式中，以确定负值是向左还是向右。

小开

@ 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
小开

另一种了解网络设计者提供的解决方案的方法是理解一些几何含义。

设 PQR = [ P，Q，R ]是形成平面的点，平面被线 [ P，R ]分成两边。我们要找出 PQR平面上的两个点，A，B，是否在同一边。

Pqr 平面上的任意点 T都可以用两个向量表示: 翻译 = P-Q 和 你 = R-Q，如下所示:

T’= T-Q = 我 * v + J * u

接下来是几何学的含义:

  1. I + j = 1: pr 行上的 T
  2. 平方上 i + j < 1: T
  3. I + j > 1: T on Snq
  4. I + j = 0: T = Q
  5. I + j < 0: T 在平方和超越 Q 上。

I + j: < 00 < 1 = 1 > 1 这是 PQR 平面 ^ 公关热线

一般来说,

  • I + j 是测量 T 离 Q 或行[ P，R ] 和
  • I + j-1的标志暗示 T 的侧面。

我和 J的其他几何意义(与此解无关)是:

  • I ，J是一个新的坐标系中 T 的标量，其中 V，u是新的轴，问:是新的起点;
  • 对于 P R，J可以分别看作 拉力。我越大，T 离 R越远(从 P的拉力越大)。

我 J的值可以通过求解方程得到:

i*vx + j*ux = T'x
i*vy + j*uy = T'y
i*vz + j*uz = T'z

我们得到两个点，平面上的 A，B:

A = a1 * v + a2 * u B = b1 * v + b2 * u

如果 A，B 在同一边，这将是正确的:

sign(a1+a2-1) = sign(b1+b2-1)

请注意，这也适用于问题: A，B 在平面的同一侧[ P，Q，R ]，其中:

T = 我 * P + J * Q + K * R

I + j + k = 1表示 T 在平面[ P，Q，R ]上，I + j + k-1的符号表示 T 的侧面。从这里我们可以看到:

A = a1 * P + a2 * Q + a3 * R B = b1 * P + b2 * Q + b3 * R

和 A，B 在平面[ P，Q，R ]的同一边，如果

sign(a1+a2+a3-1) = sign(b1+b2+b3-1)

小开

我想提供一个受物理启发的解决方案。

想象一下沿着直线施加一个力，你测量的是力在点上的转矩。如果扭矩是正的(逆时针方向) ，那么这个点就在直线的“左边”，但是如果扭矩是负的，那么这个点就在直线的“右边”。

所以如果力矢量等于定义直线的两个点的跨度

fx = x_2 - x_1
fy = y_2 - y_1

根据以下测试的符号测试点 (px,py)的侧面

var torque = fx*(py-y_1)-fy*(px-x_1)
if  torque>0  then
"point on left side"
else if torque <0 then
"point on right side"
else
"point on line"
end if
小开

直线方程是 y-y1 = m (x-x1)

这里 m 是 y2-y1/x2-x1

现在把 m 放在方程里，把条件放在 y < m (x-x1) + y1上，那么它就是左边的点

例如。

for i in rows:


for j in cols:


if j>m(i-a)+b:


image[i][j]=0
小开

A (x1，y1) B (x2，y2)长度 L = sqrt ((y2-y1) ^ 2 + (x2-x1) ^ 2)的线段

和一个点 M (x，y)

将坐标转换为点 A，新的开始点 B，新的 X 轴的点

我们得到了点 M 的新坐标

也就是 NewX = ((x-x1) (x2-x1) + (y-y1)(y2-y1))/L
从(x-x1) * cos (t) + (y-y1) * sin (t)其中 cos (t) = (x2-x1)/L，sin (t) = (y2-y1)/L

NewY = ((y-y1) (x2-x1)-(x-x1)(y2-y1))/L
From (y-y1) * cos (t)-(x-x1) * sin (t)

因为“ left”是 X 轴的一边，Y 是正的，如果 newY (M 到 AB 的距离)是正的，那么它就在 AB 的左边(新的 X 轴) 如果你只想要符号，你可以省略除以 L 的部分(总是正数)

小开

与现有解决方案有关的问题:

尽管我发现埃里克•班维尔(Eric Bainville)的回答是正确的，但我完全无法理解:

  • 两个向量怎么会有一个行列式? 我想这应用于矩阵？
  • 什么是 sign？
  • 如何将两个向量转换成矩阵？

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

  • 什么是 Bx？
  • 什么是 Y? 难道 Y不应该是矢量，而不是标量吗？
  • 为什么这个解决方案是正确的——其背后的原因是什么？

此外，我的用例涉及到 复杂曲线而不是简单的一行，因此它需要一点重新设计:

重建答案

Point a = new Point3d(ax, ay, az); // point on line
Point b = new Point3d(bx, by, bz); // point on line

如果你想知道你的点是否高于/低于 曲线，那么你需要得到你感兴趣的特定曲线的一阶导数-也就是曲线上点的切线。如果你可以这样做，那么你可以突出你的兴趣点。当然，如果你的曲线是一条直线，那么你只需要一个没有切线的兴趣点。切线就是直线。

Vector3d lineVector = curve.GetFirstDerivative(a); // where "a" is a point on the curve. You may derive point b with a simple displacement calculation:


Point3d b = new Point3d(a.X, a.Y, a.Z).TransformBy(Matrix3d.Displacement(curve.GetFirstDerivative(a)));


Point m = new Point3d(mx, my, mz) // the point you are interested in.

解决方案:

return (b.X - a.X) * (m.Y - a.Y) - (b.Y - a.Y) * (m.X - a.X) < 0; // the answer

我没问题！ 见上图的证明。绿砖满足条件，但外面的砖被过滤掉了！在我的用例中，我只需要接触圆的砖块。

All green items are within the curve

答案背后的理论

我会回来解释的，总有一天，不管怎样..。


提交答案