Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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.

like image 356
Hao Wooi Lim Avatar asked Jun 19 '10 03:06

Hao Wooi Lim


1 Answers

First find its center of mass (CM). A stable position is one in which the CM will be higher if you make a slight rotation. Now look at the hull, the smallest convex region that encloses the shape:

Convex Hull and Centre of Mass
(source: walkytalky.net)

If the hull is a polygon, then a stable position is one in which the shape is resting on one of the sides, and the CM is directly over that side (not necessarily over the midpoint of the side, just somewhere over it.

If the hull has curves (that is, if the shape has curves which touch the hull), they must be give special treatment. The shape will be stable when resting on a curved edge iff the CM is directly above the lowest point of the curve, and the radius of the curve at that point is greater than the height of the CM.

Examples:

  1. A rectangle. The hull is simply the rectangle, and the CM is at the center. The shape is stable on each of the four sides.
  2. A rectangle with the sides hollowed, but the corners still intact. The hull is still the original rectangle, and the CM is close to where it used to be. All four sides of the hull are still stable (that is, you can still rest the shape on any two corners).
  3. A circle. The CM is in the center, the hull is the circle. There are no stable positions, since the radius of the curve is always equal to the height of the CM. Give it a slight touch, and it will roll.
  4. An ellipse. The CM is at the center, the hull is the shape. Now there are two stable positions.
  5. A semicircle. The CM is somewhere on the axis of symmetry, the hull is the shape. Two stable positions.
  6. A narrow semicircular crescent. The hull is a semicircle, the CM is outside the shape (but inside the hull). Two stable positions.

Illustration of the examples
(source: walkytalky.net)

(The ellipse position marked with an X is unstable, because the curvature is smaller than the distance to the centre of mass.)

like image 137
Beta Avatar answered Oct 07 '22 01:10

Beta