{-
p __\
_ * _ (s,t) = ap
/| |\
/ \ __\
/ \ (u,v) = bp
a *-------->* b
__\
p is left of ab ==> z scale of cross-product (s,t) x (u,v) is positive.
-}
isLeftOf :: Coordinate -> Ray -> Bool
(px, py) `isLeftOf` ((ax, ay), (bx, by))
= let (s, t) = (px - ax, py - ay)
(u, v) = (px - bx, py - by)
in s * v >= t * u
{- p2 ___\ p1 * _* p3
_ * clockwise ==> p2 is left of p1p3 \ /|
/| \ \ /
/ \ anti-clockwise ==> p2 is on the right _\| /
/ _\| *
p1 * * p3 p2
-}
(Polygon pts) `containsS` p
= and leftOfList
where leftOfList = map isLeftOfp antiClockwiseRays
isLeftOfp p' = isLeftOf p p'
rays pts' = zip pts' (tail pts' ++ [head pts'])
isClockwiseOrder (p1:p2:p3:_) = p2 `isLeftOf` (p1, p3)
isClockwiseOrder _ = False
antiClockwiseRays = if isClockwiseOrder pts
then rays (reverse pts)
else rays pts
----- list of type/data used in this exercise -----
type Coordinate = (Float, Float)
type Ray = (Coordinate, Coordinate)
data Shape = Polygon [Vertex]
type Vertex = (Float, Float)
----- a test -----
polygon1 = Polygon [(-1,-1), (-1,1), (1,1), (1,-1)] -- clockwise order
polygon2 = Polygon [(-1,-1), (1,-1), (1,1), (-1,1)] -- counter-clockwise order
main = do
putStrLn $ show $ polygon1 `containsS` (0,0)
putStrLn $ show $ polygon2 `containsS` (0,0)
This entry was posted
on Wednesday, May 30th, 2007 at 4:00 pm and is filed under Haskell - SOE.
You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.