Checking to see if 3 points are on the same line

Question

I want to know a piece of a code which can actually tell me if 3 points in a 2D space are on the same line or not. A pseudo-code is also sufficient but Python is better.

Aime

How is your line defined? Function on a 2d plane? – Fao

What exactly are you given? Three points? or three points and a line? – Thump

Answer 1

You can check if the area of the ABC triangle is 0:

[ Ax * (By - Cy) + Bx * (Cy - Ay) + Cx * (Ay - By) ] / 2

Of course, you don't actually need to divide by 2.

Cano

This is much better because there is no risk of dividing by 0. – Thump

Just to point something out... This is mathematically equivalent to @dcp's answer above (if you ignore the /2), but checking if the area is 0 makes it easier to add a tolerance... (i.e. stuff < err_tolerance instead of stuff1 == stuff2 as @dcp does above) – Tizzy

+1 mathematically is the same but the concept is more simple/visual/straighforward (i like it). – Binturong

Using this formula with A:(516,520) B:(538,523) and C:(526,475) I get the area -1578! Why is that? – Aime

@Hossein: Are you asking about the absolute value, or about the sign? With your points and my formula I'm getting -510. The sign means that you chose a certain order of the points. You could swap A with C or B and you'll get a positive area, even thought it's the same triangle. – Cano

@Joe Kington: (1) You need to do -tolerance < stuff < tolerance. (2) @florin's formula requires 3 multiplications and 5 additions/subtractions to give a "should be zero" result. @dcp's formula, adjusted by changing == to -, requires 2 mults and 5 subtractions to give a "should be zero" result. I'd give @dcp the tick, not @florin. – Chargeable

@JohnMachin: If you want to go to the bare CPU operations, with my formula you need only one comparison, since the value will be always positive. With dcp's test you need two comparisons, since you don't know the sign of the difference. – Cano

Float point errors means instead of checking area == 0, you'll have a much better time checking area < 0.001 – Jokjakarta

Answer 2

This is C++, but you can adapt it to python:

bool collinear(int x1, int y1, int x2, int y2, int x3, int y3) {
  return (y1 - y2) * (x1 - x3) == (y1 - y3) * (x1 - x2);
}

Basically, we are checking that the slopes between point 1 and point 2 and point 1 and point 3 match. Slope is change in y divided by change in x, so we have:

y1 - y2     y1 - y3
-------  =  --------
x1 - x2     x1 - x3

Cross multiplying gives (y1 - y2) * (x1 - x3) == (y1 - y3) * (x1 - x2);

Note, if you are using doubles, you can check against an epsilon:

bool collinear(double x1, double y1, double x2, double y2, double x3, double y3) {
  return fabs((y1 - y2) * (x1 - x3) - (y1 - y3) * (x1 - x2)) <= 1e-9;
}

Maggoty

@dtb - I added an explanation, let me know if you still have questions. – Maggoty

nice trick. However, checking floating point numbers for equality isn't safe. You might test the absolute difference against a pre-defined threshold that is dependent on the resolution (sensitivity) you want to achieve – Eadie

Couldn't one slope be positive and one negative? I think you ought to compare their absolute value. – Burgwell

@jellybean: I thought so too, but it checks out. Remember a negative slope is a different line (top left to bottom right). If the line goes 3, 1, 2 with 1 in the middle, it still works because the negatives cancel out. – Satyr

@dtb - x1==x2 works ok, consider these cases: collinear(-2,0,-2,1,-1,1) returns false, and collinear(-2,0,-2,1,-2,2) returns true. I think the corner cases are covered, let me know if you disagree. – Maggoty

@jellybean: negative slopes will give other lines than positive ones, then no you must not compare absolute values of you won't get the right answer. – Paucity

This requires less computation than @florin's answer even if it's equivalent (so I vote for it). – Proportionate

@Mark: you are right, no floats here. On the other hand, this algorithm isn't limited for floats, so ... – Eadie

I like this because it's more stable: Multiplication/division happens after addition/subtraction. The thing missing is using comparing the sides with each other: doublesEqual((y1 - y2) * (x1 - x3) , (y1 - y3) * (x1 - x2), EPSILON). That's better than testing against the arbitrary epsilon of 1e-9 because your values might be far away from 1 (see Comparison of floating point values ). – Bimanous

@georg - Actually, it's comparing the absolute difference between the products and making sure that difference is <= 1e-9. So whether the products themselves are close to or far away from 1 is irrelevant. Again, we are just interested in whether the absolute difference of the products is 1e-9 or less, which for our purposes, means we can assume the products are equal and thus, the slopes match. Hope that helps. – Maggoty

Answer 3

y - y0 = a(x-x0) (1) while a = (y1 - y0)/(x1 - x0) and A(x0, y0) B(x1, y1) C(x2, y2). See whether C statisfies (1). You just replace the appropriate values.

Details

Gibby

Answer 4

Read this, and use it to find the equation of a line through the first two points. Follow the instructions to find m and b. Then for your third point, calculate mx + b - y. If the result is zero, the third point is on the same line as the first two.

Pompano

Answer 5

Rule 1: In any linear 2d space, two points are always on the same line.

Take 2 points and build an equation that represents a line through them. Then check if the third point is also on that line.

Good luck.

Threadgill