问题标签 [convex]

在python中，给定nxn网格中的m个随机点，我如何计算一个（大致）凸包，其中只能使用离散网格上的点而不是连续点来创建包？

像 scipy.spatial 这样的模块只给出连续的凸包，其中连接顶点的线是纯代数的，但我想要一个边界是离散的近似凸包。

我有一个数组V[1,2,....,n]，其中数组的每个元素以坐标对 (x,y) 的形式表示凸多边形的一个顶点。

给定V[1]是具有最小 x 坐标的顶点，并且顶点V[1,2,....,n]按逆时针方向排列，如图所示。还假设顶点的 x 坐标都是不同的，顶点的 y 坐标也是如此。

现在，我想找到具有最大 y 坐标值的顶点。我们都知道朴素的 O(n) 方法，但是有可能在 O(log(n)) 中找到它吗？

我使用V[1]具有最小 x 坐标的顶点的信息在 O(log(n)) 时间内找到具有最大 x 坐标的顶点。但是有可能做到最大y坐标吗？

谢谢您的帮助！

我的问题与这个有关：c++ Sorting 2D Points 顺时针，但不知何故，该解决方案对我不起作用。我正在尝试逆时针排序 4 个 2d 点。

这是我的代码：

示例：输入 (-4, 2), (1, 4), (0,1), (-1, 4)

输出 (-4, 2), (-1, 4), (1, 4), (0,1)

假设我有一组顶点，例如V = [ 0 0 ; 1 0 ; 0 1]，我想在 MATLAB 中构造它们的凸包。使用该convhulln命令，我可以提取船体侧面的顶点索引，例如convhulln(V)产量

（我最终想考虑 6D 空间中的凸包，因此该convhull命令不合适。）不过，我真正感兴趣的是显式 H 表示，即每个超平面的表面法线和偏移量方面在于。这对应于 Qhull 中convhulln声明使用的“n”选项。但是该命令convhulln(V,{'n'})只返回与上面相同的输出。我错过了什么，还是 MATLAB 根本不支持 Qhull 的“n”选项？

为什么通过管道推动的多边形“简单”和“凸”如此重要？

我正在使用 SFML 和 C++ 编码。我正在编写的程序必须是递归实现。

我的目标是创建一个函数，根据先前绘制的正方形，在不同的位置和旋转中递归地在屏幕上绘制一个正方形。

每个后续的正方形都应该小于前一个函数调用，并且向左旋转 45 度（从前一个正方形的左角）或前一个正方形的右侧旋转 45 度。

每个新方块都会产生另外两个方块等等。

我的想法是将正方形的左上点和右上点传递给两个不同的递归函数调用，并将这些点用作后续正方形的起点。

虽然生成的正方形也会将左上角和右上角传递给递归函数调用等。

我开发的代码没有显示应该从递归函数调用生成的两个方块。只显示了一侧。

我开发了以下代码（请原谅我的代码..我已经很久没有用 C++ 编码了..）

程序驱动程序 (main.cpp)

(PTree.hpp)

(PTree.cpp)

到目前为止，我已经尝试为函数 pTree 的第二次递归调用返回凸形的各个点。这也没有显示任何东西。

最初我只使用 Vector2f vPoint 并在每次递归调用之前对其进行修改，但在用尽我的知识库以获得解决方案后，我专门为右侧方块创建了一个名为 Vector2f vPointR 的新变量。

SFML 文档没有为像我这样的菜鸟提供足够的示例。API 本质上是一个选项列表，每个函数都有最少的示例（如果有的话）。我已经尽我所能搜索互联网，看看我是否通过了错误的点，但找不到答案。

确实有效的一件事（虽然不完全正确）是当我切换递归调用时......这意味着我在调用左侧方块之前移动了右侧方块的调用，但问题是左侧s 方块没有显示。

在这一点上，我也在尝试为每个正方形计算出正确的旋转，但这是我遇到的最少的问题。

我尝试递归显示这些方块的方式有问题吗？

除了 Stack Overflow 寻求帮助之外，我不知道从这里去哪里。

感谢您的时间和专业知识。

我正在尝试使用 cplex opl 并遇到错误。我阅读了手册并用谷歌搜索，但由于缺乏知识，我仍然不知道应该如何解决这个错误。任何人都可以帮助或给我一些想法来解决这个问题吗？我真的需要你的帮助。

我正在编写一个混合整数编程模型。我运行配置并收到此错误：

错误 5002：“NachfrageAusZUgeordnetenDZs#0#0”不是凸的

这是约束的代码：

约束

有人可以告诉我为什么会收到此错误吗？为什么约束不是凸的？我怎样才能改变它以使其工作？

提前感谢您的时间和精力！

我正在尝试最小化以下类型的函数：

在 MATLAB 中使用 CVX，CVX 输出“Status: Unbounded Optimal value(cvx_optval): -Inf"

这是不合理的，因为它是一个强凸函数。知道为什么我会得到这个以及如何解决它吗？

例如，为了获得这种类型的输出，我运行了一个简单的示例：

I am currently trying to implement a simple continuous collision detection system. I wondered whether it was possible, for a moving AABB, to compute the distance it can translate in an arbitrary direction d before it intersects a convex polyhedron. Here is a simple explanation in 2D:

What I want here is the length of the green lines (the orange AABB is the initial position, and the red AABB is the position where both colliders intersect).

This is also equivalent to trying to raycast the minkowski difference A⊕-B from the origin in the direction d, where A is my static convex polyhedron and B my moving AABB:

But computing a minkowski difference seems to be really performance-consuming, so I would like to know if a fast algorithm for doing that exists.

When Googling, I saw an algorithm to do that called GJK, but it only seems to return the overall minimum distance, and not the directional distance.

Thanks in advance for your answers!

PS: Please excuse my poor english and my total lack of artistic talent using paint.

我正在检测图像中的对象并从轮廓创建蒙版。然后将面膜扩张并平滑。例如，从这样的图像：

我最终得到了这样的面具：

当我使用蒙版裁剪图像（椅子）时，我丢失了椅子腿之间的（背景）信息。为了解决这个问题，我想把这个凹面罩变成凸面罩。例如，进入这个（在 Photoshop 中创建）：

我怎样才能做到这一点？：

代码（show_mask.py）：

helpers_cv2.py：

_{全尺寸图像和代码可以在这个存储库中找到。}