Как создать случайный выпуклый многоугольник?

Я пытаюсь разработать метод генерации случайных 2D выпуклых многоугольников. Он должен иметь следующие свойства:

координаты должны быть целыми числами;
многоугольник должен лежать внутри квадрата с углами (0, 0) и (C, C), где C задано:
многоугольник должен иметь число вершин, близких к заданному числу N.

Например, генерируем случайные полигоны, которые имеют 10 вершин и лежат внутри квадрата [0..100] x [0..100].

Что затрудняет эту задачу, так это то, что координаты должны быть целыми числами.

Подход, который я пытался, заключался в том, чтобы создать случайный набор точек в данном квадрате и вычислить выпуклую оболочку этих точек. Но результирующая выпуклая оболочка имеет очень мало вершин по сравнению с N.

Любые идеи?

Ответ 1

Это не совсем полно, но это может дать вам некоторые идеи.

Выйдите, если N < 3. Создайте единичный круг с N вершинами и поверните его в произвольном порядке [0..90] градусов.

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

После настройки ваших вершин найдите вершину с наибольшей величиной от начала координат. Разделите каждую вершину на эту величину, чтобы нормализовать многоугольник, а затем масштабируйте его (C/2). Переведите на (C/2, C/2) и верните целое число.

Ответ 2

Простым алгоритмом будет:

Начните со случайной строки (две вершины и два многогранника)
Возьмем случайное ребро E многоугольника
Сделать новую случайную точку P на этом краю
Возьмем прямую L, перпендикулярную E, проходящую через точку P. Вычисляя пересечение между линией T и строками, определяемыми двумя ребрами, смежными с E, вычислите максимальное смещение P, когда выпуклость не сломана.
Случайное смещение точки P в этом диапазоне.
Если недостаточно точек, повторите с 2.

Ответ 3

Ваш первоначальный подход правильный - вычисление выпуклой оболочки - это единственный способ удовлетворить случайность, выпуклость и целостность.

Единственный способ, которым я могу думать об оптимизации вашего алгоритма, чтобы получить "больше очков", - это организовать их вокруг круга, а не полностью случайным образом. Ваши точки, скорее всего, будут находиться рядом с "краями" вашего квадрата, чем возле центра. В центре вероятность должна быть равна ~ 0, так как многоугольник должен быть выпуклым.

Один простой вариант - установить минимальный радиус для ваших точек - возможно, C/2 или C * 0.75. Вычислите центр квадрата C, и если точка слишком близко, отведите его от центра до достижения минимального расстояния.

Ответ 4

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

Создайте два списка X и Y из N случайных чисел от 0 до C. Убедитесь, что дубликатов нет.
Сортировка X и Y и сохранение их максимального и минимального элементов.
Случайно разделите остальные (не max или min) элементы на две группы: X1 и X2, и Y1 и Y2.
Повторно вставьте минимальный и максимальный элементы в начале и конце этих списков (minX в начале X1 и X2, maxX в конце и т.д.).
Найдите последовательные разности (X1[i + 1] - X1[i]), изменив порядок для второй группы (X2[i] - X2[i + 1]). Сохраните их в списках XVec и YVec.
Randomize (shuffle) YVec и обрабатывать каждую пару XVec[i] и YVec[i] как 2D-вектор.
Сортируйте эти векторы по углу, а затем отложите их от конца до конца, чтобы сформировать многоугольник.
Переместите многоугольник в исходные минимальные и максимальные координаты.

Анимация и реализация Java доступны здесь: Генерация случайных выпуклых многоугольников.

Этот алгоритм основан на статье Павла Вальтра: " Вероятность того, что n случайных точек находятся в выпуклой позиции". Дискретная и вычислительная геометрия 13.1 (1995): 637-643.