Scaling un poligono arbitrario

Question

Sono stato purga internet per giorni, ma sono stato in grado di trovare una buona risposta (o almeno uno che ha senso per me) a quello che sembra come dovrebbe essere un problema comune. Come si fa a scalare un poligono arbitrario? In particolare, concava poligoni. Ho bisogno di un algoritmo in grado di gestire i poligoni concavi (sicuramente) e auto-intersecano (se possibile). L'algoritmo ovvio e semplice ho usato per gestire semplici poligono convesso è il calcolo del centroide del poligono, traducendo che centroide all'origine, scalando tutti i vertici, e traducendo il retro poligono alla sua posizione originale.

Questo approccio non funziona per molti (o forse tutti) i poligoni concavi come baricentro spesso cade all'esterno del poligono, quindi l'operazione di scalatura si traduce anche in una traduzione e devono essere in grado di scalare poligono "in loco" colpo il risultato finale viene tradotto.

C'è qualcuno a conoscenza di un metodo per il ridimensionamento poligoni concavi? O forse un modo di trovare il "centro visivo" che può essere utilizzato come quadro di riferimento per l'operazione di ridimensionamento?

Giusto per chiarire, sto lavorando in 2D spazio e vorrei scalare le mie poligoni utilizzando il "centro visivo" come il quadro di riferimento. Quindi forse un altro modo di porre la domanda sarebbe, come faccio a trovare il centro visivo di un concavo e / o un poligono autointersecante?

Grazie!

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.