最小的封闭正六边形

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函数以极坐标形式表示六边形，并返回每个角度从六边形中心到其边界的距离。阅读这篇文章getHexRadious以了解有关其功能的更多详细信息getHexRadious。这是一组随机点和任意六边形的工作原理：

算法

我建议采用两步算法：

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

第一章：（2） 跟随塔伦蒂诺《杀死比尔》第一卷

现在，我们假设我们的任意六边形是一个很好的猜测。以下功能保持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其作为成本函数。事实上，遗传算法会产生许多关于x0、y0、 和 的猜测t0，并且会选择最好的一个。它会发现更好的结果，但更耗时。仍然不能保证找到最佳的！

优化的优化

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