问题标签 [convex-polygon]

我需要解决一个相对简单的问题——我有 n 个顶点凸 2D 多边形和一条带有一些“y”坐标的水平（！）线。我只需要一件事：检查多边形是否与这条线相交（即有2个交叉点）。

我能想到的最快的方法是在多边形内找到最小/最大 y 坐标（循环重复 n 次，两次比较和两次存储），然后比较最小 y <= y < max y。

不知何故，我觉得这可以更“数学”地解决，但我总是以较慢的代码结束（例如矢量方式——我需要计算 n[i] 和 n[i+1] 的差异，然后将它们相乘、相加等 - - 比 2 cmps+stores 慢得多）。

如果我有这样的 QuadCurve（+= 节点）：

我用Java 2D填充它，结果是这样的：（x=有色）

但我想给另一面上色：

这通过在曲线周围绘制一个矩形来成功，我想为另一侧着色，然后用背景颜色填充曲线。

但这不足以填充凸圆形（基于 QuadCurves）多边形。如果矩形的某些坐标（如我使用的技巧中所述）与多边形的其他部分重叠。这是两张图片（绿色区域是我的多边形）：

替代文字 http://img204.imageshack.us/img204/7823/convexpolygon.png 替代文字 http://img708.imageshack.us/img708/3669/convexpolygon2.png

所以，问题很简单：“如何为曲线的形状构建着色？”
但我认为答案并不简单......

非常感谢任何建议。
提前致谢。

_{如果我没有得到答案，也许我会为这个问题悬赏}

给定一个凸多边形，我试图在保持其直径的同时扩大其形状（如“最大面积”）。直径定义为可以放置在多边形内的最长线段的长度。由于多边形是凸的，我假设这个直径总是可以通过扫描所有顶点对来找到。

例如，给定一个等边三角形作为输入多边形，三角形的直径是任意边的长度；平滑这将导致 3 个圆段，如图所示

对于任意凸多边形，一个非常低效的算法是计算以每个多边形顶点为中心的最大直径半径圆的交点；这就是我目前正在使用的（在 Java 中）。有更好的吗？任何伪代码或算法指针都将不胜感激。

另一个例子：一个被压扁的五边形及其对应的保持直径的最大形状。这个想法是你不能在不增加直径的情况下增加这个形状的面积（也就是说，可以在形状的边界内绘制一条比原始直径长的直线）。在这种特殊情况下，半径 = 多边形直径/2（粉红色）的单个圆似乎比半径 = 多边形直径（浅蓝色）的多个较大圆的交集要好。第二张图像将两个区域叠加在一起，以便于比较，但区域应完全包围多边形。

我找到了一些解决方案，但它们太乱了。

我是 openGL 的新手，我正在阅读红皮书。现在，作为练习，我想手动绘制一个球体。为此，我将球体分成切片和堆叠，因此我得到多个矩形，但在球体的两极附近我得到三角形。（希望这很清楚我在做什么）。现在我知道，如果您使用 GL_POLYGON 绘制一个多边形并且它恰好与自身相交，则行为是未定义的。我的问题是：给定不在一条线上的三个点 v1、v2、v3，这样做是否是未定义的行为：

这可能将两个不相关的问题合二为一，但我也想知道：如果我选择将 sphere 例程中的矩形划分为三角形，那么我如何做到这一点是否重要，也就是说，我将矩形划分为哪个对角线两个三角形？我猜想绘制一个单色球体没关系，但我不知道纹理、着色器、照明等。

我想解构以下以蓝色显示的多边形，从多边形中删除所有导致凹面的点。

目前，我一直在尝试做的是：

• 从多边形中取出每个点
• 测试该点以查看它是否落在集合的其余部分创建的多边形内
• 如果为真，则删除该点
• 如果是假的，保持这一点

这在大多数情况下都有效，但在前一种情况下，(2,3) 和 (2,4) 处的点不会都被删除。在这两种情况下，其中一个点都将被删除，但另一个点将不取决于传入数组的顺序。

我想知道的是：

1. 有什么方法可以测试我正在处理的多边形是否恰好有这些情况之一（即：连续 3 个故障点？）
   或
2. 有没有一种更有效的方法来创建凸多边形？

谢谢你。

检测一条线是否与凸多边形相交的 O(n) 算法包括检查多边形的任何边缘是否与该线相交，并查看相交的数量是奇数还是偶数。

是否有渐近更快的算法，例如 O(log n) 算法？

相关：多边形分解 - 去除凹点以形成凸多边形

我正在寻找一种算法来执行以下操作：

输入是二维点数组 (P ₀ …P _N-1 )。数组的长度 N 变化 (3 ≤ N < ∞)
对于任何 M ≤ N，可能有也可能没有顶点为 P ₀ …P _M-1的凸多边形。

请注意 ，边缘不一定是阵列中的相邻对。

找到最大 M 以使该凸多边形存在的最有效算法是什么？

我目前的算法效率很低。我用 M=3 然后 M=4, M=5 等进行测试，计算船体然后测试所有 P ₀ ...P _M-1是船体的顶点，如果不是，那么我跳出循环并返回 M- 1.

示例 #1：[(-2,2), (2,2), (-2,-2), (-1,1)]

结果：3（因为前三个点形成一个三角形，但添加 P ₃ =(-1,1)会使多边形非凸）

示例 #2：[(-2,2), (2,2), (-2,-2), (1,-1)]

结果：4（因为可以从数组中的所有 4 个点构造一个凸四边形）

更新示例 #3：[(-3,3), (3,3), (2,-1), (-3,-3), (3,-3), (-2,1)]
结果：4。

这个例子说明了为什么只取所有提供点的凸包并找到一个前缀是它的子集是不够的。(3,-3)不能是由前五个点组成的凸多边形的一部分，因为这样前一个点将(2,-1)不再位于船体上。但它(3,-3)必须被拒绝，即使它位于所有六个点的船体上并且(2,-1)没有。

无效输入示例：

• [(-1,-1), (0,0)]（分数太少）
• [(-1,-1), (0,0), (1,1), (1, -1)]（前三点是共线的：我不希望算法能够处理这个问题。）

我正在尝试获取诸如this的密集点图，并将其转换为连接的凸多边形图。多边形应尽可能大且尽可能简单，同时保持连接。结果图将用于寻路。谁能指出我正确的方向？

我正在寻找一种算法来使用 Cuda 找到一个包含所有随机点的凸多边形。有没有人知道我可以适应的非常有效的算法？