=for advent_year 2010 =for advent_day 17 =for advent_title Oh Voronoi night… =for advent_author Adam Russell Santa was having a horrible time co-ordinating the feeding of not only the big 8 reindeer (code names: comp, misc, news, rec, sci, soc, talk, and alt) but all their reindeer brothers and sisters, aunts and uncles, and various degrees of cousin. The reindeer are fed via 7 monolithic steel and concrete grain towers that were put in place centuries ago. Under the current reindeer village configuration some reindeer have to travel outside their neighborhood to get to a grain tower, and Reindeer factional tensions are on the rise. Historical Context The neighborhoods must be redrawn so that each neighborhood has a central grain tower. Replacing or moving the grain towers would be prohibitively expensive. How do we design the new neighborhoods around each of the immovable grain towers? Santa had no idea so he called in his smartest elf—Hermey the Elf, D.D.S. Luckily Hermey had an ace up his sleeve by way of having had an elven education in computational geometry before developing an obsession for all things dental. He also knew Perl. With such a powerful peanut butter and chocolate combination on his side he quickly dashed out a script using M and the problem was solved! Because Santa wanted an easy to visualize executive summary he also used P<2000-10|GD>and P<2010-13|Tkx> to make some nice visualizations. A voronoi diagramN will create neighborhoods around each of the 7 grain towers so that each neighborhood has exactly one grain tower and that grain tower is the closest grain tower from any point in the neighborhood. Making practical use of Math::Geometry::Voronoi was a little tricky at first though. There is a tempting function called C which returns the computed polygons representing the neighborhoods. However, if you also overlay the points for the grain towers over the polygons the points don't necessarily fall inside the polygon. Why aren't
the points inside the polygon? Why is this? Well, the polygons that are returned have finite edges but the voronoi algorithm draws the neighborhoods so that they extend off of Santa's compound and off into the North Pole and beyond. By A<#create_gd_edge|extending lines> to a far off point in the distance (off our canvas) we give the illusion of a line (well, technically a ray) extending to infinity. But this makes the visualization a little misleading so we A<#mod17.pl.63|remove some bells and whistles> to arrive at a simpler but more accurate representation. Why aren't
the points inside the polygon? =sourcedcode mod17.pl =begin footnote note0 Deeper info about Voronoi diagrams A. =end footnote =cut