fromPoints()
方法可以接受一组点,然后返回这些点组成的凸包。
ConvexHull.fromPoints(points)
points
: 一个二维数组,包含一系列点的坐标。每个点需要包含两个数字,分别代表点在二维空间中的 x
和 y
坐标。
fromPoints()
方法返回一个新的二维数组,其中包含凸包上的所有点坐标。
const points = [
[0, 0],
[0, 1],
[1, 1],
[1, 0],
[0.5, 0.5]
];
const convexHull = ConvexHull.fromPoints(points);
console.log(convexHull);
// [[0, 0], [0, 1], [1, 1], [1, 0]]
当传递给 fromPoints()
方法的参数无效时,该方法将抛出一个 TypeError
异常。
fromPoints()
方法使用 Graham's 扫描方法来计算凸包。该算法先找出所有点中最左边的点,然后将这个点作为凸包的起点。接下来,算法按照极角逆时针排序所有点,之后扫描这些点,如果扫过的点的向量与前两个点之间的向量不是右转,就把它加入到凸包段中。尽管 Graham's 扫描算法的时间复杂度在最坏情况下为 $O(n\log n)$,但只要不处于最坏情况,它的表现是相当不错的。