3 replies to this topic

[FlyFire]

Hi, i need to know fastest way of doing these calculations (all is 2d planar):

1) Check if ray can intersect line segment (without finding intersection point for speed reasons)
Ray defined by starting point and cross point, and line segment defined by two points.

2) find intersection between ray and line segment

3) find on which side of ray (left or right) point lies

------------------
FlyFire/CodeX
http://codexorg.webjump.com

[Splat]

Ok, the problem that I see with number 1 is that you are dealing with a line _segment_. A couple floating point multiplies and subtracts (using Cramer's rule) and you can have an X coordinate of the intersection, then a quick bounds check on the line segment to see if that intersection is actually on the segment.

As for number 2, you can follow up number with the calculation for the Y coordinate as well with little effort.

For number 3, I assume you mean on which side of a line, because if you really mean a ray then you must explain what result you want if the point lies on the line containing the ray but not the ray itself. If you do in fact mean a line, a quick check to see where the line is at the point's X coordinate (must have it's equation in y = mx + b form) will yield the answer.

I can type some quick code up for you if you need it. Just email me at: splat@bancroftpress.com

[FlyFire]

Ok, thanx for your answer.
I found solution for 3: solve line equation ax+by+c=0 (find a,b and c) for AB ray and then insert C point coordinates and check result sign (if >0, then on the left)

------------------
FlyFire/CodeX
http://codexorg.webjump.com

[TANSTAAFL]

all you need to do to determine if a line and a ray CAN cross is check to see if they are parallel, which is just checking the slopes against one another, with of course a special case for infinite slopes.

for rays, you can also use parametric equations to simplify things.

x=x0+cos(theta)*t
y=y0+sin(theta)*t
t>=0

where theta is the angle in which the ray is going and x0,y0 is the start of the ray.

to determine whether a point is on or not on the ray, you take either the x or y and solve for t, if t<0, then the point is NOT on the ray, otherwise it is. since you only care about whether or not it's negative, you dont actually have to perform the division, you can just compare things to 0