Finding a stable placement of an irregular (non-convex) shape

Question

Given an image of a 2-dimensional irregular (non-convex) shape, how would I able to compute all the ways in which it could lie stable on a flat surface? For example, if the shape is a perfect square rectangle, then it will surely have 4 ways in which it is stable. A circle on the other hand either has no stable orientation or every point is a stable orientation.

EDIT: There's this nice little game called Splitter (Beware, addictive game ahead) that seems close to what I want. Noticed that you cut a piece of the wood out it would fall to the ground and lay in a stable manner.

EDIT: In the end, the approach I took is to compute center of mass (of the shape) and compute the convex hull (using OpenCV), and then loop through every pair of vertices. If the center of mass falls on top of the line formed by the 2 vertices, it is deemed stable, else, no.

Answer 1

I'm sure this is not the most efficient algorithm, but it's an idea.

If you can order the verticles of the polygon (assuming it has a finite number of vertices), then just iterate over adjacent pairs of vertices and record the angle it rests at through some form of simulation. There will be duplicate orientations for it to sit on in the case of weird shapes, like stars, but you can accomodate for that by keeping track of the resting rotation.

Answer 2

note: this answer assumes your shape is a proper polygon.

For our purposes, we'll define an equilibrium position as one where the Center of Mass is directly above a point that is between the leftmost and rightmost ground-contact points of the object (assuming the ground is a flat surface perpendicular to the force of gravity). This will work in all cases, for all shapes.

Note that, this is actually the physical definition of rotational equilibrium, as a consequence of Newtonian Rotational Kinematics.

For a proper polygon, if we eliminate cases where they stand on a sole vertex, this definition is equivalent to a stable position.

So, if you have a straight downward gravity, first find the left-most and right-most parts of it that are touching the ground.

Then, calculate your Center of Mass. For a polygon with known vertices and uniform density, this problem is reduced to finding the Centroid (relevant section).

Afterwards, drop a line from your CoM; if the intersection of the CoM and the ground is between those two x values, it's at equilibrium.

If your leftmost point and rightmost point match (ie, in a round object), this will still hold; just remember to be careful with your floating point comparisms.

Note that this can also be used to measure "how stable" an object is -- this measure is the maximum y-distance the Center of Mass can move before it is no longer within the range of the two contact points.

EDIT: nifty diagram made hastily

So, how can you use this to find all the ways it can sit on a table? See:

---

EDIT

The programmable approach

Instead of the computationally expensive task of rotating the shape, try this instead.

Your shape's representation in your program should probably have a list of all vertices.

Find the vertices of your shape's convex hull (basically, your shape, but with all concave vertices -- vertices that are "pushed in" -- eliminated).

Then Iterate through each of pair of adjacent vertices on your convex hull (ie, if I had vertices A, B, C, D, I'd iterate through AB, BC, CD, DA)

Do this test:

1. Draw a line A through the two vertices being tested
2. Draw a line perpendicular to A, going through CoM C.
3. Find the intersection of the two lines (simple algebra)
4. If the intersection's y value is in between the y value of the two vertices, it stable. If the y values are all equal, compare the x values.

That should do the trick.

Here is an example of the test being running on one pair of vertices:

If your shape is not represented by its vertices in your data structure, then you should try to convert them. If it's something like a circle or an ellipse, you may use heuristics to guess the answer (a circle has infinite equilibrium positions; an ellipse 4, albeit only two "stable" points). If it's a curved wobbly irregular shape, you're going to have to supply your data structure for me be able to help in a program-related way, instead of just providing case-by-case heuristics.