Shrink a convex polygon

Question

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?

Answer 1

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.

Answer 2

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