Sign in to follow this  
mr_malee

Finding line segment end point closest to moving circle

Recommended Posts

it seems like this would be a simple problem but its not looking like it. say I have a line segment made from two points p1 and p2 and I have a moving circle at p3 with radius r and end point p4 how can I find which point on the line (p1 or p2) will come into contact with the moving circle first if there is any contact at all? I don't have any diagrams atm, but can draw up some if needed. Thanks for the help :)

Share this post


Link to post
Share on other sites
Quote:
how can I find which point on the line (p1 or p2) will come into contact with the moving circle first if there is any contact at all?
What do you mean by 'p1 or p2'? (The circle could easily come into contact with the segment without coming into contact with either of the endpoints.)

Share this post


Link to post
Share on other sites
You can try compute the point on the line that is closest to the center of the circle at any given time. But this might not be easy.

Share this post


Link to post
Share on other sites
Well I think I've solved it.

demo

click to position the capsule start.

here's how It works now:

1. project line segment ends onto capsule velocity.
2. find distances these intersections are back to their respective ends
3. check these distances against circle circle radius, if both are smaller, find distances both intersections are to capsule start and choose smallest, pick the edge which corresponds to this distance. If only 1 is smaller then just use the corresponding edge. if no edges are found, skip edge test.
4. if there is an edge, determine direction. for line start its 1.0, for line end its -1.0. Now test the edge as a swept circle circle test where the edge has a radius of 0, if the edge hits and the dot product of that edge to the capsule * direction > 0 then we have an edge collision and stop here.
5. no edge found, run infinite line swept test. if collision found, find distance from line start and compare with line length, if its within we have a collision and we can now drink a beer :)


jyk - as above I needed to know the closest edge and some information about its direction so I could run a circle circle swept test.

mrr - yeah, thats what I was trying to do.

I'm not sure if my solution is any good, but it works and I'm happy again :)

*1 problem remains though, and thats finding the time on velocity when the capsule start is within the line and the velocity goes through the line.

Share this post


Link to post
Share on other sites
The following steps should solve your problem:

1. Find the circle intersection point (circle origin + normal vector perpendicular to the line * circle radius. This is the point that will intersect with the line.
2. Do a line line intersection test and find the intersection point, if the point lies in the line segment you're done. If it doesn't get the closest point (p1 or p2) and do a line circle intersection test in the direction of the negative velocity vector originating from p1 or p2.

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