最小封闭正六边形

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 函数以极坐标形式表示六边形，并在每个角处从六边形的中心到其边界的 returns 距离。阅读了解有关 getHexRadious 和 getHexRadious 函数的更多详细信息。这就是这些对于一组随机点和任意六边形的工作方式：

算法

我建议采用两步算法：

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

第 1 章：(2) 跟随塔伦蒂诺的《杀死比尔》第 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 相反。它 returns 具有 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 章：更好的猜测

好吧，这个问题绝对是一个优化问题，其 objective 是最小化六边形（或 s 变量）的面积。不知道有没有解析解，SO也不是讨论的好地方。但是可以使用任何优化算法来提供更好的初始猜测。我使用 GA 以 findMinSide 作为成本函数来解决这个问题。事实上，GA 会生成很多关于 x0、y0 和 t0 的猜测，并且会选择最好的一个。它找到更好的结果，但更耗时。仍然不能保证找到最佳！

优化中的优化

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

最小封闭正六边形

Smallest enclosing regular hexagon

algorithm

geometry

mathematical-optimization