Skip to content

Instantly share code, notes, and snippets.

@lojic
Last active December 24, 2015 03:08
Show Gist options
  • Save lojic/6734952 to your computer and use it in GitHub Desktop.
Save lojic/6734952 to your computer and use it in GitHub Desktop.
Point in convex polygon detection in Haskell
type Edge = (Point, Point)
type Point = (Int, Int)
type Poly = [ Point ]
type Vector = (Int, Int)
crossProduct :: Vector -> Vector -> Int
crossProduct (x1,y1) (x2,y2) = (x1*y2) - (y1*x2)
-- Transform a list of points into a list of edges
polyEdges :: Poly -> [ Edge ]
polyEdges (p1:p2:ps) = (p1,p2) : polyEdges (p2:ps)
polyEdges _ = []
-- Compute the two vectors on which we'll compute the cross product
vectors :: Edge -> Point -> (Vector, Vector)
vectors ((x1,y1),(x2,y2)) (px,py) = ((x2-x1,y2-y1),(px-x1,py-y1))
-- Indicate whether the point is within the convex polygon
pointInPoly :: Poly -> Point -> Bool
pointInPoly poly p = all (\n -> n >= 0) normals
where normals = map (\ edge -> (uncurry crossProduct) (vectors edge p)) (polyEdges poly)
-- Example polygon
poly :: Poly
poly = [ (0,0), (10,0), (10,10), (0,10), (0,0) ]
yes = pointInPoly poly (5,5)
no = pointInPoly poly (15,15)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment