问题标签 [convex]

我正在寻找一种算法来查找从给定点集形成凸多边形的最大点子集（我的意思是数量上最大的）。我认为这可能可以使用 DP 解决，但我不确定。是否可以在 O(n^3) 中做到这一点？其实我只需要最大子集的大小，所以它不需要有唯一的解决方案

编辑 ：

只是为了保持简单，

给定输入：二维中的一组点

期望输出：形成凸多边形的最大点数，如示例中的输出为 5（ABHCD 是可能的凸多边形之一）

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

我正在创建一个在 JavaFX 中有地图的工具。我必须在该地图上绘制一个现有的多边形，以便在其上为定位服务创建区域。然后我想点击地图上的某个地方，为这个多边形添加一个新角。现在，向多边形添加一个角并不难。当我用鼠标右键单击地图上的某个地方时，我想在那里创建一个新角。但我想在“正确”位置添加那个角，这意味着在最接近新角的现有角之前或之后，而不是在多边形的末端。此外，新的多边形不应穿过 esiting 多边形（参见本文末尾的图片）。

我使用毕达哥拉斯定理来找到最近的点，但我现在的问题是，我不想在这个最近的角落之前或之后添加那个角落。

这应该是结果，老实说，我没有找到我想要的多边形是如何正确调用的。

I have two 2D convex polygons. I want to

• subtract one from the other one and
• add one to the other one

The resulting polygon must be either concave or a - better - a set of convex polygons (e.g. triangles).

Do you have any idea how I can accomplish this?

我得到了一个直角棱镜（即一个盒子）和一个任意的凸面实体，使得该盒子与上述实体的 AABB（轴对齐边界框）相匹配。

我想从盒子中“雕刻出”实体，并在这样做时将盒子分成几个围绕实体面的凸段（希望，如果实体有n 个面，则有n 个段）。基本上，在盒子上打一个实心形状的孔。这是我的意思的图片：

但是，这也必须适用于这样的形状：

我认为，问题在于，轴对称形状（如直棱柱和金字塔）比中心对称形状（如球体）要容易得多（如您所见，球体不是正确的球体；它们具有有限数量的平面）。我正在寻找一种适用于任何实体的通用算法，无论它多么复杂、旋转或倾斜。

我有一篇论文中的编程公式，想给它一个解决特定问题的工具。作者将其称为线性规划 (LP) 实例，但我不确定。配方有点像如下：

我尝试通过cplexqcp函数对其进行编程（由于二次约束，但约束不包含任何x_i^2变量）。但是我收到CPLEX Error 5002: Q in %s is not positive semi-definite error. 这是具有非凸约束的非线性规划的一个实例吗？我可以使用CPLEX或使用NLP工具来解决它吗？我是LP/NLP员工的新手（不参加任何关于他们的课程），所以非常欢迎帮助解释我的问题答案的细节。

非常感谢。

我有代表自由形式对象横截面的`System.Windows.Media.Point3D 集合。

它总是或多或少的形状像“海鸥翅膀”，“M”图案，有两个凸出的凸起，中间有一个“山谷”。它在空间上的方向是任意的，不能保证中央山谷是横截面中唯一的凹陷。

我已经有一种方法可以检测一个保证位于这些山谷之间的点，现在我想找到代表围绕中心点的“双切线”的一对点，即在两点之间经过的线保持所有其他点在同一侧，这也限制了起点。

下图显示了我想要实现的目标：

我相信叉积是找出三个点是“凹”还是“凸”的好方法，但还没有弄清楚如何执行循环（如何开始，增加什么以及何时停止）。

另外，虽然我可以使用蛮力（不是那么多点），但这肯定会伤害我的感情。

我有一个组成蠕虫轮廓的有序点向量（用opencv找到）。我试图沿着蠕虫的骨架获得积分。我想非常快地做到这一点，所以有一个简单的分割功能：

这个函数的问题是当蜗杆弯曲很多时，即轮廓在一侧变得凹入，骨架切掉了角落，不再代表蜗杆的中心。我的解决方案是，如果它们是凹的，则移动段末端，纠正段和骨架。

关于一个非常省时的函数的任何建议，它将找到轮廓上的所有凹（或凸）点？

问题图片：

我在 Matlab 中创建了 3D 凸包图。似乎在这个函数中，一些激光点用于凸包的刻面，但其他一些点位于凸包内部。我的问题是如何在 Matlab 中分别识别这些点。哪种方法适用于计算位于凸包内部的这些点到最近的凸包小平面的垂直距离（从每个点到凸包最近小平面的距离）？如果您能向我介绍一些关于凸包函数的参考资料，我将不胜感激。

我正在尝试解决一些可以映射到凸优化问题中的问题。特别是用于分析量子态断层扫描数据。

在 Matlab 中有一些工具可以帮助你做到这一点，比如 SeDuMi 或 CVX

http://sedumi.ie.lehigh.edu http://cvxr.com/cvx/

但我在 Mathematica、网络或论坛中找不到类似的东西。

有人知道在 Mathematica 中是否有一种简单的方法可以实现这种算法？

我想避免被迫切换到 Matlab 来解决这个问题。没有什么反对的，但我拥有在 Mathematica 中开发的这种状态断层扫描的大部分程序。

非常感谢。

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

或者，有没有办法将下面的示例扩展到 3D？

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

我目前正在使用这个ConvexHull示例计算体积，但出于我的目的，由于“凸”约束，体积被夸大了。

谢谢，