import { Position } from "@xyflow/react";
import { isHorizontalFromPosition } from "./edge";
import { uuid } from "../../utils/uuid";

export interface ControlPoint {
  id: string;
  x: number;
  y: number;
}

export interface NodeRect {
  x: number; // left
  y: number; // top
  width: number;
  height: number;
}

export interface RectSides {
  top: number;
  right: number;
  bottom: number;
  left: number;
}

export interface HandlePosition extends ControlPoint {
  position: Position;
}

export interface GetVerticesParams {
  source: NodeRect;
  target: NodeRect;
  sourceOffset: ControlPoint;
  targetOffset: ControlPoint;
}

/**
 * 计算两个节点之间的控制点位置
 * 
 * 该函数用于在图形编辑器中确定边的控制点,以实现更自然的边布局。
 * 主要应用于:
 * 1. 节点之间连线的路径规划
 * 2. 边的弯曲程度控制
 * 3. 避免边与节点重叠
 * 
 * 实现原理:
 * 1. 基于源节点和目标节点构建外部边界矩形
 * 2. 基于偏移点构建内部边界矩形
 * 3. 在两个矩形的边上生成候选控制点
 * 4. 过滤掉无效的控制点
 * 
 * @param {GetVerticesParams} params - 计算所需的参数
 * @param {Rect} params.source - 源节点的矩形区域,包含x、y、width、height
 * @param {Rect} params.target - 目标节点的矩形区域
 * @param {Point} params.sourceOffset - 源节点上的连接点坐标
 * @param {Point} params.targetOffset - 目标节点上的连接点坐标
 * @returns {ControlPoint[]} 有效的控制点数组,每个点包含唯一ID和坐标
 */
export const getCenterPoints = ({
  source,
  target,
  sourceOffset,
  targetOffset,
}: GetVerticesParams): ControlPoint[] => {
  // 特殊情况处理:当源点和目标点在同一直线上时,无法构成有效的控制区域
  if (sourceOffset.x === targetOffset.x || sourceOffset.y === targetOffset.y) {
    return [];
  }

  // 步骤1: 获取外部边界
  // 收集两个节点的所有顶点,用于构建外部最大矩形
  const vertices = [...getRectVertices(source), ...getRectVertices(target)];
  const outerSides = getSidesFromPoints(vertices);

  // 步骤2: 获取内部边界
  // 根据偏移点(实际连接点)计算内部矩形的四条边
  const { left, right, top, bottom } = getSidesFromPoints([
    sourceOffset,
    targetOffset,
  ]);

  // 步骤3: 计算中心参考线
  const centerX = (left + right) / 2;   // 水平中心线
  const centerY = (top + bottom) / 2;    // 垂直中心线

  // 步骤4: 生成候选控制点
  // 在内外两个矩形的边上各生成4个控制点,共8个候选点
  const points = [
    { id: uuid(), x: centerX, y: top },              // 内矩形-上
    { id: uuid(), x: right, y: centerY },            // 内矩形-右
    { id: uuid(), x: centerX, y: bottom },           // 内矩形-下
    { id: uuid(), x: left, y: centerY },             // 内矩形-左
    { id: uuid(), x: centerX, y: outerSides.top },   // 外矩形-上
    { id: uuid(), x: outerSides.right, y: centerY }, // 外矩形-右
    { id: uuid(), x: centerX, y: outerSides.bottom },// 外矩形-下
    { id: uuid(), x: outerSides.left, y: centerY },  // 外矩形-左
  ];

  // 步骤5: 过滤无效控制点
  // 移除落在源节点或目标节点内部的控制点,避免边穿过节点
  return points.filter((p) => {
    return !isPointInRect(p, source) && !isPointInRect(p, target);
  });
};

/**
 * 扩展矩形区域
 * @param rect 原始矩形区域
 * @param offset 扩展偏移量
 * @returns 扩展后的新矩形区域
 * 
 * 该函数将一个矩形区域向四周扩展指定的偏移量。
 * 扩展规则:
 * 1. x和y坐标各向外偏移offset距离
 * 2. 宽度和高度各增加2*offset
 */
export const getExpandedRect = (rect: NodeRect, offset: number): NodeRect => {
  return {
    x: rect.x - offset,
    y: rect.y - offset,
    width: rect.width + 2 * offset,
    height: rect.height + 2 * offset,
  };
};

/**
 * 检测两个矩形是否重叠
 * @param rect1 第一个矩形
 * @param rect2 第二个矩形
 * @returns 布尔值,true表示重叠,false表示不重叠
 * 
 * 使用AABB(轴对齐包围盒)碰撞检测算法:
 * 1. 计算x轴投影是否重叠
 * 2. 计算y轴投影是否重叠
 * 两个轴向都重叠则矩形重叠
 */
export const isRectOverLapping = (rect1: NodeRect, rect2: NodeRect) => {
  return (
    Math.abs(rect1.x - rect2.x) < (rect1.width + rect2.width) / 2 &&
    Math.abs(rect1.y - rect2.y) < (rect1.height + rect2.height) / 2
  );
};

/**
 * 判断点是否在矩形内
 * @param p 待检测的控制点
 * @param box 矩形区域
 * @returns 布尔值,true表示点在矩形内,false表示点在矩形外
 * 
 * 点在矩形内的条件:
 * 1. x坐标在矩形左右边界之间
 * 2. y坐标在矩形上下边界之间
 */
export const isPointInRect = (p: ControlPoint, box: NodeRect) => {
  const sides = getRectSides(box);
  return (
    p.x >= sides.left &&
    p.x <= sides.right &&
    p.y >= sides.top &&
    p.y <= sides.bottom
  );
};

/**
 * 矩形顶点计算模块
 * 用于处理图形编辑器中矩形节点的顶点、边界等几何计算
 * 主要应用于连线路径规划和节点定位
 */

/**
 * 根据矩形和外部顶点计算包围矩形的顶点坐标
 * @param box 原始矩形的位置和尺寸信息
 * @param vertex 外部控制点
 * @returns 包围矩形的四个顶点坐标
 * 算法思路:
 * 1. 合并外部顶点和原矩形的顶点
 * 2. 计算所有点的边界范围
 * 3. 根据边界生成新的矩形顶点
 */
export const getVerticesFromRectVertex = (
  box: NodeRect,
  vertex: ControlPoint
): ControlPoint[] => {
  const points = [vertex, ...getRectVertices(box)];
  const { top, right, bottom, left } = getSidesFromPoints(points);
  return [
    { id: uuid(), x: left, y: top },     // 左上角顶点
    { id: uuid(), x: right, y: top },    // 右上角顶点
    { id: uuid(), x: right, y: bottom }, // 右下角顶点
    { id: uuid(), x: left, y: bottom },  // 左下角顶点
  ];
};

/**
 * 计算一组点的边界范围
 * @param points 控制点数组
 * @returns 返回边界的上下左右极值
 * 实现方式:
 * - 使用数组map和Math.min/max计算坐标的最值
 */
export const getSidesFromPoints = (points: ControlPoint[]) => {
  const left = Math.min(...points.map((p) => p.x));   // 最左侧x坐标
  const right = Math.max(...points.map((p) => p.x));  // 最右侧x坐标
  const top = Math.min(...points.map((p) => p.y));    // 最上方y坐标
  const bottom = Math.max(...points.map((p) => p.y)); // 最下方y坐标
  return { top, right, bottom, left };
};

/**
 * 获取矩形的四条边界位置
 * @param box 矩形的位置和尺寸信息
 * @returns 矩形的上下左右边界坐标
 * 计算方式:
 * - 左边界 = x坐标
 * - 右边界 = x + width
 * - 上边界 = y坐标
 * - 下边界 = y + height
 */
export const getRectSides = (box: NodeRect): RectSides => {
  const { x: left, y: top, width, height } = box;
  const right = left + width;
  const bottom = top + height;
  return { top, right, bottom, left };
};

/**
 * 根据边界信息生成矩形的四个顶点
 * @param sides 矩形的上下左右边界坐标
 * @returns 返回四个顶点的坐标信息
 * 顶点顺序: 左上 -> 右上 -> 右下 -> 左下
 */
export const getRectVerticesFromSides = ({
  top,
  right,
  bottom,
  left,
}: RectSides): ControlPoint[] => {
  return [
    { id: uuid(), x: left, y: top },     // 左上角顶点
    { id: uuid(), x: right, y: top },    // 右上角顶点
    { id: uuid(), x: right, y: bottom }, // 右下角顶点
    { id: uuid(), x: left, y: bottom },  // 左下角顶点
  ];
};

/**
 * 获取矩形的四个顶点坐标
 * @param box 矩形的位置和尺寸信息
 * @returns 返回矩形四个顶点的坐标
 * 实现流程:
 * 1. 先计算矩形的边界
 * 2. 根据边界生成顶点
 */
export const getRectVertices = (box: NodeRect) => {
  const sides = getRectSides(box);
  return getRectVerticesFromSides(sides);
};
/**
 * 合并多个矩形区域,返回一个能包含所有输入矩形的最小矩形
 * @param boxes 需要合并的矩形数组,每个矩形包含 x,y 坐标和宽高信息
 * @returns 合并后的最小包围矩形
 * 
 * 实现原理:
 * 1. 找出所有矩形中最左边的 x 坐标(left)和最右边的 x 坐标(right)
 * 2. 找出所有矩形中最上边的 y 坐标(top)和最下边的 y 坐标(bottom) 
 * 3. 用这四个边界值构造出新的矩形
 */
export const mergeRects = (...boxes: NodeRect[]): NodeRect => {
  // 计算所有矩形的最左边界
  const left = Math.min(
    ...boxes.reduce((pre, e) => [...pre, e.x, e.x + e.width], [] as number[])
  );
  // 计算所有矩形的最右边界
  const right = Math.max(
    ...boxes.reduce((pre, e) => [...pre, e.x, e.x + e.width], [] as number[])
  );
  // 计算所有矩形的最上边界
  const top = Math.min(
    ...boxes.reduce((pre, e) => [...pre, e.y, e.y + e.height], [] as number[])
  );
  // 计算所有矩形的最下边界
  const bottom = Math.max(
    ...boxes.reduce((pre, e) => [...pre, e.y, e.y + e.height], [] as number[])
  );

  // 返回能包含所有输入矩形的最小矩形
  return {
    x: left,          // 左上角 x 坐标
    y: top,           // 左上角 y 坐标
    width: right - left,    // 宽度 = 最右边界 - 最左边界
    height: bottom - top,   // 高度 = 最下边界 - 最上边界
  };
};

/**
 * 根据给定的位置和偏移量计算控制点坐标
 * @param box - 起始位置信息，包含x、y坐标和位置类型(上下左右)
 * @param offset - 偏移距离
 * @returns 返回计算后的控制点对象，包含唯一id和新的x、y坐标
 */
export const getOffsetPoint = (
  box: HandlePosition,
  offset: number
): ControlPoint => {
  // 根据不同的位置类型计算偏移后的坐标
  switch (box.position) {
    case Position.Top: // 顶部位置,y坐标向上偏移
      return {
        id: uuid(),
        x: box.x,
        y: box.y - offset,
      };
    case Position.Bottom: // 底部位置,y坐标向下偏移
      return { id: uuid(), x: box.x, y: box.y + offset };
    case Position.Left: // 左侧位置,x坐标向左偏移
      return { id: uuid(), x: box.x - offset, y: box.y };
    case Position.Right: // 右侧位置,x坐标向右偏移
      return { id: uuid(), x: box.x + offset, y: box.y };
  }
};

/**
 * 判断一个点是否在线段上
 * @param p - 待判断的点
 * @param p1 - 线段起点
 * @param p2 - 线段终点
 * @returns 如果点在线段上返回true,否则返回false
 * 
 * 判断逻辑:
 * 1. 点必须在线段所在的直线上(x坐标相等或y坐标相等)
 * 2. 点的坐标必须在线段两端点坐标范围内
 */
export const isInLine = (
  p: ControlPoint,
  p1: ControlPoint,
  p2: ControlPoint
) => {
  // 获取x坐标的范围区间[min, max]
  const xPoints = p1.x < p2.x ? [p1.x, p2.x] : [p2.x, p1.x];
  // 获取y坐标的范围区间[min, max] 
  const yPoints = p1.y < p2.y ? [p1.y, p2.y] : [p2.y, p1.y];

  return (
    // 垂直线段:三点x坐标相等,且待判断点的y坐标在范围内
    (p1.x === p.x && p.x === p2.x && p.y >= yPoints[0] && p.y <= yPoints[1]) ||
    // 水平线段:三点y坐标相等,且待判断点的x坐标在范围内
    (p1.y === p.y && p.y === p2.y && p.x >= xPoints[0] && p.x <= xPoints[1])
  );
};

/**
 * 判断一个点是否在直线上(不考虑线段端点限制)
 * @param p - 待判断的点
 * @param p1 - 直线上的点1
 * @param p2 - 直线上的点2
 * @returns 如果点在直线上返回true,否则返回false
 * 
 * 判断逻辑:
 * 仅判断点是否与直线上的两点共线(x坐标相等或y坐标相等)
 */
export const isOnLine = (
  p: ControlPoint,
  p1: ControlPoint,
  p2: ControlPoint
) => {
  return (p1.x === p.x && p.x === p2.x) || (p1.y === p.y && p.y === p2.y);
};
export interface OptimizePointsParams {
  edgePoints: ControlPoint[];
  source: HandlePosition;
  target: HandlePosition;
  sourceOffset: ControlPoint;
  targetOffset: ControlPoint;
}

/**
 * 优化边的控制点
 * 
 * 主要功能:
 * 1. 合并坐标相近的点
 * 2. 删除重复的坐标点
 * 3. 修正起点和终点的位置
 * 
 * @param p 包含边的起点、终点、偏移点和中间控制点等信息的参数对象
 * @returns 优化后的控制点信息,包含起点、终点、起点偏移、终点偏移和中间控制点
 */
export const optimizeInputPoints = (p: OptimizePointsParams) => {
  // 合并坐标相近的点,将所有点放入一个数组进行处理
  let edgePoints = mergeClosePoints([
    p.source,
    p.sourceOffset,
    ...p.edgePoints,
    p.targetOffset,
    p.target,
  ]);

  // 从合并后的点中提取起点和终点
  const source = edgePoints.shift()!;
  const target = edgePoints.pop()!;
  const sourceOffset = edgePoints[0];
  const targetOffset = edgePoints[edgePoints.length - 1];

  // 根据起点和终点的位置类型修正其坐标
  // 如果是水平方向,则保持x坐标不变;否则保持y坐标不变
  if (isHorizontalFromPosition(p.source.position)) {
    source.x = p.source.x;
  } else {
    source.y = p.source.y;
  }
  if (isHorizontalFromPosition(p.target.position)) {
    target.x = p.target.x;
  } else {
    target.y = p.target.y;
  }

  // 移除重复的坐标点,并为每个点分配唯一ID
  edgePoints = removeRepeatPoints(edgePoints).map((p, idx) => ({
    ...p,
    id: `${idx + 1}`,
  }));

  return { source, target, sourceOffset, targetOffset, edgePoints };
};

/**
 * 简化边的控制点
 * 
 * 主要功能:
 * 1. 确保直线上只保留两个端点
 * 2. 移除位于直线内部的控制点
 * 
 * 实现原理:
 * - 遍历所有中间点
 * - 判断每个点是否在其相邻两点形成的直线上
 * - 如果在直线上则移除该点
 * 
 * @param points 原始控制点数组
 * @returns 简化后的控制点数组
 */
export function reducePoints(points: ControlPoint[]): ControlPoint[] {
  const optimizedPoints = [points[0]];

  // 遍历除首尾点外的所有点
  for (let i = 1; i < points.length - 1; i++) {
    // 判断当前点是否在前后两点形成的直线上
    const inSegment = isInLine(points[i], points[i - 1], points[i + 1]);
    // 如果不在直线上,则保留该点
    if (!inSegment) {
      optimizedPoints.push(points[i]);
    }
  }

  optimizedPoints.push(points[points.length - 1]);
  return optimizedPoints;
}
/**
 * 坐标点处理工具函数集合
 * 主要用于图形边缘控制点的坐标处理,包括合并、去重等操作
 */

/**
 * 合并临近坐标点,同时将坐标值取整
 * @param points 控制点数组
 * @param threshold 合并阈值,默认为4个像素
 * @returns 处理后的控制点数组
 * 
 * 实现原理:
 * 1. 分别记录x和y轴上的所有坐标值
 * 2. 对每个新坐标,在阈值范围内查找已存在的相近值
 * 3. 如果找到相近值则使用已存在值,否则添加新值
 */
export function mergeClosePoints(
  points: ControlPoint[],
  threshold = 4
): ControlPoint[] {
  // 存储已处理的离散坐标值
  const positions = { x: [] as number[], y: [] as number[] };

  /**
   * 查找或添加坐标值
   * @param axis 坐标轴('x'|'y')
   * @param v 待处理的坐标值
   * @returns 最终使用的坐标值
   */
  const findPosition = (axis: "x" | "y", v: number) => {
    // 向下取整,确保坐标为整数
    v = Math.floor(v);
    const ps = positions[axis];
    // 在阈值范围内查找已存在的相近值
    let p = ps.find((e) => Math.abs(v - e) < threshold);
    // 如果没找到相近值,则添加新值
    if (p == null) {
      p = v;
      positions[axis].push(v);
    }
    return p;
  };

  // 处理每个控制点的坐标
  const finalPoints = points.map((point) => {
    return {
      ...point,
      x: findPosition("x", point.x),
      y: findPosition("y", point.y),
    };
  });

  return finalPoints;
}

/**
 * 判断两个控制点是否重合
 * @param p1 控制点1
 * @param p2 控制点2
 * @returns 是否重合
 */
export function isEqualPoint(p1: ControlPoint, p2: ControlPoint) {
  return p1.x === p2.x && p1.y === p2.y;
}

/**
 * 移除重复的控制点,但保留起点和终点
 * @param points 控制点数组
 * @returns 去重后的控制点数组
 * 
 * 实现思路:
 * 1. 使用Set存储已处理的坐标字符串(格式:"x-y")
 * 2. 保留最后一个点(终点)
 * 3. 遍历时跳过重复坐标,但保留第一次出现的点
 */
export function removeRepeatPoints(points: ControlPoint[]): ControlPoint[] {
  // 先添加终点坐标,确保终点被保留
  const lastP = points[points.length - 1];
  const uniquePoints = new Set([`${lastP.x}-${lastP.y}`]);
  const finalPoints: ControlPoint[] = [];

  points.forEach((p, idx) => {
    // 处理终点
    if (idx === points.length - 1) {
      return finalPoints.push(p);
    }
    // 使用坐标字符串作为唯一标识
    const key = `${p.x}-${p.y}`;
    if (!uniquePoints.has(key)) {
      uniquePoints.add(key);
      finalPoints.push(p);
    }
  });
  return finalPoints;
}
/**
 * 判断两条线段是否相交
 * @param p0 第一条线段的起点
 * @param p1 第一条线段的终点  
 * @param p2 第二条线段的起点
 * @param p3 第二条线段的终点
 * @returns 如果两线段相交返回true,否则返回false
 * 
 * 实现原理:
 * 1. 使用向量叉积判断两线段是否平行
 * 2. 使用参数方程求解交点参数s和t
 * 3. 判断参数是否在[0,1]区间内来确定是否相交
 */
const isSegmentsIntersected = (
  p0: ControlPoint,
  p1: ControlPoint,
  p2: ControlPoint,
  p3: ControlPoint
): boolean => {
  // 计算两条线段的方向向量
  const s1x = p1.x - p0.x;
  const s1y = p1.y - p0.y;
  const s2x = p3.x - p2.x;
  const s2y = p3.y - p2.y;

  // 使用向量叉积判断两线段是否平行
  if (s1x * s2y - s1y * s2x === 0) {
    // 平行线段必不相交
    return false;
  }

  // 求解参数方程,获取交点参数s和t
  const denominator = -s2x * s1y + s1x * s2y;
  const s = (s1y * (p2.x - p0.x) - s1x * (p2.y - p0.y)) / denominator;
  const t = (s2x * (p0.y - p2.y) - s2y * (p0.x - p2.x)) / denominator;

  // 当且仅当s和t都在[0,1]区间内时,两线段相交
  return s >= 0 && s <= 1 && t >= 0 && t <= 1;
};

/**
 * 判断线段是否与矩形相交
 * @param p1 线段起点
 * @param p2 线段终点
 * @param box 矩形区域
 * @returns 如果线段与矩形有交点返回true,否则返回false
 * 
 * 实现思路:
 * 1. 首先处理特殊情况:矩形退化为点时必不相交
 * 2. 将矩形分解为四条边
 * 3. 判断线段是否与任意一条矩形边相交
 * 4. 只要与任意一边相交,则与矩形相交
 */
export const isSegmentCrossingRect = (
  p1: ControlPoint,
  p2: ControlPoint,
  box: NodeRect
): boolean => {
  // 处理特殊情况:矩形退化为点
  if (box.width === 0 && box.height === 0) {
    return false;
  }

  // 获取矩形的四个顶点
  const [topLeft, topRight, bottomRight, bottomLeft] = getRectVertices(box);

  // 判断线段是否与矩形的任意一条边相交
  return (
    isSegmentsIntersected(p1, p2, topLeft, topRight) ||      // 上边
    isSegmentsIntersected(p1, p2, topRight, bottomRight) ||  // 右边
    isSegmentsIntersected(p1, p2, bottomRight, bottomLeft) || // 下边
    isSegmentsIntersected(p1, p2, bottomLeft, topLeft)       // 左边
  );
};