Find the rotation where the shape has the smallest x-axis width

Question

I love the figure problem, and I'm looking for a smarter solution than what I could come up with.

Here is the problem:

I have many points that form a closed shape on a Cartesian grid, for example A (-1,0), B (1,0) and C (0,4), which forms a sharp triangle.

I reformulated this in a slightly less confusing way. Take the form above and imagine that you can freely rotate it. I am looking to detect a turn, where we take into account only the x axis, and the distance between the westernmost and easternmost points is the smallest.

If we take into account the shape above this distance, it will be the distance between A and B. Although for more interesting figures there may be shorter distances between the points, I believe that it is not possible to rotate the shape higher so that the western and eastern most points are smaller than the distance between A and B.

My only solution so far has been to draw points, rotate 1 degree, keep the maximum distance gained by rotation. Rinse the repeat and take the smallest. It seems a little silly, and I know that there should be a more mathematically correct way to approach this.

Any ideas?

Answer 1

Analyze the main components and compare the main component with the y axis. This optimizes the "average" square distance from each point to the y axis (i.e., the Width along the x axis). Perhaps this is also optimal or close to optimal according to your criteria.

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

Alternative solution (optimal solution):

First, we compute the convex hull of points. Note that two points with a maximum width x always go in a convex hull.

Now, for each segment in the convex hull, find the most distant vertex and record the distance. Find a pair (line segment, far peak) with a minimum distance. Optimal rotation is one that aligns this line segment in the vertical direction.

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

Answer 2

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

Answer 3

Rotary calipers are a good tool to solve this problem.

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

Answer 4

I'm not too sure about your understanding of mathematics, so please accept my apologies if this goes over your head, or if it is really too easy to explain, but the solution that instantly stood out for me is to use Fourier analysis on a discrete sample of the polygon width at fixed angles.

Your approach to rotation by a small amount and the test can be considered as a discrete sample of a continuous function.

We know that there is a continuous function that determines the measure you are measuring for each possible rotation, you simply evaluate it at given points. that is, as you know, there is an angle with a function of the width of the polygon, and we can estimate the width of the polygon for a finite set of angles given enough time.

So, assuming that we can find an expression in terms of elementary functions for this angle-to-width function, we could potentially precisely determine all the angles that give the smallest possible width by solving the equation.

We know that since you rotate through 2PI radians, the width function will be 2PI periodic, and so you could completely restore the function, given that sufficient angles were selected using Fourier analysis.

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

I think this is determined by the smallest distance between the boundary points.

 ceil(perimiterLength/smallestDistanceBetweenPoints); 

In short, I will overcriminate the perimeter of the boundary by placing evenly spaced samples along the perimeter, using an interval equal to or less than the smallest distance. Let me call this number n. (Honestly, I'm not sure if this is correct)

An example of east and west points at n points with evenly spaced angles through 2PI radians and the superposition of their difference in the form of an n-point angle on the width function.

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

Use any of your favorite methods to determine the minimum function value.

So, I suppose that for an example of a triangle you determine that you need a ceiling (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 by creating a formula like

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

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