2

I'm looking for an algorithm to calculate the translation, rotation and scaling required to position a convex polygon (P1) inside another convex polygon (P2). I need it to return the "best fit", meaning P1 is completely contained within P2 and has the maximum area possible.

Consider the following diagram: https://i.stack.imgur.com/PfnSG.png

The black polygon on the right (P1) needs to be placed optimally inside the blue polygon on the left (P2).

I have found lots of written papers online about polygon containment algorithms but those algorithms are to determine whether or not polygons can fit inside another polygon given the ability to translate and rotate them.

The algorithm that I'm looking for should always produce a result because it includes the ability to scale the polygon P1. I understand that this type of algorithm could produce multiple optimal answers and that's okay.

Any help?

Bradley Odell
  • 1,248
  • 2
  • 15
  • 28

1 Answers1

4

OK, if nobody has better idea, I would like to give a not-so-good algorithm.

Let's say you have P1 with p vertices and P2 with q vertices, and you want to fit P1 inside P2.

You already found articles describing how to determine whether P1 can fit inside P2. For example this article gives an algorithm in O(pq^2) time. I'm not sure if it can be still faster if you know both P1 and p2 are convex.

So, start with a large number a such that a(P1) cannot fit inside (P2), and do a binary search on the value of a.

This is not very clever, but at least it gives the answer. If anyone else posts a better answer, please ignore mine...

WhatsUp
  • 1,618
  • 11
  • 21
  • Seems like this yields an optimal solution with only an additional logarithmic factor. I don't see what's not so good about it – Niklas B. Jul 21 '15 at 21:50
  • I myself don't like it so much, because the problem is essentially discrete, and theoretically the "true" answer can be calculated exactly. So for example if all vertices of the polygons have rational coordinates, then the answer should also be a rational number, while my algorithm can only approximate it with real numbers. – WhatsUp Jul 21 '15 at 21:55
  • This is relevant: http://stackoverflow.com/questions/5440688/the-guess-the-number-game-for-arbitrary-rational-numbers. Also note that best fit may require irrational scaling (e.g., unit "diamond" into unit square), so in general an approximation is the best an algorithm can do. – Edward Doolittle Jul 21 '15 at 23:07
  • Ja, my statement about rationality is not quite correct. It should be some algebraic function of the coordinates. – WhatsUp Jul 22 '15 at 01:49