{"id":158,"date":"2011-02-02T10:55:08","date_gmt":"2011-02-02T10:55:08","guid":{"rendered":"http:\/\/xiveterritory.com\/blog\/?p=158"},"modified":"2011-07-26T19:28:10","modified_gmt":"2011-07-26T19:28:10","slug":"recursive-polygon-subdivision","status":"publish","type":"post","link":"https:\/\/khalifahterritory.com\/blog\/?p=158","title":{"rendered":"Recursive Polygon Subdivision"},"content":{"rendered":"\n<!-- Facebook Like Button v1.9.6 BEGIN [http:\/\/blog.bottomlessinc.com] -->\n<iframe src=\"http:\/\/www.facebook.com\/plugins\/like.php?href=https%3A%2F%2Fkhalifahterritory.com%2Fblog%2F%3Fp%3D158&amp;layout=standard&amp;show_faces=false&amp;width=450&amp;action=like&amp;colorscheme=light\" scrolling=\"no\" frameborder=\"0\" allowTransparency=\"true\" style=\"border:none; overflow:hidden; width:450px; height: 30px; align: left; margin: 2px 0px 2px 0px\"><\/iframe>\n<!-- Facebook Like Button END -->\n<p>Lab : Experimenting with a 2D Polygon Subdivision Algorithm<br \/>\n<a href=\"http:\/\/xiveterritory.com\/blog\/wp-content\/uploads\/2011\/02\/SD001_001.jpg\"><img decoding=\"async\" title=\"SD001_001\" src=\"http:\/\/xiveterritory.com\/blog\/wp-content\/uploads\/2011\/02\/SD001_001.jpg\" alt=\"\" width=\"710px\" height=\"360px\" \/><\/a><br \/>\nThis 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 \u2013 surprise is always good.<\/p>\n<p><strong>The Subdivide Algorithm<\/strong><\/p>\n<p>Here are the basic steps used to create the sketch above:<\/p>\n<div style=\"margin-left: 40px !important; display: block;\">\n<ul>\n<li>Create the first polygon<\/li>\n<li>Pick two adjacent vertices at random<\/li>\n<li>Use linear interpolation to find a point between them (P1)<\/li>\n<li>You now have a point on one line segment connecting the two vertices<\/li>\n<li>Choose another line segment from the polygon<\/li>\n<li>Find a point along this line segment ( P2 )<\/li>\n<li>Build a new polygon by moving clockwise from P1 to P2<\/li>\n<li>Build a second polygon by moving clockwise from P2 back to P1<\/li>\n<li>Splice the original polygon from the list and insert the two new ones<\/li>\n<li>Choose a polygon from the list and ( ? repeat )<\/li>\n<\/ul>\n<\/div>\n<p>Very simple, but you can start to have fun with each of these steps to produce different<br \/>\nresults. Here are some of the variations which can be created with the demo.<\/p>\n<div style=\"margin-left: 40px !important; display: block;\">\n<ul>\n<li>Choose line segments to cut at random<\/li>\n<li>Always subdivide between the two longest line segments<\/li>\n<li>Always interpolate ( choose points ) half way along segments<\/li>\n<li>Choose points at random positions along line segments<\/li>\n<li>Only mark some polygons eligible for subdivision<\/li>\n<li>Vary the minimum area of divisible polygons<\/li>\n<\/ul>\n<\/div>\n<p><strong>Source Code<\/strong><\/p>\n<p>The Polygon class is a DisplayObject (it extends Sprite) and implements it\u2019s own draw method. I\u2019ve 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\u2019ll put these examples on Flickr soon.<\/p>\n<p>If you\u2019re interested in the source code, it\u2019s 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\u2019s asynchronous JPEG encoder \u2013 thanks guys :).<\/p>\n<table>\n<tbody>\n<tr>\n<td><a href=\"http:\/\/xiveterritory.com\/blog\/archives\/Subdivision.zip\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-151\" title=\"icon-simple-download2\" src=\"http:\/\/xiveterritory.com\/blog\/wp-content\/uploads\/2011\/02\/icon-simple-download2.png\" border=\"0\" alt=\"\" width=\"40\" height=\"40\" \/><\/a><\/td>\n<td>Download | Recursive Polygon<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p><font style=\"font-size:10px;color:#9e9e9e;\">Special credit thanks to http:\/\/blog.soulwire.co.uk\/<\/font><\/p>\n\n<!-- Facebook Like Button v1.9.6 BEGIN [http:\/\/blog.bottomlessinc.com] -->\n<iframe src=\"http:\/\/www.facebook.com\/plugins\/like.php?href=https%3A%2F%2Fkhalifahterritory.com%2Fblog%2F%3Fp%3D158&amp;layout=standard&amp;show_faces=false&amp;width=450&amp;action=like&amp;colorscheme=light\" scrolling=\"no\" frameborder=\"0\" allowTransparency=\"true\" style=\"border:none; overflow:hidden; width:450px; height: 30px; align: left; margin: 2px 0px 2px 0px\"><\/iframe>\n<!-- Facebook Like Button END -->\n","protected":false},"excerpt":{"rendered":"<p>Lab : Experimenting with a 2D Polygon Subdivision Algorithm This is a little algorithm I sketched in my moleskin on&#8230;<\/p>\n","protected":false},"author":1,"featured_media":159,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[],"class_list":["post-158","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-experiment","end"],"_links":{"self":[{"href":"https:\/\/khalifahterritory.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/158","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/khalifahterritory.com\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/khalifahterritory.com\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/khalifahterritory.com\/blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/khalifahterritory.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=158"}],"version-history":[{"count":28,"href":"https:\/\/khalifahterritory.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/158\/revisions"}],"predecessor-version":[{"id":223,"href":"https:\/\/khalifahterritory.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/158\/revisions\/223"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/khalifahterritory.com\/blog\/index.php?rest_route=\/wp\/v2\/media\/159"}],"wp:attachment":[{"href":"https:\/\/khalifahterritory.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=158"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/khalifahterritory.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=158"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/khalifahterritory.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=158"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}