![]() There's another interesting algorithm named after Steven Fortune, who published it in a paper in 1986. 3D Graphics cards use a Z-buffer (a value for each pixel of the display) to determine which is the 'nearest' pixel to the viewer to perform hidden surface removal (thus it only renders the pixel for the object nearest). This gives hints to how Voronoi diagrams can be generated using a 3D graphics technique using cones plotted into a depth buffer. These circles continue to grow until they hit the edges of other cones. ![]() ![]() As they pass through, they generate circles. Imagine a cone with apex at each node, and then these cones slowly being pushed through a plane. Here's a couple of animations of this:Īn analogous way to think about these growing circles is to imagine them as cones in 3D extruding out of the plane. (Or you could think about them as crystals growing from nucleation sites). This brute force approach is not very efficient, and the code ends up calculating distances for nodes that are clearly not in the running.Īnother possible strategy is a kind of flood fill: We can generate circles of ever-increasing radii from each node until they touch. Whichever of these distances is the shortest, colour the pixel with that colour. The easiest to understand is a simple brute force approach: For each pixel we care about, simply calculate the distance from each of the nodes. There are many ways to generate Voronoi diagrams. It’s mesmerizing to watch how the regions morph as their nodes pass by each other and the regions representing the nearest points change in geometery. Here’s a couple of animated versions where some of the points are moving. The regions tessellate perfectly, and are easy to decode. Rather than simply showing just the boundaries, we can shade each region with a colour representing all the pixels that are closest to each node. (To celebrate the centenary of Voronoi, Ukraine released a two-hryvnia coin for him). They are named after Georgy Feodosevich Voronoi, a Ukrainian mathematician, who died in 1908. These are Voroni diagrams (sometimes called Voronoi Tesesellations, Dirichlet Tessellations, or Thiessen polygons). Each of the boundaries' partitions off the space for which well is nearer. ![]() What happens if I add a third well? Or a fourth? We now get regions like these. Additionally, if I drew two circles of any same (arbitrary) radius greater than half the distance between the wells, then they would overlap on this line. It’s easy to see that dividing line bisects the perpendicular straight line connecting both wells. Also, if I had infinitely small feet, and I stood anywhere on this line, I’d be equidistant from both of the wells. The line dividing which well is nearer is a straight line. To the ‘left’ of the line, it’s nearer to go to the well on the well on the ‘left’, to the ‘right’ of the line, it’s closer to go to the well on the ‘right’. It’s possible to draw a line dividing the desert. If I want to go to the nearest well, which well do I visit? Clearly, it depends one where I am standing. Imagine I’m in a desert, and there are two wells where I can obtain water. These constructions are really pretty, and simple to explain. This week I’m going to talk about Voronoi diagrams.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |