algorithm - 最小的封闭正六边形

Question

是否有任何算法/方法可以在一组点(x，y)周围找到最小的正六边形。

最小的意思是最小的面积。

我目前的想法是找到包围点的最小圆，然后从那里创建一个六边形并检查所有点是否都在里面，但这听起来像是一个永无止境的问题。

Answer 1

需求

首先，让我们将六边形定义为四边形 [x0, y0, t0, s] ，其中 (x0, y0) , t0和 s分别是它的中心、旋转和边长。


接下来，我们需要找到任意点是否在六边形内。以下函数执行此操作:

function getHexAlpha(t, hex)
    t = t - hex.t0;
    t = t - 2*pi * floor(t / (2*pi));
    return pi/2 - abs(rem(t, pi/3) - (pi/6));
end

function getHexRadious( P, hex )
    x = P.x - hex.x0;
    y = P.y - hex.y0;
    t = atan2(y, x);
    return hex.s * cos(pi/6) / sin(getHexAlpha(t, hex));
end

function isInHex(P, hex)
    r = getHexRadious(P, hex);
    d = sqrt((P.x - hex.x0)^2 + (P.y - hex.y0)^2);
    return r >= d;
end

长话短说， getHexRadious函数以极坐标形式表示六边形，并返回从六边形中心到每个角度的边界的距离。阅读 this post更多详情 getHexRadious和 getHexRadious职能。这是一组随机点和任意六边形的工作方式:


算法

我建议一个两步算法:

1- 猜一个覆盖大部分点的初始六边形:)
2- 调 s覆盖所有点

第1章:(2)在杀死比尔 Vol.1 中跟随塔伦蒂诺

现在，让我们假设我们的任意六边形是一个很好的猜测。以下功能保留 x0, y0, t0和调 s涵盖所有要点:

function getHexSide( P, hex )
    x = P.x - hex.x0;
    y = P.y - hex.y0;
    r = sqrt(x^2 + y^2);
    t = atan2(y, x);
    return r / (cos(pi/6) / sin(getHexAlpha(t, hex)));
end

function findMinSide( P[], hex )
    for all P[i] in P
        S[i] = getHexSide(P, hex);
    end
    return max(S[]);
end

getHexSide功能与 getHexRadious相反.它返回六边形所需的最小边长 x0, y0, t0覆盖点 P .这是之前测试用例的结果:


第2章:(1)

作为猜测，我们可以找到彼此相距最远的两个点，并在其上拟合六边形直径之一:

function guessHex( P[] )
    D[,] = pairwiseDistance(P[]);
    [i, j] = indexOf(max(max(D[,])));
    [~, j] = max(D(i, :));
    hex.x0 = (P[i].x + P[j].x) / 2;
    hex.y0 = (P[i].y + P[j].y) / 2;
    hex.s = D[i, j]/2;
    hex.t0 = atan2(P.y(i)-hex.y0, P.x(i)-hex.x0);
    return hex;
end

虽然这种方法可以找到一个相对较小的多边形，但作为一种贪心的方法，它永远不能保证找到最优解。

第3章:更好的猜测

嗯，这个问题绝对是一个优化问题，其目标是最小化六边形(或 s 变量)的面积。我不知道它是否有解析解，SO 不是讨论它的合适场所。但是任何优化算法都可以用来提供更好的初始猜测。我用 GA 用 findMinSide 解决了这个问题作为其成本函数。事实上，GA 对 x0 产生了很多猜测。 , y0 , 和 t0最好的一个将被选中。它会找到更好的结果，但更耗时。仍然不能保证找到最佳的!



优化优化

在优化算法方面，性能始终是一个问题。请记住，六边形只需要包围点的凸厅。如果您正在处理大量点，最好找到凸厅并摆脱其余的点。