问题标签 [convex-polygon]

我是 MATLAB 新手。我想找到一组平面的方程，这些平面是我使用计算的凸包的一部分convhulln。它是一个凸多面体。我试图搜索很多，但找不到任何东西。任何帮助表示赞赏。

这是我找到凸包的一组点。代码不在 MATLAB 中，但很容易理解。所有点都是 3D 点。

计算凸包后如何在three.js中找到定向边界框？

在下图中：绿色代表凸包（我将其显示为网格以进行可视化），白色是 AABB。

我知道three.js 中没有可用的内置方法。我从threejs示例中尝试了OBB.js，但这对我不起作用。凸包算法看起来很有前途。任何有关下一步的指示都将非常有帮助。

据我了解，我需要计算形成凸包边界的一组顶点的协方差矩阵（并排除其他内部顶点）。我如何获得这些顶点？

是否有使用节点和元素连接信息获取最外层表面的函数或算法？由于一般的凸包算法只使用节点信息，所以通过搜索最外层表面只能得到三角形表面。我想通过使用元素连接来获取表面信息。

让我们考虑一个多边形，其边缘接近正交，在 (70, 89)° 或 (91, 110)° 的范围内。我们知道多边形中的角度之和是 180° 的倍数。

问题是如何将具有自定义形状的多边形转换为具有直角的最小多边形。

作为一个非常简单的案例，让我们考虑下面的示例：

我们想要实现的是，下面的多边形：

边的数量可以更多。上面的例子只是一个简单的例子。

如果有一个移动的凸多边形和一个静态的凸多边形，我怎么能得到它可以移动的距离，以便多边形刚好接触另一个多边形？

当多边形已经发生碰撞时，我可以使用 SAT 计算将多边形与另一个分离的向量，但是该平移向量可能会改变多边形移动的方向。我希望多边形仅在其原始方向上移动并停止，因此我需要知道它在碰撞之前可以行进的距离，或者通过在与运动相反的方向上移动移动多边形来分离多边形的矢量。

概念图

我正在使用 scipy.spatial.ConvexHull API 来评估一组点的凸包，并且效果很好。鉴于以下代码：

如何评估vertices等于的凸组合的系数（权重） p1？

非常感谢你，摩西

我有一组对象，每个对象要么是一个多边形，要么是一个圆，每个对象都有平移向量和围绕一个点的旋转。

我还没有真正尝试过任何事情，但从一些研究中我知道你必须将凹多边形分割成凸多边形，然后对它们应用碰撞算法。

根据我的研究，SAT 出现了很多，但其他一些也出现了，我发现很多相关的帖子都很旧，所以链接和参考不再可用。

问题是我不知道他们是否让您获得撞击点和撞击时间，或者只是让您沿着垂直于最近表面的矢量平移对象（以行进最小距离）。我的标准是效率和某种程度的简单性。

所以我的问题是：我应该使用哪种算法来确定可能的凹多边形和/或球体之间发生碰撞的点和时间，每个球体和/或球体都有自己的平移向量和围绕一个点的旋转（两者都可以是 0）。

我被给定为输入 n 对整数，它们描述了 2D 平面中的点，这些点提前知道是某个凸多边形的顶点。我想以顺时针或逆时针的方式有效地对这些点进行排序。

起初我想做一些类似于 Graham Scan 的初始步骤，但我看不到一种简单的方法来打破与锚点成相同角度的顶点的关系。请注意，当您沿着多边形的边走时，有时这些顶点可能会越来越靠近锚点，有时它们可​​能会越来越远。

似乎确实有效的方法是在多边形内部产生一个点（例如，n 个点的平均值），并使用它作为输入径向排序的锚点。事实上，因为锚点位于内部，所以从它发出的任何光线最多包含一个输入点，因此不会有联系。

整体复杂度不受影响：计算中点是 O(n) 任务，瓶颈是实际排序。
这确实涉及比有希望的 Graham Scan 版本更多的操作（我们假设没有要打破的关系），但更大的损失是通过在混合中引入除法来留下整数算术。
反过来，这可以通过将所有内容缩放 n 倍来解决，但在这一点上，这似乎是在抓住稻草。

我错过了什么吗？有没有一种更简单、更有效的方法来解决这个排序问题，最好是可以避免浮点计算的方法？

我正在查看手册的 Partition_2 部分和示例，以查看 CGAL 是否可以处理带孔的多边形的凸分区。所有示例似乎都使用没有任何孔的多边形。有谁知道这是否受到任何 CGAL 分区算法的支持？

https://github.com/CGAL/cgal/blob/master/Partition_2/include/CGAL/partition_2.h

https://doc.cgal.org/latest/Partition_2/index.html

谢谢，乔希。

我的目标是获得一个多面体的所有面（以 A[x,y,z]'>b 的形式）的表示，这是两个凸多面体之间凸差的结果。意思是，找到所有平面的交点，这是 P1 - P2 = { x - y | 的 Minkowski 差异的结果。x \in P1，y \in P2 }。

我正在寻找一个已建立的库（Python？）或如何有效地做到这一点的想法。我想过做一些类似于GJK 算法的事情，但我需要所有的面孔，而不仅仅是快速计算原点是否在里面。此外，在 3D 或更高维度中以方法论方式使用此支持功能似乎效率低下。另外，假设我得到了顶点，我现在是否需要从上面的两个向量与叉积形成平面方程，对于每个面，或者有没有办法从 Minkowski 和本身获得它？（记住对更高维度的需求）。