0

I was going through computational geometry problems and encountered the following problem, and couldn't come up with an answer.

What I want is: Given a fixed width W, I need to rotate a simple 2D polygon with n points such that it width won't exceed W, and to get a minimum height polygon.

A picture for illustration: enter image description here

I can start rotating the polygon and check for its height and width each time, but obviously this will be very expensive and inaccurate..

I found this answer, but it's for convex polygons and without the width limitations and couldn't figure how(if possible) to do the necessary adjustments

Any suggestions?

sagi
  • 40,026
  • 6
  • 59
  • 84
  • If you have to deal with non convex polygons, the first step I would take is to remove the vertexes which lead to a non convex shape. In other words I would convert the non convex polygon into a convex one. – Elec1 Dec 29 '22 at 09:42
  • Right, as said by Elec1, the problem has the same solution with the given polygon and with its convex hull (obtained by Melkman's algorithm in linear time). The answer can be found by rotating calipers (also linear time), finding all sides such that the hull fits in the specified width when rotated to be vertical; then you can add a rotation to make the width exactly as specified, and compute the corresponding height. –  Dec 29 '22 at 09:47
  • see [2D OBB approximation](https://stackoverflow.com/a/42997918/2521214) You just change the search condition to fit the larger axis to your width instead of minimal area – Spektre Jan 03 '23 at 09:22

1 Answers1

2

When a convex polygon is rotated, the plot of its width and of its height* as functions of the angle are piecewise sinusoidal functions. You can establish this by considering antipodal pairs (https://en.wikipedia.org/wiki/Rotating_calipers). By simple geometric considerations, you can find the amplitude and phase of the sinusoids, and the angles where they intersect.

Now if you construct the width function, you can find the angles at which it is exactly the specified W (by solving A.sin(Θ-Φ) = W in the relevant intervals), and from the angle obtain the corresponding value of the height.

If your polygon is concave, you can obtain its convex hull in linear time (in the size of the polygon) by the Melkman's algorithm (https://en.wikipedia.org/wiki/Convex_hull_of_a_simple_polygon). Then rotating calipers and the resolution of the sinusoid equations also take linear time (in the size of the hull).

*The plot of the height is that of the width with a 90° shift.