Lab : Experimenting with a 2D Polygon Subdivision Algorithm
This is a little algorithm I sketched in my moleskin on the train and for once had the free time to build. The idea is to split a convex polygon between two line segments, creating two new polygons. Each shape is pushed into a queue ready to be subdivided itself. Despite the simplicity of the algorithm, the results are quite nice and with certain configurations often far removed from what I would have expected – surprise is always good.
The Subdivide Algorithm
Here are the basic steps used to create the sketch above:
Very simple, but you can start to have fun with each of these steps to produce different
results. Here are some of the variations which can be created with the demo.
Source Code
The Polygon class is a DisplayObject (it extends Sprite) and implements it’s own draw method. I’ve had a lot of fun filling the shapes with textures, but kept it minimal for the example. One technique which I found worked well was to choose two vertices and compute the angle between them. From this I created a transformation matrix to use with Graphics.beginBitmapFill, giving the sketch a more 3 dimensional feel as if the collection of polygons was a 3D mesh with textures mapped to it. I’ll put these examples on Flickr soon.
If you’re interested in the source code, it’s available in my code repository or you can download the archive below (for the demo GUI, I am using minimal comps courtesy of Keith Peters and for image encoding, Ian McLean’s asynchronous JPEG encoder – thanks guys :).
![]() |
Download | Recursive Polygon |
Special credit thanks to http://blog.soulwire.co.uk/