My last post dealt with a similar subject, but it didn't quite tell the whole story. No sooner had I posted it and attempted to implement it in a project, I ran into a problem. Granted, it was on a Java GUI in Java code (not a Python project) - but the concept is universal. When is a floating point number small enough that another mathematical operation on it will take it to zero or to the realm of infinity?

Python (I'm using CPython 2.5) is pretty forgiving in this sense.

>>> 1.0/1.0e-308

1e+308

>>> 1.0/1.0e-309

inf

There comes a point when even a representable number equals zero.

>>> 0.0 == 1.0e-10000

True

With some trigonometric functions from the math module:

>>> math.atan2(1.0, 0.0000000000000001)

1.5707963267948966

>>> 2 * _

3.1415926535897931

>>> _ == math.pi

True

>>> math.cos(1.0000000000000000001e-250)

1.0

The equation for the slope of a line in the Cartesian plane is (y2 - y1)/(x2 - x1) where y2, y1, x2, and x1 are the x and y coordinates of the enpoints of the line.

One way I've handled the infinite slope problem in the past is by setting a value as infinity:

# one million

>>> INFINITY = 1.0e+6

>>> slope = 1000000.0

>>> slope == INFINITY

True

This works sometimes, but it's not totally safe from error.

What I ended up doing this time was checking for zero or near zero values in the numerator and denominator of the slope equation.

NEARZERO = 1.0e-6

if math.abs(y2 - y1) < NEARZERO:

# set y2 == y1 or vice versa

# and proceed with the calculations

# for a zero slope

if math.abs(x2 - x1) < NEARZERO:

# set x2 == x1 or vice versa

# and proceed with the calculations

# for an infinite slope

This solved my problem in the sense that it gave reasonable results that served the problem domain well.

Lastly, you could use a similar method to check for duplicate points. If both numerator and denominator of the slope equation are near zero, the line segment is too small and the point should be done away with:

if (math.abs(y2 - y1) < NEARZERO and

math.abs(x2 - x1) < NEARZERO):

# duplicate point

# delete it

Disclaimer: I am not a floating point math expert. There may be better solutions out there. These are a couple practical ones that have worked for me.

Your NEARZERO value is usually called "epsilon". This is a common technique for compensating for floating point precision limits.

ReplyDeleteTwo things I highly recommend reading on the subject of floats:

http://cowboyprogramming.com/2007/01/05/visualizing-floats/

http://www.cygnus-software.com/papers/comparingfloats/comparingfloats.htm

In general the slope-intercept method of modeling lines is problematic as you have found. I much prefer using a normal unit vector and an offset from the origin. This does not suffer from these types of precision issues until the line gets *very* far away from the origin.

You can find a python implementation I wrote of this here if it helps:

https://bitbucket.org/caseman/planar/src/9f8615991edd/lib/planar/line.py

@casey - thanks a ton for the links and info. This is very helpful feedback. It would behoove me to learn vector math, and your link will be a good start. Carl T.

ReplyDelete