几何学在前端边界计算中的应用和原理分析(一)

[MrXujiang]

前言

之所以会开设这个专栏, 是为了弥补部分程序员对代数和几何学的短板(当然也是为了巩固我的数学基础), 同时在实用价值上, 代数和几何学在编程界也起到了非常重要的推动作用, 比如我们看到的各种建模软件, 仿真&设计软件, 内部都涉及了很多数学原理, 在Web界, 我们比较熟悉的可视化图表, 在线设计软件Figma, 各式各样的可视化低代码产品, 都或多或少的应用了几何学原理, 所以要先让自己做出高价值的产品, 让自己的编程水平更进一步, 代数和几何学知识是非常有必要的。

在《100+前端几何学应用案例》 专栏中, 我会和大家由浅入深地分享一些应用几何学知识实现的经典Web案例, 比如:

• 游戏领域的边界问题(碰撞, 射击策略等)
• 几何画板的实现方案
• 常见的几种可视化图表实现方案
• 骨骼动画实现原理
• 从零封装一个图形库

等等, 每一个实战案例我都同步到 阿几里德编程实践 代码仓库中, 有兴趣的朋友可以参考学习。

接下来开始我们的第一篇分享——几何边界问题的编程实践。

几个常见边界计算的例子和实现原理

这篇文章主要会介绍三种常见图形(矩形, 圆形, 三角形)的边界计算方案, 其中会应用一些几何学和代数知识, 相信大家会从中汲取到自己需要的知识, 并应用到自己的项目中。

在开始实现之前我们先做一些准备工作:

1. 约定坐标体系(左上角为原点, x轴向右为正方向, y轴向下为正方向)
2. 工程采用vite构建, 前端使用vue3作为开发语言(当然其他框架也是完全没问题的, 看个人喜好)

1. 计算鼠标指针是否在矩形内部

有了上面的坐标体系, 我们就来解决矩形边界问题。为了让大家更好的理解边界问题的价值, 我这里来举一个形象的例子:

比如说我们在玩射击游戏, 只有射中靶子才能得分, 如上图, 这里有涉及到靶的边界问题, 这里转换为矩形边界问题就是: 判断一个点 (x,y) 是否在矩形(ABCD)内部:

由上图我们很容易就可以想出一种方案, 即判断 x 是否在区间 [a0, a1] 之间, y 是否在 [b0, b1] 之间。

我们先来构造一个矩形, 这里为了保证矩形足够通用, 我写了一个生成矩形的函数:

const generateRectangleMeta = (startPos: [number, number], w: number, h: number) => {
  if (
    startPos &&
    Array.isArray(startPos) &&
    startPos.length >= 2 &&
    typeof w === "number" &&
    typeof h === "number"
  ) {
    const [a0, b0] = startPos;
    const a1 = a0 + w;
    const b1 = b0 + h;
    return {
      startPos,
      w,
      h,
      endPos: [a1, b1],
      pos: [
        [a0, b0],
        [a1, b0],
        [a1, b1],
        [a0, b1],
      ],
    };
  } else {
    throw new Error("Please pass in the correct parameters");
  }
};

由上面的代码可知, 我们只需要传入矩形的左顶点坐标和宽高, 即可生成一个矩形元数据集合, 包含了:

• 左顶点坐标
• 矩形的宽高数据
• 右底点坐标
• 矩形四个顶点的坐标集合

有了以上数据之后, 我们就可以画出一个任意位置的矩形。

下一步就是获取任意点的坐标, 为了方便演示, 这里以鼠标指针作为点(x, y),
我们再来构造一个画布:

我们以画布的左上角作为坐标原点(0,0), 来计算一下鼠标在画布中的相对位置, 这里我使用vue3 的 hooks 来实现, 具体代码如下:

const cardOffset = ref({ x: 0, y: 0 });

onMounted(() => {
    // 获取画布左上角距离页面左上角的距离
  const { offsetTop, offsetLeft } = document.querySelector("#boundCard") as HTMLElement;
  cardOffset.value.x = offsetLeft;
  cardOffset.value.y = offsetTop;
});

const { x, y } = useMouse(window, (x, y) => {
  // 边界计算
  const { x: x0, y: y0 } = cardOffset.value;
  const dotX = x - x0;
  const dotY = y - y0;
  const { startPos, endPos } = rectangle;
  if (
    startPos[0] <= dotX &&
    endPos[0] >= dotX &&
    startPos[1] <= dotY &&
    endPos[1] >= dotY
  ) {
      // 在矩形内
    console.log("inset");
  } else {
      // 在矩形外
    console.log("out");
  }
});

上述代码中 useMouse 是一个组合函数, 主要用来获取鼠标的位置, 实现如下:

// event.ts
import { onMounted, onUnmounted } from 'vue'

export function useEventListener(
    target: HTMLElement | Window, 
    event: keyof HTMLElementEventMap, 
    callback: (this: HTMLElement, ev: any) => any) {
  onMounted(() => target.addEventListener(event, callback))
  onUnmounted(() => target.removeEventListener(event, callback))
}

// mouse.ts
import { ref } from 'vue'
import { useEventListener } from './event'

export function useMouse(target: HTMLElement | Window, callback?: (x: number, y:number) => void) {
  const x = ref(0)
  const y = ref(0)

  useEventListener(target, 'mousemove', (event) => {
    const { pageX, pageY } = event;
    x.value = pageX
    y.value = pageY
    callback && callback(pageX, pageY)
  })

  return { x, y }
}

之所以要把获取鼠标坐标的方法单独提出来, 是为了更好的复用, 也符合 hooks 倡导的理念, 对vue3 hooks感兴趣的朋友也可以研究一下。

经过上述的步骤, 我们就实现了判断矩形边界的功能, 完整效果演示如下:

是不是有种实现了 css 中 hover 的感觉呢? 通过以上方式, 我们可以轻松判断在画布中的任意点, 是否在矩形内部, 从而实现有意思的射击游戏。

当然我们探索的本质问题其实是: 判断一个点是否在指定形状的内部。我们有很多方式实现, 比如向量法, 面积法等, 对于简单的矩形, 圆形, 我们可以用精简的方式来判断, 对于比较复杂的如三角形, 我会在后面的内容中和大家详细分享实现方案。

2. 计算鼠标指针是否在圆内部

上面分享了判断一个点是否在矩形中的实现方案, 接下来我们继续探索圆形的边界问题。

我们都知道只要确定了圆的半径(R) 和 圆心坐标(x0, y0), 就能在坐标系里画出一个圆。这里我们先写一个生成圆的函数:

const generateCircleMeta = (pos: [number, number], r: number = 1) => {
  if(pos && Array.isArray(pos) && pos.length) {
    const [x, y] = pos;
    return {
      startPos: [x - r, y - r],
      pos,
      r
    }
  }else {
    throw new Error("Please pass in the correct parameters");
  }
}

之所以要写这个函数是因为我们的目标对象是 dom, 这样方便确定 dom 的位置。(当然我们也可以用其他方式定义一个圆, 这里的方案只做参考)

同时由于圆的特殊性, 我们要判断一个点是否在圆内, 只需要判断这个点和圆心的直线距离是否大于半径(r)即可。

$ r1 = Math.sqrt((x1 - x0)^2 + (y1 - y0)^2) $

我们用 javascript 来实现一下:

const isOutCircle = ref(false);
// 生成圆形数据元
const circle = generateCircleMeta([200, 400], 100);

useMouse(window, (x, y) => {
  // 边界计算
  const { x: x0, y: y0 } = cardOffset.value;
  const dotX = x - x0;
  const dotY = y - y0;
  const { pos, r } = circle;
  const r1 = Math.sqrt(Math.pow(dotX - pos[0], 2) + Math.pow(dotY - pos[1], 2));
  if (r >= r1) {
    console.log("inset");
    isOutCircle.value = false;
  } else {
    console.log("out");
    isOutCircle.value = true;
  }
});

由代码可知我们需要把几何中的坐标计算法转换为 javascript 支持的语法模式, 逻辑也很简单, 这里就不展开讨论了。

通过以上的实现, 我们就可以轻松计算任意矩形和圆形的边界问题了, 这也是我们工作中比较常见的计算场景, 接下来我们再来看一下如何计算三角形的边界。

3. 计算鼠标指针是否在三角形内部

要想解决这个问题, 我们需要先解决如何使用 HTMLDiv 画一个三角形。这里之所以不用 svg 或者 canvas 来画(虽然这两种方式画三角形会更简单), 主要是为了让大家更充分的感受几何学的魅力。也许有朋友会说了, 画个三角形不很方便吗? 用 css 或者 css背景渐变 都可以画出来, 但是通过上面的方式很难对三角形边界进行计算了, 我们需要知道三角形的三个顶点坐标, 所以这里我讲给大家介绍一种三角函数的方式, 来画任意的三角形。

3.1 从画一个线段开始

我们先来考虑一个简单的问题: 已知两个点的坐标 A(x0, y0) 和 B(x1, y1), 如何用 dom 画一个线段AB。

从图中我们可以分析出, 我们只要知道起点A, 线段AB的长度以及线段的角度a , 就能画出一个线段。 同时利用三角函数, 我们有以下的计算公式:

$ A = tana = (y1 - y0) / (x1 - x0) $

$ a = arctanA $

我们可以通过坐标来计算出角度和线段的长度, 对于web中的角度我们需要做一个基本的换算:

$ 1deg = 180 / Math.PI $

有了以上的知识铺垫, 我们来实现一下生成线段数据元的函数:

const generateLineMeta = (pos: [[number, number], [number, number]]) => {
  if (pos && Array.isArray(pos) && pos.length >= 2) {
    const [A, B] = pos;
    const dx = B[0] - A[0];
    const dy = B[1] - A[1];
    const l = Math.sqrt(Math.pow(dx, 2) + Math.pow(dy, 2));
    const tanAB = dy / dx;
    const AB = (Math.atan(tanAB) * 180) / Math.PI;
    return {
      startPos: A,
      endPos: B,
      angle: AB,
      l,
    };
  } else {
    throw new Error("Please pass in the correct parameters");
  }
};

上面代码中之所以用 tan 来计算, 是为了简化我们的计算公式, 当然大家也可以尝试用反正玄函数来计算。 将生成的元数据应用到我们的 dom 上即可得到我们想要的线段:

线段实现了, 我们要想画三角形是不是就很方便了呢? 我们只需要用根据三角形的3个顶点坐标画出首尾相连的3条线段即可。

3.2 用 HTMLDiv 画一个三角形

我们只需要对上面的生成线段的函数稍加改造, 就可以实现生成三角形数据元的函数。(更确切的说是生成任意边的数据元的函数)

const generateLinesMeta = (pos: [number, number][], isLine: boolean = false) => {
  if (pos && Array.isArray(pos) && pos.length >= 2) {
    let i = 0,
      len = pos.length,
      result = [];
    while (i < len) {
      // 如果是线段, 则不添加闭合点
      if (isLine && !pos[i + 1]) {
        break;
      }
      let A = pos[i];
      let B = pos[i + 1 > len - 1 ? 0 : i + 1];
      if (A[0] > B[0]) {
        [B, A] = [A, B];
      }
      const dx = B[0] - A[0];
      const dy = B[1] - A[1];
      const l = Math.sqrt(Math.pow(dx, 2) + Math.pow(dy, 2));
      const tanAB = dy / dx;
      const AB = (Math.atan(tanAB) * 180) / Math.PI;
      result.push({
        startPos: A,
        endPos: B,
        angle: AB,
        l,
      });
      i++;
    }

    return result;
  } else {
    throw new Error("Please pass in the correct parameters");
  }
};

上述笔者实现的代码中, 添加了 isLine 参数, 这个参数可以控制我们绘制的图形是闭合多四边形还是折线集合。

经过上面的实现, 我们终于用 HTML 画出了三角形, 接下来就是我们最后的冲刺了—— 判断空间内的点是否在三角形内部。

在上面两个图形的边界计算中我们用特殊方法来计算出了任意一个点是否在其内部, 但是对于三角形, 以上方法可能都不适用了, 那我们怎么来实现它呢?

想想我们初中高中学的向量 和 几何原理, 会不会有一些启发呢?

由上图可知, 我们是不是可以通过任意一点与三角形(S为该三角形的面积)三个顶点组成的三角形的面积(S1, S2, S3)来判断这个点是否在其内部呢? 如果点在三角形内部, 则会满足如下条件:

$ S = S1 + S2 + S3 $

如果点在三角形S外部, 则满足如下条件:

$ S < S1 + S2 + S3 $

所以说现在的问题就变成了求三角形面积的问题了。因为三角形的三个顶点坐标 (x1, y1), (x2, y2), (x3, y3) 是已知的,任意点的坐标 (x0, y0) 也是已知的, 我们可以根据向量叉积的计算方式来求出三角形的面积。

$ AB * AC = ||AB||||AC|| sin(θ)n $

向量叉积得到的是一个垂直于向量AB, AC所在平面的向量, n代表和平面垂直的法向量。

我们可以直接用高中课本的结论来算三角形的面积, 如下:

$ S = Math.abs(x1y2 + x2y3 + x3y1 - x2y1 - x3y2 - x1y3) / 2 $

也可以用上面的三角函数来推导出上述的公式, 这里我就不一一和大家介绍了, 有了上面的结论, 我们就很容易算出一个点是否在三角形内部了。

文章的 demo 代码大家想参考也可以在如下地址学习参考: 趣谈前端仓库

同时如果大家有更好的方案, 也欢迎在仓库里反馈交流。

总结

几何学博大精深, 我们市面上看到的很多设计软件, 都应用了大量的几何学原理和算法, 本篇意在为大家展示其在 web 中的一个应用, 我们可以把上述的算法应用到实际工作中, 实现非常有意思的web 应用。同时我也会分享前端可视化低代码的最佳实践, 感兴趣的小伙伴也可以参考我的专栏 低代码可视化专栏.

更多推荐

Dooring无代码搭建平台技术演进之路

从零开发一款可视化大屏制作平台

从零开发一款图片编辑器Mitu