Scaling an arbitrary polygon

Question

I've been scouring the internet for days, but have been unable to find a good answer (or at least one that made sense to me) to what seems like it should be a common question. How does one scale an arbitrary polygon? In particular, concave polygons. I need an algorithm which can handle concave (definitely) and self-intersecting (if possible) polygons. The obvious and simple algorithm I've been using to handle simple convex polygons is calculating the centroid of the polygon, translating that centroid to the origin, scaling all the vertices, and translating the polygon back to its original location.

This approach does not work for many (or maybe all) concave polygons as the centroid often falls outside the polygon, so the scaling operation also results in a translation and I need to be able to scale the polygon "in place" without the final result being translated.

Is anybody aware of a method for scaling concave polygons? Or maybe a way of finding the "visual center" which can be used as a frame of reference for the scaling operation?

Just to clarify, I'm working in 2D space and I would like to scale my polygons using the "visual center" as the frame of reference. So maybe another way to ask the question would be, how do I find the visual center of a concave and/or self-intersecting polygon?

Thanks!

Answer 1

The reason why you can't find a good answer is because you are being imprecise with your requirements. First explicitly define what you mean by "in-place". What is being kept constant?

Once you have figured that out, then translate the constant point to the origin, scale the polygon as usual, and translate back.

Answer 2

I'm not sure what your problem is.

You're working in an affine space, and you're looking for an affine transformation to scale your polygon ?

If i'm right, just write the transformation matrix:

• scaling matrix
• homotethy

And transform your polygon with matrix

You can look up for affine transformation matrix.

hope it helps

---

EDIT

if you want to keep the same "center", you can just do an homotethy of parameter lambda with center G = barycenter of the polygon:

it verifies :

G won't move since it's the center of the homotethy.

It will still verify the relation below, so it will still be the barycenter. (you just multiply the relation by lambda)

in your case G is easy to determinate: G(x,y) : (average of x values of points, average of y values of points)

and it should do what you need

Answer 3

Perhaps Craig is looking for a "polygon offset" algorithm - where each edge in the polygon is offset by a given value. For example, given a clockwise oriented polygon, offsetting edges towards the left will increase the size of the polygon. If this is what Craig is looking for then this has been asked and answered before here - An algorithm for inflating/deflating (offsetting, buffering) polygons.

If you're looking for a ready made (opensource freeware) solution, I've also created a clipping library (Clipper) written in Delphi, C++ and C# which includes a rather simple polygon offsetting function.