我有一组点。我想将它们分成 2 个不同的集合。为此，我选择两个点（a和b）并在它们之间画一条假想线。现在我想把这条线左边的所有点放在一组里，把这条线右边的点放在另一组里。
我如何判断任何给定点z是在左侧还是右侧？我试图计算azb之间的角度——小于 180 的角度在右侧，大于 180 的角度在左侧——但由于 ArcCos 的定义，计算出的角度总是小于 180°。是否有计算大于 180° 的角度的公式（或任何其他选择右侧或左侧的公式）？
问问题
166402 次
15 回答
264
试试这个使用叉积的代码：
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;
}
其中a = 线点 1；b = 线点 2；c = 检查点。
如果公式等于 0，则这些点是共线的。
如果线是水平的，那么如果点在线上方，则返回 true。
于 2010-08-11T18:19:46.063 回答
231
使用向量行列式的符号，查询点(AB,AM)在哪里：M(X,Y)
position = sign((Bx - Ax) * (Y - Ay) - (By - Ay) * (X - Ax))
它0在线上，+1在一侧，-1在另一侧。
于 2009-10-13T14:12:42.813 回答
46
你看看行列式的符号
| x2-x1 x3-x1 |
| y2-y1 y3-y1 |
一侧的点为正，另一侧为负（线本身的点为零）。
于 2010-08-11T18:14:35.913 回答
10
矢量(y1 - y2, x2 - x1)垂直于线，并且始终指向右侧（或始终指向左侧，如果您的平面方向与我的不同）。
然后，您可以计算该向量的点积，并(x3 - x1, y3 - y1)确定该点是否与垂直向量（点积 > 0）位于直线的同一侧。
于 2010-08-11T18:14:59.500 回答
6
使用线ab的方程 ，得到与要排序的点在同一 y 坐标的线上的 x 坐标。
- 如果点的 x > 线的 x，则该点位于线的右侧。
- 如果点的 x < 线的 x，则该点位于线的左侧。
- 如果点的 x == 线的 x，则该点在线上。
于 2009-10-13T14:22:29.930 回答
5
首先检查是否有垂直线：
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)和。这是一些伪代码，详细说明了应该发生的情况：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
于 2010-08-11T18:20:41.717 回答
5
我在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));
}
于 2011-12-15T18:34:10.870 回答
4
我想提供一个受物理学启发的解决方案。
想象一下沿线施加的力，并且您正在测量力关于该点的扭矩。如果扭矩为正（逆时针），则该点位于线的“左侧”，但如果扭矩为负，则该点位于线的“右侧”。
因此，如果力矢量等于定义线的两点的跨度
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
于 2018-12-18T15:00:30.007 回答
3
假设点是 (Ax,Ay) (Bx,By) 和 (Cx,Cy)，您需要计算：
(Bx - Ax) * (Cy - Ay) - (By - Ay) * (Cx - Ax)
如果点 C 在由点 A 和 B 形成的线上，这将等于零，并且根据边的不同，符号也会不同。这取决于您的 (x,y) 坐标的方向，但您可以将 A、B 和 C 的测试值插入此公式以确定负值是在左侧还是在右侧。
于 2013-03-19T12:35:33.447 回答
2
这是一个版本，同样使用叉积逻辑，用 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
于 2015-02-21T00:42:20.570 回答
1
基本上，我认为对于任何给定的多边形来说，有一个更容易和直接的解决方案，比如说由四个顶点（p1，p2，p3，p4）组成，在多边形中找到两个极端相反的顶点，在另一个单词，例如找到最左上角的顶点（比如说 p1）和位于最右下角的相反顶点（比如说 ）。因此，给定您的测试点 C(x,y)，现在您必须在 C 和 p1 以及 C 和 p4 之间进行双重检查：
if cx > p1x AND cy > p1y ==> 意味着 C 在 p1 的下方和右侧 if cx < p2x AND cy < p2y ==> 意味着 C 在 p4 的上方和左侧
结论，C在矩形内。
谢谢 ：）
于 2011-05-17T17:31:09.617 回答
1
@AVB 用红宝石回答
det = Matrix[
[(x2 - x1), (x3 - x1)],
[(y2 - y1), (y3 - y1)]
].determinant
如果det为正则其上方，如果为负则其下方。如果为0，则在线。
于 2013-07-21T18:57:14.793 回答
0
了解网络专家提供的解决方案的另一种方法是了解一点几何含义。
令pqr =[P,Q,R] 是形成平面的点，该平面被线[P,R]分为 2 条边。我们要找出pqr平面上的两个点 A,B 是否在同一侧。
pqr 平面上的任何点T都可以用 2 个向量表示：v = PQ 和u = RQ，如：
T' = TQ = i * v + j * u
现在几何含义：
- i+j =1: pr线上的T
- i+j <1: T 上 Sq
- i+j >1: Snq 上的 T
- i+j =0：T = Q
- i+j <0：T 在 Sq 和 Q 之外。
i+j: <0 0 <1 =1 >1
---------Q------[PR]--------- <== this is PQR plane
^
pr line
一般来说，
- 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,j的值可以通过求解方程得到：
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)
于 2018-12-17T21:26:23.667 回答
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
于 2020-09-14T06:39:55.473 回答
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
from (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
从 (y-y1)*cos(t)-(x-x1)*sin(t)
因为“左”是 X 轴的一侧，其中 Y 为正，如果 newY（即 M 到 AB 的距离）为正，那么它在 AB 的左侧（新的 X 轴）您可以省略除以 L （总是正的），如果你只想要符号
于 2020-12-27T19:12:58.280 回答