Skip to content

Instantly share code, notes, and snippets.

@melrief
Created August 31, 2013 22:47
Show Gist options
  • Save melrief/6401140 to your computer and use it in GitHub Desktop.
Save melrief/6401140 to your computer and use it in GitHub Desktop.
An example of Graphics.Rendering.Chart usage from the haskell chart package (https://github.com/timbod7/haskell-chart/wiki). Calculates and shows the convex hull (http://en.wikipedia.org/wiki/Convex_hull) from a finite list of points using the Graham's scan method (http://en.wikipedia.org/wiki/Graham_scan)
name: convexhull
version: 0.1
build-type: Simple
Executable: viewConvexHull
Main-is: ViewConvexHull.hs
build-depends: base >= 4
,Chart
,Chart-cairo
,colour
,data-default-class
,lens
-- To build just copy this and convexhull.cabal somewhere
-- and then run cabal build
--
-- Usage Example:
-- > ./dist/build/viewConvexHull/viewConvexHull plot.pdf 1,10 10,5 4,6 7,9 20,1 4,2 5,6 8,2 3,9
--
-- this creates a pdf file called plot.pdf with the plot in the current directory
module Main where
import Control.Arrow
((&&&))
import Control.Applicative
((<$>))
import Control.Lens
import Control.Monad
(mapM_
,when)
import Data.Colour
(opaque
,transparent)
import Data.Colour.Names
import Data.Default.Class
import Data.Function
(on)
import Data.List
(sort
,sortBy)
import Graphics.Rendering.Chart hiding (Point)
import Graphics.Rendering.Chart.Backend.Cairo
import System.Environment
(getArgs
,getProgName)
import System.Exit
(exitSuccess)
type Point a = (a,a)
data CCW = Collinear | Clockwise | CounterClockwise
deriving (Show)
ccw :: (Num a,Ord a)
=> Point a
-> Point a
-> Point a
-> CCW
ccw (ax,ay) (bx,by) (cx,cy) =
case area2 `compare` zero of
EQ -> Collinear
LT -> Clockwise
GT -> CounterClockwise
where area2 = (bx-ax)*(cy-ay) - (by-ay)*(cx-ax)
zero = fromInteger 0
sortOnPolarAngle [] = []
sortOnPolarAngle [x] = [x]
sortOnPolarAngle (x:xs) = x:sortBy (compare `on` polarAngle x) xs
where polarAngle (ax,ay) (bx,by) = negate $ (bx-ax) / (by-ay)
grahamScan :: (Fractional a,Ord a)
=> [Point a]
-> ([Point a],[Point a]) -- ^ points part of the hull and not
grahamScan = checkAndGo . sortOnPolarAngle . sortBy (compare `on` snd)
where checkAndGo [] = ([],[])
checkAndGo [p] = ([p],[])
checkAndGo (p1:p2:ps) = go [p2,p1] ps []
go hull [] notHull = (hull,notHull)
go (h:[]) (p:ps) notHull = go [p,h] ps notHull
go (h1:h2:hs) (p:ps) nhs = case ccw h2 h1 p of
CounterClockwise -> go (p:h1:h2:hs) ps nhs
_ -> go (h2:hs) (p:ps) (h1:nhs)
pointsChart :: (Fractional a,PlotValue a)
=> String
-> [Point a]
-> [Point a]
-> Renderable ()
pointsChart title ps1 ps2 = toRenderable mkLayout
where mkLayout = layout1_title .~ title
$ layout1_plots .~ plots
$ layout1_left_axis . laxis_override .~ axisTicksHide
$ layout1_bottom_axis . laxis_override .~ axisTicksHide
$ def
plots = [Left $ toPlot plotPS1
,Left $ toPlot plotLines
,Left $ toPlot plotPS2
,Left $ toPlot margins]
plotPS1 = plot_points_style .~ filledCircles 2 (opaque red)
$ plot_points_values .~ ps1
$ def
plotLines = plot_lines_style . line_color .~ opaque red
$ plot_lines_values .~ [ps1 ++ [head ps1]]
$ def
plotPS2 = plot_points_style .~ filledCircles 2 (opaque blue)
$ plot_points_values .~ ps2
$ def
margins = plot_points_style .~ filledCircles 0 transparent
$ plot_points_values .~ [(minx,miny)
,(maxx,miny)
,(maxx,maxy)
,(minx,maxy)]
$ def
sortedXs = sort $ map fst ps1
sortedYs = sort $ map snd ps1
paddingX = (maximum sortedXs - minimum sortedXs) / fromInteger 10
paddingY = (maximum sortedYs - minimum sortedYs) / fromInteger 10
minAndSpaceX = (subtract paddingX) . minimum
maxAndSpaceX = (+ paddingX) . maximum
minAndSpaceY = (subtract paddingY) . minimum
maxAndSpaceY = (+ paddingY) . maximum
(minx,maxx) = minAndSpaceX &&& maxAndSpaceX $ sort $ map fst ps1
(miny,maxy) = minAndSpaceY &&& maxAndSpaceY $ sort $ map snd ps1
printUsage :: IO ()
printUsage = do
progName <- getProgName
putStrLn $ "Usage: " ++ progName ++ " <output_file.pdf> <point1> [<point2>...]"
++ '\n':" where point = <x>,<y> (example: 1,2)"
main :: IO ()
main = do
args <- getArgs
when (length args < 2) (printUsage >> exitSuccess)
let points = map (read . (\s -> '(':s ++ ")")) $ tail args :: [(Double,Double)]
let (hull,notHull) = grahamScan points
renderableToPDFFile (pointsChart "Convex Hull" hull notHull) 640 480 (head args)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment