Scaling an arbitrary polygon

algorithm polygon concave
Craig picture Craig · Jul 26, 2011 · Viewed 13.7k times · Source

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

Ricky Bobby picture Ricky Bobby · Jul 26, 2011

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:

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 :
enter image description here

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

Related questions

An algorithm for inflating/deflating (offsetting, buffering) polygons

How would I "inflate" a polygon? That is, I want to do something similar to this: The requirement is that the new (inflated) polygon's edges/points are all at the same constant distance from the old (original) polygon's (on the …

Read More
How do I efficiently determine if a polygon is convex, non-convex or complex?

From the man page for XFillPolygon: If shape is Complex, the path may self-intersect. Note that contiguous coincident points in the path are not treated as self-intersection. If shape is Convex, for every pair of points inside the polygon, the …

Read More
How to check if a point (x,y) is inside a polygon in the Cartesian coordinate system?

This question already has an answer here: Point in Polygon aka hit test C# Point in polygon Given a random polygon formulated with N line equations in the Cartesian coordinate system, is there any standard formula that is used to …

Read More