Самый маленький вмещающий правильный шестиугольник

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, чтобы охватить все точки

Глава 1: (2) Вслед за Тарантино в Kill Bill 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, и будет выбран лучший. Он находит лучшие результаты, но требует больше времени. До сих пор нет гарантии, чтобы найти оптимальный!

Оптимизация оптимизации

Когда дело доходит до алгоритмов оптимизации , производительность всегда проблема. Имейте в виду, что шестиугольник должен заключать только выпуклый зал из точек. Если вы имеете дело с большими наборами точек, лучше найти выпуклый зал и избавиться от остальных точек.