概述
在前端领域中，数据的处理和可视化是十分重要的。而计算凸包，即多个点集中围成的最小凸多边形区域，是数据可视化中一项常见的任务。本篇文章将介绍一个 npm 包，即 monotone-chain-convex-hull，并详细说明其使用方法。
安装
npm install monotone-chain-convex-hull
使用方式
用法
-- -------------------- ---- ------- ------ ---------- ---- ----------------------------- ----- ------ - - --- --- --- --- --- --- --- --- --- --- -- ----- ------ - ------------------- --------------------
输出
[ [0, 0], [2, 0], [2, 2], [0, 2], ]
参数说明
函数 convexHull(points) 接收一个点集数组为参数，每个点是一个长度为 2 的数组，表示坐标。返回值也是一个点集数组，表示围成的凸多边形。如果输入的点集不足三个点，将返回一个空数组。
算法原理
本模块实现了一种叫做 “单调链上的凸壳” 算法。该算法可以快速地计算出给定点集中围成的最小凸多边形。
算法流程如下：
将所有点按照 x 坐标进行排序。
分别对左右两边的点集进行排序，以确定上凸壳和下凸壳。
对于每个点，判断其是否在上凸壳中或下凸壳中。判断方式如下：
对于上凸壳，从右往左依次遍历每个点，将该点加入凸壳中，直到加入该点后凸壳不再凸出，则该点不在凸壳中。
对于下凸壳，从左往右依次遍历每个点，将该点加入凸壳中，直到加入该点后凸壳不再凸出，则该点不在凸壳中。
将上凸壳和下凸壳合并，得到最终的凸多边形。
示例
点集排序
-- -------------------- ---- ------- ----- ------ - - --- --- --- --- --- --- --- --- --- --- -- ----- ------------ - --------------- -- -- ---- - ------ --------------------------
输出
[ [0, 0], [0, 2], [1, 1], [2, 0], [2, 2], ]
计算上凸壳
-- -------------------- ---- -------
----- --------- - ---
--- ---- ----- -- ------------- -
----- -
---------------- -- - --
--------- - -------------------------- - ------ -
--------------------------- - ----- - -------------------------- - ------ --
--------------------------- - ----- - -------------------------- - ------ -
--------- - -------------------------- - ------
- -
----------------
-
----------------------
-
-----------------------输出
[ [0, 0], [2, 0], [2, 2], [0, 2], ]
计算下凸壳
-- -------------------- ---- -------
----- --------- - ---
--- ---- ----- -- ----------------------- -
----- -
---------------- -- - --
--------- - -------------------------- - ------ -
--------------------------- - ----- - -------------------------- - ------ --
--------------------------- - ----- - -------------------------- - ------ -
--------- - -------------------------- - ------
- -
----------------
-
----------------------
-
-----------------------输出
[ [0, 2], [2, 2], [2, 0], [0, 0], ]
合并上下凸壳
const hull = upperHull.concat(lowerHull.slice(1, -1)); console.log(hull);
输出
[ [0, 0], [2, 0], [2, 2], [0, 2], ]
总结
本文介绍了 npm 包 monotone-chain-convex-hull 的使用方法，并介绍了算法原理。此算法是计算凸多边形的常用算法之一，能够快速、准确地计算出一个点集的凸多边形。在数据可视化等场景中得到广泛应用。
来源：JavaScript中文网 ，转载请注明来源 https://www.javascriptcn.com/post/66245