问题标签 [convex]

想象一下，你有一条曲线。你怎么能把它变成一条直线？你知道任何可以帮助我的论文或算法吗？我知道我这样做的一种方法是定义能量函数。但是，我不知道标准可能是什么。我的问题不是简单的曲线，比如半圆。附上曲线示例。我认为将点投影在 x 轴或 y 轴上的线上不是一个好的选择。

谢谢！

我是 cvx 的新手，在解决以下凸问题时出错：

在上述公式中，L=|E|、“p”和“m”被赋予正实数指数。这是我的代码：

我猜代码的第一部分（目标函数）有问题，这会导致以下严格的凸编程错误：

但是，我不知道如何解决它。

我有优化问题。我需要找到从圆内点到圆周长的最短路径。约束的函数是凹的。为了使它起作用，我需要将此凹函数更改为凸函数。我寻找“无法进入的极点：地球最遥远地方的计算算法”和三角测量，但找不到可行的解决方案。有任何想法吗？

我有一组点云（一组已确定在自己的区域内的点）。

目标是结合这些单独的集群

一世。相交

ii. 在彼此之间的某个最小距离内

Check ii 使这变得更加困难。为了快速处理这些点云，我正在创建 AABB（沿 X 轴对齐的轴对齐边界框）。

我目前的方法是使用分离轴定理的一些属性：

1. 为每个点云创建 AABB
2. 对于每个 AABB，检查它们是否重叠，方法是将它们投影到随机轴上，然后按照它们落在这条线上的位置 o(nlog(n)) 对这些线性投影进行排序。然后，我浏览此列表以使用 SAT 检查交叉点 O(N)。大多数 AABB 的线性投影不会重叠，因此不会相交，而那些我可以手动检查的投影（因为 1D 中没有重叠保证没有相交，但反之则不然）。

最后一部分是我卡住的地方。完成上述一维投影是为了避免 O(n^2) 成对检查交叉点。但是为了组合在某个阈值内但不相交的凸多边形，我看不到 O(N^2) 成对检查的方法。

有没有办法构建一些树或图形来组合彼此在一定距离内的所有凸多边形而不检查每个成对组合？

如果使用我的步骤 1 和 2，您可以假设剩余的点云/AABB 不相交。

编辑

一个潜在的解决方案是将其添加threshold/2到AABB宽度和高度，并检查交叉点。如果它们相交，那么我可以检查两个实际的交叉点（这对 AABB 来说很快），以及两者之间的最小距离。

在 Christer Ericson 关于碰撞检测的巨著中，他给出了一种加速 GPU 方法，用于使用以下算法检测凸多边形之间的碰撞。

我对 OpenGL 完全陌生，我的问题是，考虑到以下两点std::vector：

如何将其传递std::vector<Point>给以下函数并在 C++ 中返回结果？我的向量是一个凸多边形顺序逆时针。

设 CH1 和 CH2 是两个凸多边形。给出一个算法，在时间上与顶点数成线性关系，计算它们并集的凸包，证明它适用于两个多边形之间相互关系的所有不同可能情况。

有什么办法吗？

我目前正在为游戏开发 2D 照明系统。地图由可以具有某些标签和特征的图块组成。在这种情况下，我将一些图块设置为“不透明”，并编写了一个函数来为每个不透明图块生成一堆矩形。我想通过将大组矩形合并成凸多边形来优化这个几何形状。

我的矩形被定义为数组中线段的集合。

矩形多边形示例：

所以我的问题是如何从一大群矩形中生成一小群凸多边形？我绝不是专业的编码人员，因此请在您的答案中包含详尽的解释，并在可能的情况下提供示例。我花了几个多小时试图自己解决这个问题。

谢谢！

这样的功能还存在吗？如果是这样，我在哪里可以找到它？

基本上，我正在寻找 Matlab 的 convhulln() 函数的等价物。它将一个数据集（具有 N 维）作为其输入，并返回属于该数据空间的凸包的数据点。

我需要能够判断点是否位于凸包（C/C++）的内部/外部或边界（边缘）上的算法。

凸包被描述为点 X，Y 的数组，整数，连接从 i 到 i+1。

目前我使用缠绕数算法，在这里描述：http: //geomalgorithms.com/a03-_inclusion.html 它的函数“wn_PnPoly()”。

如果Point恰好位于凸的边界（边缘）上，是否有可能以及如何使绕组数算法检测？是否有另一种算法可以做到这一点？（需要在整数上工作）。

我有一张纸的照片，我拿着我的网络摄像头，并希望将照片的区域最小化为仅纸。这样，我的 OCR 程序可能会更准确，也可能更快。

到目前为止，我已经采取了几个步骤将论文与背景隔离开来。

首先，我使用 Canny Edge 检测，设置了高阈值。这为我的图像边缘提供了两种颜色的表示。在它上面，我可以看到背景中碰巧有锐利边缘的其他一些伪影中的圆角矩形。

接下来，我使用 Hough 变换，在黑色背景上以极坐标绘制超过 100 个点的矢量。生成的图像如图所示：

看到中间那个大的（最大的）几乎是矩形的图形了吗？这就是我拿着的纸。我需要将该梯形隔离为多边形，或者以其他方式获取其顶点的坐标。

我可以在原始图像上使用这些坐标来隔离纸张的 PNG，仅此而已。

如果您能回答这三个子问题中的任何一个，我也将不胜感激。

- 你如何找到图像上这些线的交叉点的位置？

- 我将如何摆脱任何不形成中心梯形多边形的线？

- 有了这些点，有什么比凸包更好的东西可以让我只得到图像的梯形/矩形区域？

这是另一个示例，其中我的程序生成了更好的图像：