二维码
搜索 ×

第九章 空间算法

  • 作者：Jackey Hoo
  • 更新时间：2024年06月18日
  • 阅读量：0
  • 收藏数：0
文章标签： 空间算法 数学工具类 测量工具类 坐标工具类 图形开发 AnyGraph图形开发引擎

本章摘要

在图形开发进阶中，空间算法与数学工具至关重要。本章将带领你深入探索anyGraph图形开发引擎所提供的数学工具类、测量工具类以及坐标工具类，并提供了详细的实现方法与源代码，让你在图形系统的构建与优化中更加游刃有余。

图形系统开发实战课程 - 进阶篇 第九章 空间算法

第九章 空间算法

  在图形开发过程中经常会使用到数学运算、坐标转换、空间算法等方面的功能，本章就来讲解一下anyGraph 所提供的一些工具类。

1. 数学工具类

  anyGraph 提供了 MathUtil 工具类，提供了一些常用的数学函数。

1.1 弧度和角度

  角度是角的度量单位，它是指两条射线在圆周上形成的夹角的度数，通常使用度来表示。一个完整的圆有360度。弧度是一种度量角度的方法，是将圆周分为360等分，每一份的角度为1弧度。

  弧度数/π=角度值/180°，其中π是一个常数，等于圆周率（约为3.14159265…）

因此：

  • 角度 = 弧度 * (180 / π)
  • 弧度 = 角度 / (180 / π)

   MathUtil 类提供了 toDegrees(angleInRadians) 和 toRadians(angleInDegrees) 方法，实现弧度和角度相互转换，其源代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * 将弧度转换为度
 * @param {number} angleInRadians 以弧度为单位的角度
 * @return {number} 角度（以度为单位）
 */
function toDegrees(angleInRadians) {
    return (angleInRadians * 180) / Math.PI;
}

/**
 * 将度数转换为弧度
 * @param {number} angleInDegrees 以度为单位的角度
 * @return {number} 角度（弧度）
 */
function toRadians(angleInDegrees) {
    return (angleInDegrees * Math.PI) / 180;
}

1.2 生成随机数

  JavaScript 内置的 Math 对象提供了一个生成随机数的函数 random()，该函数返回一个浮点数，伪随机数在范围从0 到小于1。

  实际在应用过程中，经常需要生成的是某个范围内的随机整数，因此 MathUtil 类提供了 getRandomNum(min, max) 方法，可生成大于等于 min 小于等于 max 的随机整数，其源代码如下：

1
2
3
4
5
6
7
8
/**
 * 获取min和Max之间的随机整数
 */
function getRandomNum(min, max) {
    let range = max - min;
    let rand = Math.random();
    return Math.floor(min + Math.round(rand * range));
}

1.3 返回指定小数位数的值

  在 JavaScript 中，浮点运算的小数位是由计算机的浮点数表示方式决定的。JavaScript 使用 IEEE 754 标准来表示浮点数，其中包括单精度浮点数（32位）和双精度浮点数（64位）。单精度浮点数（32位）可以表示大约7位小数，而双精度浮点数（64位）可以表示大约15位小数。

  实际在应用过程中，可能并不需要保留这么长的小数位数，因此 MathUtil 类提供了 toFixed(n, decimals) 方法，可返回指定小数位数的浮点数，如果不指定小数位数，则返回两位数的浮点数。其源代码如下：

1
2
3
4
5
6
7
8
9
10
11
/**
 * 返回一个小数位数有限的数字(四舍五入到指定的小数位数)
 * 例如：toFixed(10.465,2)的返回值为10.47, toFixed(10.995, 2)的返回值为11
 * @param {number} n The input number.
 * @param {number} decimals The maximum number of decimal digits.
 * @return {number} The input number with a limited number of decimal digits.
 */
function toFixed(n, decimals = 0) {
    const factor = Math.pow(10, decimals);
    return Math.round(n * factor) / factor;
}

1.4 线性差值

  线性插值法是指使用连接两个已知量的直线来确定在这两个已知量之间的一个未知量的值的方法。

  下面这张图是线性差值的一个示例，蓝色的两个点为已知量，中间橙色的点为根据系数计算出的未知量，系数的取值范围是 0 ~ 1 。

运行效果

  MathUtil 类提供了 lerp(a, b, x) 方法，可返回指定系数的差值。

1
2
3
4
5
6
7
8
9
10
/**
 * 计算a和b之间的x的线性插值。
 * @param {number} a 开始值
 * @param {number} b 结束值
 * @param {number} x 插值系数.
 * @return {number} 插值.
 */
function lerp(a, b, x) {
    return a + x * (b - a);
}

该方法经常配合缓动函数使用。

1.5 返回指定范围内的数字

  MathUtil 类提供了 clamp(value, min, max) 方法，可返回指定范围内的数字。

1
2
3
4
5
6
7
8
9
10
/**
 * 获取指定范围内的数字
 * @param {number} value 数值.
 * @param {number} min 范围最小值.
 * @param {number} max 范围最大值.
 * @return {number} 指定范围内的数字，或与范围最接近的数字
 */
function clamp(value, min, max) {
    return Math.min(Math.max(value, min), max);
}

2. 测量工具类

  anyGraph 提供了 Measure 工具类，提供了一些常用的测量函数。

2.1 点与点之间的距离

  点与点之间的距离，可使用勾股定理 进行计算，其图示分解过程如下图所示：

运行效果

其源代码如下：

1
2
3
4
5
6
7
8
9
10
11
/**
 * 返回点p1(x1,y1)和p2(x2,y2)之间距离的平方。
 * @param {Array} p1[x1, y1]
 * @param {Array} p2[x2, y2]
 * @return {number} Squared distance.
 */
static dist(p1, p2) {
    const dx = p2[0] - p1[0];
    const dy = p2[1] - p1[1];
    return Math.sqrt(dx * dx + dy * dy);
}

Math.sqrt() 方法为 javaScript内置的求一个数的平方根。

2.2 折线长度

  点与点之间的距离，其实就是线段的长度，折线由多个线段组成，因此通过循环计算每一个线段的长度，即可计算出折线的长度。

1
2
3
4
5
6
7
8
9
10
11
/**
 * 计算折线长度
 * @param {Array} coords 折线点坐标数组
 */
static getLength(coords) {
    let length = 0;
    for (let i = 0; i < coords.length - 1; i++) {
        length += this.dist(coords[i], coords[i + 1]);
    }
    return length;
}

2.3 点与线之间的距离

  计算点与线之间的距离，可先计算点到线段的垂足（垂足是指一个点，它与线段上的两个端点形成的两条线段互相垂直）。当垂足在线段上时，点与线之间的距离为坐标到线段上垂足的距离，当垂足在线段外部时，点与线之间的距离为点与离线段最近的线段坐标之间的距离。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * 返回点p[x,y]和线段(p1[x1,y1], p2[x2,y2])之间最接近距离。
 * @param {Array} p[x, y]
 * @param {Array} p1[x1, y1]
 * @param {Array} p2[x2, y2]
 * @return {number} distance.
 */
static distToSegment(p, p1, p2) {
    // 计算线段两端点的差值
    const dx = p2[0] - p1[0];
    const dy = p2[1] - p1[1];

    // 如果dx和dy都不等于0, p1p2是一个线段，否则p1p2为同一个点
    if (dx !== 0 || dy !== 0) {
        // 计算p到线段p1p2的垂足t
        const t = ((p[0] - p1[0]) * dx + (p[1] - p1[1]) * dy) / (dx * dx + dy * dy);
        if (t > 1) {
            // 如果t大于1，说明垂足在线段p1p2外，此时将p1设置为p2
            p1[0] = p2[0];
            p1[1] = p2[1];
        } else if (t > 0) {
            // 如果t大于0且小于等于1，说明垂足在线段p1p2上，此时将p1设置为垂足的坐标
            p1[0] += dx * t;
            p1[1] += dy * t;
        }
    }

    // 计算并返回两点之间的距离
    return this.dist(p, p1);
}

2.4 多边形面积

  对于任意一个多边形，如果已知其各个顶点的坐标 ，那么这个多边形的面积为：

  其中

  算法原理参见：利用鞋带定理（Shoelace formula）求2D多边形面积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * 多边形计算面积
 * @param {Array} coords 多边形顶点坐标数组
 */
static getArea(coords) {
    // 多边形面积换算公式
    // S = Math.abs(0.5 * (x1 * y2 - y1 * x2 + x2 * y3 - y2 * x3 +….+ xn * y1 - yn * x1)));
    let area = 0;
    for (let i = 2; i < coords.length; i++) {
        let ax = coords[i - 1][0] - coords[0][0];
        let bx = coords[i - 1][1] - coords[0][1];
        let cx = coords[i][0] - coords[0][0];
        let dx = coords[i][1] - coords[0][1];
        // 三角形面积公式
        // S = 0.5 * (ax * dx - cx * bx);
        area += 0.5 * (ax * dx - cx * bx);
    };
    //顺时针为正，逆时针为负
    return Math.abs(area);
}

2.5 两点与X轴夹角的角度

  两点连线与x轴的夹角（取旋转角）对应的tanθ三角函数值就是斜率，所以求出斜率，再用反三角函数计算即可。

  JavaScript中有一个函数Math.atan2()，返回从原点(0,0)到(x,y)点的线段与x轴正方向之间的平面角度(弧度值)，也就是Math.atan2(y,x)，该函数可通过斜率计算出角度。

  计算公式如下：

  源代码如下：

1
2
3
4
5
6
7
8
9
/**
 * 计算两点与X轴夹角的角度
 * @param {*} p1
 * @param {*} p2
 * @returns
 */
static calcAngle(p1, p2) {
    return MathUtil.toFixed(MathUtil.toDegrees(Math.atan2(p2[1] - p1[1], p2[0] - p1[0])), 2);
}

3 坐标工具类

  在第一章 基础知识 基础数学知识 中分别讲述了使用三角函数和矩阵变换两种方式实现坐标的平移、缩放、旋转等变换的数学知识，本节讲述 anyGraph 中使用三角函数实现坐标变换的具体实现。

  这些方法封装到了 anyGraph 的工具类 Coordinate 中。

3.1 坐标平移

  平移就是将一个向量（或者点）的 x 和 y 各自移动一段距离。将平移前的坐标(x,y)换算到平移后的新坐标(, )的等式如下：


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * 坐标平移
 * @param {Array<Coord>} coords 坐标.
 * @param {number} deltaX x方向上的平移距离
 * @param {number} deltaY y方向上的平移距离
 * @return {Array<Coord>} 转换后的坐标.
 */
static translate(coords, deltaX, deltaY) {
    let dest = [];
    for (let j = 0; j < coords.length; j += 1) {
        dest[j] = [];
        dest[j][0] = coords[j][0] + deltaX;
        dest[j][1] = coords[j][1] + deltaY;
    }
    return dest;
}

3.2 基于原点坐标旋转

  旋转是一种线性变换，是指将一个向量（或者点）的 x 和 y 绕着一个定点旋转一定的角度。将旋转前的坐标(x, y)换算到旋转后的新坐标(, )的等式需要用到以下几个三角函数：

  • 三角函数：

  • 三角恒等式中的两角和差公式：

根据三角函数，可知在旋转之前：

在旋转之后 是不变的，假设旋转角度为 ， 根据三角函数和三角恒等式可得出：

即：

因此，旋转的源代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * 基于原点坐标旋转
 * @param {Array<Coord>} coords 坐标
 * @param {number} angle 角度
 * @return {Array<Coord>} 转换后的坐标
 */
static rotate(coords, angle) {
    let cos = Math.cos(angle);
    let sin = Math.sin(angle);
    let dest = [];
    for (let j = 0; j < coords.length; j++) {
        let x = coords[j][0] * cos - coords[j][1] * sin;
        let y = coords[j][1] * cos + coords[j][0] * sin;
        dest.push([x, y]);
    }
    return dest;
}

3.3 基于锚点进行坐标旋转

  基于锚点进行坐标旋转是一种组合变换，它包括了3个过程：

  1. 将锚点坐标平移至原点；
  2. 基于原点进行坐标旋转；
  3. 将原点平移至锚点；

  因此可在将基于原点坐标旋转的代码基础之上增加坐标平移的功能即可，其源代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * 基于锚点进行坐标旋转
 * @param {Array<Coord>} coords 坐标
 * @param {number} angle 角度
 * @param {Coord} anchor 锚点坐标
 * @return {Array<Coord>} 转换后的坐标
 */
static rotateByAnchor(coords, angle, anchor) {
    let cos = Math.cos(angle);
    let sin = Math.sin(angle);
    let anchorX = anchor[0];
    let anchorY = anchor[1];
    let dest = [];
    for (let j = 0; j < coords.length; j++) {
        let deltaX = coords[j][0] - anchorX;
        let deltaY = coords[j][1] - anchorY;
        dest.push([anchorX + deltaX * cos - deltaY * sin, anchorY + deltaX * sin + deltaY * cos]);
    }
    return dest;
}

3.4 基于原点进行坐标缩放

  缩放是指将一个向量（或者点）的 x 和 y 各自进行指定比例的缩放。将缩放前的坐标(x, y)换算到缩放后的新坐标(, )的等式如下：


  在这个等式中，坐标轴的横向缩放倍数记为sx，将原有x坐标乘以它，则可以得出新的横坐标；同时坐标轴的纵向缩放倍数记为sy，将原有y坐标乘以它，则可以得出新的纵坐标。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * 基于原点进行坐标缩放
 * @param {Array<Coord>} coords 坐标.
 * @param {number} sx x方向上的缩放比例
 * @param {number} sy y方向上的缩放比例
 * @return {Array<Coord>} 转换后的坐标.
 */
static scale(coords, sx, sy = sx) {
    let dest = [];
    for (let j = 0; j < coords.length; j++) {
        dest.push([coords[j][0] * sx, coords[j][1] * sy]);
    }
    return dest;
}

3.5 基于锚点进行坐标缩放

  基于锚点进行坐标缩放是一种组合变换，它包括了3个过程：

  1. 将锚点坐标平移至原点；
  2. 基于原点进行坐标缩放
  3. 将原点平移至锚点；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 基于锚点进行坐标缩放
 * @param {Array<Coord>} coords 坐标.
 * @param {number} sx x方向上的缩放比例
 * @param {number} sy y方向上的缩放比例
 * @param {Array<Coord>} anchor Scale anchor point.
 * @return {Array<Coord>} 转换后的坐标.
 */
static scaleByAnchor(coords, sx, sy, anchor) {
    let dest = [];
    let anchorX = anchor[0];
    let anchorY = anchor[1];
    for (let j = 0; j < coords.length; j += 1) {
        let deltaX = coords[j][0] - anchorX;
        let deltaY = coords[j][1] - anchorY;
        dest[j] = [];
        dest[j][0] = anchorX + sx * deltaX;
        dest[j][1] = anchorY + sy * deltaY;
    }
    return dest;
}

3.6 坐标反向

  坐标反向是对已有坐标值的数组或列表进行逆序操作，从而得到新的坐标数组。

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * 坐标反转
 * @param {Array<Coord>} coords 
 * @returns {Array<Coord>} coords
 */
static reverse(coords) {
    let dest = [];
    for (let j = coords.length - 1; j >= 0; j -= 1) {
        dest.push(coords[j]);
    }
    return dest;
}

  “图形系统实战开发-进阶篇 第九章 空间算法” 的内容讲解到这里就结束了，如果觉得对你有帮助有收获，可以关注我们的官方账号，持续关注更多精彩内容。

本文为“图形开发学院”（www.graphanywhere.com）网站原创文章，遵循CC BY-NC-ND 4.0版权协议，商业转载请联系作者获得授权，非商业转载请附上原文出处链接及本声明。

历史发布版本

第1版发布时间：2024-02-01
第2版发布时间：2024-06-18

社交媒体频道

知识分享频道：CSDN-图形开发学院

图形系统开发实战课程：进阶篇（上）——9.空间算法-CSDN博客

发布时间：2024-03-04

问答咨询频道：知乎-图形开发学院

图形系统开发实战课程：进阶篇（上）——9.空间算法-知乎

发布时间：2024-03-21

推荐教程