问题标签 [non-convex]

我有一个纬度列表，它围绕中心点形成一个多边形。我想顺时针得到 Lat-Long 的有序列表，以便连接该有序列表中的 Lat-Long 顶点并形成非凸多边形。

我有 20 到 30 个随机生成的 3D 点作为定义多面体的顶点。我曾尝试使用DelaunayTri(points)枚举面并使用叉积的行列式来计算和求和四面体体积，但我不确定它是否适用于非凸面的多面体。

另一种可能的方法是将凹多面体划分为凸多面体（通过检测凸包内的点），但这种不相交划分的算法让我望而却步。

另外，如何绘制这样一个凹形船体？

我有一些图像，其中包括凸多边形和非凸多边形。每个图像都包含一个多边形。我需要检测角坐标并需要按顺时针或逆时针顺序对它们进行排序。对于凸多边形，我使用Harris 角点检测来检测角点，使用凸包对点进行排序。但我不知道如何对非凸多边形进行排序。由于我的输入是图像，我认为一些图像处理技术可能有助于通过沿着多边形边缘移动来对它们进行分类。有没有复杂度最低的方法？

示例图像：

我随机命名了角落。

预期输出：

我希望按此顺序 1 3 5 9 4 2 8 7 6 10或1 10 6 7 8 2 4 9 5 3. 你可以从任何时候开始，不一定1

编辑1：

在rayryeng 的解决方案适用于所有凸多边形以及一些非凸多边形之后，有一些非凸多边形与他的算法不匹配。

这是一个例子

我正在计划通过带有两个嘴的凹双对称六边形来可视化流动。

边 d1 的长度等于边 d2 的另一个长度的示例：

我最初在这里讨论的关于不规则六边形的命名。

有标准的网格工具，您可以在其中绘制自己的网格，但我想要一些标准库，这样我以后可以与其他人更好地合作进行流模拟。我没有在 MathCentral File Exchange 中找到任何 Hexagons 网格库。

是否有任何用于不规则六边形形状的标准网格库？我也对任何其他语言持开放态度，因为我可以阅读代码并将这些标准转换为 Matlab 库。

假设我有重叠的多边形。两者都不一定是凸的。什么是找到它们内部而不是边界上的点的有效算法？

假设它们重叠，并且我们的多边形由它们的 3D 顶点集定义。

手头的问题是与 3D 空间内的 2D 增长有关的科学模拟的一部分。2D 形状通过将（三角形）段添加到先前增长的形状来增长。

请注意，3D 中的实际段具有厚度，因此，我的代码实际上适用于三角棱镜。

在某一时刻，这些 2D 形状（具有任何相对方向和位置）发生碰撞。

如果其中一个新的三角棱柱与先前插入的线段相交，我只想插入与先前插入的线段不相交的线段的“部分”。如下所示，标记为 T1 和 T2 的段。

在第一步中，我计算了所有相交边到面。然后，我使用 3D 中的 CGAL Delaunay Triangulation 包对四面体网格中的结果点集进行网格划分。最后一步，我扔掉所有与之前插入的线段相交的四面体。在大多数情况下，这很有效——但我现在确信这个想法由于根本原因而行不通。

有什么更可靠的计算方法？

我正在使用 Scipy 的LBFGS实现来最小化非凸目标函数。结果还不错。但收敛状态为“ABNORMAL_TERMINATION_IN_LNSRCH”。

这可能是因为我的目标函数是非凸的吗？或者这是否意味着我的梯度（手动分析计算并作为参数传递给 Scipy 的 LBFGS）是错误的？

我需要优化一个非凸问题（最大似然），当我尝试二次优化算法（如 bfgs、Nelder-Mead）时，它无法找到极值，而是经常得到鞍点。

您可以从这里下载数据。

现在，我决定进行网格搜索并尝试了 scipy.optimize.brute，但我收到了这个错误。事实上，我的真实变量是 47，我把它减少到 31 来工作，但仍然没有。请帮忙。

你知道非凸 QCQP 求解器吗？对于学者或学生来说，免费软件将是一件大事。我试图找到这样的求解器但没有成功......

我的问题是以下形式：

• 具有线性（严格和非严格）不等式
• 在不等式之间具有逻辑约束（例如等价、含义）
• 令 X = {x1, ..., xn} 是一组变量，而 Y = {y1, ..., ym} 是一组变量。二次约束的形式如下：
  • x1 = x1y1 + x2y2
  • x2 = x1y3 + x3y4
  • x3 = x2y5 + x1y6
  • ...
  • 左侧 X 的一个变量
  • 等式约束
  • 系数等于 1 的两个变量的乘积之和
  • st 两个变量的每个乘积仅出现在 X 的一个变量和 Y 的一个变量之间。

目标函数是线性的。

谢谢您的帮助

我有兴趣L0-norm在 matlab 中绘制惩罚函数。

事实上，我知道L0-norm向量x的 || x ||_0，返回一个值，该值指定x中非零元素的总数。换句话说，|| x ||_0 = #(i | xi !=0)。

例如，对于 x 的 L1 范数，它返回 x中元素的绝对值之和。绘制 L_1 范数惩罚函数的 matlab 代码是：

但是现在 L_0 范数呢？

任何帮助将不胜感激！