标签: convex-hull

我有一套积分.我想把它们分成两组.为此,我选择两个点(a和b)并在它们之间绘制一条虚线.现在我想让一行中从这一行留下的所有点和另一组中从该行开始的那些点.

如何判断任何给定点z是左侧还是右侧？我试图计算azb之间的角度- 小于180的角度在右侧,大于180在左侧 - 但由于ArcCos的定义,计算的角度总是小于180°.是否有公式计算大于180°的角度(或选择右侧或左侧的任何其他公式)？

我在numpy中有一个坐标点云.对于大量的点,我想知道点是否位于点云的凸包中.

我尝试了pyhull,但我无法弄清楚如何检查点是否在ConvexHull:

hull = ConvexHull(np.array([(1, 2), (3, 4), (3, 6)]))
for s in hull.simplices:
    s.in_simplex(np.array([2, 3]))

引发LinAlgError:数组必须是正方形.

假设我有个的以随机顺序阵列,并且我需要找到一个多边形(由对它们进行排序,使得每对相邻的表示的一侧)穿过所有的点,并且其两侧是不相交的进程.

我尝试通过选择一个点,并将所有点添加到其下面的最终数组,从左到右排序.然后,添加其上方的所有点,从右到左排序.

我被告知我可以添加一个额外的点并自然排序以避免自我交叉..虽然我无法弄明白.有什么简单的方法可以做到这一点？

标准凸包算法不适用于(经度,纬度)点,因为标准算法假设您需要一组笛卡尔点的船体.纬度 - 经度点不是笛卡尔坐标,因为经度在反子午线(+/- 180度)处"环绕".即,经度179以东两度是-179.

因此,如果您的一组点恰好跨越反子午线,您将计算出错误地在世界各地伸展的虚假船体.

我可以使用标准凸包算法来解决这个问题的任何建议,或指向正确的"地球"船体算法？

现在我想起来,有更多有趣的案例需要考虑而不是跨越反梅迪安.考虑一个包围地球的点"带" - 它的凸包将没有东/西边界.或者甚至更进一步,{(0,0),(0,90),(0,-90),(90,0),( - 90,0),(180,0)}的凸包是什么？ - 它似乎包含整个地球表面,所以它的周边有哪些点？

给定一组积分S (x, y, z).如何找到convex hull那些点？

我尝试从这里理解算法,但是得不到多少.

它说:

首先将所有点投影到xy平面上,并通过选择具有最高y坐标的点然后执行礼品包装的一次迭代以确定边缘的另一个端点来找到肯定在船体上的边缘.这是不完整船体的第一部分.然后我们迭代地构建船体.考虑这第一个优势; 现在找到另一个点,以形成船体的第一个三角形面.我们通过选择点来使得所有其他点位于该三角形的右侧,当适当地观察时(就像在礼品包装算法中一样,我们选择边缘使得所有其他点位于右侧)那边缘).现在船体有三条边; 继续,我们任意选择其中一个,并再次扫描所有点以找到另一个点来构建具有此边缘的新三角形,并重复此直到没有剩余边缘.(当我们创建一个新的三角形面时,我们向池中添加两条边;但是,我们必须首先检查它们是否已经添加到船体中,在这种情况下我们忽略它们.)有O(n)个面,每次迭代需要O(n)时间,因为我们必须扫描所有剩余的点,给出O(n2).

任何人都可以用更清晰的方式解释它或建议一种更简单的替代方法.

给出飞机上的n个点.No 3是共线的.

给定数k.

找到k个点的子集,使得k个点的凸包具有k个点的子集的任何凸包的最小周长.

我可以想到一个天真的方法在O(n ^ kk log k)中运行.(找到大小为k的每个子集的凸包并输出最小值).

我认为这是一个NP问题,但我找不到任何适合减少的东西.

有人对这个问题有什么想法？

一个例子,

the set of n=4 points {(0,0), (0,1), (1,0), (2,2)} and k=3

结果:

{(0,0),(0,1),(1,0)}

由于该组包含3个点,因此结果的凸包和周长小于任何其他3个点的周长.

我正在寻找一种算法,用于寻找从给定点集形成凸多边形的最大点子集(通过最大数量,我的意思是数量).我认为这可能是使用DP解决的,但我不确定.是否可以在O(n ^ 3)中执行此操作？实际上我只需要最大子集的大小,因此它不需要有唯一的解决方案

编辑:

只是为了保持这个简单,

给定输入:2D中的一组点

期望输出:形成凸多边形的最大点数,如示例中输出为5(ABHCD是可能的凸多边形之一)

有一个类似的问题spoj.com/problems/MPOLY可以在O(N ^ 3)中使用DP解决,我的问题是关于该问题的概括,它不必包含(0,0)

scipy ConvexHull(参见http://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.ConvexHull.html)对象中的"area"属性的值似乎不是(我理解为be)凸壳的面积.另一方面,"体积"的值似乎确实是凸包的面积.

from scipy.spatial import ConvexHull
import numpy

points = numpy.array([[-1,-1], [1,1], [-1, 1], [1,-1]])
hull = ConvexHull(points)

print("Volume is %2.2f" % hull.volume) # Prints 4.00
print("Area is %2.2f" % hull.area) # Prints 8.00

在上面的例子中,我预计4点凸壳的面积为4.0.那就是"音量".那么"地区"给了我们什么？

qhull库(qhull.org)有几个例子可以在他的网站上开始,但是关于C++的所有信息对我来说都不是很有用.

我试图制作一个简单的3D点凸壳,我从一个文件中读取,我不能使用在调用qhull.exe作为外部应用程序的网站中建议的技术,因为我需要制作几个凸包从我在数据点中做出的一些修改.

我找不到这样做的简单例子,有人可以帮我完成这项任务吗？任何信息都会有用.

谢谢

我使用scipy.spatial.ConvexHull创建了一个凸包.我需要计算凸包和光线之间的交点,从0开始并在某个其他定义点的方向上.已知凸包含0,因此应保证交叉.问题的维度可以在2到5之间变化.我尝试了一些谷歌搜索,但没有找到答案.我希望这是计算几何中已知解决方案的常见问题.谢谢.