38

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.

Unihedron
  • 10,902
  • 13
  • 62
  • 72
Hossein
  • 40,161
  • 57
  • 141
  • 175

5 Answers5

81

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.

florin
  • 13,986
  • 6
  • 46
  • 47
  • 4
    This is much better because there is no risk of dividing by 0. – John Smith Sep 28 '10 at 14:31
  • 3
    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) – Joe Kington Sep 28 '10 at 14:43
  • 1
    +1 mathematically is the same but the concept is more simple/visual/straighforward (i like it). – joaquin Sep 28 '10 at 15:08
  • Using this formula with A:(516,520) B:(538,523) and C:(526,475) I get the area -1578! Why is that? – Hossein Oct 02 '10 at 11:02
  • 1
    @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. – florin Oct 04 '10 at 04:30
  • 1
    @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. – John Machin Oct 06 '10 at 02:53
  • @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. – florin Jan 08 '14 at 01:21
  • Float point errors means instead of checking `area == 0`, you'll have a much better time checking `area < 0.001` – Mirror318 Aug 02 '17 at 01:10
64

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;
}
dcp
  • 54,410
  • 22
  • 144
  • 164
  • @dtb - I added an explanation, let me know if you still have questions. – dcp Sep 28 '10 at 14:30
  • 2
    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 – Boris Gorelik Sep 28 '10 at 14:34
  • 1
    Couldn't one slope be positive and one negative? I think you ought to compare their absolute value. – Johannes Charra Sep 28 '10 at 14:37
  • @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. – Mark Peters Sep 28 '10 at 14:39
  • 2
    @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. – dcp Sep 28 '10 at 14:42
  • @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. – kriss Sep 28 '10 at 14:45
  • 2
    This requires less computation than @florin's answer even if it's equivalent (so I vote for it). – martineau Sep 29 '10 at 00:13
  • @Mark: you are right, no floats here. On the other hand, this algorithm isn't limited for floats, so ... – Boris Gorelik Sep 29 '10 at 10:47
  • 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](http://www.cygnus-software.com/papers/comparingfloats/Comparing%20floating%20point%20numbers.htm) ). – Georg Jan 30 '15 at 16:22
  • @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. – dcp Dec 24 '15 at 13:13
0

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

Dimitris Leventeas
  • 1,622
  • 2
  • 16
  • 29
0

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.

Douglas
  • 36,802
  • 9
  • 76
  • 89
-1

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.

Rob Vermeulen
  • 1,910
  • 1
  • 15
  • 22