标签: convex

我正在寻找一个C++库,我正在处理凸目标和约束函数.

我有一个3D实体,表示为一组多面体凸壳的联合.(或者单个凸起,如果这样可以使事情变得更容易.)我想将该实体近似为一组球体的并集,以最小化集合中球体的数量和近似中的误差.(后一个目标是刻意模糊的:任何合理的误差度量都可以.同样,目标组合的方式在空中;要么球体的数量或误差度量可能受到限制,要么两者的某些功能可以最小化.我不想把自己指定到一个角落.)

近似值不需要完全包含原始集合或完全包含在原始集合中.每个球体可以具有任意半径.

这感觉就像NP完全的问题,并且在任何情况下都不太可能使用精确方法,所以我假设解决方案在于随机优化领域.感觉k-means的某些变体可能适合(将未覆盖的位置分配给它们最近的球体,并精炼球体以覆盖其中的一些),但我不确定如何处理多重覆盖的位置,或者如何找到局部的,不一定是覆盖 - 即使对于单个球体也是最佳的.此外,对于迭代方法,效率很重要,并且执行3D布尔操作不会有效.

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

编辑:

只是为了保持这个简单,

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

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

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

假设平面上有许多凸多边形,也许是地图.这些多边形可以相互碰撞并共享边缘,但不能重叠.

为了测试两个多边形P和Q是否重叠,首先我可以测试P中的每个边缘以查看它是否与Q中的任何边相交.如果找到了交叉点,我声明P和Q相交.如果没有相交,那么我必须测试P完全被Q包含的情况,反之亦然.接下来,有P == Q的情况.最后,情况是共享一些边缘,但不是全部.(最后两种情况可能被认为是相同的一般情况,但这可能并不重要.)

我有一个算法,可以检测两个线段相交的位置.如果这两个段是共线的,则不会认为它们与我的目的相交.

我是否正确列举了这些案例？有关这些案件的测试建议吗？

请注意,我不是要找到交叉的新凸多边形,我只想知道交叉是否存在.有许多记录良好的算法可以找到交集,但我不需要经过所有的努力.

我想知道两个3D凸包（vs ）之间的碰撞位置的大概3D位置和 3D法线。 AB

括号中的CPU显示了我完成的程序所需的相对CPU时间。

第1部分：抢先体验（CPU 1％）

第一步，我使用一种非常便宜的算法- 分离轴定理。
例如，我将15轴用于2个多维数据集。（在实际情况下，形状会更复杂。）
如果至少有1个可以分开的轴，return "no-collide"。
否则，请执行下一部分。

第2部分：顶点与体积（CPU 10％）

• 检查-的每个顶点A是否在内部B。
• 检查-的每个顶点B是否在内部A。

第3部分：Edge vs Edge（CPU> 20％）

有一个奇怪的情况，例如https://gamedev.stackexchange.com/questions/75437/collision-detection-3d-rectangles-using-sat。我从那里偷了图像：

因此，我还需要edge vs edge。

• 对于每对A和B的边缘（12 * 12 = 144对），在找到边缘最近点A对的边缘B。检查顶点是否在内部B。
• （反之亦然）对于每对B＆A边，检查该顶点是否在内部A。

哇，这是很多计算。
但是，还没有结束。

问题

1. 报告的碰撞位置不太准确（左：当前，右：希望）：-

   

   为了解决这个问题，我考虑过要生成一个新的凸形= A intersect B。
   有一些免费的C ++库（例如OpenMesh），但是我认为它过于占用 CPU资源。
   请注意，我不需要准确无误。

2. 有时还会报告错误的正常状态（左：当前，右：希望）：-

   

   ^这个问题可能通过增加来解决边缘 …

我的问题与普劳问题非常相似; 但有这种差异:

如何找到可以适合非凸区域的最大凸区域？

例如,考虑这个非凸区域:

任何想法或解决方案将不胜感激,谢谢.

我正试图为我解决一个相当困难的问题.我不是编程的新手,但我真的不知道如何找出这个问题.它给出了一组以Xi和Yi坐标作为输入的点(point []).该程序必须输出多边形的凸包的周长,但如果有必要,它可以将船体分成两部分,两个单独的凸包,每个将包含多个点.这种划分的目标是使周长更短(如果这两个船体的周长之和短于一个船体的周长;例如:两个远离彼此的点集群).问题还在于船体不能超过两个.我很感激任何想法.

这个问题有一个简单的例子(可能还有很多要点).在这里你可以看到两个分开的船体的周长比一个周长短.

ADD:实际上,"周长"是指周长.

这是我的代码的关键部分:

m.x = (a.x + b.x)/2;
    m.y = (a.y + b.y)/2;

    ab.first = b.x - a.x;
    ab.second = b.y - a.y;

    for (i=0; i<n; ++i)
    {
        if (p[i].x * ab.first + p[i].y * ab.second - (SQ(ab.second) + SQ(ab.first))/2 > 0)
            left[l++]=p[i];
        else if (p[i].x * ab.first + p[i].y * ab.second - (SQ(ab.second) + SQ(ab.first))/2 < 0)
            right[r++]=p[i];
        if (p[i].x * ab.first + p[i].y * ab.second - (SQ(ab.second) + SQ(ab.first))/2 == 0)
            mid[md++]=p[i];
    }

也许这更像是一个数学问题,而不是编程问题,但我一直在尝试在XNA中实现旋转卡尺算法.

我在维基百科上详细介绍了使用单调链从我的点集推导出一个凸包.

现在,我正在尝试对我的算法进行建模,以便在找到OBB之后找到OBB:http: //www.cs.purdue.edu/research/technical_reports/1983/TR%2083-463.pdf

但是,我不明白它在最终页面上提到的DOTPR和CROSSPR方法应该返回什么.

我知道如何获得两点的Dot Product和两点的Cross Product,但似乎这些函数应该返回两个边/线段的Dot和Cross Products.我的数学知识无疑是有限的,但这是我对算法所寻求的最佳猜测

    public static float PolygonCross(List<Vector2> polygon, int indexA, int indexB)
    {
        var segmentA1 = NextVertice(indexA, polygon) - polygon[indexA];
        var segmentB1 = NextVertice(indexB, polygon) - polygon[indexB];

        float crossProduct1 = CrossProduct(segmentA1, segmentB1);
        return crossProduct1;
    }

    public static float CrossProduct(Vector2 v1, Vector2 v2)
    {
        return (v1.X * v2.Y - v1.Y * v2.X);
    }

    public static float PolygonDot(List<Vector2> polygon, int indexA, int indexB)
    {
        var segmentA1 = NextVertice(indexA, polygon) - polygon[indexA];
        var segmentB1 = …

给定一个三维三角形网格,我怎样才能知道它是凸面还是凹面？有算法检查吗？如果是这样,定义公差范围以忽略小凹陷将是有用的.

^{图片来源:http://www.rustycode.com/tutorials/convex.html}

如何使用python和scipy计算凸包的质心？我发现的只是计算面积和体积的方法。

问候，坦率。