Geek Answers Handbook

How to determine that 3 points are precisely collinear in Z ^ 2

Another question is about collinear points. This twist, I use integer arithmetic, and I'm looking for exact collinearity, not a fuzzy epsilon test.

With the built-in assembly, I can get the exact answer: the x86 multiplication instruction gives access to both the upper and the lower parts of the product, both of which are important when calculating the cross-product ( X - A ) x ( B - A ); I can just OR two halves together and check for zero. But I hope there is a way to do this in C, here is this:

  • Overflow proof
  • Portable
  • Elegant

roughly in that order. And at the same time, the way to do this is that there is / NOT:

  • enable casting in double
  • use a larger integer type - suppose I already use the largest integer type available for my type of coordinate component
  • false positives or false negatives are output.

I am not interested in the question of whether X is outside segment AB ; these are just four uninteresting comparisons.

My nightmare scenario is that I will have to split each coordinate component into two halves and do a long multiplication explicitly, so that I can track all the high halves in partial products. (And then you need to do the add-with-carry explicitly.)

+8
c
source share
2 answers

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

You can use the Euclidean algorithm to find GCD x1 and y1 , and separate them as in GCM. Do the same for (x2,y2) . If in both cases you have the same pair, then both vectors have the same direction.

+2
source share

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

 c = a + (a - b) * scalar

i.e:.

 c - a = scalar * (a - b)

So, take the first component (ca) , divide it into the first component (ab) , save this value. Then repeat for each subsequent component, and if any of them is different, the points are not colinear.

If you want to completely abandon the use of floating point division (which would be the easiest way to do this), then you will need to save the ratio and compare it.

0
source share

More articles:


All Articles