advent-of-code-2021/day-05/lib/line_segment.sml

structure LineSegment = struct
    type point = (int * int);
    datatype LineSegment = LineSegment of point * point;

    datatype ThreePointOrientation = Clockwise | CounterClockwise | Colinear;

    (* This only works for horizontal and vertical and diagonal line segments. *)
    fun contains_point seg point =
        let
            val (px,py) = point;
            val LineSegment ((ax, ay), (bx, by)) = seg;
            (* delta of start and end of segment *)
            val delta_x_ab = ax - bx;
            val delta_y_ab = ay - by;
            (* delta to point *)
            val delta_x_ap = ax - px;
            val delta_y_ap = ay - py;
        in
            ((point = (ax, ay)) orelse (point = (bx, by))) orelse
            (MathExtra.sign(delta_x_ab) = MathExtra.sign(delta_x_ap) andalso
             MathExtra.sign(delta_y_ab) = MathExtra.sign(delta_y_ap) andalso
             (((abs delta_x_ap) = (abs delta_y_ap)) orelse
              (delta_x_ap = 0) orelse
              (delta_y_ap = 0)))
        end;

    fun three_point_orientation (a: point) (b: point) (p: point) =
        (*
        Definition of orientation of 3 ordered points in a 2D plane:

        Co-linear order and orientation:

              C
           B
        A

        Clockwise order and orientation:

           B
        A
           C

        Counter-clockwise order and orientation:

           C
        A
           B

        Orientation can be found by substracting the 2 slopes of AB and BC from
        each other. This results in 3 cases:

        If the result is 0, then they 2 line segments AB and BC must have the
        same slope and that implies, that they are on the same line, which is
        called "colinear" or "colinearity".

        If the result is < 0, then the 2 line segments AB and BC have inequal
        slope and that BC has the higher slope. A higher slope means, that the
        turn from AB to BC is counter-clockwise, as seen in the following
        example:
              C

            B
        A

        If the result is > 0, then the 2 line segments AB and BC also have
        inequal slope, and AB has a higher slope than BC. This means, that the
        turn from AB to BC is clockwise, as seen in the following example:

         A
             B

              C

        The slope can be calculated as follows:

        A = (x1,y1)
        B = (x2,y2)
        C = (x3,y3)
                                        y2 - y1
        slope_AB = (y2-y1) / (x2-x1) = ---------
                                        x2 - x1

                                        y3 - y2
        slope_BC = (y3-y2) / (x3-x2) = ---------
                                        x3 - x2
        Substraction of fractions:

         a     c     ad - cb
        --- - --- = ---------
         b     d       bd

        TODO: How / why does the denominator disappear?

        *)
        let
            val (ax, ay) = a;   (* p *)
            val (bx, by) = b;   (* q *)
            val (px, py) = p;   (* r *)
        in
            let
                (* But why?! -- Explain this formula. *)
                val result = (by - ay) * (px - bx) - (bx - ax) * (py - by);
            in
                if result = 0
                then Colinear
                else
                    if result > 0
                    then Clockwise
                    else CounterClockwise
            end
        end;

    (* fun colinear seg1 seg2 = *)
    (*     (* Implement check for colinearity. *) *)
    (*     nil; *)

    (* fun intersection_point seg1 seg2 = *)
    (*     let *)
    (*         val LineSegment ((a1x, a1y), (b1x, b1y)) = seg1; *)
    (*         val LineSegment ((a2x, a2y), (b2x, b2y)) = seg2; *)
    (*     in *)
    (*         (* SOME or NONE ... *) *)
    (*         (* Implement algorithm to determin intersection point, if one exists. *) *)
    (*     end; *)
end;