Saturday, April 2, 2011

2D geometry + infinite and zero slopes

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
>>> 1.0/1.0e-309

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

>>> 0.0 == 1.0e-10000

With some trigonometric functions from the math module:

>>> math.atan2(1.0, 0.0000000000000001)
>>> 2 * _
>>> _ == math.pi

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

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

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.