Android, Bitmaps, and Convex Hull


In a game I’m currently working on (Lollipop Land) I set out to add more characters to the game. The object of the game is to jump/fly your way through lollipops without hitting one or face planting onto the ground.

The next major release will have at least 11 new characters. Each character is a set of PNG files that make up an AnimatedDrawable. The new characters are different shapes and sizes, thus adding complexity to when the character actually intersects with an obstacle in the game. Each PNG also has significant transparency. After some research, I came across the convex hull algorithm. Ultimately, my goal was to eliminate any transparency in the image for the best precision when passing through obstacles in the game. The convex hull algorithm is exactly what I was looking for.

What is convex hull?

If you had an image or object and put a rubber band around that object, the convex hull would be the set of points at which the rubber band touched the object. Here is a more thorough definition:

In mathematics, the convex hull or convex envelope of a set X of points in the Euclidean plane or Euclidean space is the smallest convex set that contains X. For instance, when X is a bounded subset of the plane, the convex hull may be visualized as the shape formed by a rubber band stretched around X. 1

Formally, the convex hull may be defined as the intersection of all convex sets containing X or as the set of all convex combinations of points in X. With the latter definition, convex hulls may be extended from Euclidean spaces to arbitrary real vector spaces; they may also be generalized further, to oriented matroids.2

Finding x and y boundaries for a bitmap:

First off, you need to load your bitmap or drawable into memory. Once we have a reference to the bitmap we can parse the bitmap pixel by pixel. 3

The code above will give us a path around our bitmap, but the set of points will be much larger than desired. To increase performance we can use the Quickhull algorithm. Here is my modified Quickhull class for Android:

Now with this helper class we can get the convex hull of a Bitmap on Android with a single line of code.

Let’s test out the Google logo to see the “rubber band” in action.

Original image:


google-logo-png

Drawn with points from quick hull:

google_logo_1


1 Andrew, A. M. (1979), Another efficient algorithm for convex hulls in two dimensions, Information Processing Letters 9 (5): 216–219, 10.1016/0020-0190(79)90072-3

2 Brown, K. Q. (1979), Voronoi diagrams from convex hulls, Information Processing Letters 9 (5): 223–228, 10.1016/0020-0190(79)90074-7

3 Kaplan, Josh. “Brown CS: Android Attack!” : Image Transparency (aka an Absurd Application of Convex Hull). N.p., 22 Mar. 2010. Web.

  • Maulik Patel

    is there any project where this code is implemented..? when i am running this algorithm .. get wrong point and also not any line draw on object..

  • Satish Varadha

    I need matlab code for the same. i am doing in matlab please send me the code in matlab