9

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.)

6
  • Does the cross-product generalise to n dimensions? Commented Feb 28, 2012 at 0:17
  • Your title mentions Z^n, but the text of your question mentions the cross product, which I believe is only defined when n=3 (or n=2, by treating it as n=3 with z=0). Could you clarify whether you're looking for a general solution, or just an n=3 solution? I ask because, even though an n=2 or n=3 approach can easily be generalized to arbitrary dimensions (by checking for collinearity along overlapping two-or-three-element subsets of dimensions), it might be less elegant.
    – ruakh
    Commented Feb 28, 2012 at 0:20
  • @OliCharlesworth - Yes, but it's an (n-1)-ary operation.
    – user554546
    Commented Feb 28, 2012 at 0:23
  • Thanks for pointing out the ambiguity, fixed title to Z^2 (embedded in a Z^3 world) Commented Feb 28, 2012 at 0:23
  • 1
    In Z^2, I think this problem is equivalent to "how do I determine if two rational numbers are equivalent?". Commented Feb 28, 2012 at 0:25

2 Answers 2

3

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.

11
  • 1
    But what if all the numbers are co-prime and large? Commented Feb 28, 2012 at 0:36
  • 1
    @OliCharlesworth Then the GCD is 1, and x1*y2==x2*y1 iff x1==x2 && y1==y2
    – asaelr
    Commented Feb 28, 2012 at 0:38
  • Oh, I see what you're getting at. Commented Feb 28, 2012 at 0:41
  • +1: I have a feeling that this achieves all the OP's goals. However, it will almost certainly be less computationally efficient than just emulating long multiplication (GCD typically involves modulo arithmetic). Commented Feb 28, 2012 at 0:51
  • @OliCharlesworth: The Euclidean algorithm doesn't involve any modulo arithmetic, just comparison and subtraction. See en.wikipedia.org/wiki/Euclidean_algorithm.
    – ruakh
    Commented Feb 28, 2012 at 0:52
0

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.

5
  • That fails the "avoid casting to double" requirement. If you use rationals instead of doubles, there may be an overflow issue. Commented Feb 28, 2012 at 0:19
  • That's logically equivalent to what I was about to answer, but the problem is that you could easily end up with floats when dividing one component by another, and it sounds like the OP wants to avoid floating point arithmetic.
    – user554546
    Commented Feb 28, 2012 at 0:19
  • @Osi, Jack; see edit. Also, checking ratios are the same without reducing to the most basic form might be quite easy with integer division.
    – James
    Commented Feb 28, 2012 at 0:22
  • 1
    I want to avoid floating point arithmetic because I have no guarantee that double has any more precision than int. double could be a 52-bit-mantissa type, whilst int could be a 64-bit integer. So indeed, floating point division is out. Commented Feb 28, 2012 at 0:30
  • @BerndJendrissek That isn't necessarily true. You could get away with fewer bits of precision in your double than your int if you could place some constraint on the ratio of (a-b):(c-a), in any case, see note about comparing ratios: you can compare ratios by multiplying up to the largest of the numerators that you're comparing, no floating point involved.
    – James
    Commented Feb 28, 2012 at 0:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.