问题标签 [convex-polygon]

假设我有一个在 6 维空间中给出的点云，我可以根据需要使其尽可能密集。这些点最终位于低维多面体的表面上（即点向量 (x1, x2, ... x6) 似乎是共面的）。

我想找到这个未知多面体的顶点，我目前的尝试通过 Python 中的 scipy 接口使用 qhull 算法。一开始我只会收到错误消息，显然是由低维输入和/或许多退化点引起的。我尝试了几种蛮力方法来消除退化点，但不是很成功，所以最后，我认为所有这些点都必须位于凸包上。

这个问题非常有帮助，因为它建议通过主成分分析进行降维。如果我将点投影到 4D 超平面，qhull 算法运行没有错误（对于任何更高的维度它都不会运行）。

上述问题的答案提到，在计算投影点的凸包后，需要将单纯形转换回来。但是 qhull 输出仅包含索引，为什么这些与初始点的索引不匹配？

现在我的问题是我不知道使用哪种精度来实际获得正确的顶点。无论我制作的点云有多密集，获得的顶点都以不同的精度不同。例如，对于 (10000, 6) 数组中的初始点，我得到（其中 E0.03 是它的最大值）：

并将其绘制在轴 0、1、2 的一些（不是非常丰富的）投影中（其中蓝色点代表初始点云的选择）：

但是为了获得更高的精度（当然），我得到了不同的集合：

相同的投影（只是角度略有不同）：

我怀疑第一张图片没有足够的顶点，而第二张图片可能有太多。虽然我当然无法从这些图中提取严格的信息。但是有没有一种很好的方法来找出使用哪种精度？或者也许是一个完全不同的方法来解决这个问题（我已经尝试了一些）？

如何有效地测试一个轴对齐的矩形 R 是否与一个漂亮的四边形 Q 相交？

• Nice 的意思是：Q 是凸的（不是 V 形）且非自相交的（不是领结，不是退化的）。
• 只是二维。
• 只是是/否。我不需要实际的交叉区域。
• 编辑： Q 和 R 可以打开或关闭，无论方便。

显然，对于 Q 的每个边，可以测试它是否与 R 相交。这将问题减少到 如何测试线段是否与二维中的轴对齐矩形相交？.

但是，就像 Liang-Barsky 利用 R 的轴对齐比 Cohen-Sutherland 更快一样，Q 的属性可能被利用来获得比多次运行 Liang-Barsky 更快的东西。

因此，多边形-矩形相交算法 Sutherland-Hodgman、Vatti 和 Greiner-Hormann，所有这些算法都让 Q 为非凸的，不太可能是最优的。

矩形-矩形相交的区域看起来很有希望，即使它没有利用 R 的轴对齐性。

假设你得到了一条线的方程（在 2d 中），以及形成凸多边形的线方程（多边形可以是无界的）。如何确定线是否与多边形相交？

此外，是否有预定义此类任务的计算几何库？我问是因为我不仅对 2D 版本感兴趣，而且对 n 维几何感兴趣。

我正在尝试使用库 Scipy 和 ConvexHull 创建一个 Convex Hull。据我所知，它叫QHull。

当我要添加的点没有“全维度”时，就会出现问题。例子：

有输出：

但是，如果我添加一个额外的点，使凸包具有完整的维度：

然后一切正常。一个例子和另一个例子之间的区别（我已经做了很多其他例子，所以我确定）是第一种情况下的凸包在二维空间中是一维的，而在第二种情况下，是 2-二维空间中的维度（即全维度）。

有任何想法吗？我想传递一些 qhull_options 自从文档指出以来，正如答案中提到的那样：

QHullError 当 Qhull 遇到错误条件时引发，例如在未启用解决选项时出现几何退化。

但是，我已经阅读了QHull 中的许多选项，但似乎都没有解决这个问题。我随机尝试了其中一些，但收效甚微。

任何帮助都会有所帮助。我正在开发一个创建数百个这样的船体的程序，其中一些不是全维度的。

我有一条与二维平面中的凸多边形相交的直线。存在一个半径不变的圆。圆心在这条线上移动。因此，起初多边形和圆形不相交，随着圆形越来越接近多边形，相交会随着它们彼此远离而增加然后减少。我想证明凸多边形和圆的交集区域没有局部最小值（当圆在线移动时）。

我正在寻找一种算法来计算将凸多边形（P1）定位在另一个凸多边形（P2）内所需的平移、旋转和缩放。我需要它来返回“最佳拟合”，这意味着 P1 完全包含在 P2 中并且具有可能的最大面积。

考虑下图：http: //i.imgur.com/ckaIIv7.png

右侧的黑色多边形 (P1) 需要最佳放置在左侧的蓝色多边形 (P2) 内。

我在网上找到了很多关于多边形包含算法的书面论文，但这些算法是确定多边形是否可以放入另一个多边形中，因为它们具有平移和旋转的能力。

我正在寻找的算法应该总是产生结果，因为它包括缩放多边形 P1 的能力。我知道这种类型的算法可以产生多个最佳答案，这没关系。

有什么帮助吗？

众所周知，如果一个人想要布局实数的方形网格（又名矩阵），他可以使用array行优先顺序。让我们画一些元素 i 的邻域：

为简单起见，我们假设 i 在方形网格的中间某处，因此没有边界问题。（我们可以%(width*height)在边界网格上添加和连接）。因此，如果想对第 i 个元素附近的每个元素做某事，则应该这样做：

我想将此算法推广到任何类型的正多边形网格（即三角形、正方形、五边形、六边形等）。常规意味着它仅由一种类型的多边形（即仅由三角形）构成。

如何概括任何类型的多边形网格： 1. 阵列中其他网格的布局？2. 循环中的这些 N(for square mesh 4) 语句？

问题“如何在多边形网格中找到瓷砖的所有邻居？” 使用图表快速解决。但我想使用数组，这样我就可以用 CUDA 将它们复制到显卡上。

网格示例：

将三角剖分的成本定义为已添加的对角线长度的总和。给定一个凸多边形，它最便宜的三角剖分的成本是多少？如果我们将多边形视为一组 n 坐标： v_1=x_1,y_1,...,v_n=x_n,y_n 并且解决方案必须具有 n-3 对角线（不重叠，因为它是三角剖分）

我一直试图让这个动态编程问题再次出现，但我似乎找不到一个好的问题。我并没有真正认识到次优结构来找到复发。任何人都可以帮我解决这个问题吗？

我想在 Box2D Cocos2d JS 的附加图像中创建一个斜坡。但是，将精灵附加到它时，我无法正确创建它。我的代码是：

图像尺寸为 200 * 50，worldScale = 30。

给定一个二维点数组 (#pts x 2) 和一个点数组连接到哪个点 (#bonds x 2 int 数组，索引为 pts)，我如何有效地返回由键形成的多边形数组？

可能存在不闭合多边形的“悬空”键（如下图左上角），这些应该被忽略。

这是一个例子：