# Polygon-Circle Collision Algorithm not working

EDIT: Updated code and video

I've been working on one of the last pieces of my collision detection system for my game, a polygon-circle collision method. I'm almost there with it, but there's a few minor issues that seem to pop up with it. I'll explain the few things I'm seeing, but it's probably easier just to watch the short video I have below:

https://1drv.ms/v/s!AjUDP95TjAMqje8AVA0LpPfeszVYoA

There are the three things I'm seeing:

• Little bit of bumpiness when going down a slope vs up (I'm guessing I just need to smooth out the movement adjustment a little bit
• When going around certain corners, the adjustment distance gets computed incorrectly, which results in either:
• A small bit of excess distance
• A large amount of excess distance

Below are the major components of my code, happy to update the post and add any other relevant code chunks that made be needed. Any assistance with this would be appreciated. Thanks!

Physics World Update Method:

IEnumerable<PhysicsFixtureBase> results = this.physicsTree.Query(fixture);
foreach (PhysicsFixtureBase otherFixture in results)
{
if (fixture.Body != otherFixture.Body && fixture.Intersects(otherFixture, out adjustment))
{
this.OnContact(fixture, otherFixture);
body.SetVelocity(Vector3.Zero);
}
}


Main Intersection Method:

public static bool Intersects(PhysicsCircleFixture circle, PhysicsPolygonFixture otherPolygon, out Vector3 adjustment)
{
bool result = PhysicsCollisionHandler.Intersects(otherPolygon, circle, out adjustment);
return result;
}

public static bool Intersects(PhysicsPolygonFixture polygon, PhysicsCircleFixture otherCircle, out Vector3 adjustment)
{

Vector2 circleCenter = otherCircle.GetPosition2D();

Vector2 closestPoint = Vector2.Zero;
float closestDistance = float.MaxValue;

foreach (Vector2 point in polygon.Points)
{
float distance = circleCenter.Distance(point);
if (distance < closestDistance)
{
closestDistance = distance;
closestPoint = point;
}
}

Vector2 previousPoint = polygon.Points[polygon.Points.Count - 1];
foreach (Vector2 currentPoint in polygon.Points)
{
Vector2 edge = currentPoint - previousPoint;
float interp = edge.DotProduct(circleCenter - previousPoint) / edge.DotProduct(edge);
if (0.0f < interp && interp < 1.0f)
{
Vector2 point = previousPoint + edge * interp;
float distance = circleCenter.Distance(point);

if (distance < closestDistance)
{
closestDistance = distance;
closestPoint = point;
}
}
previousPoint = currentPoint;
}

{
float penetrationDistance = circleRadius - closestDistance;
Vector2 normalizedVector = (closestPoint - circleCenter) / closestDistance;
}

}


Helper Code:

public static Vector2 Normal(this Vector2 vector) { return new Vector2(-vector.Y, vector.X); }

public class Range
{
public float Min { get; set; }

public float Max { get; set; }

public Range(float min, float max)
{
this.Min = min;
this.Max = max;
}

public float Length() { return this.Max - this.Min; }

public Range Intersects(Range other)
{
Range longestDistance = new Range(Math.Min(this.Min, other.Min), Math.Max(this.Max, other.Max));
if (longestDistance.Length() < (this.Length() + other.Length()))
{
return new Range(Math.Max(this.Min, other.Min), Math.Min(this.Max, other.Max));
}
return null;
}
}

public Range PhysicsPolygonFixture.ProjectOnAxis(Vector2 axis)
{
Range range = new Range(float.MaxValue, float.MinValue);
foreach (Vector2 point in this.Points)
{
float projection = point.DotProduct(axis);
if (projection < range.Min)
{
range.Min = projection;
}
if (projection > range.Max)
{
range.Max = projection;
}
}
return range;
}

public Range PhysicsCircleFixture.ProjectOnAxis(Vector2 axis)
{
float circleCenterProjection = this.GetPosition2D().DotProduct(axis);
}


The code that checks for edge collisions is definitely causing the problems you're seeing. Since it's also a little more complex than necessary, I think the right solution is to rewrite it completely.

Remove the entire foreach (Vector2 edge in polygon.Edges) loop, and add the following code above the line if (closestDistance < circleRadius):

Vector2 pointPrev = polygon.Points[polygon.Points.Length - 1];
foreach (Vector2 pointCur in polygon.Points)
{
Vector2 edge = pointCur - pointPrev;

float interp = edge.DotProduct(circleCenter - pointPrev) / edge.DotProduct(edge);

if (interp > 0.0f && interp < 1.0f)
{
Vector2 point = pointPrev + edge * interp;
float distance = circleCenter.Distance(point);

if (distance < closestDistance)
{
closestDistance = distance;
closestPoint = point;
}
}

pointPrev = pointCur;
}


Note 1

I tried to use your function and type names. The only thing I didn't have a reference for was whether polygon.Points is an array or a list.

Note 2

The only tricky bit there is the calculation of interp; it combines two calculations into one to avoid a square root. It normalizes the edge vector and also divides the projection of the circle's center onto the edge by the length of the edge vector.

• Thanks for the feedback. I put in your changes and gave it a run, but there not seems to be the opposite effect of the previous code. Instead of the corners leaving gaps between the two objects, the corners now end up going into the object and causing a slingshot back and forth effect. I've edited the original post with the updated code and included a new video of the effects: 1drv.ms/v/s!AjUDP95TjAMqje8AVA0LpPfeszVYoA I'll continue looking into it, but my guess is the new logic is saying that the edges are closer than the points someone, to a certain extent. – SaviorXTanren May 9 '17 at 4:21
• I think I see the problem. In your new code, try negating adjustment. Right now, it points from the circle toward the collision point, and that seems backwards to me. – Victor T. May 9 '17 at 13:59
• I tried that, but that actually makes it get even worse. The circle ends up sling-shot effect through the entire triangle like a weird black hole. I definitely think the effects I'm seeing have something to do specifically with the point collision chunk of code; either in determining which point is the closest (unlikely) or in the adjustment chunk of code (more likely). – SaviorXTanren May 10 '17 at 16:23
• I did some testing around in the code when the circle hits one of the corners and here's what I do know: 1) The correct closest point is selected. 2) One of the edges is NOT selected as the closest point. 3) Every time the collision detection is determined with the point, an adjustment is made. 4) My guess is that every time the collision happens with a point, the first adjustment ends up pushing it into the triangle, which makes the second collision push it out of the triangle, thus giving the ping-pong effect. I'll keep digging into the adjustment logic for points. – SaviorXTanren May 10 '17 at 16:23
• I figured it out! Had absolutely nothing to do with the code above. I have some QuadTree code I'm using to reduce physics calculations. My QuadTree Query code to find objects that are nearby it was failing when it came to the edges of the shape. That's why there was the ping-pong effect (It wouldn't find it for a few frames, then find it and shoot it back). Thanks for all your help with the other logic though! – SaviorXTanren May 11 '17 at 0:44