concaveman

concaveman

JavaScript 中的一个非常快速的 2D 凹壳 算法 (生成点集的一般轮廓)。

使用方法

import concaveman from 'concaveman';

const points = [[10, 20], [30, 12.5], ...];
const polygon = concaveman(points);

签名: concaveman(points[, concavity = 2, lengthThreshold = 0])

• points 是一个包含 [x, y] 点的数组。
• concavity 是凹陷程度的相对度量。1 会产生相对详细的形状,Infinity 会产生凸壳。 您可以使用小于 1 的值,但它们会产生非常奇怪的形状。
• lengthThreshold: 当一个分段的长度低于此阈值时,就不再被视为需要进一步细分。 较高的值会产生更简单的形状。

算法

该算法基于论文 [A New Concave Hull Algorithm and Concaveness Measure] 中的思想。 对于 n 维数据集, 2012 年](https://jise.iis.sinica.edu.tw/JISESearch/fullText?pId=245&code=5A9B97538372AA1) 作者: Jin-Seo Park 和 Se-Jong Oh。 这种实现比论文中所述的实现大幅提高了性能 从 O(rn),其中 r 是输出点的数量,转换为 O(n log n) 通过引入一个快速的 k 最近点到段的算法, 一种使用优先级队列的深度优先 kNN R-树搜索的修改。

TypeScript

可以通过 npm install --save @types/concaveman 安装。

依赖项

• rbush 用于点索引
• tinyqueue 作为优先级队列
• point-in-polygon 用于点在多边形内的查询
• robust-predicates 用于 3 点方向测试

TypeScript type definitions