sattar.imamov
BAN USERSuppose we have three points A, B, C such that A - the leftmost point, B - middle point, C - the rightmost point. Also recall that the equation of the line passing through the two points, as follows: (Y - Y1) / (Y2 - Y1) = (X - X1) / (X2 - X1).
Then an algorithm for finding points with integer coordinates what inside the triangle as follows:
1) Find the equation of segments AB, AC, BC
2) Determine which side will be incremented Y coordinate (if B is greater than A, then up, otherwise down)
3) Move from point A to point C on the segment AC
4) For each X will move up (down) from function AB to AC, after to BC. On each point (x, y) check, whether this point is above (below) the points on the function AB and AC
Code on F#:
type Point = {x : int; y : int}
let fst (x, _, _) = x
let snd (_, x, _) = x
let thd (_, _, x) = x
let FindMoveStrategy (leftPoint : Point) (middlePoint : Point) =
match leftPoint, middlePoint with
leftPoint, middlePoint when leftPoint.y < middlePoint.y -> ((fun x -> x + 1), (fun curY yTo -> curY < yTo), (fun (y : float) -> (int)y + 1))
| _, _ -> ((fun x -> x - 1), (fun curY yTo -> curY > yTo), (fun (y : float) -> (int)y))
let LineEquation (point1 : Point) (point2 : Point) =
fun (x : int) -> (float)(point2.y - point1.y) * (float)(x - point1.x) / (float)(point2.x - point1.x) + (float)point1.y
let FindPoints (xFrom : int)
(xTo : int)
(equationFrom : int -> float)
(equationTo : int -> float)
(fMove : (int -> int) * (int -> int -> bool) * (float -> int))
(state : Point list) =
let rec InnerFindPoints (curX : int) (state : Point list) =
match curX with
curX when curX < (xTo + 1) ->
let rec InnerY (curY : int) (state : Point list) =
match curY with
curY when (snd fMove) curY ((int)(equationTo curX)) -> InnerY (fst fMove curY) ({new Point with x = curX and y = curY} :: state)
|_ -> state
InnerY ((thd fMove) (equationFrom curX)) state
|> InnerFindPoints (curX + 1)
| _ -> state
InnerFindPoints xFrom state
[<EntryPoint>]
let main argv =
let A = {new Point with x = 1 and y = 1}
let B = {new Point with x = 3 and y = 5}
let C = {new Point with x = 5 and y = 3}
let sortedPointList = List.sort (A :: B :: C :: [])
let leftPoint = sortedPointList.Item(0)
let middlePoint = sortedPointList.Item(1)
let rightPoint = sortedPointList.Item(2)
let moveStrategy = FindMoveStrategy (leftPoint) (middlePoint)
let equationFrom = LineEquation leftPoint rightPoint
let equationTo1 = LineEquation leftPoint middlePoint
let equationTo2 = LineEquation middlePoint rightPoint
let res = FindPoints leftPoint.x middlePoint.x equationFrom equationTo1 moveStrategy []
|> FindPoints (middlePoint.x + 1) rightPoint.x equationFrom equationTo2 moveStrategy
printfn "%A" res
0
RepCathyPotts, abc at 8x8
In my role as a Customer Services Manager, I excel in understanding the unique needs of clients and customers. I ...
F#:
- sattar.imamov January 14, 2014