Difference between revisions of "Bresenham's line drawing algorithm"
Jump to navigation
Jump to search
(Add link to an alternative implementation) |
|||
(One intermediate revision by one other user not shown) | |||
Line 1: | Line 1: | ||
− | |||
<haskell> |
<haskell> |
||
+ | |||
+ | import List (sort,unfoldr) |
||
+ | |||
+ | type Point = (Integer,Integer) |
||
+ | |||
line :: Point -> Point -> [Point] |
line :: Point -> Point -> [Point] |
||
line pa@(xa,ya) pb@(xb,yb) = map maySwitch . unfoldr go $ (x1,y1,0) |
line pa@(xa,ya) pb@(xb,yb) = map maySwitch . unfoldr go $ (x1,y1,0) |
||
Line 21: | Line 25: | ||
</haskell> |
</haskell> |
||
− | Thanks to Cheddai Fouche for the above implementation |
+ | Thanks to Cheddai Fouche for the above implementation. |
+ | |||
+ | The core logic is in the "go" function which is passed to unfoldr. |
||
+ | |||
+ | And here is an implementation of generalized Bresenham's line drawing algorithm, in terms of balanced words: https://github.com/LambdaHack/LambdaHack/blob/2f031f8a09d07d46b8e0dfeff1d9653d31ea19cc/Game/LambdaHack/Common/Point.hs#L112 |
Revision as of 09:59, 13 April 2018
import List (sort,unfoldr)
type Point = (Integer,Integer)
line :: Point -> Point -> [Point]
line pa@(xa,ya) pb@(xb,yb) = map maySwitch . unfoldr go $ (x1,y1,0)
where
steep = abs (yb - ya) > abs (xb - xa)
maySwitch = if steep then (\(x,y) -> (y,x)) else id
[(x1,y1),(x2,y2)] = sort [maySwitch pa, maySwitch pb]
deltax = x2 - x1
deltay = abs (y2 - y1)
ystep = if y1 < y2 then 1 else -1
go (xTemp, yTemp, error)
| xTemp > x2 = Nothing
| otherwise = Just ((xTemp, yTemp), (xTemp + 1, newY, newError))
where
tempError = error + deltay
(newY, newError) = if (2*tempError) >= deltax
then (yTemp+ystep,tempError-deltax)
else (yTemp,tempError)
Thanks to Cheddai Fouche for the above implementation.
The core logic is in the "go" function which is passed to unfoldr.
And here is an implementation of generalized Bresenham's line drawing algorithm, in terms of balanced words: https://github.com/LambdaHack/LambdaHack/blob/2f031f8a09d07d46b8e0dfeff1d9653d31ea19cc/Game/LambdaHack/Common/Point.hs#L112