How to Make Sure Everyone Gets a Fair Slice of the Park

Now that we have the tools we need to cut our park into nice little pieces, how do we figure out the best way to cut it up?

Well, I don't have a perfect answer (if there is any to be had) but it's not too hard to come up with a pretty good solution using a heuristic approach. Here's how we're going to do it:

First, we cut the park roughly down the middle in two halves- If the park is "fat", we cut it vertically... If the park is "tall", we cut it horizontally. Next, we calculate the surface area of each side- Using the ratio of surface areas, we can now randomly break our picnickers into two populations, one for each side.

We keep doing this until every person has their own space- Here's the code that makes it work:



  
  let boundingRect :: [Polygon] -> (Float,Float,Float,Float) 
      boundingRect p = (minimum xs,minimum ys,maximum xs,maximum ys)
          where xs = map fst $ concat p
                ys = map snd $ concat p

  let halveTriangles :: Int -> [Polygon] -> ([Polygon],[Polygon]) 
      halveTriangles n p = let (l,t,r,b) = boundingRect p         
                               f         = fromIntegral n         
                               h         = fromIntegral $ div n 2 
                           in if r-l > b-t
                              then sliceX ((r*h+l*(f-h))/f) p
                              else sliceY ((b*h+t*(f-h))/f) p

  let distance :: Point -> Point -> Float 
      distance p1 p2 = sqrt (deltax*deltax+deltay*deltay)
          where deltax = (fst p1)-(fst p2)
                deltay = (snd p1)-(snd p2)

  let area :: Polygon -> Float 
      area [a,b,c] = let x = distance a b
                         y = distance b c
                         z = distance c a
                         s = (x+y+z)/2
                     in sqrt (s*(s-x)*(s-y)*(s-z))

  let allocatePeople :: Int -> [Polygon] -> [[Polygon]] 
      allocatePeople 0 t = []
      allocatePeople 1 t = [t]
      allocatePeople n t = let (t1,t2) = halveTriangles n t            
                               a1      = sum $ map area t1             
                               a2      = sum $ map area t2             
                               f = round $ (fromIntegral n)*a1/(a1+a2) 
                           in (allocatePeople f t1)++(allocatePeople (n-f) t2)

  let lots = allocatePeople (length people) triangles

  writeFile "tut4.svg" $ writePolygons $ concat $ zipWith ($) (cycle rainbow) lots

Here's what tut4.svg looks like- Every picnicgoer get their own picnic lot, of a decent size and shape:


The halveTriangles function in this code snippet takes a count of the number of picnic attendees (for the block of land currently being allocated) and cuts the park roughly in half, based on its bounding rectangle. I say "roughly", because we would only want to cut the park exactly in half if the number of people is even- If its odd, then an even cut can be very unfair- Imagine if there were three people left- In that case, an even cut on a rectangular lot would force two of the people to share a single half... It's much smarter if we cut slightly off-center when there's an odd number of people, then it'll be more likely that everyone will get their fair share. The halveTriangles function does the math for this- It also compares the length and width of the lot to decide whether a horizontal or vertical cut would lead to "squarer" lots.

The other important function is the allocatePeople function- This is basically the "land commissioner" of this algorithm- It's the function that recursively cuts things into smaller and smaller pieces, and divies up the land chunks to subsets of the people, by comparing land area (via the area function, which uses Heron's Law) against the number of people. In the end, everyone gets a pretty fair piece.


What's good about this code?

This kind of code is perfect for a functional programming language, like Haskell- All we're doing is successively churning through all of our park land and handing off to people, something that is easily captured using the recursive allocatePeople function.

Another cool feature of this code is that it colors all the land chunks using a rainbow of colors- We do this by converting our rainbow of colors into an infinitely repeating rainbow of colors using the cycle function, and then we write a little esoteric code that will call every successive rainbow color function (remember, rainbow consisted of a list of color-applying functions) to make a rainbow-colored map of park lots.


What's bad about this code?

First of all, every time we need to check the land area for a region of the park we're recalculating it from scratch- Since this is done over and over again for the same pieces as the park is recursively subdivided, a lot of computrons are being wasted. A better version would "remember" previous triangle areas using memoization.

A second problem with this land subdivision algorithm is that it isn't mathematically perfect... It's just a heuristic: If you look at the final map, you can see small areas that are missing/wasted in the end- You may also be able to come up with certain degenerate park shapes that could break the algorithm altogether. Luckily, here in Washington DC we don't have no stinkin' degenerately shaped parks... though I can't vouch for Baltimore. (Just Kidding)




NEXT