Point Crossing Line-Path Algorithm

Question

I have a problem in which i need to verify if a point had crossed a line-path,
a line path is collection of line(y=ax+b).
Does anyone know some known algorithim for this?

so i solved it like this: i added 2 points in the start and the end of the path- so now it is a polygon i added the 2 points in 90 degrees to the points in a fixed distance. and i used the ray algorithim.

Answer 1

There are simple algorithms to know if a point is inside or outside a polygon: http://en.wikipedia.org/wiki/Point_in_polygon This can be adapted to a line path setting by pushing some edges of the polygon to infinity (in practice, you can put your line path in a large box and cansider the polygon formed by the part of the box that is on the right (or left, as you want) side of the line).

Answer 2

Given a input point (x_1, y_1) , and your line is of the form y = ax + b, then you can tell where your input point locates by putting x_1 into the line equation:

if y_1 == a * x_1 + b then (x_1, y_1) is on the line
if y_1 < a * x_1 + b then (x_1, y_1) locates below the line
if y_1 > a * x_1 + b then (x_1, y_1) locates above the line

So you can tell whether a point has crossed a line by keeping track of the above result of that point.

Answer 3

so i solved it like this: i added 2 points in the start and the end of the path- so now it is a polygon i added the 2 points in 90 degrees to the points in a fixed distance. and i used the ray algorithim.

edit: its not always 90 degrees, it's depens on the angle between point start and point end

Answer 4

I know of two approaches:

1. use adapted point inside polygon algorithm
   • you must know which way is which side (crossed/non-crossed side)
   • so create a vector dir which points from line patch to the crossing side
   • it can be average normal (or normal of start-end point line)
   • cast ray from tested point in dir direction
   • count intersections with your line patch
   • if intersection occurs exactly on a connection point of two lines count it only once
   • at the end if the count is nonzero and odd then point has crossed line patch
   • this is robust error prone but little bit slow
   • see the left picture
2. if your line patch is not too complex shaped use winding rule (scalar vector multiplication)
   • line patch lines must be in single direction from start to end !!!
   • select lines from patch that are close to your point (1-5 should be sufficient)
   • ideally at the same height on the right picture
   • of course in real it can be rotated so select lines by the distance (no need to sqrt it)
   • compute dot product for selected lines like this:
   • line P0,P1, point P -> dot product = ((P1-P0).(P-P1))
   • dot product of 2 vectors ((x0,y0,z0).(x1,y1,z1))=(x0*x1+y0*y1+z0*z1)
   • the polarity of the result means the winding direction CW/CCW
   • if all the windings are correct than the point is not crossed
   • if the line patch shape is complex then problems can occur if point is too close to it
   • in that case test only lines of the same 'height' or use method 1.
   • to get the 'height' compute the distance between point and the line start point in lines direction
   • if its from zero to size of line that its OK else do not use it
   • also can be done with dot product on normal vector to line direction