使用JavaScript创建点集的凸包

Question

3

我希望使用KineticJS创建图像的轮廓。

1 - 我将所有图像的顶点保存在一个[x，y]数组中：

var points = [[0, 0], [0,350], [170, 0], [170, 300], [135, 135] , [135, 435], [305, 135], [305, 435]];

2 - 我想要在这些点周围创建凸包。

3 - 然后，我希望将凸包的距离稍微调高一些，以便所有对象都能位于凸包内。

我在网上找到了一个实现凸包生成的javascript实现，并尝试将其绑定到我的KineticJS脚本中。

但是，我遇到了一个错误：

"Uncaught RangeError: Maximum call stack size exceeded in the buildConvexHull function:"

allBaseLines.push(baseLine)

我的代码在fiddle里，但它不能运行… http://jsfiddle.net/gvFrd/5/

- sumisu

可能凸包算法期望在“points”中得到一对列表。您首先有x坐标的列表，然后是y坐标的列表。 - Lutz Lehmann

我将结构更改为 var points = [[0, 0], [0,350], [170, 0], [170, 300], [135, 135] , [135, 435], [305, 135], [305, 435]];但错误仍未消失。 - sumisu

for循环看起来有点奇怪。尝试将两行代码合并为for(var pt in points)。但是也许我对JS了解不够。 - Lutz Lehmann

谢谢，那不是错误，但我意识到我太蠢了，无法复制和粘贴...该函数与getConvexHull相同...我已更新所有内容，但错误在于未定义基线... - sumisu

2个回答

2

一个简单的算法是将点集分成两个子集，找到三个最远的点并进行三角剖分。三角形内的每个点都在凸包中。然后对其他点重复此步骤。搜索快速凸壳算法。您也可以使用Delaunay三角剖分。您可以在phpclasses.org下载我的凸包类。它使用Delaunay三角剖分。

- Micromega

看起来 Andrew 算法实现起来会更简单。 - Nuclearman

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user3413723 · Accepted Answer

Hull.js看起来是你正在寻找的答案。在生成凸包之后，它还可以将边缘向内推，并生成更多线段，以获得看起来相当准确的轮廓。