Blog
Recursive Polygon Subdivision
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:
- Create the first polygon
- Pick two adjacent vertices at random
- Use linear interpolation to find a point between them (P1)
- You now have a point on one line segment connecting the two vertices
- Choose another line segment from the polygon
- Find a point along this line segment ( P2 )
- Build a new polygon by moving clockwise from P1 to P2
- Build a second polygon by moving clockwise from P2 back to P1
- Splice the original polygon from the list and insert the two new ones
- Choose a polygon from the list and ( ? repeat )
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.
- Choose line segments to cut at random
- Always subdivide between the two longest line segments
- Always interpolate ( choose points ) half way along segments
- Choose points at random positions along line segments
- Only mark some polygons eligible for subdivision
- Vary the minimum area of divisible polygons
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/
