3 points collinear in 2d

Question

I am trying to check when 3 points (double) are collinear in 2-D. I found various Pascal functions that return true if checked; these functions use an integer to indicate the X and Y coordinates. I need a more accurate calculation up to at least the first three digits of the decimal part of X and Y, expressed as a double type. Who can help me?

I found this function:

function Collinear(x1, y1, x2, y2, x3, y3: Double): Boolean; begin Result := (((x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)) = 0); end; 

But I think the calculation will never be 0. Should I use something like this?

 function Collinear(x1, y1, x2, y2, x3, y3: Double): Boolean; begin Result := (((x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)) < 0.01); end; 

Answer 1

David's code will work, but you should get tolerance depending on the parameters, for example:

 function Collinear(const x1, y1, x2, y2, x3, y3: Double): Boolean; inline; var tolerance: double; begin tolerance := abs(max(x1,x2,x3,y1,y2,y3)) * 0.000001; Result := abs((x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)) < tolerance; end; 

If you don’t do this and use a constant, you may encounter strange errors with large values ​​for x1..y3.

Answer 2

The scalar equation of the product that you calculate is zero if and only if the three points are linear. However, on a machine with finite precision, you do not want to check if it is equal to zero, but instead you check the zero value to a small tolerance.

Since the equation can be negative as well as positive, your test will not work. It returns false positives when the equation is evaluated with a large negative value. So you need to check that the absolute value is small:

 function Collinear(const x1, y1, x2, y2, x3, y3: Double): Boolean; const tolerance = 0.01;//need a rationale for this magic number begin Result := abs((x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)) < tolerance; end; 

Exactly how to choose tolerance depends on information that you did not provide. Where do the values ​​come from? Are they dimensional?