How can I check if a point is below a line or not ?

I've the following data:

Line [ {x1,y1}, {x2,y2} ]
Points {xA,yA}, {xB,yB} ...

I need to write a small algorithm in python to detect points on one side and the other side of the line.

thanks

Solution

You could try using a cross product -- http://en.wikipedia.org/wiki/Cross_product.

v1 = (x2-x1, y2-y1)   # Vector 1
v2 = (x2-xA, y2-yA)   # Vector 2
xp = v1[0]*v2[1] - v1[1]*v2[0]  # Cross product (magnitude)
if xp > 0:
    print('on one side')
elif xp < 0:
    print('on the other')
else:
    print('on the same line!')

You'd need to calibrate what each side is. If you want it to be "below" or "above" you need to ensure the points on the line are sorted horizontally.

I haven't tested this.

Edit I initially put in the dot product formula. :o

Edit 2 D'oh, I was putting the coordinates into a set instead of a tuple. Using namedtuple('point', 'x y') for the vectors is nice if you're running a reasonably modern version of Python.

Luckily I found Calculating a 2D Vector's Cross Product.