import numpy as np


def compute_target_coords(source_coords):
    """
    To determine the transformation matrix, we must first get the coordinates from/to which the source coordinates transform.
    This part is easy because we want the target points to be a perfect rectangle with width/height determined by the source coordinates.
    The width/height do not necessarily need to be determined by the source coordinates and this approach often produces images that do not maintain aspect ratios.

    :param source_coords: (list) The coordinates the user defines on the input image
    :return: (np.array) The target coordinates the source coordinates "transformed" into
    """

    # We assume the points to be in a specific order!
    (tl, tr, br, bl) = source_coords

    # compute the width of the new image, which will be the
    # maximum distance between bottom-right and bottom-left
    # x-coordiates or the top-right and top-left x-coordinates
    widthA = np.sqrt(((br[0] - bl[0]) ** 2) + ((br[1] - bl[1]) ** 2))
    widthB = np.sqrt(((tr[0] - tl[0]) ** 2) + ((tr[1] - tl[1]) ** 2))
    maxWidth = max(int(widthA), int(widthB))

    # compute the height of the new image, which will be the
    # maximum distance between the top-right and bottom-right
    # y-coordinates or the top-left and bottom-left y-coordinates
    heightA = np.sqrt(((tr[0] - br[0]) ** 2) + ((tr[1] - br[1]) ** 2))
    heightB = np.sqrt(((tl[0] - bl[0]) ** 2) + ((tl[1] - bl[1]) ** 2))
    maxHeight = max(int(heightA), int(heightB))

    # now that we have the dimensions of the new image, construct
    # the set of destination points to obtain a "birds eye view",
    # (i.e. top-down view) of the image, again specifying points
    # in the top-left, top-right, bottom-right, and bottom-left order
    target_coords = np.array([
        [0, 0],
        [maxWidth - 1, 0],
        [maxWidth - 1, maxHeight - 1],
        [0, maxHeight - 1]], dtype="float32")

    return target_coords


def direct_linear_transformation(source_coords, target_coords):
    """
    Solves a set of variables from a set of similarity relations.
    Singular Value Decomposition (SVD) is a widely used technique to decompose a matrix into several component matrices, exposing many of the useful and interesting properties of the original matrix.

    :param source_coords: (list) The coordinates the user defines on the input image
    :param target_coords: (np.array) The target coordinates the source coordinates "transformed" into
    :return: (np.array) The homography (i.e. transformation matrix) That defines the transformation between the source and target coordiantes
    """

    # Create a matrix that represents the source and target coordinates
    A = []
    for source_coord, target_coord in zip(source_coords, target_coords):
        ax, ay = source_coord[0], source_coord[1]
        bx, by = target_coord[0], target_coord[1]
        A.append([-ax, -ay, -1, 0, 0, 0, bx * ax, bx * ay, bx])
        A.append([0, 0, 0, -ax, -ay, -1, by * ax, by * ay, by])

    # Compute singular value decomposition for A
    U, S, V = np.linalg.svd(np.asarray(A))  # A = USV^T

    # The solution is the last column of V (9 x 1) Vector
    L = V[-1, :]

    # Divide by last element as we estimate the homography up to a scale
    L = L / V[-1, -1]
    H = L.reshape(3, 3)

    return H