# Shrink a convex polygon

Shrinking a concave polygon is quite hard, to do well. But I expect shrinking a convex polygon would be easy.

The naive approach of moving each vertex a certain distance to the centre gives me poor results though: Notice how for long edges, the displacement is much less than the other shapes.

static void shrink_poly( int numcoord, jcv_point* coords )
{
jcv_point c = {0,0};
for ( int i=0; i<numcoord; ++i )
{
c.x += coords[i].x;
c.y += coords[i].y;
}
c.x = c.x / numcoord;
c.y = c.y / numcoord;

const float bordersz = 0.008f;
for ( int i=0; i<numcoord; ++i )
{
float dx = coords[i].x - c.x;
float dy = coords[i].y - c.y;
float l = sqrtf( dx*dx+dy*dy );
float dirx = dx / l;
float diry = dy / l;
coords[i].x = c.x + (l-bordersz) * dirx;
coords[i].y = c.y + (l-bordersz) * diry;
}
}


So for my second approach, I move the edges instead of the vertices, to get even spacing. However, doing this causes the shapes to degenerate: non neighbouring edges start to intersect. I would have to identify these and then collapse the superfluous edge to a new vertex at the intersection point. It also creates concave sections in the polygons, as seen below.

static void shrink_poly( int numcoord, jcv_point* coords )
{
const float bordersz = 0.008f;
float shiftx[ numcoord ];
float shifty[ numcoord ];

for ( int e=0; e<numcoord; e++ )
{
const int i=e;
const int j = (i+1)%numcoord;
jcv_point& v0 = coords[ i ];
jcv_point& v1 = coords[ j ];
float dx = v1.x - v0.x;
float dy = v1.y - v0.y;
float nx = -dy;
float ny =  dx;
float l = sqrtf( nx*nx + ny*ny );
nx = nx / l;
ny = ny / l;
shiftx[e] = bordersz*nx;
shifty[e] = bordersz*ny;
}

for ( int v=0; v<numcoord; v++ )
{
const int e0 = v;
const int e1 = (v+numcoord-1) % numcoord;
assert( e0 >= 0  && e0 < numcoord );
assert( e1 >= 0  && e1 < numcoord );
coords[ v ].x += shiftx[e0];
coords[ v ].y += shifty[e0];
coords[ v ].x += shiftx[e1];
coords[ v ].y += shifty[e1];
}
}


Is there a simple and effective way for shrinking convex polygons?

The easiest solution is to just deal with the lines separately. Define a winding order, let's say polygons go anti-clockwise. Loop through every vertex and subtract it from the next one. Normalize the resulting vector. This should result in unit length vectors pointing in an anti-clockwise direction around the polygon. Now rotate them anti clockwise 90 degrees (a vector can be rotated anti-clockwise by taking the (x, y) coordinates and replacing them with (-y, x)). Take the first point from the line segment you got the vector from and add the result vector to it. You can multiply the vector by a constant amount to get different shrinking amount (higher constants make it shrink faster). Then take this point and the vector and convert them to a line equation using the

n.x * x+n.y * y - n.x * P. x - n.y * P. y = 0


where n is the vector, P is the point and (x, y) is a variable for every point on the line.

Now you shrunk every line and converted them to a line equation. The next step is to take every 2 neighbouring equations and solving for the point where both of them equal 0. That gives you a vertex. Take every vertex and construct the polygon from it. This results in a constant, uniform shrinkage.

• I think this still needs a method to deal with cases where a line somewhere gets shrunk to zero or negative length, so the result has fewer vertices than you started with. – DMGregory Jun 5 '18 at 11:34

A solution to do this will be:

• enclose the polygon in a circle.
• for each vertex of the polygon, calculate normalized vector:

vi = ( vertex - center of circle ) / radius of circle

• if you change the radius of the circle to be radius', shrinking it, just recalculate vertices:

vi' = center + radius' * vi

• You can't perfectly enclose every polygon into a circle – Bálint Jun 5 '18 at 7:46
• You don't need to have a perfect enclosing. Whatever circle having all the vertices inside will do the work. The only concern is the center point in order to control the displacement of vertices. – Jordi Cruzado Jun 5 '18 at 8:14