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

Question

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

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

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

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

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

Есть идеи?

Answer 1

Это не совсем завершено, но может дать вам несколько идей.

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

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

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

Answer 2

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

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

Answer 3

Вот самый быстрый из известных мне алгоритмов, который генерирует каждый выпуклый многоугольник с равной вероятностью.Выход имеет ровно 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.
• Рандомизируйте (перемешайте) YVec и обработайте каждую пару XVec[i] и YVec[i] как двумерный вектор.
• Сортируйте эти векторыпо углу, а затем расположите их вплотную, чтобы сформировать многоугольник.
• Переместите многоугольник к исходным минимальным и максимальным координатам.

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

Этот алгоритм основан на работе Павла Вальтра: « Вероятность того, что n случайных точек находятся в выпуклом положении ». Дискретный и вычислительныйГеометрия 13,1 (1995): 637-643.

Answer 4

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

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

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