Find a rotation where the shape has the least width possible on the x-axis

Question

I am toying around with a shape problem and I am looking for a more clever solution than what I have been able to come up with.

Here is the problem:

I have a set of points that form an enclosed shape on a Cartesian grid, say A(-1,0),B(1,0), and C(0,4) which forms an acute triangle.

I have reworded this in a slightly less confusing way. Take the shape above and imagine that you can freely rotate it. I am looking to discover the rotation where we only take into account the x-axis and the distance between the western most and eastern most point is at its smallest.

When taking into account the shape above that distance would be the distance between A and B. While for more interesting shapes there may be shorter distances between points, I believe there is no way to rotate the shape above such that the western and eastern most points is less that the distance between A and B.

My only solution thus far has been to plot the points, rotate 1 degree, store the maximum distance keyed by the rotation. Rinse repeat and take the smallest one. This seems a bit kludgy and I know there has to be a more mathematically sound way to approach this.

Any ideas?

Answer 1

Rotating Calipers is the good instrument to solve this problem.

More specifically, it is necessary to construct convex hull, then to find the width of a convex polygon.

Answer 2

Let {N} be the set of points defining the smallest convex polygon that contains your shape, sorted in order clockwise. For every edge (N - 1, N): determine the distance from this edge to the farthest-away point. Take the shortest of these distances and rotate your shape such that the corresponding edge is perpendicular to the X axis.

Answer 3

I'm not overly certain of your grasp of mathematics, so please accept my apologies if this goes over your head, or if it is indeed too simply explained, but the solution that instantly stood out to me is to use Fourier analysis on a discrete sampling of the width of the polygon at fixed angles.

Your approach to rotate by a small amount and test could be considered a discrete sampling of a continuous function.

We know that there is a continuous function that defines the measure you are after for each possible rotation, you are just evaluating it at set points. i.e. an angle to polygon width function is known to exist, and we can evaluate the width of the polygon for a finite set of angles given enough time.

So, supposing we could find an expression in terms of elementary functions for this angle-to-width function, we could potentially determine exactly all of the angles which yield the minimum possible width by solving an equation.

We know that because you are rotating through 2PI radians, the width function will be 2PI periodic, and so you could perfectly reconstruct the function, given that enough angles were sampled, by applying Fourier analysis.

The question is, how many samples do you need to produce a perfect reconstruction of the function?

I think it's determined by the smallest distance between the boundary points.

ceil(perimiterLength/smallestDistanceBetweenPoints);

In short, I am resampling the perimiter of the boundary by placing evenly spaced samples along the perimiter, using a spacing that is equal to or smaller than the smallest distance. Let's call this number n. (To be honest I am not overly certain if this is correct)

Sample easterly and westerly points at n points at evenly spaced angles through 2PI radians, and plot their difference as an n-point angle to width function.

Take the Fourier transform of this graph to give you the sets of real Fourier series coefficients needed to define the distance function

Use any of your favourite methods for identifying the the minimum value of a function.

So I suppose for you triangle example you determine that you need ceil(3 + root(3)) = 5 samples. Calculate the distance at 0 2pi/5 4pi/5 6pi/6 and 8pi/5, take the Fourier transform of this result and reconstruct the signal, creating a formula like

a0 + a1 sin (t) + a2 sin (2t)

And then you have to determine the minimum of this function (for which there are many options)

Answer 4

Do the principal component analysis and align the principle component to the y axis. This will optimize the "mean" square distance from every point to the y axis (i.e. width on x axis). Perhaps this is also optimal or close to the optimal by your criteria.

See: http://en.wikipedia.org/wiki/Principal_component_analysis

Alternative Solution (Optimal solution):

First calculate the convex hull of the points. Note that the two points with maximum x width are always going to in the convex hull.

Now, for every line segment in the convex hull find the vertex that is farthest and note down the distance. Find the (line segment, farthest vertex) pair with minimum distance. Optimal rotation is the one that aligns that line segment in vertical direction.

Complexity: O(nlogn) for the convex hull part and O(m^2) for the second part where m is the number of points on the convex hull.