问题标签 [convex]

我正在制作自己的简单 2D 游戏引擎，我想使用分离轴定理来检测碰撞，但它要求对象是凸多边形，我真的很希望能够以简单的方式创建这些多边形，因为每个物理对象在我的游戏中，需要将自己的多边形映射到它，因此为每个对象手动创建这些多边形（通过提供多边形的每个顶点的像素坐标）会非常痛苦。

有没有更好的方法来做到这一点？

我需要找到一种算法，该算法从给定的一组Ssize点计算凸包n。我知道正好有 6 个点形成S凸包。

计算这个的最好和最有效的方法是什么？

我考虑过从S（n选择6个点）生成所有可能的点组合，这将花费O（n ^ 6），然后检查这是否是一个凸包，这将花费O（n）但会导致非常糟糕的总运行时间。一定会有更好的办法。有什么提示吗？

如何检查多边形是凹的还是凸的？使用openGL。我将点作为 .txt 文件的输入，然后用这些点绘制一个多边形，然后问题就来了。我需要一种算法来检测多边形的类型。凹或凸。

}

我最近对足球统计感兴趣。现在我想在 Python 3.5 ( paper-link ) 中实现著名的 Dixon-Coles 模型。

基本问题是，从论文中描述的模型中，得到了具有大量参数的似然函数，需要将其最大化。

例如：一个德甲赛季的似然函数会产生 37 个参数。当然我做了相应的负对数似然函数的最小化。我知道这个log函数是严格凸的，所以优化应该不会太难。我还包括了分析梯度，但是当参数数量超过 ~10 时，来自SciPy-Package的优化方法会失败（scipy.optimize.minimize()）。

我的问题： 还有哪些其他优化技术最适合涉及约 40 个独立参数的优化问题？

对其他方法的一些提示会很棒！

我误解了逻辑回归公式推导中最小值背后的想法。

这个想法是尽可能地增加假设（即正确的预测概率尽可能接近 1），这反过来又需要尽可能地最小化成本函数 $J(\theta)$。

现在有人告诉我，要让这一切发挥作用，成本函数必须是凸的。我对凸性的理解要求没有最大值，因此只能有一个最小值，即全局最小值。真的是这样吗？如果不是，请解释为什么不。此外，如果不是这种情况，那么这意味着成本函数中可能存在多个最小值，这意味着多组参数会产生越来越高的概率。这可能吗？或者我可以确定返回的参数是指全局最小值，因此是最高概率/预测？

我需要一种快速算法来找到大型简单封闭多边形的凸包。

Lee 的算法（如此处第 2.1 节所述）在大多数情况下都很好，但不是所有情况。例如，顺时针多边形 (3,3)-(1,2)-(2,1)-(2,2)-(3,0)-(0,1)-(0,3)-(3 ,3) 将得到解决方案 (3,3)-(2,1)-(0,1)-(0,3)-(3,3) - 它不包括所有顶点。

错误是 (2,2) 被放入堆栈。我看不出如何修改 Lee 的算法来纠正这个问题。你能？

当然，我可以改用 Melkman 的算法，但 Lee 的算法利用了我的条件，使它更简单、更快速，如果可能的话，我更喜欢它。此外，我很惊讶文献中的 Lee 算法据说是正确的。

我将尝试使用此处的修改代码来解释我的问题： https ://stats.stackexchange.com/questions/22805/how-to-draw-neat-polygons-around-scatterplot-regions-in-ggplot2

在我的示例中，我使用 Iris 数据集。

到目前为止，我的尝试已经产生了这个结果：

我的目标是在有壳散点图上绘制双箱线图（boxplotdou） - 具有相同的尺寸。当前代码是：

我试图在 ggplot() 中插入 boxplotdou(... 但出现错误：“不知道如何将 o 添加到绘图中”。

任何帮助，将不胜感激。

-卡里

我们如何制定一个线性规划来告诉我们任意点 x[ j ] ∈ X，其中 X = {x1, ... ,xn} ⊂ Rn 是否是 X 的凸包的极值点，即 conv( X）？

根据这个线性规划的解，我们应该能够断言“是的，x[ j ] 是一个极值点”，或者“不是”。

好吧，我的想法是这样的：

{min: 0} s.t. x[ j ] = Σi ( a[ i ] * x[ i ] ); i ∈ {1, ... ,k}, ∀ j ∈ {1, ... ,k}

如果存在这样的 a[ i ] ，则意味着 x[ j ] 是其他 x 的线性组合，这似乎违反了极值点的定义。

但是，我相信这张 LP 并没有涵盖整个背景。即，如果我们选择一个位于 conv(X) 内部（不在边缘上）并且不是其他人的线性组合的 x[ j ] 怎么办。然后该模型将导致错误的结果。在我看来，如果 选定的 x [ j ] 位于 conv(X) 的边缘，则上述模型会很好。

谢谢。

我有一组形成 2d 多边形的 3d 点。它们按顺时针或逆时针顺序排列（一个或另一个，但我事先不知道哪个）。

现在，我想对它进行三角测量，我正在尝试通过使用切耳方法来做到这一点。问题是，为了让算法起作用，我需要检查给定的角度是否是凹的。

在二维空间中，按顺时针顺序，您可以使用叉积并查看结果箭头的方向以了解角度是否为凹角（因为您正在有效地检查它是左转还是右转）。但是，不知道我的点是顺时针还是逆时针，也不知道平面的法线，我不知道如何解决这个问题。

有一些类似的问题，例如this one，但它们假设为 2d 空间，这使事情变得更容易。

我正在寻找一种算法，该算法可以将包含一组非重叠凸多边形的区域作为输入，并将多边形外部的空间分解为一组非重叠凸四边形。四边形需要具有它们（单独）使用尽可能多的水平空间的特性。

这是输入：

这是所需的输出：

我觉得我已经看到了这种算法的一些变体，用于计算在非常古老的绘画程序中要被洪水填充的区域。有没有比O(n^2)时间更好的方法来做到这一点？

编辑：我意识到输出中有一些三角形。我可能应该说四边形是所需的输出，只有在物理上不可能使用四边形时才回退到三角形。