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:
- Overflow-proof
- Portable
- Elegant
in roughly that order. And at the same time, a way to do it that is/does NOT:
- involve casting to
double
- involve using a bigger integer type - assume that I'm already using the biggest integer type available for my coordinate component type
- 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.)
n-1
)-ary operation.