CODEWITHSUNDEEP
algorithmgeometrymathematical-optimization
Einir
Einir

Reputation: 53

Smallest enclosing regular hexagon

Is there any algorithm / method to find the smallest regular hexagon around a set of points (x, y).

And by smallest I mean smallest area.

My current idea was to find the smallest circle enclosing the points, and then create a hexagon from there and check if all the points are inside, but that is starting to sound like a never ending problem.

Upvotes: 5

Views: 440

Answers (1)

saastn
saastn

Reputation: 6015

Requirements

First of all, let's define a hexagon as quadruple [x0, y0, t0, s], where (x0, y0), t0 and s are its center, rotation and side-length respectively.
enter image description here

Next, we need to find whether an arbitrary point is inside the hexagon. The following functions do this:

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

Long story short, the getHexRadious function formulates the hexagon in polar form and returns distance from center of hexagon to its boundary at each angle. Read this post for more details about getHexRadious and getHexRadious functions. This is how these work for a set of random points and an arbitrary hexagon: enter image description here

The Algorithm

I suggest a two-stepped algorithm:

1- Guess an initial hexagon that covers most of points :)
2- Tune s to cover all points

Chapter 1: (2) Following Tarantino in Kill Bill Vol.1

For now, let's assume that our arbitrary hexagon is a good guess. Following functions keep x0, y0, t0 and tune s to cover all points:

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

The getHexSide function is reverse of getHexRadious. It returns the minimum required side-length for a hexagon with x0, y0, t0 to cover point P. This is the outcome for previous test case: enter image description here

Chapter 2: (1)

As a guess, we can find two points furthest away from each other and fit one of hexagon diameters' on them:

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

enter image description here Although this method can find a relatively small polygon, but as a greedy approach, it never guarantees to find the optimum solutions.

Chapter 3: A Better Guess

Well, this problem is definitely an optimization problem with its objective being to minimize area of hexagon (or s variable). I don't know if it has an analytical solution, and SO is not the right place to discuss it. But any optimization algorithm can be used to provide a better initial guess. I used GA to solve this with findMinSide as its cost function. In fact GA generates many guesses about x0, y0, and t0 and the best one will be selected. It finds better results but is more time consuming. Still no guarantee to find the optimum!

enter image description here

Optimization of Optimization

When it comes to optimization algorithms, performance is always an issue. Keep in mind that hexagon only needs to enclose the convex-hall of points. If you are dealing with large sets of points, it's better to find the convex-hall and get rid of the rest of the points.

Upvotes: 2

Related Questions