C# 如何判断一个点是在一条直线的右边还是左边
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1560492/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to tell whether a point is to the right or left side of a line
提问by Aaginor
I have a set of points. I want to separate them into 2 distinct sets. To do this, I choose two points (aand b) and draw an imaginary line between them. Now I want to have all points that are left from this line in one set and those that are right from this line in the other set.
我有一组积分。我想将它们分成 2 个不同的集合。为此，我选择两个点（a和b）并在它们之间画一条假想线。现在我想把这条线左边的所有点放在一组中，把这条线右边的点放在另一组里。
How can I tell for any given point zwhether it is in the left or in the right set? I tried to calculate the angle between a-z-b– angles smaller than 180 are on the right hand side, greater than 180 on the left hand side – but because of the definition of ArcCos, the calculated angles are always smaller than 180°. Is there a formula to calculate angles greater than 180° (or any other formula to chose right or left side)?
我如何知道任何给定的点z是在左边还是右边？我试图计算azb之间的角度- 小于 180 的角度在右侧，大于 180 的角度在左侧 - 但由于 ArcCos 的定义，计算出的角度总是小于 180°。是否有计算大于 180° 的角度的公式（或任何其他选择右侧或左侧的公式）？
采纳答案by Eric Bainville
Use the sign of the determinant of vectors (AB,AM), where M(X,Y)is the query point:
使用向量的行列式的符号，查询点(AB,AM)在哪里M(X,Y)：
position = sign((Bx - Ax) * (Y - Ay) - (By - Ay) * (X - Ax))
It is 0on the line, and +1on one side, -1on the other side.
它0在线，+1在一侧，-1在另一侧。
回答by mbeckish
Using the equation of the lineab, get the x-coordinate on the line at the same y-coordinate as the point to be sorted.
使用直线ab的方程，在与要排序的点相同的 y 坐标处获得直线上的 x 坐标。
- If point's x > line's x, the point is to the right of the line.
- If point's x < line's x, the point is to the left of the line.
- If point's x == line's x, the point is on the line.
- 如果点的 x > 线的 x，则该点位于线的右侧。
- 如果点的 x < 线的 x，点在线的左边。
- 如果点的 x == 线的 x，则点在线上。
回答by AVB
You look at the sign of the determinant of
你看行列式的符号
| x2-x1 x3-x1 |
| y2-y1 y3-y1 |
It will be positive for points on one side, and negative on the other (and zero for points on the line itself).
一侧的点为正，另一侧为负（直线本身的点为零）。
回答by Victor Nicollet
The vector (y1 - y2, x2 - x1)is perpendicular to the line, and always pointing right (or always pointing left, if you plane orientation is different from mine).
矢量(y1 - y2, x2 - x1)垂直于线，并且始终指向右侧（或始终指向左侧，如果您的平面方向与我的不同）。
You can then compute the dot product of that vector and (x3 - x1, y3 - y1)to determine if the point lies on the same side of the line as the perpendicular vector (dot product > 0) or not.
然后，您可以计算该向量的点积，并(x3 - x1, y3 - y1)确定该点是否与垂直向量（点积 > 0）位于直线的同一侧。
回答by jethro
Try this code which makes use of a 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;
}
Where a= line point 1; b= line point 2; c= point to check against.
其中a= 线点 1；b= 线点 2；c= 要检查的点。
If the formula is equal to 0, the points are colinear.
如果公式等于 0，则这些点共线。
If the line is horizontal, then this returns true if the point is above the line.
如果线条是水平的，那么如果点在线条上方，则返回 true。
回答by maksim
First check if you have a vertical line:
首先检查是否有垂直线：
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
Then, calculate the slope: m = (y2-y1)/(x2-x1)
然后，计算斜率： m = (y2-y1)/(x2-x1)
Then, create an equation of the line using point slope form: y - y1 = m*(x-x1) + y1. For the sake of my explanation, simplify it to slope-intercept form (not necessary in your algorithm): y = mx+b.
然后，使用点斜率形式创建直线方程：y - y1 = m*(x-x1) + y1。对于我的解释起见，简化为斜截式（在你的算法不是必需的）： y = mx+b。
Now plug in (x3, y3)for xand y. Here is some pseudocode detailing what should happen:
现在插上(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
回答by Mohamed
basically, I think that there is a solution which is much easier and straight forward, for any given polygon, lets say consist of four vertices(p1,p2,p3,p4), find the two extreme opposite vertices in the polygon, in another words, find the for example the most top left vertex (lets say p1) and the opposite vertex which is located at most bottom right (lets say ). Hence, given your testing point C(x,y), now you have to make double check between C and p1 and C and p4:
基本上，我认为有一个更简单直接的解决方案，对于任何给定的多边形，假设由四个顶点（p1，p2，p3，p4）组成，在多边形中找到两个极端相反的顶点，在另一个话，找到例如最左上角的顶点（比方说 p1）和位于最右下角的相反顶点（比方说）。因此，鉴于您的测试点 C(x,y)，现在您必须在 C 和 p1 以及 C 和 p4 之间进行双重检查：
if cx > p1x AND cy > p1y ==> means that C is lower and to right of p1 next if cx < p2x AND cy < p2y ==> means that C is upper and to left of p4
if cx > p1x AND cy > p1y ==> 表示 C 位于 p1 的下方和右侧 if cx < p2x AND cy < p2y ==> 表示 C 位于 p4 的上方和左侧
conclusion, C is inside the rectangle.
结论，C在矩形内。
Thanks :)
谢谢 ：）
回答by Al Globus
I implemented this in java and ran a unit test (source below). None of the above solutions work. This code passes the unit test. If anyone finds a unit test that does not pass, please let me know.
我在 java 中实现了这个并运行了一个单元测试（来源如下）。上述解决方案均无效。这段代码通过了单元测试。如果有人发现未通过的单元测试，请告诉我。
Code: NOTE: nearlyEqual(double,double)returns true if the two numbers are very close.
代码： 注意：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;
}
Here's the unit test:
这是单元测试：
@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));
}
回答by user2154342
Assuming the points are (Ax,Ay) (Bx,By) and (Cx,Cy), you need to compute:
假设点是 (Ax,Ay) (Bx,By) 和 (Cx,Cy)，您需要计算：
(Bx - Ax) * (Cy - Ay) - (By - Ay) * (Cx - Ax)
(Bx - Ax) * (Cy - Ay) - (By - Ay) * (Cx - Ax)
This will equal zero if the point C is on the line formed by points A and B, and will have a different sign depending on the side. Which side this is depends on the orientation of your (x,y) coordinates, but you can plug test values for A,B and C into this formula to determine whether negative values are to the left or to the right.
如果点 C 位于由点 A 和 B 形成的线上，则该值将为零，并且根据边的不同将具有不同的符号。这是哪一侧取决于您的 (x,y) 坐标的方向，但您可以将 A、B 和 C 的测试值插入此公式以确定负值是向左还是向右。
回答by boulder_ruby
@AVB's answer in ruby
@AVB 在 ruby 中的回答
det = Matrix[
[(x2 - x1), (x3 - x1)],
[(y2 - y1), (y3 - y1)]
].determinant
If detis positive its above, if negative its below. If 0, its on the line.
如果det为正则在上方，如果为负则在下方。如果为0，它就行了。
