最小外接正六边形

Question

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

“最小”指的是面积最小。

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

- Einir

---

您可以在 https://dev59.com/snRA5IYBdhLWcg3wyBD1 找到一些相关信息。 - SomeDude

使用圆形包围可能是一个开始。解决方案位于外接六边形（任意旋转）和内切六边形（某些其他旋转）之间。 - Ripi2

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) 仿效Tarantino在《杀死比尔》第一部中 目前，让我们假设我们的任意六边形是一个好的猜测。下面的函数保持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的反函数。它返回一个六边形所需的最小边长，以覆盖点P，该六边形具有x0, y0, t0。以下是先前测试案例的结果： 第二章：（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

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

第三章：更好的猜测

好吧，这个问题肯定是一个优化问题，其目标是最小化六边形的面积（或s变量）。我不知道它是否有解析解，而且Stack Overflow不是讨论这个问题的合适场所。但任何优化算法都可以用来提供更好的初始猜测。我使用遗传算法来解决这个问题，其中findMinSide是其成本函数。实际上，遗传算法会生成关于x0、y0和t0的许多猜测，然后选择最佳猜测。它可以找到更好的结果，但需要更长的时间。仍然不能保证找到最优解！

优化的优化

当涉及到优化算法时，性能总是一个问题。请记住，六边形只需要包围点的凸壳即可。如果你处理大量点集，最好找到凸壳并摆脱其余的点。

- saastn

---

所以我的想法是正确的，这是一个优化问题，可能没有最优解。但现在我离答案更近了，谢谢。所以我没有漏掉什么，GA是... - Einir