CODEWITHSUNDEEP
algorithmcomputational-geometry
user1763180
user1763180

Reputation: 115

Point Crossing Line-Path Algorithm

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.

Upvotes: 2

Views: 1897

Answers (4)

Spektre
Spektre

Reputation: 51845

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

Line patch crossing

Upvotes: 0

user1763180
user1763180

Reputation: 115

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

Upvotes: 0

keelar
keelar

Reputation: 6026

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.

Upvotes: 1

Thomash
Thomash

Reputation: 6379

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).

Upvotes: 1

Related Questions