跳到主要内容

二维拓扑运算

求直线, 射线, 线段之间的交点​

基础​

几何定义​
  • 直线/射线：p + su；
  • 线段：[p0，p1]；
基本思路​
  • 检测两者是否平行；
  • 检测两者是否重合；
  • 求交点；

直线和直线的交点​

直线和直线的交点​
  • 设直线分别为 p + su 和 q + tv；
const lineline = (line1: Line, line2: Line) => {
  const u = line1.direction;
  const v = line2.direction;
  const p = line1.point;
  const q = line2.point;

  // 检测两者是否平行或重合
  if (Vector.cross(u, v) === 0) {
    // 检测两者是否重合
    const w = Vector.sub(p, q);
    if (Vector.cross(w, v) === 0) return line1;

    // 两者无交点
    return false;
  } // 求两者交点
  else {
    // 求 s 的计算公式
    const w = Vector.sub(q, p);
    const s = Vector.cross(w, v) / Vector.cross(u, v);

    // 求交点
    const result = Vector.add(p, Vector.multiplyScalar(u, s));
    return result;
  }
};

射线和直线的交点​

射线和直线的交点​
  • 设射线和指向分别为 p + su (s>=0) 和 q + tv；
const lineline = (ray: Ray, line: Line) => {
  const u = ray.direction;
  const v = line.direction;
  const p = ray.point;
  const q = line.point;

  // 检测两者是否平行或重合
  if (Vector.cross(u, v) === 0) {
    // 检测两者是否重合
    const w = Vector.sub(p, q);
    if (Vector.cross(w, v) === 0) return ray;

    // 两者平行, 无交点
    return false;
  } // 求两者交点
  else {
    // 求 s 的计算公式
    const w = Vector.sub(q, p);
    const s = Vector.cross(w, v) / Vector.cross(u, v);

    // 两者无交点, 射线 s 必须大于 0
    if (s < 0) return false;

    // 求交点
    const result = Vector.add(p, Vector.multiplyScalar(u, s));
    return result;
  }
};

线段和直线的交点​

线段和直线的交点​
  • 设线段和指向分别为 [p1，p2] 和 q + tv；
  • 线段可转换为 p + su (1>=s>=0)
const lineline = (segment: Segment, line: Line) => {
  const u = Vector.sub(p2, p1);
  const v = line.direction;
  const p = segment.start;
  const q = line.point;

  // 检测两者是否平行或重合
  if (Vector.cross(u, v) === 0) {
    // 检测两者是否重合
    const w = Vector.sub(p, q);
    if (Vector.cross(w, v) === 0) return segment;

    // 两者平行, 无交点
    return false;
  } // 求两者交点
  else {
    // 求 s 的计算公式
    const w = Vector.sub(q, p);
    const s = Vector.cross(w, v) / Vector.cross(u, v);

    // 两者无交点, 线段 s 必须在 [0, 1] 区间
    if (s < 0 || s > 1) return false;

    // 求交点
    const result = Vector.add(p, Vector.multiplyScalar(u, s));
    return result;
  }
};

射线和射线的交点​

射线和射线的交点​
  • 设两条射线分别为 p + su (s>=0) 和 q + tv (t>=0)；
const rayRay = (segment: Ray, ray: Ray) => {
  const u = ray1.direction;
  const v = ray2.direction;
  const p = ray1.point;
  const q = ray2.point;

  // 检测两者是否平行或重合
  if (Vector.cross(u, v) === 0) {
    // 检测两者是否重合
    const w = Vector.sub(p, q);
    // 两者平行, 无交点
    if (Vector.cross(w, v) !== 0) return false;

    let range1, range2;
    // 射线关于 y 轴平行
    if (u.x === 0) {
      // 射线投影到 y 轴
      range1 = projection(segment, "y");
      range2 = projection(ray, "y");
    } else {
      range1 = projection(segment, "x");
      range2 = projection(ray, "x");
    }

    // 使用分离轴定律判断两者是否相交
    const range3 = rangeOverlap(range1, range2);

    // 两者不相交
    if (range.length === 0) return false;

    // 根据重叠范围生成重合部分
    return generateFromRang(range3);
  } // 求两者交点
  else {
    // 求 s 的计算公式
    const w = Vector.sub(q, p);
    const s = Vector.cross(w, v) / Vector.cross(u, v);
    const t = Vector.cross(u, w) / Vector.cross(v, u);

    // 两者无交点, s 和 t 必须均大于 0
    if (s < 0 || t < 0) return false;

    // 求交点
    const result = Vector.add(p, Vector.multiplyScalar(u, s));
    return result;
  }
};

线段和射线的交点​

线段和射线的交点​
  • 设线段和指向分别为 [p1，p2] 和 q + tv (t>=0)；
  • 线段可转换为 p + su (1>=s>=0)；
const segmentRay = (segment: Segment, ray: Ray) => {
  const u = Vector.sub(p2, p1);
  const v = ray.direction;
  const p = segment.start;
  const q = ray.point;

  // 检测两者是否平行或重合
  if (Vector.cross(u, v) === 0) {
    // 检测两者是否重合
    const w = Vector.sub(p, q);
    // 两者平行, 无交点
    if (Vector.cross(w, v) !== 0) return false;

    let range1, range2;
    // 关于 y 轴平行,  投影到 y 轴
    if (u.x === 0) {
      range1 = projection(segment, "y");
      range2 = projection(ray, "y");
    } else {
      range1 = projection(segment, "x");
      range2 = projection(ray, "x");
    }

    // 使用分离轴定律判断两者是否相交
    const range3 = rangeOverlap(range1, range2);

    // 两者不相交
    if (range.length === 0) return false;

    // 根据重叠范围生成重合部分
    return generateFromRang(range3);
  } // 求两者交点
  else {
    // 求 s 的计算公式
    const w = Vector.sub(q, p);
    const s = Vector.cross(w, v) / Vector.cross(u, v);
    const t = Vector.cross(u, w) / Vector.cross(v, u);

    // 两者无交点, s 在 [0 ,1], t 必须均大于 0
    if (s < 0 || s > 1 || t < 0) return false;

    // 求交点
    const result = Vector.add(p, Vector.multiplyScalar(u, s));
    return result;
  }
};

线段和线段的交点​

线段和线段的交点​
  • 设线段和指向分别为 [p1，p2] 和 [q1，q2]；
  • 线段可转换为 p + su (1>=s>=0) 和 q + tv (1>=t>=0)；
const segmentSegment = (segment: Segment, ray: Segment) => {
  const u = Vector.sub(p2, p1);
  const v = Vector.sub(q1, q2);
  const p = segment1.start;
  const q = segment2.start;

  // 检测两者是否平行或重合
  if (Vector.cross(u, v) === 0) {
    // 检测两者是否重合
    const w = Vector.sub(p, q);
    // 两者平行, 无交点
    if (Vector.cross(w, v) !== 0) return false;

    let range1, range2;
    // 关于 y 轴平行,  投影到 y 轴
    if (u.x === 0) {
      range1 = projection(segment1, "y");
      range2 = projection(segment2, "y");
    } else {
      range1 = projection(segment1, "x");
      range2 = projection(segment2, "x");
    }

    // 使用分离轴定律判断两者是否相交
    const range3 = rangeOverlap(range1, range2);

    // 两者不相交
    if (range.length === 0) return false;

    // 根据重叠范围生成重合部分
    return generateFromRang(range3);
  } // 求两者交点
  else {
    // 求 s 的计算公式
    const w = Vector.sub(q, p);
    const s = Vector.cross(w, v) / Vector.cross(u, v);
    const t = Vector.cross(u, w) / Vector.cross(v, u);

    // 两者无交点, s 在 [0 ,1], t 必须均大于 0
    if (s < 0 || s > 1 || t < 0 || t > 1) return false;

    // 求交点
    const result = Vector.add(p, Vector.multiplyScalar(u, s));
    return result;
  }
};

多边形面积计算​

多边形面积计算公式​

S=12∣∑i=1n(xiyi+1−xi+1yi)∣S=\frac{1}{2} |\sum_{i=1}^{n}\left(x_{i} y_{i+1}-x_{i+1} y_{i}\right)|

中心点的计算​

三角形中心点 (质心) 的计算公式​

c=(p1+p2+p3)/3c = (p_1 + p_2 + p_3)/3

任意多边形中心点 (质心) 的计算公式​
  • 多边形分割为多个三角形；
  • 计算三角形中心点，三角形面积作为权重；

任意多边形中心点的计算公式

过直线/射线/线段外一点求垂线​

几何定义​
  • 假设线段两点 A 和 B；
  • 线段外一点 P；
  • P 在 AB 上的垂点为 C；
垂线的计算公式​

AC→=(AP→⋅AB→)∣AB∣→(AB→)∣AB∣→\overrightarrow{AC}=\frac{(\overrightarrow{AP}\cdot\overrightarrow{AB})}{\overrightarrow{|AB|}}\frac{(\overrightarrow{AB})}{\overrightarrow{|AB|}}

求直线/射线/线段外一点到直线/射线/线段的最短距离​

几何定义​
  • 假设线上两点 A 和 B；
  • 线外一点 P；
  • P 在 AB 上的垂点为 C；
最短距离计算公式​

AC→=(AP→⋅AB→)∣AB∣→(AB→)∣AB∣→\overrightarrow{AC}=\frac{(\overrightarrow{AP}\cdot\overrightarrow{AB})}{\overrightarrow{|AB|}}\frac{(\overrightarrow{AB})}{\overrightarrow{|AB|}} r=(AP→⋅AB→)∣AB∣2→r=\frac{(\overrightarrow{AP}\cdot\overrightarrow{AB})}{\overrightarrow{|AB|^2}}

直线​

d=∣CP∣→d = \overrightarrow{|CP|}

射线​
d={d=∣CP∣→if r≥0∣AP∣→if r<0d = \begin{cases} d = \overrightarrow{|CP|} &if\ r\geq 0 \\ \overrightarrow{|AP|} &if\ r \lt 0 \end{cases}
线段​
d={d=∣BP∣→if r>1∣CP∣→if 1≥r≥0∣AP∣→if r<0d = \begin{cases} d = \overrightarrow{|BP|} &if\ r\gt 1 \\ \overrightarrow{|CP|} &if\ 1 \ge r \ge 0 \\ \overrightarrow{|AP|} &if\ r \lt 0 \\ \end{cases}