import { sum, findIndex, getShapeDirection, getDist, throttle, TINY_NUM, find } from "@daybrush/utils";
import { OverlapPointInfo, PointInfo, Rect } from "./types";
import { flat, isSameConstants, isSamePoint, tinyThrottle } from "./utils";

/**
 * @namespace OverlapArea
 */

/**
 * Gets the size of a shape (polygon) made of points.
 * @memberof OverlapArea
 */
export function getAreaSize(points: number[][]): number {
    if (points.length < 3) {
        return 0;
    }
    return Math.abs(sum(points.map((point, i) => {
        const nextPoint = points[i + 1] || points[0];

        return point[0] * nextPoint[1] - nextPoint[0] * point[1];
    }))) / 2;
}


/**
 * Get points that fit the rect,
 * @memberof OverlapArea
 */
export function fitPoints(points: number[][], rect: Rect): number[][] {
    const { width, height, left, top } = rect;
    const { minX, minY, maxX, maxY } = getMinMaxs(points);
    const ratioX = width / (maxX - minX);
    const ratioY = height / (maxY - minY);

    return points.map(point => {
        return [
            left + (point[0] - minX) * ratioX,
            top + (point[1] - minY) * ratioY,
        ];
    });
}
/**
 * Get the minimum and maximum points of the points.
 * @memberof OverlapArea
 */
export function getMinMaxs(points: number[][]): { minX: number, minY: number, maxX: number, maxY: number } {
    const xs = points.map(point => point[0]);
    const ys = points.map(point => point[1]);

    return {
        minX: Math.min(...xs),
        minY: Math.min(...ys),
        maxX: Math.max(...xs),
        maxY: Math.max(...ys),
    };
}
/**
 * Whether the point is in shape
 * @param - point pos
 * @param - shape points
 * @param - whether to check except line
 * @memberof OverlapArea
 */
export function isInside(pos: number[], points: number[][], excludeLine?: boolean): boolean {
    const [x, y] = pos;
    const {
        minX,
        maxX,
    } = getMinMaxs(points);

    const xLine = [[minX, y], [maxX, y]];
    const xLinearConstants = getLinearConstants(xLine[0], xLine[1]);
    const lines = convertLines(points);

    interface IntersectionPosInfo {
        pos: number[];
        line: number[][];
        type: "intersection" | "point" | "line";
    }
    const intersectionPosInfos: IntersectionPosInfo[] = [];

    lines.forEach(line => {
        const linearConstants = getLinearConstants(line[0], line[1]);
        const standardPoint = line[0];

        if (isSameConstants(xLinearConstants, linearConstants)) {
            intersectionPosInfos.push({
                pos: pos,
                line,
                type: "line",
            });
        } else {
            const xPoints = getPointsOnLines(getIntersectionPointsByConstants(xLinearConstants, linearConstants), [xLine, line]);

            xPoints.forEach(point => {
                if (line.some(linePoint => isSamePoint(linePoint, point))) {
                    intersectionPosInfos.push({
                        pos: point,
                        line,
                        type: "point",
                    });
                } else if (tinyThrottle(standardPoint[1] - y) !== 0) {
                    intersectionPosInfos.push({
                        pos: point,
                        line,
                        type: "intersection",
                    });
                }
            })
        }
    });

    if (!excludeLine) {
        // on line
        if (find(intersectionPosInfos, p => p[0] === x)) {
            return true;
        }
    }
    let intersectionCount = 0;
    const xMap = {};

    intersectionPosInfos.forEach(({ pos, type, line }) => {
        if (pos[0] > x) {
            return;
        }
        if (type === "intersection") {
            ++intersectionCount;
        } else if (type === "line") {
            return;
        } else if (type === "point") {
            const point = find(line, linePoint => linePoint[1] !== y);
            const prevValue = xMap[pos[0]];
            const nextValue = point[1] > y ? 1 : -1;

            if (!prevValue) {
                xMap[pos[0]] = nextValue;
            } else if (prevValue !== nextValue) {
                ++intersectionCount;
            }
        }
    });
    return intersectionCount % 2 === 1;
}
/**
 * Get distance from point to constants. [a, b, c] (ax + by + c = 0)
 * @return [a, b, c]
 * @memberof OverlapArea
 */
export function getDistanceFromPointToConstants(
    [a, b, c]: [number, number, number],
    pos: number[],
) {
    return (a * pos[0] + b * pos[1] + c) / (a * a + b * b);
}

/**
 * Get the coefficient of the linear function. [a, b, c] (ax + by + c = 0)
 * @return [a, b, c]
 * @memberof OverlapArea
 */
export function getLinearConstants(point1: number[], point2: number[]): [number, number, number] {
    const [x1, y1] = point1;
    const [x2, y2] = point2;
    // ax + by + c = 0
    // [a, b, c]
    let dx = x2 - x1;
    let dy = y2 - y1;

    if (Math.abs(dx) < TINY_NUM) {
        dx = 0;
    }
    if (Math.abs(dy) < TINY_NUM) {
        dy = 0;
    }

    // b > 0
    // ax + by + c = 0
    let a = 0;
    let b = 0;
    let c = 0;
    if (!dx) {
        if (dy) {
            // -x + 1 = 0
            a = -1;
            c = x1;
        }
    } else if (!dy) {
        // y - 1 = 0
        b = 1;
        c = -y1;
    } else {
        // y = -a(x - x1) + y1
        // ax + y + a * x1 - y1 = 0
        a = -dy / dx;
        b = 1;
        c = -a * x1 - y1;
    }

    return [a, b, c] as [number, number, number];
}
/**
 * Get intersection points with linear functions.
 * @memberof OverlapArea
 */
export function getIntersectionPointsByConstants(
    linearConstants1: number[],
    linearConstants2: number[],
): number[][] {
    const [a1, b1, c1] = linearConstants1;
    const [a2, b2, c2] = linearConstants2;

    const isZeroA = a1 === 0 && a2 === 0;
    const isZeroB = b1 === 0 && b2 === 0;
    let results: number[][] = [];

    if (isZeroA && isZeroB) {
        return [];
    } else if (isZeroA) {
        // b1 * y + c1 = 0
        // b2 * y + c2 = 0
        const y1 = -c1 / b1;
        const y2 = -c2 / b2;

        if (y1 !== y2) {
            return [];
        } else {
            return [
                [-Infinity, y1],
                [Infinity, y1],
            ];
        }
    } else if (isZeroB) {
        // a1 * x + c1 = 0
        // a2 * x + c2 = 0
        const x1 = -c1 / a1;
        const x2 = -c2 / a2;

        if (x1 !== x2) {
            return [];
        } else {
            return [
                [x1, -Infinity],
                [x1, Infinity],
            ];
        }
    } else if (a1 === 0) {
        // b1 * y + c1 = 0
        // y = - c1 / b1;
        // a2 * x + b2 * y + c2 = 0
        const y = -c1 / b1;
        const x = -(b2 * y + c2) / a2;

        results = [[x, y]];
    } else if (a2 === 0) {
        // b2 * y + c2 = 0
        // y = - c2 / b2;
        // a1 * x + b1 * y + c1 = 0
        const y = -c2 / b2;
        const x = -(b1 * y + c1) / a1;

        results = [[x, y]];
    } else if (b1 === 0) {
        // a1 * x + c1 = 0
        // x = - c1 / a1;
        // a2 * x + b2 * y + c2 = 0
        const x = - c1 / a1;
        const y = -(a2 * x + c2) / b2;

        results = [[x, y]];
    } else if (b2 === 0) {
        // a2 * x + c2 = 0
        // x = - c2 / a2;
        // a1 * x + b1 * y + c1 = 0
        const x = - c2 / a2;
        const y = -(a1 * x + c1) / b1;

        results = [[x, y]];
    } else {
        // a1 * x + b1 * y + c1 = 0
        // a2 * x + b2 * y + c2 = 0
        // b2 * a1 * x + b2 * b1 * y + b2 * c1 = 0
        // b1 * a2 * x + b1 * b2 * y + b1 * c2 = 0
        // (b2 * a1 - b1 * a2)  * x = (b1 * c2 - b2 * c1)
        const x = (b1 * c2 - b2 * c1) / (b2 * a1 - b1 * a2);
        const y = -(a1 * x + c1) / b1;

        results = [[x, y]];
    }

    return results.map(result => [result[0], result[1]]);
}
/**
 * Get intersection points to the two lines.
 * @memberof OverlapArea
 */
export function getIntersectionPoints(
    line1: number[][],
    line2: number[][],
    isLimit?: boolean,
): number[][] {
    const points = getIntersectionPointsByConstants(
        getLinearConstants(line1[0], line1[1]),
        getLinearConstants(line2[0], line2[1]),
    );

    if (isLimit) {
        return getPointsOnLines(points, [line1, line2]);
    }
    return points;
}

export function isPointOnLine(
    pos: number[],
    line: number[][],
) {
    const linearConstants = getLinearConstants(line[0], line[1]);

    return tinyThrottle(getDistanceFromPointToConstants(linearConstants, pos)) === 0;
}

/**
 * Get the points on the lines (between two points).
 * @memberof OverlapArea
 */
export function getPointsOnLines(
    points: number[][],
    lines: number[][][],
): number[][] {
    const minMaxs = lines.map(line => [0, 1].map(order => [
        Math.min(line[0][order], line[1][order]),
        Math.max(line[0][order], line[1][order]),
    ]));
    let results: number[][] = [];

    if (points.length === 2) {
        const [x, y] = points[0];
        if (!tinyThrottle(x - points[1][0])) {
            /// Math.max(minY1, minY2)
            const top = Math.max(...minMaxs.map(minMax => minMax[1][0]));
            /// Math.min(maxY1, miax2)
            const bottom = Math.min(...minMaxs.map(minMax => minMax[1][1]));

            if (tinyThrottle(top - bottom) > 0) {
                return [];
            }
            results = [
                [x, top],
                [x, bottom],
            ];
        } else if (!tinyThrottle(y - points[1][1])) {
            /// Math.max(minY1, minY2)
            const left = Math.max(...minMaxs.map(minMax => minMax[0][0]));
            /// Math.min(maxY1, miax2)
            const right = Math.min(...minMaxs.map(minMax => minMax[0][1]));

            if (tinyThrottle(left - right) > 0) {
                return [];
            }
            results = [
                [left, y],
                [right, y],
            ];
        }
    }

    if (!results.length) {
        results = points.filter(point => {
            const [pointX, pointY] = point;

            return minMaxs.every(minMax => {
                return (0 <= tinyThrottle(pointX - minMax[0][0]) && 0 <= tinyThrottle(minMax[0][1] - pointX))
                && (0 <= tinyThrottle(pointY - minMax[1][0]) && 0 <= tinyThrottle(minMax[1][1] - pointY));
            });
        });
    }

    return results.map(result => [tinyThrottle(result[0]), tinyThrottle(result[1])]);

}
/**
* Convert two points into lines.
* @function
* @memberof OverlapArea
*/
export function convertLines(points: number[][]): number[][][] {
    return [...points.slice(1), points[0]].map((point, i) => [points[i], point]);
}

function getOverlapPointInfos(points1: number[][], points2: number[][]): OverlapPointInfo[] {
    const targetPoints1 = points1.slice();
    const targetPoints2 = points2.slice();

    if (getShapeDirection(targetPoints1) === -1) {
        targetPoints1.reverse();
    }
    if (getShapeDirection(targetPoints2) === -1) {
        targetPoints2.reverse();
    }
    const lines1 = convertLines(targetPoints1);
    const lines2 = convertLines(targetPoints2);
    const linearConstantsList1 = lines1.map(line1 => getLinearConstants(line1[0], line1[1]));
    const linearConstantsList2 = lines2.map(line2 => getLinearConstants(line2[0], line2[1]));

    const overlapInfos: OverlapPointInfo[] = [];

    linearConstantsList1.forEach((linearConstants1, i) => {
        const line1 = lines1[i];
        const linePointInfos: OverlapPointInfo[] = [];
        linearConstantsList2.forEach((linearConstants2, j) => {
            const intersectionPoints = getIntersectionPointsByConstants(linearConstants1, linearConstants2);
            const points = getPointsOnLines(intersectionPoints, [line1, lines2[j]]);

            linePointInfos.push(...points.map(pos => ({
                index1: i,
                index2: j,
                pos,
                type: "intersection" as const,
            })));
        });
        linePointInfos.sort((a, b) => {
            return getDist(line1[0], a.pos) - getDist(line1[0], b.pos);
        });

        overlapInfos.push(...linePointInfos);

        if (isInside(line1[1], targetPoints2)) {
            overlapInfos.push({
                index1: i,
                index2: -1,
                pos: line1[1],
                type: "inside" as const,
            });
        }
    });

    lines2.forEach((line2, i) => {
        if (!isInside(line2[1], targetPoints1)) {
            return;
        }
        let isNext = false;
        let index = findIndex(overlapInfos, ({ index2 }) => {
            if (index2 === i) {
                isNext = true;
                return false;
            }

            if (isNext) {
                return true;
            }
            return false;
        });
        if (index === -1) {
            isNext = false;
            index = findIndex(overlapInfos, ({ index1, index2 }) => {
                if (index1 === -1 && index2 + 1 === i) {
                    isNext = true;
                    return false;
                }

                if (isNext) {
                    return true;
                }
                return false;
            });
        }
        if (index === -1) {
            overlapInfos.push({
                index1: -1,
                index2: i,
                pos: line2[1],
                type: "inside" as const,
            });
        } else {
            overlapInfos.splice(index, 0, {
                index1: -1,
                index2: i,
                pos: line2[1],
                type: "inside" as const,
            });

        }
    });
    const pointMap: Record<string, boolean> = {};

    return overlapInfos.filter(({ pos }) => {
        const key = `${pos[0]}x${pos[1]}`;

        if (pointMap[key]) {
            return false;
        }
        pointMap[key] = true;
        return true;
    });
}

/**
* Get the points of the overlapped part of two shapes.
* @function
* @memberof OverlapArea
*/
export function getOverlapPoints(points1: number[][], points2: number[][]): number[][] {
    const infos = getOverlapPointInfos(points1, points2);

    return infos.map(({ pos }) => pos);
}

function isConnectedLine(line: OverlapPointInfo[]) {
    const {
        0: {
            index1: prevIndex1,
            index2: prevIndex2,
        },
        1: {
            index1: nextIndex1,
            index2: nextIndex2,
        }
    } = line;

    if (prevIndex1 !== -1) {
        // same line
        if (prevIndex1 === nextIndex1) {
            return true;
        }
        if (prevIndex1 + 1 === nextIndex1) {
            return true;
        }
    }
    if (prevIndex2 !== -1) {
        // same line
        if (prevIndex2 === nextIndex2) {
            return true;
        }
        if (prevIndex2 + 1 === nextIndex2) {
            return true;
        }
    }

    return false;

}
/**
* Get the areas of the overlapped part of two shapes.
* @function
* @memberof OverlapArea
*/
export function getOverlapAreas(points1: number[][], points2: number[][]): number[][][] {
    const infos = getOverlapPointInfos(points1, points2);
    const areas: OverlapPointInfo[][] = [];
    let area: OverlapPointInfo[];

    getOverlapPointInfos(points1, points2).forEach((info, i, arr) => {
        if (i === 0 || !isConnectedLine([arr[i - 1], info])) {
            area = [info];
            areas.push(area);
        } else {
            area.push(info);
        }
    });

    return areas.map(area => area.map(({ pos }) => pos));
}
function findReversedAreas(points1: number[][], points2: number[][], index: number = 0, areas: number[][][] = []): number[][][] {
    const isFirst = areas.length === 0;
    const length = points1.length;
    const nextIndex = points1[index] ? index : 0;
    const nextPoints1 = [...points1.slice(nextIndex), ...points1.slice(0, nextIndex)];

    for (let i = 0; i < length; ++i) {
        const point1 = nextPoints1[i];

        if (find(points2, point2 => point2[0] === point1[0] && point2[1] === point1[1])) {
            continue;
        }
        if (areas.some(nextArea => find(nextArea, areaPoint => areaPoint[0] === point1[0] && areaPoint[1] === point1[1]))) {
            if (isFirst) {
                continue;
            } else {
                break;
            }
        }
        let nextArea: number[][];

        if (isFirst) {
            nextArea = [];
            areas.push(nextArea);
        } else {
            nextArea = areas[areas.length - 1];
        }
        nextArea.push(point1);


        const line = [point1, points1[index + 1] || points1[0]];
        const nextPoint2 = points2.filter(point2 => {
            return isPointOnLine(point2, line);
        }).sort((a, b) => {
            return getDist(point1, a) - getDist(point1, b);
        })[0];

        if (!nextPoint2) {
            findReversedAreas(nextPoints1, points2, i + 1, areas);
            break;
        } else {
            const point2Index = points2.indexOf(nextPoint2);

            findReversedAreas(points2, points1, point2Index, areas);
            if (!isFirst) {
                break;
            }
        }
    }
    return areas;
}
export function findConnectedAreas(points1: number[][], points2: number[][]) {
    return findReversedAreas(points1, [...points2].reverse());
}
/**
* Get non-overlapping areas of two shapes based on points1.
* @memberof OverlapArea
*/
export function getUnoverlapAreas(points1: number[][], points2: number[][]): number[][][] {
    if (!points2.length) {
        return [[...points1]];
    }
    const overlapAreas = getOverlapAreas(points1, points2);
     let unoverlapAreas = [points1];

    overlapAreas.forEach(overlapArea => {
        const nextOverlapArea = [...overlapArea].reverse();

        unoverlapAreas = flat(unoverlapAreas.map(area => {
            const connectedAreas = findReversedAreas(area, nextOverlapArea);
            const firstConnectedArea = connectedAreas[0];

            if (connectedAreas.length === 1 && nextOverlapArea.every(point => firstConnectedArea.indexOf(point) === -1)) {
                const lastPoint = firstConnectedArea[firstConnectedArea.length - 1];
                const firstPoint = [...nextOverlapArea].sort((a, b) => {
                    return getDist(lastPoint, a) - getDist(lastPoint, b);
                })[0];
                const firstIndex = nextOverlapArea.indexOf(firstPoint);

                firstConnectedArea.push(
                    ...nextOverlapArea.slice(firstIndex),
                    ...nextOverlapArea.slice(0, firstIndex),
                    nextOverlapArea[firstIndex],
                    lastPoint,
                );
            }
            return connectedAreas;
        }));
    });

    return unoverlapAreas;
}
/**
* Gets the size of the overlapped part of two shapes.
* @function
* @memberof OverlapArea
*/
export function getOverlapSize(points1: number[][], points2: number[][]): number {
    const points = getOverlapPoints(points1, points2);

    return getAreaSize(points);
}