问题标签 [qhull]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票
1 回答
1177 浏览

r - 在 R 中绘制由 quickhull 算法给出的凸包(convhulln 函数)

我需要在 R 中绘制由 quickhull 算法给出的凸包。这是一个例子。

ConVexHull$hull 给出一个 m 维索引矩阵,其中每一行定义一个暗维“三角形”。

我知道如何使用 chull 函数进行绘图,但我不确定 chull 是否给出与 convhulln 给出的相同的船体

0 投票
1 回答
1178 浏览

python - Qhull Convex hull 要我输入至少3分

更新:我决定尝试使用线性编程包来确定两个多面体的顶点是否是线性可分的。(顶点实际上是我的数据,而不是多面体。)我认为这会更好,所以我不再需要这个问题的答案。

我正在编写一些涉及检查某些多面体是否不相交的代码。这些多面体由它们顶点的凸包定义,我正在使用Qhull. 特别是,我使用的方法是:

这很好用,只是有时我的集合中只有 2 或 1 个点。Qhull不喜欢这个,它吐出这个错误:

QhullError: QH6214 qhull input error: not enough points(1) to construction initial simplex (need 3)

执行时:| qhull i 为 Qhull 2015.2.r 2016/01/18 选择的 Qt 选项:run-id 109084531 发生率 Qtriangulate _pre-merge _zero-centrum

虽然我可以通过编写一些捕获少于 3 点的情况的子程序来处理这个问题,Qhull但不处理这种情况令人沮丧。所以我正在寻找:

1)让Qhull正确处理这个问题的简单方法

或者

2)使用的替代包

谢谢!

0 投票
1 回答
931 浏览

python - 使用 qhull/SciPy 计算大型数据集的凸包时的问题

我开始尝试使用该scipy.spatial.ConvexHull函数,它(如果我理解正确的话)是qhullC 库的包装器。我将 SciPy 0.19.1 与 Python3 一起使用。

我首先使用了一个真实世界的数据集,该数据集具有 21 个维度的 700 个点,然后scipy.spatial.ConvexHull崩溃,出现以下错误:scipy.spatial.qhull.QhullError: QH6235 qhull error (qh_memalloc): negative request size (-2003053336). Did int overflow due to high-D?.

使用以下示例 Python3 代码进行几次尝试后:

我设法将问题缩小到维度。它有 21 个维度的 39 个随机生成的点,它可以工作。40分,有时会崩溃,有时会成功。我不确定,但似乎存在内存分配错误?

  1. 有没有办法避免内存问题?对于凸包算法来说,700 点太多了吗?
  2. 浏览 Google 的搜索结果,我注意到有一些算法可以计算凸包的近似值。你推荐他们吗?他们可以在我的情况下工作吗?其中一些是否已经有 Python 实现?
  3. 可能我想计算高维空间的凸包,最多 100,000 维。这是疯狂,还是可以以明智的方式完成?
0 投票
1 回答
1097 浏览

python - 如果凸包是完美的矩形(python 3),如何获得构成凸包的所有点?

打开图像以查看以下代码的结果

我想获得凸包上点的坐标索引(黑色+线上的点)。我选择矩形只是为了得到一个极端的情况。

hull.points只能给出标记为红色的点(仅矩形的角点)。

代码结果

0 投票
1 回答
4980 浏览

python - LinearNDInterpolator -- Qhull 精度误差:初始单纯形是平坦的

我正在尝试scipy.interpolate.LinearNDInterpolator()在 8 维空间中插入数据点,但遇到了一个我不明白的错误:

接下来是我将在下面发布的更多文字。使用我可以在网上找到的内容,我无法解决我的代码中的错误。这一切对我来说都是正确的(我只复制了相关部分):

其中points是 Nx8 嵌套的浮点数列表,s是 Nx1 浮点数列表,两者均在前面定义。

从我在文档中看到的内容来看,在我看来我做得对。我的错误在哪里?我应该使用不同的方法吗?

这是完整的 Qhull 错误

0 投票
1 回答
600 浏览

python - 从 scipy.spatial.Voronoi 有效地确定 Voronoi 图中的相邻单元格

我正在研究一种使用 Voronoi 图的算法。我需要知道每个给定的细胞,它有哪些细胞作为邻居;也就是说,它与哪些邻居共享一条边。这类似于一个现有的问题。但是,我已经有一个计算这个的算法,但我希望加快它的速度并避免冗余计算。

目前我正在使用 scipy.spatial.Voronoi 的输出来执行此操作,它为我提供了可以用来构建此映射的顶点、点等数组。但是,我运行这个算法有很多点,我想加快这个过程。

我的理解是 scipy 和 Qhull 计算 Delaunay 三角剖分,然后用它来计算 Voronoi 图。我认为(但可能是错误的)可以从 Delaunay 三角测量中找到邻接信息。我想知道当我生成 Voronoi 图时是否有办法从 scipy/Qhull 中提取此信息(如果存在)。

如果没有,是否有任何首选方法可以做到这一点?从长远来看,直接使用 Qhull 会更好吗?

谢谢。

0 投票
2 回答
545 浏览

numpy - 约束 Qhull 生成的 Voronoi 顶点的域

简而言之,我的问题是:是否可以限制 Qhull 生成的 Voronoi 顶点的域?如果是这样,一个人怎么能这样做?

我的上下文问题:我正在研究数据可视化,其中我在 2D 字段中有点。这些点有点重叠,所以我稍微“抖动”它们以使它们不重叠。

我目前完成这项任务的方法是使用劳埃德算法来移动这些点。Lloyd 算法本质上采用初始点位置,计算 Voronoi 图,并在算法的每次迭代期间将每个点移动到其 Voronoi 区域的中心。

这是 Python 中的一个示例:

正如我们所见,在每次迭代(第 2 帧和第 3 帧)期间,原始数据集(第 1 帧,顶部)中的点重叠越来越少,这很棒!

在此处输入图像描述

这种方法的问题是我目前正在从图中删除那些 voronoi 区域边界超出初始数据集域的点。(如果我不这样做,最外层的点会迅速射入超空间并远离其余点。)这最终意味着我最终会丢弃点,这是不好的。

我想我可以通过约束 Qhull Voronoi 域来解决这个问题,以便只在原始数据域中创建 Voronoi 顶点。

是否可以以这种方式约束 Qhull?其他人可以提供的任何帮助将不胜感激!


更新

在收到@tfinniga 的出色回复后,我整理了一篇博客文章,详细介绍了 Lloyd 迭代的有界和无界形式。我还整理了一个小包lloyd,以便更轻松地在数据集上运行有界 Lloyd 迭代。我想分享这些资源,以防它们帮助其他人进行相关分析。

0 投票
0 回答
80 浏览

matlab - MATLAB `convnhulln` 不支持 Qhull 法线选项?

假设我有一组顶点,例如V = [ 0 0 ; 1 0 ; 0 1],我想在 MATLAB 中构造它们的凸包。使用该convhulln命令,我可以提取船体侧面的顶点索引,例如convhulln(V)产量

(我最终想考虑 6D 空间中的凸包,因此该convhull命令不合适。)不过,我真正感兴趣的是显式 H 表示,即每个超平面的表面法线和偏移量方面在于。这对应于 Qhull 中convhulln声明使用的“n”选项。但是该命令convhulln(V,{'n'})只返回与上面相同的输出。我错过了什么,还是 MATLAB 根本不支持 Qhull 的“n”选项?

0 投票
0 回答
347 浏览

python - 为什么即使没有重复的输入点,scipy.spatial.Voronoi() 也会输出零区域?

为什么有些 Voronoi 区域是空的?

我有一个人的表面点云,我试图找到它的 Voronoi 图。所以我发现scipy.spatial.Voronoi(),包括一些相当不错的文档。但有时vor.regions包括空白区域,并且文档并没有完全解释它们为什么在那里。它充其量解释了与其 Delaunay 计算的关系“请注意,由于与上述 Delaunay 三角剖分类似的数值精度问题,Voronoi 区域可能比输入点少。” 但如果是这样,那只是因为 qhull 使用与用于 Delaunay 三角剖分的相似(或完全相同)的算法计算 Voronoi,才会发生这种情况。在数学上,Voronoi 区域应该为空的唯一原因是它的点是否重复

具体目标:

我希望复制本文的结果,该结果使用 Voronoi 图来计算每个输入点的法线向量。所以我可以做一个解决方法,我使用与附近点的正确计算法线相似的法线,或者我可以忽略任何给出零 Voronoi 区域的点。但我真的很想知道如何解决这些空白区域,这样我就可以尽可能多地使用输入数据。

背景和其他研究

这个答案表明Voronoi(points, qhull_options='Qbb Qc Qx')并且在文档中scipy 建议qhull_options="QJ Pp"

输入数据: http ://columbia.edu/~nxb2101/minimal_stickfig_.npy

代码:

任何形式的帮助表示赞赏;如果您不确定 qhull 为什么这样做或如何解决它,请告诉我您为从点云制作高质量网格所做的工作

0 投票
1 回答
97 浏览

python - 通过python中的插值或QHull的分散数据的轮廓

我试图从我的数据中绘制 z = .95 的轮廓,但是,我无法按照我的意愿进行插值。我尝试按如下方式使用griddata

也可以在下图中看到,我尝试通过将 z 轴切割为 0.95 来使用 qhull。

下面我试图说明这两种方法以及它本质上应该是什么样子(它只是为了说明目的而使用不同的数据),但是,由于我的数据在 (1.7, 420) 附近的下降,我在该区域的插值中出现了曲折我什至无法通过单独处理数据片段来解决这个问题,而 QHULL 方法只是错过了数据的准确性,因此我无法使用它。有什么方法可以对数据进行插值以获得类似的曲线,如下所示?

谢谢!

代码的输出

我的数据如下(x,y,z);