=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.
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 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.
=sourcedcode mod17.pl
=begin footnote note0
Deeper info about Voronoi diagrams
A.
=end footnote
=cut