Viktor Hesselbom

Projecting circle or point out of polygon shape

This post will describe a method to project a circle (or a point) out of either a convex or a concave polygon. The example code will be written in ActionScript.

Okay, let's get started. For this I have written a simple vector class and a polygon class. They are nothing special, the vector class is like you would expect and the polygon class is simply an array of vectors. Never-the-less, if you want to look at them I have linked them, along with the complete code of what I'm discussing, at the end of this post.

First of all, if you don't know what a vector is (or what particular vector I'm talking about, since the word is used for so much) it's basically a line segment. In my vector class I store the length of the vector along with the direction.

EDIT: Actually, a vector is simply a point in a coordinate space. Woops. Sorry, I learn as I go. :)

First we create a new vector to use as the position of the circle and a polygon shape.

point = new Vector2D (0, 0);
shape = new Polygon ();
shape.addPoint (80, 20);
shape.addPoint (110, 30);
shape.addPoint (100, 60);
shape.addPoint (70, 70);
shape.addPoint (40, 40);
shape.connectLines ();

That's it for the initializing. I will leave the rendering process to you. ;)

Now, the first thing we want to check is the closest way out of the polygon. To do this we loop through the polygon's walls and check the distance between the point and each wall and return the closest. The actual method of checking the distance between a point and a line is outside of this post's scope but you can check it out in the vector class provided at the end of the post.

This is the code of what I just described:

closestDistance = null;
for each (var v:Vector2D in shape.lines)
{
	var dist:Vector2D = v.distanceToVector (point);
	if (closestDistance == null || dist.len < closestDistance.len)
		closestDistance = dist;
}

Now we have the closest distance as a vector line and can simply project the point out of the polygon by translating the point with the distance. The vx and vy of the vector class is simply the direction * length of the vector.

if (closestDistance != null)
{
	point.x -= closestDistance.vx;
	point.y -= closestDistance.vy;
}

Here's how this would look (point being at mouse and circle is the point projected by the closest distance):

As you surely noticed it now tries to project the point out of the polygon even though the point isn't inside the polygon! The obvious way to fix this is to check if the point is inside the polygon. To do this we create a vector to serve as a horizontal ray from outside the polygon to the point. Make sure that the ray always starts outside of the polygon. Then the only thing we have to do is to check how many walls in the polygon is intersecting the ray. If the amount is an odd number it means the point is inside the polygon. This method is described in detail here.

This is how it could look in code, combining with what we already have.

// Create ray to check if point is inside shape
ray = new Vector2D (0, point.y);
ray.vx = point.x;
ray.dx = 1;
isInside = false;
 
// Update closest distance and find ray collisions
closestDistance = null;
var hits:int = 0;
for each (var v:Vector2D in shape.lines)
{
	var dist:Vector2D = v.distanceToVector (point);
	if (closestDistance == null || dist.len < closestDistance.len)
		closestDistance = dist;
	if (ray.isIntersecting (v))
		hits ++;
}
 
isInside = (hits%2 == 1);
 
if (closestDistance != null)
{
	if (isInside)
	{
		point.x -= closestDistance.vx;
		point.y -= closestDistance.vy;
	}
}

Where it checks if the ray is intersecting the wall we will run into a problem if the ray is intersecting at the exact corner (vertex) of the wall because then it will record both that wall and the previous one (because it would also be at the exact opposite corner of that wall) and add two hits instead of one and thus giving us a false result. To work around this we can add a check to see if the ray's y is the same as the wall's y and if it is we don't increment hits. Remember that the x and y of the wall is the first corner and x+vx and y+vy is the second corner. Because this is not a problem at the top and bottom corners we can disregard the check if the wall is at the top or bottom. So change that part of the code to this:

if ((ray.y != v.y || ray.y == shape.lowestPos || ray.y == shape.highestPos) && ray.isIntersecting (v))
	hits ++;

Here's how this would look (the red line is the ray):

Much better!

That's it if all you want to do is to project a point out of a shape. If you want to project the complete circle outside of the shape there's not much extra work! The first thing you have to do is add the radius to the projection. All you have to do is getting the direction of the projection (closest distance, remember?) and multiply it with the circle's radius.

point.x -= radius * closestDistance.dx;
point.y -= radius * closestDistance.dy;

This works fine and dandy when the point is still inside the polygon. But if the point is outside of the polygon but the borders of the circle is still inside it won't get noticed. To fix this we only have to check if the closest distance is less than or equal to the circle's radius. And because if this is true (the circle being outside the polygon but still colliding) the distance projection would be projecting in the wrong direction and we have to add the radius with the reversed direction. Like this:

var isCircleInside:Boolean = (closestDistance.len <= radius);
 
if (closestDistance != null)
{
	if (isInside)
	{
		point.x -= closestDistance.vx;
		point.y -= closestDistance.vy;
		point.x -= radius * closestDistance.dx;
		point.y -= radius * closestDistance.dy;
	}
	else if (isCircleInside)
	{
		point.x -= closestDistance.vx;
		point.y -= closestDistance.vy;
		// Notice the inverse direction:
		point.x -= radius * -closestDistance.dx;
		point.y -= radius * -closestDistance.dy;
	}
}

This is how it would look now:

There's still a small bug left to fix. In the previous example, if you manage to place the point exactly at a line the distance between the point and closest wall will be 0 and thus the dx and dy will be 0 and the circle won't be pushed out. This is solvable by first telling the code to also store the closest wall (to which the closest distance is associated to) and calculating it's right and left normals. The right and left normals are the two vectors that are perpendicular to the vector. One with direction to the right and the other to the left. Then we use one of the normals as the new direction. But which normal to use? Maybe a little naively I just check the rotation of the wall with atan2 and if the value is positive use left normal and if negative use right normal. If anyone knows a more elegant solution, please do tell.

In any case, this is what you would change the projection part to:

if (closestDistance != null)
{
	var dx:Number = closestDistance.dx;
	var dy:Number = closestDistance.dy;
	if (dx == 0 && dy == 0)
	{
		var lx:Number = closestWall.dy;
		var ly:Number = -closestWall.dx;
		var rx:Number = -closestWall.dy;
		var ry:Number = closestWall.dx;
		if (Math.atan2 (closestWall.dy, closestWall.dx) > 0)
		{
			dx = lx;
			dy = ly;
		}
		else
		{
			dx = rx;
			dy = ry;
		}
	}
	if (isInside)
	{
		point.x -= closestDistance.vx;
		point.y -= closestDistance.vy;
		point.x -= radius * dx;
		point.y -= radius * dy;
	}
	else if (isCircleInside)
	{
		point.x -= closestDistance.vx;
		point.y -= closestDistance.vy;
		point.x -= radius * -dx;
		point.y -= radius * -dy;
	}
}

And this is the result:

And we're done! Phew. Any questions welcome.

These are the classes I used for this post: