npm 包 bound-points 使用教程

简介

bound-points 是一个 npm 包，用于计算平面上一组点的边界。这个包封装了计算凸包和最小矩形包围盒的算法，并提供了简单易用的 API。

安装

在终端中运行以下命令进行安装：

npm install bound-points

使用

计算凸包

凸包是指包含所有点的最小凸多边形。可以使用 convexHull 函数计算凸包。

const { convexHull } = require('bound-points')

const points = [[0, 0], [1, 1], [2, 2], [-1, 1]]
const hull = convexHull(points)
console.log(hull) // [[-1, 1], [2, 2], [0, 0]]

计算最小矩形包围盒

最小矩形包围盒是指包含所有点的最小矩形。可以使用 boundingBox 函数计算最小矩形包围盒。

const { boundingBox } = require('bound-points')

const points = [[0, 0], [1, 1], [2, 2], [-1, 1]]
const box = boundingBox(points)
console.log(box) // { x: -1, y: 0, width: 3, height: 2 }

深度解析

凸包算法

凸包算法是计算凸包的一种方法。常见的几何计算凸包算法有 Graham 扫描法、Jarvis 步进法、快速凸包算法等。bound-points 使用了 Andrew's monotone chain 算法，该算法复杂度为 O(n log n)。

Andrew's monotone chain 算法的基本思路如下：

1. 将点按照 x 坐标从小到大排序。
2. 分别计算出上半部分和下半部分的凸包。
3. 将上半部分和下半部分的凸包合并。

具体实现细节可以查看源码。

最小矩形包围盒算法

最小矩形包围盒算法是计算最小矩形包围盒的一种方法。常见的算法有旋转卡壳算法、最小矩形面积算法等。bound-points 使用了最小矩形面积算法。

最小矩形面积算法的基本思路如下：

1. 计算点集的凸包。
2. 对于任意两个相邻的点 P 和 Q，将其连线称作边 L。
3. 遍历所有可能的边 L，计算 L 线段两侧的点集分别能组成的最小矩形面积。
4. 取最小面积即可。

具体实现细节可以查看源码。

总结

bound-points 提供了简单易用的 API，可以方便地计算平面上一组点的边界。凸包算法和最小矩形包围盒算法是计算平面上点集边界的常见算法，在实际场景中有广泛应用。

来源：JavaScript中文网 ，转载请注明来源 https://www.javascriptcn.com/post/48334