Выпуклая оболочка для нарисованного пользователем круга

Question

Я работаю над игрой, в которой я должен найти выпуклую оболочку для набора точек. Я пытаюсь выбрать правильный алгоритм. Наборы точек - это нарисованные пользователем фигуры, поэтому у них есть порядок. В идеале пользователь рисует эллипс, но он может рисовать что угодно, лишь бы это был один штрих. Ниже приведены некоторые примеры:

Я хочу найти выпуклую оболочку этих фигур. Все алгоритмы выпуклой оболочки, которые я нашел, предполагают случайный, упорядоченный набор точек. Какой алгоритм лучше всего подходит для моей конкретной ситуации, когда пользователь рисует точки, щелкая и перетаскивая мышь, чтобы точки были в порядке.

Примечания:

В частности, многие из них являются алгоритмами, чувствительными к выходу. O (n log h) где n - количество точек во множестве всех точек оригинала, а h - множество точек в выпуклой оболочке. Я ожидаю, что с этими формами h ~ = n, потому что они в основном являются контурами сами по себе.

Наконец, вся цель этого состоит в том, чтобы найти прямоугольник наименьшей площади точек, такой как это:

Может кто-нибудь придумать лучший способ найти прямоугольник, кроме первого нахождения выпуклой оболочки? После исследования это кажется лучшим способом, но мой особый случай может быть другим.

Заранее спасибо!

Answer 1

Держитесь подальше от алгоритмов O (N Log H). Они сложные и медленные!

Использование O (N Log N) намного лучше. Я рекомендую подход monotone chain , простой и быстрый.

Вас не должен беспокоить порядок сложности O (N Log N), который связан только с фазой сортировки. Дополнительный коэффициент Log N / Log H не так катастрофичен (и не существует для множества выпуклых точек), в то время как асимптотическая константа для сортировки очень хорошая.

Если вы стремитесь к максимальной эффективности, конкретное расположение ваших точек предлагает альтернативный подход: точки будут образовывать длинные увеличивающиеся (уменьшающиеся) последовательности, которые вы можете легко обнаружить и отсортировать, объединяя шаги. Сложность снизится до O (N Log K), где K - количество монотонных последовательностей, следовательно, фактически O (N) (это называется Natural Merge Sort).

Вы не очень далеки от варианта использования алгоритма Мелкмана O (N), который можно использовать для корпуса простого многоугольника. К сожалению, условие простоты может не сработать вблизи закрытия кривой, и я не вижу простого способа исправить это.

---

Для ограничивающего прямоугольника Вращающиеся Штангенциркули, безусловно, ваши лучшие друзья.

Answer 2

Мне просто интересно, что произойдет, если вы примените следующий подход:

Думайте о своем полигоне как о матрице 2 x N

P = [x1, x2, ..., xN;
     y1, y2, ..., yN]; 

, где каждый столбец содержит x и yкоордината вершины многоугольника.Затем для любого угла phi между, скажем, 0 и pi/2 определите матрицу вращения

U(phi) = [cos(phi) -sin(phi);
          sin(phi)  cos(phi)];

После этого поверните многоугольник на угол phi, умножив матрицы

P_phi = U(phi)*P;

Тогда функция

f(phi) = ( max( P_phi[1][] ) - min( P_phi[1][] ) )*( max( P_phi[2][] ) - min( P_phi[2][] ) )

- это площадь прямоугольника с горизонтальными и вертикальными краями, надписанная вокруг повернутого многоугольника P(phi).Здесь P_phi[1][] - первая строка координат x матрицы P_phi, а P_phi[2][] - вторая строка координат y.Следовательно, вы хотите найти угол phi и вершины, собранные в матрице 2 x 4 R_phi, прямоугольника, выровненного по осям, который дает минимум функции f(phi) для phi in [0, pi/2], потому что этоплощадь прямоугольника наименьшей площади, надписанного вокруг вашего многоугольника.После того, как вы найдете phi и R_phi, просто поверните назад, как показано ниже R = U(-phi)*R_phi, и это прямоугольник, который вы ищете.

Я не уверен, работает ли это предложение ...

Answer 3

Чтобы найти наименьший вмещающий прямоугольник, выровненный в определенном направлении, вам необходимо знать крайние точки в этом направлении и в ортогональном направлении, и выпуклая оболочка кодирует эту информацию особенно удобным способом, например, для вращающихся штангенциркулей.Если вы хотите приблизиться, вы можете просто попробовать направления каждые пять градусов (или что-то еще), с временем пробега O (nd), где d - количество направлений.Это хорошо работает с поддержкой SIMD, если она у вас есть.