Check is a point (x,y) is between two points drawn

问题:

I have drawn a line between two points A(x,y)---B(x,y) Now I have a third point C(x,y). I want to know that if C lies on the line which is drawn between A and B. I want to do it in java language. I have found couple of answers similar to this. But, all have some problems and no one is perfect.

回答1:

if (distance(A, C) + distance(B, C) == distance(A, B))
    return true; // C is on the line.
return false;    // C is not on the line.

or just:

return distance(A, C) + distance(B, C) == distance(A, B);

The way this works is rather simple. If C lies on the AB line, you'll get the following scenario:

A-C------B

and, regardless of where it lies on that line, dist(AC) + dist(CB) == dist(AB). For any other case, you have a triangle of some description and 'dist(AC) + dist(CB) > dist(AB)':

A-----B
 \   /
  \ /
   C

In fact, this even works if C lies on the extrapolated line:

C---A-------B

provided that the distances are kept unsigned. The distance dist(AB) can be calculated as:

  ___________________________
 /           2              2
V (A.x - B.x)  + (A.y - B.y)

Keep in mind the inherent limitations (limited precision) of floating point operations. It's possible that you may need to opt for a "close enough" test (say, less than one part per million error) to ensure correct functioning of the equality.

回答2:

ATTENTION! Math-only!

You can try this formula. Put your A(x1, y1) and B(x2, y2) coordinates to formula, then you'll get something like

y = k*x + b; // k and b - numbers

Then, any point which will satisfy this equation, will lie on your line. To check that C(x, y) is between A(x1, y1) and B(x2, y2), check this: (x1<x<x2 && y1<y<y2) || (x1>x>x2 && y1>y>y2).

Example

A(2,3) B(6,5)

The equation of line:

(y - 3)/(5 - 3) = (x - 2)/(6 - 2)
(y - 3)/2 = (x - 2)/4
4*(y - 3) = 2*(x - 2)
4y - 12 = 2x - 4
4y = 2x + 8
y = 1/2 * x + 2; // equation of line. k = 1/2, b = 2;

Let's check if C(4,4) lies on this line.

2<4<6 & 3<4<5 // C between A and B

Now put C coordinates to equation:

4 = 1/2 * 4 + 2
4 = 2 + 2 // equal, C is on line AB

PS: as @paxdiablo wrote, you need to check if line is horizontal or vertical before calculating. Just check

y1 == y2 || x1 == x2

回答3:

I believe the simplest is

// is BC inline with AC or visa-versa
public static boolean inLine(Point A, Point B, Point C) {
   // if AC is vertical
   if (A.x == C.x) return B.x == C.x;
   // if AC is horizontal
   if (A.y == C.y) return B.y == C.y;
   // match the gradients
   return (A.x - C.x)*(A.y - C.y) == (C.x - B.x)*(C.y - B.y);
}

You can calculate the gradient by taking the difference in the x values divided by the difference in the y values.

Note: there is a different test to see if C appears on the line between A and B if you draw it on a screen. Maths assumes that A, B, C are infinitely small points. Actually very small to within representation error.

回答4:

The above answers are unnecessarily complicated. The simplest is as follows.

1. if (x-x1)/(x2-x1) = (y-y1)/(y2-y1) = alpha (a constant), then the point C(x,y) will lie on the line between pts 1 & 2.

2. If alpha < 0.0, then C is exterior to point 1.

3. If alpha > 1.0, then C is exterior to point 2.
4. Finally if alpha = [0,1.0], then C is interior to 1 & 2.

Hope this answer helps.

回答5:

I think all the methods here have a pitfall, in that they are not dealing with rounding errors as rigorously as they could. Basically the methods described will tell you if your point is close enough to the line using some straightforward algorithm and that it will be more or less precise.

Why precision is important? Because it's the very problem presented by op. For a computer program there is no such thing as a point on a line, there is only point within an epsilon of a line and what that epsilon is needs to be documented.

Let's illustrate the problem. Using the distance comparison algorithm:

Let's say a segment goes from (0, 0) to (0, 2000), we are using floats in our application (which have around 7 decimal places of precision) and we test whether a point on (1E-6, 1000) is on the line or not.

The distance from either end of the segment to the point is 1000.0000000005 or 1000 + 5E-10, and, thus, the difference with the addition of the distance to and from the point is around 1E-9. But none of those values can be stored on a float with enough precission and the method will return true.

If we use a more precise method like calculating the distance to the closest point in the line, it returns a value that a float has enough precision to store and we could return false depending on the acceptable epsilon.

I used floats in the example but the same applies to any floating point type such as double.

One solution is to use BigDecimal and whichever method you want if incurring in performance and memory hit is not an issue.

A more precise method than comparing distances for floating points, and, more importantly, consistently precise, although at a higher computational cost, is calculating the distance to the closest point in the line.

Shortest distance between a point and a line segment

It looks like I'm splitting hairs but I had to deal with this problem before. It's an issue when chaining geometric operations. If you don't control what kind of precission loss you are dealing with, eventually you will run into difficult bugs that will force you to reason rigorously about the code in order to fix them.

回答6:

An easy way to do that I believe would be the check the angle formed by the 3 points. If the angle ACB is 180 degrees (or close to it,depending on how accurate you want to be) then the point C is between A and B.