Sign in to follow this  
ViperG

2D Vector intersection with circle or box

Recommended Posts

ViperG    206
If I have a 2D vector, I know how to tell if the end is inside either units, but how do I tell if the vector is going through the items? I want to make a beam like weapon, but it's possible for this beam to be outside these objects, and have it moved until it's going through the objects. Then I will test with a circle radius first, to see if it's close enough(closest point on the 2D vector to the center of circle), and if it's inside the circle I will test to see if it's going through the box. But I can't seem to find a good example or tutorial that I can understand. Can someone explain this to me in lamen's terms.

Share this post


Link to post
Share on other sites
cynicalpenguin    122
Assuming you have a starting point P, a vector V that has its tail located at P, and a circle with center point C and radius R circle-line collision goes something like this:

Calculate the vector C - P, we'll call it U.

If U dot U < R * R then we know that the point is located inside of the circle
and we know that there is a collision.

Otherwise if U dot V < 0 then the ray is travelling in the opposite direction and will never collide with the circle, so we can trivially say that there will not be a collision.

If neither of these are the case then we need to do a little more work (you'd have to do this anyway if you wanted to determine where the collision occurs)

First we need to project the vector U onto the vector V. We'll call this D. So,

D = (U dot V) / |V| (Note, we do _not_ want to use |V|^2 here)

Now we'll use the Pythagorean Theorem to find the shortest distance to the line defined by L: P + tV.

We'll call this distance N.
So,

N*N = (U dot U) - D*D

If N*N > R*R then we know that the ray will miss, otherwise there is a collision.

If you're interested in computing the value t that defines the point of intersection you can do the following:

Using the Pythagorean Theorem again we'll compute a distance M.

M*M = R*R - N*N

Finally,

tEntry = (D - M) / |V|
tExit = (D - M) / |V|

So, the point at which the line first hits the circle is X = P + tEntry*V.

Pictures would help out a lot, but I don't have anywhere to host them. If you'd like some I can email them to you.

Hope this helped,
Dave

Share this post


Link to post
Share on other sites
jyk    2094
So you're asking for an algorithm to intersect a line segment with an axis-aligned box in 2D, right? If so, do you just need a boolean result, or do you need the actual points of intersection?

Share this post


Link to post
Share on other sites
ViperG    206
Quote:
Original post by cynicalpenguin
Assuming you have a starting point P, a vector V that has its tail located at P, and a circle with center point C and radius R circle-line collision goes something like this:


Calculate the vector C - P, we'll call it U.



Ok let me get this straight, I want to normalize my beam vector, then see what the vector is from C to P?

Quote:



If U dot U < R * R then we know that the point is located inside of the circle
and we know that there is a collision.


This I don't understand. Why would I want to get the dot product of U and U. And why would multiplying my radius of the circle help me? if my circle radius was 25 then I would be testing U dot U (that would return like, what a -1-1) and compare it to the int 625?

Quote:


Otherwise if U dot V < 0 then the ray is travelling in the opposite direction and will never collide with the circle, so we can trivially say that there will not be a collision.



This I understand. anything above 0 means that the vectors are within 90 degres of each other.




If neither of these are the case then we need to do a little more work (you'd have to do this anyway if you wanted to determine where the collision occurs)

First we need to project the vector U onto the vector V. We'll call this D. So,

D = (U dot V) / |V| (Note, we do _not_ want to use |V|^2 here)[/qoute]

[/qoute]

Not sure what is going on, clueless after this...

[qoute]

Now we'll use the Pythagorean Theorem to find the shortest distance to the line defined by L: P + tV.

We'll call this distance N.
So,

N*N = (U dot U) - D*D

If N*N > R*R then we know that the ray will miss, otherwise there is a collision.

If you're interested in computing the value t that defines the point of intersection you can do the following:

Using the Pythagorean Theorem again we'll compute a distance M.

M*M = R*R - N*N

Finally,

tEntry = (D - M) / |V|
tExit = (D - M) / |V|

So, the point at which the line first hits the circle is X = P + tEntry*V.

Pictures would help out a lot, but I don't have anywhere to host them. If you'd like some I can email them to you.

Hope this helped,
Dave


Help!

Share this post


Link to post
Share on other sites
cynicalpenguin    122
Ahh, I think I misunderstood your question the first time through, it sounds like you're more interested in the intersection of a line segment and a circle.

If you model the beam as a point, a normalized vector that gives the direction the beam should travel, and a length that defines how long the beam is then I think the following might do what you want.

We'll define the beam to have it's base point located at P with the normalized vector V defining its direction and the scalar L which defines the beam's length.

To move the beam along the line you'd just do this:
P = P + sV, where s is the speed you'd like the beam to move at.

To determine if the beam is intersecting a circle defined with center point C and radius R follow these steps:

1.) Create the _unnormalized_ vector C-P, we'll call it U.

First we're going to test if the base point of the beam is located inside the circle. This will trivially tell us if the beam is intersecting the circle.

2.) If U dot U < R*R then the point is located inside of the circle.

We're using U dot U here because it is the same as the magnitude of U squared. We compare this against R*R so that we don't have to take a square root to determine if we're inside or not. Another way to think about it is like this, if the length of U is less than R then P must be inside the circle. This gives the equation

|U| < R, squaring both sides we get
|U|*|U| < R*R, recognizing |U|*|U| as U dot U we get
U dot U < R*R from above.

3.) Calculate the point Q defined as P + LV

Q is just the point located at the end of the beam, we'll perform the same test as before to see if this point is inside the circle or not.

4.) If (C-Q)dot(C-Q) < R*R then there is an intersection.

If we haven't detected an intersection from the previous two cases then a little more work needs to be done to determine if there is an intersection or not.

First we need to find out if the beam even comes within R distance of the center of the circle. To do this we need to calculate the shortest distance from C to the ray. This is done by,

5.) Finding the vector W that is the projection of U onto V.
So, W = (U dot V)*V (since V is already normalized).

Since we are dealing with a line segment and not the entire ray now would be a good time to make sure that the collision would occur within the segment. To do this you just need to make sure that the length of W is less than L.

6.) If (U dot V) > L there is not a collision.

Likewise, if U dot V is negative then the circle is located behind the beam and we know there won't be a collision.

7.) If (U dot V) < 0 there is not a collision.

From here we need to calculate the vector U-W, which is the vector that represents the shortest distance to C. We'll call this vector Z.

8.) Z = U-W

If |Z| < R then we know that the beam passes through the circle.

So, using the ideas from earlier

9.) If Z dot Z < R*R there is a collision

10.) Otherwise there is not a collision.

Hope this was a little more clear. I'd recommend drawing it out and labeling everything before you try to implement it.

Dave

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this