9

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!

Craig
  • 564
  • 1
  • 5
  • 20
  • maybe construct an artificial bounding rectangle (or other region) to help you with the centering and translation. – Randy Jul 26 '11 at 13:13
  • Hmm, I've tried using the center of a bounding box as a frame of reference, but that left my result translated also. Also tried scaling the bounding box by the desired factor and using the edges as frames of reference, but still did not end up with a pure untranslated solution. Did you have something specific in mind that I should try with a bounding box? Thanks for the response! – Craig Jul 26 '11 at 13:30
  • What I mean by center is the "visual center" of the polygon. The best way I can think of describing it would be "zooming" in on a polygon, so you would want the visual center of the polygon to remain constant throughout the zoom. – Craig Jul 26 '11 at 13:57
  • Draw a concave polygon and label what you mean by the "visual center." Visual center is not a technical term and there's no way for us to know what you mean by it without giving either a precise definition or at least some examples so we can infer one. – tskuzzy Jul 26 '11 at 14:13
  • I would, but I don't have enough points to post images.. The obvious polygon that shows the problem is an L-shaped polygon. As the polygon is scaled the polygon area is also translated further and further from the centroid. Not sure how to define visual center other than maybe these images that it doesn't want me to post: [Original Polygon](http://imgur.com/0iUQ9) and [Polygon Scaled by 4X](http://imgur.com/SSFDL) – Craig Jul 26 '11 at 14:34
  • Sounds like you're a bit confused about your notion of centre. What's your *precise application* for this? What's wrong with centre of mass? I don't see why it's a problem if the "centre" is not inside the polygon in the case of concave polygons. Make a drawing please where you show: "*this* is the centre of mass, but I need *this* other point to be invariant under the transformation" – Szabolcs Jul 26 '11 at 14:34
  • @Craig OK, I see. Where would you say is the "visual centre" of this then? http://i.imgur.com/gE2MR.png *Why* do you need the point to be inside the polygon? – Szabolcs Jul 26 '11 at 14:41
  • You are right, the "visual center" would not be inside that polygon. I'm feeling dumb.. I think I may be confusing my expected behavior of a polygon scale with the behavior that can be observed by performing a polygon offset along the vertex normals. I will have to get clarification on the requirements.. What an embarrassing first question :-*.. the behavior just seems awkward in the L-shaped case, guess I should have thought about it some more, thanks for setting me straight. – Craig Jul 26 '11 at 15:15
  • 1
    Possible duplicate of [An algorithm for inflating/deflating (offsetting, buffering) polygons](http://stackoverflow.com/questions/1109536/an-algorithm-for-inflating-deflating-offsetting-buffering-polygons) – user276648 Jul 21 '16 at 03:43

3 Answers3

6

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

Ricky Bobby
  • 7,490
  • 7
  • 46
  • 63
4

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.

Community
  • 1
  • 1
Angus Johnson
  • 4,565
  • 2
  • 26
  • 28
  • 1
    Small internet ha, I'm currently using Clipper for this project and even posted on the sourceforge forums for the project a couple times :-). I think I was just expecting an offset-like behavior (where the polygon grows/shrinks "in place") from a scale like operation (using a factor rather than a unit offset)... Thanks again for the Clipper library, it has proven extremely useful! – Craig Jul 26 '11 at 18:35
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.

tskuzzy
  • 35,812
  • 14
  • 73
  • 140
  • My idea of in place is the "visual center" remains constant between the original polygon and the scaled polygon. I'm not sure how to go about finding the visual center for concave polygons or if going down the road of trying to find/define a "visual center" is the right way to go. – Craig Jul 26 '11 at 13:53
  • Can you post some images of a case where using the centroid doesn't work well? – tskuzzy Jul 26 '11 at 13:58