标签: convex-hull

我有一大堆顶点,其中一些是边,一些是冗余的(在形状内),我想删除它们.

我能想到的最简单的算法是,如果它们碰到其他人形成的形状,则逐个检查.但它应该是一个非常慢的算法.

我想过从边缘挑选一个(距离每个例子最远的一个)并计算从这个开始的最长路径...应该得到边缘路径,对吗？

有什么建议吗？

我需要为类赋值创建一个2D凸包函数,我想要一个比赋值更强大的测试用例.有没有人知道一个大的测试案例(25 <n <100)的解决方案？

尝试绘制ConvexHull使用ComputationalGeometry包中的PlanarGraphPlot,它在图形中使用时不起作用.

关于如何使用Graphics绘制ConvexHull的任何想法？

我想使用minkowski和来预测两个凸形之间的确切碰撞点.根据我的理解,速度矢量与minkowski和相交的点是我必须沿着矢量移动我的物体的量,所以它们只是触摸(我已经知道它们会碰撞).这是我的意思的一个例子(为简单起见,我只使用了矩形):

我的意思是我可以计算与凸包的每一条线的交点,并且只使用最接近的但是看起来非常低效.我的想法是计算最接近向量的单纯形,但我不知道如何做到最好.我发现了一种算法,它可以计算物体之间的最小距离,或者更精确地计算从minkowski总和到原点的最小距离(http://www.codezealot.org/archives/153).该算法的一部分试图找到最接近原点的单纯形,这是我想做的事情.我试图改变它以满足我的需求,但我没有成功.对我而言,听起来应该有一个非常简单的解决方案,但我对矢量数学并不是那么好.

我希望我的问题可以解决,因为我的英语不太好:D

我有一组点,想找到凸壳.当我把它们交给scipy.spatial(ConvexHull或Delaunay)时,我只能得到原来的一组点.通过施工,情况不应该如此.

以下是作为酸洗numpy数组的点.我的代码如下:

import pickle
from scipy import spatial
import matplotlib.pyplot as plt

points = pickle.load( open( "points.p", "rb" ) )

hullpoints = spatial.ConvexHull(points).points


# plot points
fig = plt.figure()
ax = fig.gca(projection='3d')
# ax.plot(points[:, 0], points[:, 1], points[:, 2], 'r.') # original points
ax.plot(hullpoints[:, 0], hullpoints[:, 1], hullpoints[:, 2], 'r.') # convex hull of points


# set labels and show()
ax.set_xlabel('Player 1')
ax.set_ylabel('Player 2')
ax.set_zlabel('Player 3')
plt.show()

显然有些这些点是内部的凸包,并应通过spatial.ConvexHull(点)或spatial.Delaunay(点)被移除,如在给定的2D例子完成这里.

有谁知道为什么我得到了原来的一套积分？我可以蛮力找到外部点并仅绘制那些(最终目标是由点近似的外部形状的表面图),但似乎scipy.spatial应该能够做到这一点.

除了CGAL python绑定之外，python中的3维中是否存在“ alpha形状”函数？

或者，是否可以将下面的示例扩展到3D中？

2D示例：在matplotlib中，在散点图中的数据点周围绘制平滑多边形

我目前正在使用此ConvexHull示例计算体积，但出于我的目的，由于“凸”约束而使体积膨胀。

谢谢，

我正在使用scipy.spatial包http://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.ConvexHull.html#scipy.spatial.ConvexHull制作一个凸包.

我试过搜索,但还不知道是否有一种简单的方法可以找到是否有任何点(纬度/经度)位于凸包内.有什么建议？

我有一个vertices形状 (N,3) 的 numpy 数组，其中包含 3D 球形多边形的 N 个顶点，即所有这些点都位于球体的表面上。球体的中心和半径已知（以单位球体为例）。我想绘制由这些顶点包围的球形多边形。（从数学上来说，我想绘制这些顶点生成的球凸包）。

我该如何使用 来做到这一点matplotlib？我尝试过Poly3DCollection，但这只绘制了欧几里得多边形。plot_surface我设法用这样的方法绘制了整个单位球体：

u = np.linspace(0, 2 * np.pi, 100)
v = np.linspace(0, np.pi, 100)
x = np.outer(np.cos(u), np.sin(v))
y = np.outer(np.sin(u), np.sin(v))
z = np.outer(np.ones(np.size(u)), np.cos(v))
ax.plot_surface(x, y, z, rstride=5, cstride=5, color='y', alpha=0.1)

我想人们可以手动计算要从中删除哪些点x, y, z，然后仍然使用这些点plot_surface来绘制多边形。这是正确的使用方法matplotlib还是它有另一个我可以直接使用的模块？

如果没有方便的方法来做到这一点matplotlib，你能推荐任何其他库吗？

我一直在以多种不同的方式解决这个问题，经过一个月的尝试，我认为是时候用新的眼光来审视它了。我正在尝试制作一个图像缩放应用程序，用于重新调整 8 位精灵的大小并将它们转换为矢量图像。到目前为止，我所做的工作是这样的；它获取图像，将其分解为形状（具有相同颜色的相邻像素的区域），然后形状中的每个像素被四个像素替换：

private Point[] expand(int x, int y){\n    x *= factor;\n    y *= factor;\n    return new Point[]{new Point(x+half_factor,y), new Point(x+factor,y+half_factor),\n            new Point(x+half_factor, y+factor), new Point(x,y+half_factor)};\n}\n

这四个点中的每一个都被放入一个二维布尔数组中：

private void placePoint(int x, int y){\n    table[x][y] = !table[x][y];\n    extrema(x,y);\n}\n

单个形状的结果如下所示：

现在我想将所有这些点（减去内部的点）变成一个多边形，并且我尝试了许多不同的解决方案，最近我一直在尝试找到最近的邻居，直到它开始，但是每个算法我尝试失败。对于这个特定的示例，它到达右下角的 goomba，该 goomba 是颠倒的，并且在其左侧的像素簇中变得混乱。该程序认为路径已完成，并从那里创建一条到左上角的线，完全忽略左下象限中的点。

这就是我想要的样子：

以下是一些在我的情况下始终正确的事情，可能有助于找到有效的算法：

\n
1. 所有点列表中的第一个点是最外面路径的一部分
\n
2. 最外面路径中的每个点都有一个距离它 C 个单位或距离它 \xe2\x88\x9aC 个单位的邻居
\n
3. 最外面的路径始终是闭合路径
\n

任何帮助都感激不尽！

更新：

我已经尝试了下面的所有解决方案和建议，并取得了一些进展，但仍然没有得到所需的输出。

原来的：

输出：

最终更新： …

我读到了计算凸壳的算法.大多数都需要O(n*log(n))时间,n输入点的数量在哪里.

我们S = {p_1, p_2, ..., p_n}是一组由x坐标进行排序,即点,p_1.x <= p_2.x <= ... <= p_n.x.

我来描述计算的凸壳的算法S,CH(S)在O(n)时间.另外,我还必须分析算法的运行时间.