Board index » delphi » Polygon fit

Polygon fit

Does anybody know of an algorithm or pointers for fitting (using translate
and uniform scale transformations only) a convex polygon into another? By
fitting I mean scaling the inner one as large as possible. I wouldn't mind
info about the nonconvex case but I fear it would be too tricky. Thanks.
 

Re:Polygon fit


Do you mean the average best affine transformation ??

Bye Alex

Josh P. schrieb:

Quote
> Does anybody know of an algorithm or pointers for fitting (using translate
> and uniform scale transformations only) a convex polygon into another? By
> fitting I mean scaling the inner one as large as possible. I wouldn't mind
> info about the nonconvex case but I fear it would be too tricky. Thanks.

Re:Polygon fit


This isn't so easy as it seems.

It requires an optimisation tool. I would do it like this:

1) Make sure you have generic code that can do polygon substraction:

polygon A - polygon B = polygon(s) C.

There's a package available that can do this (look for the link to the
pascal code from Stefan Schedel (a license is required for commercial apps):
http://www.cs.man.ac.uk/aig/staff/alan/software/

2) Make sure you have code that can calculate the area (e.g. Gauss
divergence)
Also present in the same package

Now write an optimisation tool that does this
maximize F, based on design variables X, with equality constraint G.

F is the area of inner polygon B, after transforming using X
X[1] = Delta-X shift of polygon B within A
X[2] = Delta-Y shift of polygon B within A
X[3] = Scale of polygon B

G must be equal to 0, where G is the area of polygon C

Polygon A is a square (big enough to fit the outer polygon) from which you
substract the outer polygon, to create a kind of "inverse".

For these optimisation problems there are some pascal solutions, but not
that many. A possible site to check is:
http://www-rab.larc.nasa.gov/nmp/fNMPcode.htm

I have such an optimization component for sale as well (but very expensive
to be honest).

You can use multiple random startpoints (for instance 100) and then let the
optimisation run. If you have a good percentage of equal maxima, you can bet
that this is your solution.

The optimizer will make sure that you get an as big as possible inner
polygon, that just fits into the outer one. This method works just fine for
concave and convex polygons.

An analytical method would be more elegant, but hard to find.

Kind regards,

Nils Haeck
www.simdesign.nl

Quote
"Josh P." wrote in message news:3e4d538b$1@newsgroups.borland.com...
> Does anybody know of an algorithm or pointers for fitting (using translate
> and uniform scale transformations only) a convex polygon into another? By
> fitting I mean scaling the inner one as large as possible. I wouldn't mind
> info about the nonconvex case but I fear it would be too tricky. Thanks.

Re:Polygon fit


"Nils Haeck" <n.haeck_nos...@chello.nl> wrote

Thanks for all the info! It sure will come in handy. But for the current
problem, I believe I came up with a pretty straightforward analytical
solution O(N1*N2) when the outer polygon is convex (no restrictions on inner
one), which is good enough for me.

Other Threads