问题标签 [convex]

假设在一个平面上有许多凸多边形，也许是一张地图。这些多边形可以相互碰撞并共享一条边，但不能重叠。

要测试两个多边形P和Q是否重叠，首先我可以测试P中的每条边，看看它是否与Q中的任何边相交。如果找到一个交点，我声明P和Q相交。如果没有相交，那么我必须测试P完全被Q包含的情况，反之亦然。接下来，存在P == Q的情况。最后，有些情况共享一些边缘，但不是全部。（这最后两种情况可能被认为是相同的一般情况，但这可能并不重要。）

我有一个算法可以检测两条线段相交的位置。如果这两个线段是共线的，则出于我的目的，它们不被视为相交。

我是否正确列举了这些案例？对这些案例的测试有什么建议吗？

请注意，我不是要找到作为交叉点的新凸多边形，我只想知道是否存在交叉点。有许多有据可查的算法可以找到交叉点，但我不需要付出所有努力。

我正在寻找一个 C++ 库，我正在处理凸目标和约束函数。

我正在尝试研究和实现一些计算机视觉技术，例如对 2D 中的一组任意点进行运动跟踪。我正在为我知道的一组点生成一个凸包，并为它可能映射到的一组点生成一个凸包。我正在寻找可以帮助我比较两个船体的相似程度的资源，然后如果足够相似，它们实际上是如何相互映射的？任何关于在哪里可以找到讨论这种算法风格和该领域可能更复杂算法的好资源/书籍的信息将不胜感激。

给定凸多边形 P 和 P 边界上的点 A，我如何计算 P 边界上的点 B 使得 AB 将 P 分成给定比例的两个区域？

理想情况下，我想要一个分析解决方案。作为最后的手段，我可​​以在多边形的任何地方画一条线并逐渐移动它，直到比例正确到给定的精度。

一旦我知道它应该在多边形上的哪两个点之间，我已经计算出如何计算 B 。因此，如果有办法找出它应该在哪些点之间移动，我应该能够从那里拿走它！

我是 android 动画的新手，所以如果有人可以帮助我，我想转换一个对象，比如说一个矩形以具有凸面外观。我可以用一些功能来做到这一点，比如让我们说倾斜或......如果有人有想法或示例代码，我会非常感激。提前谢谢你

我有一个由点表示的凸多边形。点由x 坐标数组和y 坐标数组表示。

例如：

如何按顺时针方向对这些点进行排序？点的数量并不总是相同，但多边形仍然是凸的。

是否有不使用atan2 或math.h中的其他函数的解决方案？

给定 2D 空间中的两个凸多边形，您将如何构建线段，该线段在线上的任何点都与任一凸多边形的最近点等距？

我正在寻找凸多边形而不是点的 Voronoi 图的实现，但我不确定如何开始计算仅两个多边形的线。所以我想我会一步一步从这里开始。

编辑为了使问题更清楚一点，我想将平面（或其子集）一分为二。

假设我们在左边有多边形 A，在右边有多边形 B。会有一条平分线将平面分成左边的点和右边的点。线上的每个点与任一多边形的距离相等。直线左侧的每个点都比多边形 B 更接近多边形 A。直线右侧的每个点都最接近多边形 B。

这是由我编写的 Matlab 脚本生成的图像，该脚本强力逼近近似值：

我相信，这个问题并不像检查两个多边形“之间”的空间那么简单，因为线必须直接延伸到两个形状之间的区域之外。理想情况下，我想找到一个可以推广到两个以上形状的解决方案，在我看来，这似乎使问题更加复杂。这是一个（显然非常粗略的）近似值：

你会推荐任何凸优化库吗？

理想情况下是开源的。半定规划和 QCQP 的先验。

（我打算将它与 fsharp 一起使用，但任何 dotnet 都可以）

我正在创建一个在 Android 中使用 libgdx 的应用程序。

当最终用户仅单击纹理的可见部分时，我需要添加一个触摸侦听器，无论它是凹形图像还是凸形图像。

我怎样才能做到这一点？

我记得有一个不错的想法（尽管我从未见过它的实现），即为每个纹理提供一种独特的颜色，并在绘制其真实内容之前用这种颜色绘制其可见部分，如果触摸完成在颜色上，表示最终用户点击了图像。是否可以对 libgdx 使用相同的技术？如果是这样，怎么做？

当然，对于我选择旋转/缩放的图像也是如此。

也许这更像是一个数学问题而不是编程问题，但我一直在尝试在 XNA 中实现旋转卡尺算法。

我已经使用维基百科上详述的单调链从我的点集中推导出了一个凸包。

现在我正在尝试对我的算法进行建模，以在此处找到 OBB： http ://www.cs.purdue.edu/research/technical_reports/1983/TR%2083-463.pdf

但是，我不明白它在最后一页提到的 DOTPR 和 CROSSPR 方法应该返回什么。

我了解如何获得两点的点积和两点的叉积，但似乎这些函数应该返回两条边/线段的点积和叉积。诚然，我的数学知识有限，但这是我对该算法正在寻找什么的最佳猜测

但是，当我按照我的这部分代码中的指示使用这些方法时......

..当我给它一组测试点时，它为 j, k 返回相同的索引：

请注意，我调用 polygon.Reverse 以按照 perdue.edu 的技术文档中所示的逆时针顺序放置这些点。我的用于查找点集的凸包的算法会按逆时针顺序生成点列表，但假设 y < 0 高于 y > 0 因为当绘制到屏幕时，0,0 是左上角. 颠倒列表似乎就足够了。我还删除了最后的重复点。

经过这个过程，数据变成：

• 向量 2(115, 14)
• 向量2(129, 0)
• 向量2(131, 0)
• 向量 2(204, 63)
• 矢量2(199, 68)
• 向量 2(150, 110)
• 向量 2(1, 138)
• 向量 2(0, 138)

当 i 等于 0 且 j 等于 3 时，此测试在第一个循环中失败。它发现行 (115,14) 到 (204,63) 和行 (204,63) 到 (199,68) 的叉积) 为 0。然后发现同一行的点积也为 0，因此 j 和 k 共享相同的索引。

相反，当给定这个测试集时： http ://www.wolframalpha.com/input/?i=polygon+%282%2C1%29%2C%281%2C2%29%2C%281%2C3%29%2C% 282%2C4%29%2C%284%2C4%29%2C%285%2C3%29%2C%283%2C1%29

我的代码成功返回此 OBB： http ://www.wolframalpha.com/input/?i=polygon+%282.5%2C0.5%29%2C%280.5%2C2.5%29%2C%283%2C5%29% 2C%285%2C3%29

我已经阅读了http://www.geometrictools.com/LibMathematics/Containment/Wm5ContMinBox2.cpp上的 C++ 算法，但我太密集了，无法完全遵循它。它似乎也与上​​述论文中详述的另一个非常不同。

有谁知道我正在跳过哪个步骤或在我的代码中看到一些错误以查找两条线段的点积和叉积？有没有人在 C# 中成功实现过这段代码并有一个例子？