{"id":888,"date":"2009-10-07T21:40:56","date_gmt":"2009-10-07T10:40:56","guid":{"rendered":"http:\/\/www.vectorstorm.org\/?p=888"},"modified":"2009-10-07T22:40:18","modified_gmt":"2009-10-07T11:40:18","slug":"voronoi","status":"publish","type":"post","link":"https:\/\/www.vectorstorm.com.au\/2009\/10\/07\/voronoi\/","title":{"rendered":"Voronoi"},"content":{"rendered":"

\"Voronoi\"<\/a>As promised, here’s that same image from the previous post (or very similar to it; fixed one or two minor bugs), converted into a Voronoi diagram<\/a>.<\/p>\n

Immediately, you can see that these sorts of shapes would work quite well for MMORPG regions; \u00a0they’re irregular and somewhat chaotic, but still somehow look as though they’ve been carefully arranged. \u00a0I love that these don’t look at all ‘boxy’, like the old region borders did; \u00a0some of these regions have eight or more sides!<\/p>\n

[warning: \u00a0tech follows]<\/p>\n

A Voronoi diagram is constructed by seeding the map with a certain number of “sites” (about 80 of them, in this image), and then figuring out for each point on the map, which “site” that point of the map is closest to. \u00a0The shapes you see here are the regions which are closest to each randomly placed “site”. \u00a0The sites in the Voronoi diagram aren’t being drawn here, but each of the points of the triangles in the Delaunay triangulation image from yesterday is a “Site” in today’s image. \u00a0For example, one “Site” is near my cursor in this screenshot, and anything inside the border around it is closer that that one Site than to any other Site.<\/p>\n

As it happens, the “Sites” in the Voronoi diagram are the same as the vertices in the Delaunay triangulation. \u00a0Remember how yesterday I mentioned that rule about “in a correct Delaunay triangulation, if you drew a circle which touched all three corners of any triangle, there would be no other Delaunay triangle vertices inside that circle”? \u00a0Well, it just so happens that if you made those circles for every triangle which used a particular vertex, and then found the center point of each of those circles, and then drew lines connecting those circle center points, you’d end up with a shape like one of the ones in today’s screenshot. \u00a0Follow these instructions for every vertex in the Delaunay triangulation, and you’d have your Voronoi diagram, just like the one here. \u00a0It’s math magic that doing this operation with circle centerpoints in the Delaunay triangulation happens to also define the regions which are nearer to one site than to any other site.<\/p>\n

And I’ve explained it horribly; \u00a0apologies! \u00a0It makes my head spin, too, when I think about these algorithms, which is one of the reasons why it’s taken me so long to complete.<\/p>\n

[end tech]<\/p>\n

Anyhow. \u00a0I haven’t connected these boundaries to the real game regions, yet; \u00a0right now, this is just drawing an outline at about the right scale. \u00a0Actually hooking it up will be a task for tomorrow. \u00a0But compared to the maths that were required to generate the outline, that task should be trivial.<\/p>\n","protected":false},"excerpt":{"rendered":"

As promised, here’s that same image from the previous post (or very similar to it; fixed one or two minor bugs), converted into a Voronoi diagram. Immediately, you can see that these sorts of shapes would work quite well for MMORPG regions; \u00a0they’re irregular and somewhat chaotic, but still somehow look as though they’ve been…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"spay_email":""},"categories":[3],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/so9WK-voronoi","_links":{"self":[{"href":"https:\/\/www.vectorstorm.com.au\/wp-json\/wp\/v2\/posts\/888"}],"collection":[{"href":"https:\/\/www.vectorstorm.com.au\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.vectorstorm.com.au\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.vectorstorm.com.au\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.vectorstorm.com.au\/wp-json\/wp\/v2\/comments?post=888"}],"version-history":[{"count":0,"href":"https:\/\/www.vectorstorm.com.au\/wp-json\/wp\/v2\/posts\/888\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.vectorstorm.com.au\/wp-json\/wp\/v2\/media?parent=888"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.vectorstorm.com.au\/wp-json\/wp\/v2\/categories?post=888"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.vectorstorm.com.au\/wp-json\/wp\/v2\/tags?post=888"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}