标签: convex-hull

我有给定为一组的三元组的3D表面(X_I,Y_I,z_i),其中X -1和Y_I大致在网格上,并且每个(X_I,Y_I)具有单个关联z_i值.典型的网格是20x20

我需要在给定的公差范围内找到哪些点属于表面的凸包.我正在寻找一种有效的算法来执行计算(我的客户提供了一个O(n³)版本,在400点数据集上需要大约10秒......)

我在 numpy 中有一组点，我通过 (scipy.spatial.ConvexHull 而不是 scipy.spatial.Delaunay.convex_hull) 计算它们的 ConvexHull，现在我想知道我是否向我的数组添加新点是这个点位于点云与否？在 numoy 中最好的方法是什么？

我应该提到我看到了这个问题并且它没有解决我的问题（因为它使用 cipy.spatial.Delaunay.convex_hull 来计算 ConvexHull）

我想围绕使用 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：buildConvexHull 函数中超出了最大调用堆栈大小：

allBaseLines.push(baseLine)

我的代码在小提琴中，但它不起作用... http://jsfiddle.net/gvFrd/5/

我有一个没有特定顺序的线段列表。

我想找到由线段形成的所有封闭空间（多边形）。有没有一种有效的算法或方法可以用来做到这一点？

下图说明了这个问题。给定黑色线段，如何检测绿色多边形？

OpenCV函数中convexityDefects()用于计算轮廓的凸度缺陷的算法是什么？

请描述和说明该算法的高级操作，以及其输入和输出。

如果每个点的每个坐标是p/q形式的有理数,并且p和q的有界值,则表明在平面中n个点的凸包可以在O(n)时间内计算.

注意:这是一个家庭作业问题.我可以想到以某种方式避免扫描所有点使用Jarvis March.也许这可以通过向固定方向投射光线(使用合理条件)来检查下一个点存在的位置来完成.

如果我知道我的点总是排列成两个矩形,是否有优化的方法来获得凸包？

我编写了经典的凸包算法(仅通过枚举所有点),但由于我有一堆矩形对,如果可能有更有效的方法来处理这种特殊情况,我就会徘徊.

这就是我所说的,澄清一下:

我尝试以各种方式对点进行排序,但我找不到优化它的一般规则.基本的凸壳算法是否也是最有效的方法呢？

更新

为了澄清我的最终目标,我已经将~100个矩形分组成两对,以及数千个点,我必须实时检查它们是否位于每个凸包内.现在我已经考虑了一下,我猜凸壳部分不会成为整个操作的瓶颈(但仍然有~100个,我的目标是实时60fps处理),所以我可能也可以使用@BartKiers建议的普通ol算法,然后在分析后再回到这个算法.

我会暂时搁置这个问题,或许某人有一个优化的想法,无论如何都可能有用.

我想知道是否有任何基于 numpy 的工具可以：

1. 给定一个 3D 二进制输入 numpy 图像，找到它的凸包；
2. 并返回此 3D 凸包内的体素（3D 像素）的索引或类似列表。

一种可能性是使用skimage.morphology.convex_hull_image()，但这仅支持 2D 图像，因此我必须逐个切片（在 z 轴上）调用此函数，这很慢。[编辑：见下面的注释。]

我绝对更喜欢更有效的方式。例如， scipy.spatial.ConvexHull() 可以获取 N 维空间中的点列表，并返回一个凸包对象，该对象似乎不支持查找其凸包图像/体积。

points = np.transpose(np.where(image))
hull = scipy.spatial.ConvexHull(points)
# but now wonder an efficient way of finding the list of 3D voxels that are inside this convex hull

任何想法如何？请注意效率对我的申请很重要。谢谢！

更新：同时，convex_hull_image()已经扩展到支持 ND 图像，但对于中等大小的数据来说速度很慢。下面接受的答案要快得多。

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

library(geometry)
x1 <- rnorm(100, 0.8, 0.3)
y1 <- rnorm(100, 0.8, 0.3)
ConVexHull<-convhulln(cbind(x1,y1),"FA")

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

我知道如何使用 chull 函数进行绘图，但我不确定 chull 是否提供与 convhulln 相同的外壳

  Plot_ConvexHull<-function(xcoord, ycoord, lcolor){
  hpts <- chull(x = xcoord, y = ycoord)
  hpts <- c(hpts, hpts[1])
  lines(xcoord[hpts], ycoord[hpts], col = lcolor)
} 
xrange <- range(c(x1))
yrange <- range(c(y1))
par(tck = 0.02, mgp = c(1.7, 0.3, 0))
plot(x1, y1, type = "p", pch = 1, col = "black", xlim = c(xrange), ylim =    c(yrange)) …

I have character images like this:

After getting contours and convexHull the output is like this:

For that I used following code:

import cv2
img = cv2.imread('input.png', -1)

ret, threshed_img = cv2.threshold(cv2.cvtColor(img, cv2.COLOR_BGR2GRAY),
                        127, 255, cv2.THRESH_BINARY)
image, contours, hier = cv2.findContours(threshed_img, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_NONE)
for cnt in contours:
    # get convex hull
    hull = cv2.convexHull(cnt)
    cv2.drawContours(img, [hull], -1, (0, 0, 255), 1)    
cv2.imwrite("output.png", img)

As you can see in the following image there are identified contours which are vertically aligned with …