CODEWITHSUNDEEP
c
Bernd Jendrissek
Bernd Jendrissek

Reputation: 1088

How to determine if 3 points are exactly collinear in Z^2

Another collinear-points question. This one's twist is, I'm using integer arithmetic, and I'm looking for exact collinearity, not a fuzzy epsilon-based test.

With inline assembly, I can get an exact answer: the x86 multiply instruction gives access to both the high and low parts of the product, both of which matter in calculating the cross product (X - A) x (B - A); I can simply OR the two halves together and test for zero. But I'm hoping there's a way to do it in C, that's:

  1. Overflow-proof
  2. Portable
  3. Elegant

in roughly that order. And at the same time, a way to do it that is/does NOT:

  1. involve casting to double
  2. involve using a bigger integer type - assume that I'm already using the biggest integer type available for my coordinate component type
  3. yield either false positives or false negatives.

I'm not concerned in this question about whether X is beyond the segment AB; that's just four uninteresting comparisons.

My nightmare scenario is that I'll have to break each coordinate component into two halves, and do long multiplication explicitly, just so I can keep track of all the high halves in the partial products. (And then having to do add-with-carry explicitly.)

Upvotes: 9

Views: 1002

Answers (2)

asaelr
asaelr

Reputation: 5456

After some comparisons and simple checks, you can get 2 couple of positive numbers (x1,y1), (x2,y2), that you want to check if x1*y2==x2*y1.

You can use the Euclidean algorithm to find the GCD of x1 and y1, and divide them both by the GCM. Do the same thing for (x2,y2). If you got the same couple in both cases, then both vectors have the same direction.

Upvotes: 3

James
James

Reputation: 25513

If three points (a, b, c) are exactly colinear then the following identity holds:

c = a + (a - b) * scalar

i.e.:

c - a = scalar * (a - b)

So take the first component of (c-a), divide it by the first component of (a-b), save that value. Then repeat for each subsequent component, and if any of them differ, the points are not colinear.

If you want to avoid completely using floating point division (which would be the easiest way to do it), then you'll have to store the ratio, and compare that instead.

Upvotes: 0

Related Questions