haskell floating point precision

Question

I wrote a little program to find the position of a point(x,y) in relation to a line defined by a point(px,py) and an angle(deg) to the x-axis (in a cartesian coordinate system).

toRadian deg = deg * (pi / 180)

lineSlope deg = tan $ toRadian deg

lineYintercept (x,y) deg = y - (x * lineSlope deg)

relativePointPosition (px,py) deg (x,y)
    | s < 0 && deg>=0 && deg<90 = "Left"
    | s < 0 && deg>=90 && deg<180 = "Left"
    | s < 0 && deg>=180 && deg<270 = "Right"
    | s < 0 && deg>=270 && deg<360 = "Right"
    | s > 0 && deg>=0 && deg<90 = "Right"
    | s > 0 && deg>=90 && deg<180 = "Right"
    | s > 0 && deg>=180 && deg<270 = "Left"
    | s > 0 && deg>=270 && deg<360 = "Left"
    | s > 0 && deg==360 = "Right"
    | s < 0 && deg==360 = "Left"
    | otherwise = "On the line"
    where s = lineSlope deg * x + lineYintercept (px,py) deg -  y

It works exceptionaly well for points that are away from the line, but not so well for points that are close or on the line. How can I improve the accuracy??

Answer 1

The problem is, that several calls to functions like tan or pi are defaulting your calculations to type Double, or generally to any type of Floating. It is commonly known under programmers, that you should never compare two floating point values for equality (you do implicit), because the calculations may often cause small errors. It would be better to define an own function, which tests whether the difference of two floating numbers is under a specific limit:

equals :: Floating a => a -> a -> Bool
equals a b = abs (a - b) < 0.000001 -- change the value to whatever fits best

And handle the "equality" cases first.

Answer 2

How are you running this code? Your method will only return that the point is on the line if is absolutely spot on the line. If you are drawing the line on the screen and reading where the user clicks then unless your angle is a "nice" angle like 0, 90, etc, it's unlikely that the pixel lies exactly on the line.

First consider drawing a line at exactly 0 degrees, starting at (100, 100). Clicking at (200, 100) will be on the line because tan 0 == 0, so lineSlope 0 == 0 and thus s comes down to 100 - 100 == 0. But now consider if the line is at 0.000001 degrees. Taking the tangent gets a number like 0.000000017 according to my calculator. So now clicking at (200, 100) evaluates s to 0.000000017 * 200 + 100 - 100 * 0.000000017 - 100, which all comes out at a tiny bit over 0. But that tiny bit breaks your equality comparison, and your function will say "Right".

You probably want to compare distance to the line with an epsilon value (see, for example, the first part of this page: http://www.cygnus-software.com/papers/comparingfloats/comparingfloats.htm -- but not the hacky bit later on) to allow a little tolerance for being so close to the line you count as on the line.

Answer 3

You could use the fact that your line, given by angle (px,py) may be given by an equational definition on the form a*x+b*y+c=0 where a,b,c are given by

sin angle*(x-px) - cos angle*(y-py) = 0

Thus, you can simply define

lineF angle (px,py) = \ (x,y) -> (sin angle)*(x-px)-(cos angle)*(y-py)

and use this in a test like this

lineTest angle (px,py) (x,y) 
   | f (x,y) < -eps = "Left"
   | f (x,y) > eps = "Right"
   | otherwise = "On the line"
  where
    f = lineF angle (px,py)
    eps = 1e-9 -- confidence interval as Neil Brown specified.

Basically, the function defining a line in its most general form gives you a function that will compute the distance from the line, that you can use to test where things are located too. You might need some fiddling to figure out what "Left" and "Right" are actually supposed to mean wrt a generic line.