Slicing Up A Park, Neatly

Now that weve broken up our park into little triangles, it's pretty easy to write some functions that will partition the park into chunks by slicing our triangle piles along arbitrary horizontal and vertical lines. Here's the code that will do that:

  
  let clipTriangle :: (Point -> Point -> Point) -> [Point] -> [Point] -> [Polygon] 
      clipTriangle i [] [a,b,c] = [] 
      clipTriangle i [a]  [b,c] = [[a,i a b,i a c]]
      clipTriangle i [a,b]  [c] = [[a,i a c,b],[b,i a c,i b c]]
      clipTriangle i [a,b,c] [] = [[a,b,c]]

  let slice :: (Point -> Bool) -> (Point -> Point -> Point) -> [Polygon] -> ([Polygon],[Polygon]) 
      slice f i t = (clip f,clip $ not.f)
          where clip g = concatMap ((uncurry $ clipTriangle i).(partition g)) t 
                      
  let sliceX :: Float -> [Polygon] -> ([Polygon],[Polygon]) 
      sliceX x = slice ((x >).fst) interpolateX
          where interpolateX (x1,y1) (x2,y2) = (x,y1+(y2-y1)*(x-x1)/(x2-x1)) 

  let sliceY :: Float -> [Polygon] -> ([Polygon],[Polygon]) 
      sliceY y = slice ((y >).snd) interpolateY
          where interpolateY (x1,y1) (x2,y2) = (x1+(x2-x1)*(y-y1)/(y2-y1),y) 

  let (left_side,right_side) = sliceX 200 triangles

  writeFile "tut3.svg" $ writePolygons $ (red left_side) ++ (blue right_side)


If we look at tut3.svg, this is what we'll see:



Let's look at the different functions to see how this works... The slice is the heavy lifter in this code snippet: It embodies the abstract action of slicing a pile of polygons using a line. What makes it cool is that it is extremely abstract and general- The actual line is represented by two functions passed into it: One function, of type (Point -> Bool), lets slice know if a point is on one side or the of the arbitrary line. The other function, of type (Point -> Point -> Point), lets it know the point at which two points on opposite sides of the line intersect with the line- Our interpolation function.

Think of what this means: By making slice a higher order function (higher order functions are functions that take other functions as parameters) we can decouple the task of slicing from any details about the location or angle of the cut. Having the abstract slice function makes it easier to write more concrete vertical and horizontal slicing functions (sliceX and sliceY, respectively.) If we wanted to, we could write functions that slice at other angles nearly as easily, still using slice to do the actual cutting.

The clipTriangle function is a tool used by slice, which figures out if a given triangle is cut by a line and breaks it into 3 baby triangles, if this is the case.


What's good about this code?

We used higher order programming to decouple the general job of slicing triangles along a line from the grimy math involved with specific types of lines. This is another great tool for modularizing our programs that Haskell makes easy.


What's bad about this code?

Actually, I think this code is pretty much all around good, given the task at hand.

NEXT