我有一组点。我想把它们分成两个不同的集合。为此，我选择两个点（a 和 b），并在它们之间画出一个虚拟的直线。现在我想把线左侧的所有点放入一个集合中，将右侧的点放入另一个集合中。
如何判断任何给定的点 z 是属于左边集合还是右边集合？我尝试计算 a-z-b 之间的角度 - 小于180度的角度位于右手边，大于180度的角度位于左手边 - 但由于ArcCos的定义，计算出的角度总是小于180度。是否有公式可以计算大于180度的角度（或任何其他选择左或右侧的公式）？
如何判断一个点在一条直线的左侧还是右侧
179
- Aaginor
3
右侧或左侧如何定义？A）从P1看向P2或B）在平面上线的左侧或右侧。 - phkahler
2澄清一下，针对你问题的第二部分，你可以使用atan2()来计算正确的角度，而不是使用acos()。然而，正如Eric Bainville所指出的那样，使用叉积是解决这个问题的最佳方案。 - dionyziz
下面许多解决方案都不起作用，因为如果交换点a和b（我们用来定义直线的点），它们会给出相反的答案。我提供了一个Clojure的解决方案，在比较第三个点之前将这两个点按字典顺序排序。 - Purplejacket
16个回答
1
现有解决方案存在的问题：
虽然我发现Eric Bainville的答案是正确的，但我觉得它完全不足以理解：
- 两个向量如何有行列式？我以为只有矩阵有行列式吧？
sign是什么意思？- 如何将两个向量转换成矩阵？
position = sign((Bx - Ax) * (Y - Ay) - (By - Ay) * (X - Ax))
Bx是什么？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
答案背后的理论
我会回来解释这个。总有一天。某种程度上...
- BenKoshy
2
1如果你能写出这个答案，你就能写出一个好的问题。我可以想到100种处理变化环境的方法。杂货店和航空公司会改变价格，但结账时不会收取与标签/搜索结果上不同的价格。也许你可以在计算中包含所有变化的参数。也许你可以将更改限制在时间表内。也许你可以使用双重锁定。 - Panagiotis Kanavos
@PanagiotisKanavos，感谢您的评论。我认为这是一个非常简单的关于循环等问题的问题，不需要锁/环境，我很好奇其他人会如何处理它，并且随意提出了我脑海中想到的第一个方法名称 - 一些有趣/无害的玩笑 - 这是个大错误。我将查看一些一年级的控制/流程教程，并尝试简化它。 - BenKoshy
1
@AVB在Ruby中的答案
如果
det = Matrix[
[(x2 - x1), (x3 - x1)],
[(y2 - y1), (y3 - y1)]
].determinant
如果
det是正数，则在直线上方，如果是负数，则在直线下方。如果为0，则在直线上。- boulder_ruby
1
基本上，我认为有一个更简单和直接的解决方案。对于任何给定的多边形，假设由四个顶点(p1、p2、p3、p4)组成，在多边形中找到两个极端相反的顶点，换句话说，找到例如最左上角的顶点（假设为p1）和位于最右下角的相对顶点（假设为p4）。因此，给定您的测试点C(x,y)，现在您必须在C和p1以及C和p4之间进行双重检查：
如果cx > p1x AND cy > p1y ==> 意味着C在p1的下方且向右 下一步 如果cx < p2x AND cy < p2y ==> 意味着C在p4的上方且向左
结论：C在矩形内。
谢谢 :)
- Mohamed
1
1(1) 回答了与所问问题不同的问题？听起来像是“边界框”测试，当一个矩形与两个轴对齐时。(2) 更详细地说：假设了4个点之间可能存在的关系。例如，取一个矩形并将其旋转45度，这样你就得到了一个菱形。在那个菱形中，不存在所谓的“左上角点”。最左边的点既不是最上面的也不是最下面的。当然，4个点可以组成更奇怪的形状。例如，3个点可以朝一个方向远离，而第4个点则朝另一个方向。继续努力！ - ToolmakerSteve
0
给定点A(x1,y1)和点B(x2,y2)，它们之间的线段长度为L=sqrt((y2-y1)^2 + (x2-x1)^2)，还有一个点M(x,y)。进行坐标变换，使得点A成为新起点，点B成为新X轴上的一点，我们可以得到点M的新坐标。
新的X坐标为newX=((x-x1)(x2-x1)+(y-y1)(y2-y1))/L，其中cos(t)=(x2-x1)/L，sin(t)=(y2-y1)/L，而原来的坐标为(x-x1)*cos(t)+(y-y1)*sin(t)。
新的Y坐标为newY=((y-y1)(x2-x1)-(x-x1)(y2-y1))/L，而原来的坐标为(y-y1)*cos(t)-(x-x1)*sin(t)。
因为“左侧”是X轴正方向上Y坐标为正的一侧，如果新的Y坐标（即M到AB的距离）为正，则M在AB的左侧（新的X轴上）。如果只需要符号，可以省略除以L（始终为正数）。
- P.Tsiros
0
了解网友提供的解决方案的另一种方法是了解一些几何学的含义。
设pqr=[P,Q,R]是形成一个平面的点，该平面由线[P,R]分为两个部分。我们要找出在pqr平面上的两个点A、B是否在同一侧。
在pqr平面上，任何点T都可以用2个向量表示：v=P-Q和u=R-Q，如下：
T' = T-Q = i * v + j * u
现在来看几何学的含义：
- i+j=1：T在pr线上
- i+j<1：T在Sq上
- i+j>1：T在Snq上
- i+j=0：T=Q
- i+j<0：T在Sq上且超过Q
i+j: <0 0 <1 =1 >1
---------Q------[PR]--------- <== 这是PQR平面
^
pr线
一般来说，
- i+j是T离Q或线段[P,R]的距离的度量，而
- i+j-1的符号表示了T的位置关系。
i和j的其他几何意义（与此解决方案无关）是：
- i、j是T在一个新坐标系中的标量，其中v,u是新轴，Q是新原点；
- i、j可以被看作是P,R的拉力。 i越大，T离R越远（从P施加更大的拉力）。
可以通过解方程组来获得的值：
i*vx + j*ux = T'x
i*vy + j*uy = T'y
i*vz + j*uz = T'z
所以我们在平面上给出了2个点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 = i * P + j * Q + k * R
i+j+k=1意味着T在平面[P、Q、R]上，而i+j+k-1的符号则表示其在平面上的位置。因此我们有：
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)
sign(a1+a2+a3-1) = sign(b1+b2+b3-1)
- runsun
0
直线方程为 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
- DevilWhite
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接