| Collision Detection: Line vs Point, Circle and Rectangle |
|
| Written by Xuro | |||
| Wednesday, 03 March 2010 20:47 | |||
|
I recently needed to refresh my math a bit in order to detect the intersection of a line and a rectangle, or a line and a point. For everything so far, I had been using rectangular bounding boxes and simply using the standard built-in Rectangle .Intersects() functionality: if (bullets[i].Rect.Intersects(zombie.Rect))
{
zombie.alive = false;
bullets[i].alive = false;
player1.score += 1;
//chance for ammo drop
bool dropAmmo = (random.NextDouble() > 0.9);
if (dropAmmo)
{
SpawnPickupable(zombie.position, Vector2.Zero, PickupableType.Ammo);
}
break;
}
if (bullets[i].Rect.Intersects(enemy.Rect)) { enemy.alive = false; bullets[i].alive = false; //... }
This worked well, but with a new laser weapon I wanted to test for the collision between a line and a rectangle. I didn't need pixel-perfect collision, so I ended up going with using line-point collision as an approximation. In a nutshell, I do this: Given a line segment AB, and a point p... A) Find the point on the line segment nearest to the point p B) Calculate the distance between the nearest point and p C) Compare the distance between the points to a collision threshold distance, and if point p is closer to the line than that threshold distance I count it as a collision and react accordingly.
This approach works great for line-point intersections (collides if distance very near 0) and line-circle intersections (collides if distance < radius), and is a decent approximation of line-rectangle collision - good enough for my present needs. Here's some sample code that demonstrates, using the C# XNA framework, calculating the Line to Point distance, and using that distance to approximate line to rectangle collision detection.
public float DistanceLineSegmentToPoint(Vector2 A, Vector2 B, Vector2 p) { //get the normalized line segment vector Vector2 v = B - A; v.Normalize(); //determine the point on the line segment nearest to the point p float distanceAlongLine = Vector2.Dot(p, v) - Vector2.Dot(A, v); Vector2 nearestPoint; if (distanceAlongLine < 0) { //closest point is A nearestPoint = A; } else if (distanceAlongLine > Vector2.Distance(A,B)) { //closest point is B nearestPoint = B; } else { //closest point is between A and B... A + d * ( ||B-A|| ) nearestPoint = A + distanceAlongLine * v; } //Calculate the distance between the two points float actualDistance = Vector2.Distance(nearestPoint, p); return actualDistance; }
public bool LineIntersectPoint(Vector2 A, Vector2 B, Vector2 p, float dist) { float actualDistance = DistanceLineSegmentToPoint(A,B,p); if (actualDistance <= dist) return true; else return false; }
Having calculated the actual distance between p and the closest point on the line segment, we can use that info several ways: Detecting Line and Point intersection/collision We know that if distance == 0 (or very close, to allow for floating point errors), then the point p is on the line Detecting Line and Circle intersection/collision (calculate distance between line segment and the center point of circle) We know that if distance <= Radius of Circle, then the circle intersected the line Detecting Line and Rectangle intersection/collision (calculate distance between the line segment and the center point of rect) It is important to highlight that this last one is just a rough approximation. We know that if distance <= half the width of the shortest side, then the rectangle is definitely intersecting the line. However, beyond that there is a range of distances where distance alone is not a perfect indicator of intersection... i.e. the rectangle may or may not intersect the line depending on how it is rotated. However, choosing a reasonable distance threshold somewhere around half the average of the two sides can yield a workable approximation if you don't need pixel-perfect collisions and the Rect is fairly symmetrical.
If you do need pixel perfect collision, there is a good per-pixel tutorial at the Creator's Club site.
|
|||
| Last Updated on Wednesday, 03 March 2010 20:46 |


Comments
you can grab the line in the back, pull it and let it snap back in place like a rubber...
FYI finding a line-circle intersect point involves using what you know about the line/circle to determine the equations representing the two, and then solve the system of equations. I began writing an article about this, but came across some good C# articles already written on the subject. You can check them out in my post on finding object intersect points. Hope they help!
Finding Intersect Points: funplosion.com/devblog/calculating-intersect-points.html
I feel so stupid, I just scoured the internet for like a whole week and tested about 5 different code examples trying to fix this, and didn't realise my mistake until now! I'm so happy that my game is finally working
Now all I have to do is find where the line intersects with the circle's perimeter..... From the look of it, it seems that some simple trigonometry can solve that... but I'm no maths expert, I do graphics lol
Unless I am misunderstanding, that is actually what the code is intended to do - detect the collision between a point and line segment. If the point you are testing against is beyond one of the line segment endpoints, then the endpoint will be found as the nearest point on the line segment and it will calculate distance from that point. For your purposes are you looking to test for collision... not against the line-segment AB, but against the infinite line that contains points A and B?
Glad to see someone trying to use the code - if you can give me more information about what the behavior is you are aiming for, I would be happy to try and help troubleshoot the issue.
RSS feed for comments to this post.