3
\$\begingroup\$

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.

first approach: moving vertices to centre.

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.

second attempt: moving edges.

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?

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – DMGregory Jun 5 '18 at 11:34
-1
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ You can't perfectly enclose every polygon into a circle \$\endgroup\$ – Bálint Jun 5 '18 at 7:46
  • \$\begingroup\$ 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. \$\endgroup\$ – Jordi Cruzado Jun 5 '18 at 8:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.