用户绘制圆的凸包
Convex Hull For User-Drawn Circle
我正在开发一款游戏，我必须在其中找到一组点的凸包。我正在尝试选择正确的算法。点集是用户绘制的形状，因此它们是有顺序的。理想情况下，用户画一个椭圆，但只要是单笔画，他们就可以画任何东西。下面是一些示例：
我想找到这些形状的凸包。我发现的所有凸包算法都假设一组随机、无序的点。当用户通过单击并拖动鼠标绘制点时，哪种算法最适合我的特定情况，因此点是有序的。
备注：
特别是，许多是输出敏感算法。 O(n log h) 其中n是所有点集合中的点数，原始的，h是凸包中的点集合。对于这些形状，我希望 h ~= n，因为它们本身基本上就是轮廓。
最后，整个目标是找到点的最小面积矩形，例如：
除了先求凸包，还有谁能想到更好的求矩形的方法吗？经过研究，这似乎是最好的方法，但我的特殊情况可能会有所不同。
提前致谢！
要找到在特定方向对齐的最小外接矩形，您需要知道该方向和正交方向的极值点，并且凸包以特别方便的方式编码此信息，例如旋转卡尺.如果你愿意近似，你可以尝试每五度（或其他）的方向，用 O(nd) 的 运行 时间，其中 d 是方向的数量。如果您有 SIMD 支持，这可以很好地工作。
远离 O(N Log H) 算法。他们又难又慢！
使用 O(N Log N) 个是更好的选择。我推荐 monotone chain 方法，既简单又快速。
您不必担心 O(N Log N) 的复杂度顺序，这只是排序阶段造成的。额外的 Log N / Log H 因子并不是那么灾难性的（并且对于凸点集来说是不存在的），而排序的渐近常数非常好。
如果您追求最大效率，您的点的特定排列建议采用另一种方法：这些点将形成长的递增（递减）序列，您可以通过合并步骤轻松检测和排序。复杂度将降至 O(N Log K)，其中 K 是单调序列的数量，因此实际上是 O(N)（这称为自然归并排序）。
您距离 Melkman 的 O(N) 算法的用例不远，该算法可用于简单多边形的外壳。不幸的是，简单条件可能会在曲线接近尾声时失效，我认为没有简单的方法可以解决这个问题。
对于边界矩形，旋转卡尺绝对是您最好的朋友。
我只是想知道如果您应用以下方法会发生什么：
将多边形想象成一个 2 x N 矩阵
P = [x1, x2, ..., xN;
y1, y2, ..., yN];
其中每列包含多边形顶点的 x 和 y 坐标。然后，对于 0 和 pi/2 之间的任何角度 phi 定义旋转矩阵
U(phi) = [cos(phi) -sin(phi);
sin(phi) cos(phi)];
之后，通过矩阵相乘将多边形旋转到角度 phi
P_phi = U(phi)*P;
然后函数
f(phi) = ( max( P_phi[1][] ) - min( P_phi[1][] ) )*( max( P_phi[2][] ) - min( P_phi[2][] ) )
是具有水平和垂直边缘的矩形区域，上标在旋转的多边形周围 P(phi)。这里P_phi[1][]是矩阵的第一行x坐标P_phi，P_phi[2][]是第二行y坐标。
因此，您想找到 axes-aligned 矩形的角度 phi 和收集在 2 x 4 矩阵 R_phi 中的顶点，它们给出函数的最小值
f(phi) 表示 phi in [0, pi/2] 因为那是 smallest-area 矩形的区域，覆盖在您的多边形周围。在找到 phi 和 R_phi 之后
只需按如下方式旋转回来
R = U(-phi)*R_phi 这就是您要查找的矩形。
我不确定这个建议是否有效...
我正在开发一款游戏，我必须在其中找到一组点的凸包。我正在尝试选择正确的算法。点集是用户绘制的形状，因此它们是有顺序的。理想情况下，用户画一个椭圆，但只要是单笔画，他们就可以画任何东西。下面是一些示例：
我想找到这些形状的凸包。我发现的所有凸包算法都假设一组随机、无序的点。当用户通过单击并拖动鼠标绘制点时，哪种算法最适合我的特定情况，因此点是有序的。
备注：
特别是，许多是输出敏感算法。 O(n log h) 其中n是所有点集合中的点数，原始的，h是凸包中的点集合。对于这些形状，我希望 h ~= n，因为它们本身基本上就是轮廓。
最后，整个目标是找到点的最小面积矩形，例如：
除了先求凸包，还有谁能想到更好的求矩形的方法吗？经过研究，这似乎是最好的方法，但我的特殊情况可能会有所不同。
提前致谢！
要找到在特定方向对齐的最小外接矩形，您需要知道该方向和正交方向的极值点，并且凸包以特别方便的方式编码此信息，例如旋转卡尺.如果你愿意近似，你可以尝试每五度（或其他）的方向，用 O(nd) 的 运行 时间，其中 d 是方向的数量。如果您有 SIMD 支持，这可以很好地工作。
远离 O(N Log H) 算法。他们又难又慢！
使用 O(N Log N) 个是更好的选择。我推荐 monotone chain 方法，既简单又快速。
您不必担心 O(N Log N) 的复杂度顺序，这只是排序阶段造成的。额外的 Log N / Log H 因子并不是那么灾难性的（并且对于凸点集来说是不存在的），而排序的渐近常数非常好。
如果您追求最大效率，您的点的特定排列建议采用另一种方法：这些点将形成长的递增（递减）序列，您可以通过合并步骤轻松检测和排序。复杂度将降至 O(N Log K)，其中 K 是单调序列的数量，因此实际上是 O(N)（这称为自然归并排序）。
您距离 Melkman 的 O(N) 算法的用例不远，该算法可用于简单多边形的外壳。不幸的是，简单条件可能会在曲线接近尾声时失效，我认为没有简单的方法可以解决这个问题。
对于边界矩形，旋转卡尺绝对是您最好的朋友。
我只是想知道如果您应用以下方法会发生什么：
将多边形想象成一个 2 x N 矩阵
P = [x1, x2, ..., xN;
y1, y2, ..., yN];
其中每列包含多边形顶点的 x 和 y 坐标。然后，对于 0 和 pi/2 之间的任何角度 phi 定义旋转矩阵
U(phi) = [cos(phi) -sin(phi);
sin(phi) cos(phi)];
之后，通过矩阵相乘将多边形旋转到角度 phi
P_phi = U(phi)*P;
然后函数
f(phi) = ( max( P_phi[1][] ) - min( P_phi[1][] ) )*( max( P_phi[2][] ) - min( P_phi[2][] ) )
是具有水平和垂直边缘的矩形区域，上标在旋转的多边形周围 P(phi)。这里P_phi[1][]是矩阵的第一行x坐标P_phi，P_phi[2][]是第二行y坐标。
因此，您想找到 axes-aligned 矩形的角度 phi 和收集在 2 x 4 矩阵 R_phi 中的顶点，它们给出函数的最小值
f(phi) 表示 phi in [0, pi/2] 因为那是 smallest-area 矩形的区域，覆盖在您的多边形周围。在找到 phi 和 R_phi 之后
只需按如下方式旋转回来
R = U(-phi)*R_phi 这就是您要查找的矩形。
我不确定这个建议是否有效...