Разделить сетку (2D массив) на части произвольной формы?

Question

Проблема
Я хочу разделить сетку (двумерный массив) на части произвольной формы (например, тектонические плиты Земли ).

Критерии:

• Пользователь вводит размер сетки (программа должна масштабироваться, поскольку она может быть очень большой).
• Пользователь вводит коэффициент деления сетки (сколько частей).
• Сетка представляет собой шестигранную решетку прямоугольной формы, которая закрывается сверху и снизу, оборачивается вокруг слева и справа.
• Нет фрагментации частей.
• Нет частей внутри других частей.
• Никаких крошечных или сверхбольших частей.
• Части произвольной формы, которые не являются идеальными кругами или вытянутыми змеиными формами.

Мое решение:

• Создать метод, который может получить доступ / манипулировать соседними ячейками.
• Произвольно определить размер каждой части (сумма всех частей равна размеру всего двумерного массива).
• Заполните весь двумерный массив идентификатором последней части.
• Для каждой части, кроме последней:
• Поместить текущий номер детали в случайную ячейку двумерного массива.
• Выполните итерацию по всему массиву и сохраните адрес каждой ячейки рядом с любыми ячейками, которые уже заполнены текущим номером детали.
• Извлеките один из сохраненных адресов и заполните эту ячейку текущим идентификационным номером пластины (и, таким образом, деталь начнет формироваться).
• Повторяйте, пока не будет достигнут размер детали.

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

Запуск моего решения дает следующее:
Размер сетки: 200
ширина: 20
высота: 10
Запчасти: 7

66633333111114444466
00033331111114444466
00003331111114444466
00003331111144444660
00000333111164444660
00000336111664422600
00000336615522222200
00006655555522222200
00006655555552222220
00066655555552222220

Номер детали: 0
Размер части: 47

Номер детали: 1
Размер детали: 30

Номер детали: 2
Размер части: 26

Номер детали: 3
Размер части: 22 * ​​1079 *

Номер детали: 4
Размер части: 26

Номер детали: 5
Размер части: 22 * ​​1085 *

Номер детали: 6
Размер части: 27

Проблемы с моим решением:

• Последняя часть всегда фрагментирована - в приведенном выше случае есть три отдельные группы по шесть человек.
• Алгоритм остановится, когда детали образуются в тупиках, и у них нет места для увеличения до их полного размера (алгоритм не позволяет формировать детали поверх других деталей, если это не последняя деталь, которая установлена по всему массиву 2D в начале).
• Если я не укажу размеры деталей перед формированием массива 2d, а просто укажу количество деталей и случайное генерирование размеров деталей на лету, это оставляет возможность формирования крошечных деталей, что может даже не быть там вообще, особенно когда двумерный массив очень большой. Мой текущий метод определения размера деталей ограничивает размеры деталей до 10-40% от общего размера двумерного массива. Я могу согласиться с тем, чтобы не указывать размеры частей, если есть какой-то супер-элегантный способ сделать это - единственный элемент управления, который будет у пользователя, - это размер двухмерного массива и количество частей.

Другие идеи:

• Сформируйте части в идеально выровненные квадраты, затем обведите 2D-массив и случайным образом разрешите каждой части вторгаться в другие части, деформируя их в случайные формы.
• Нарисуйте змеевидные линии по сетке и заполните созданные места, возможно, используя некоторую математику, подобную этой: http://mathworld.wolfram.com/PlaneDivisionbyLines.html

Вывод:
Так вот в чем суть: я начинающий программист, который не уверен, правильно ли я решаю эту проблему.Я могу создать еще несколько методов «исправления», которые сдвигают фрагментированные части вместе и позволяют формирующимся частям «выпрыгивать» из тупиков, если они застряли в них, но это кажется грязным.1118 * Как бы вы подошли к этой проблеме?Есть ли какая-нибудь сексуальная математика, которую я мог бы использовать, чтобы упростить вещи возможно?

Thx

Answer 1

Несколько месяцев назад я сделал нечто подобное для игры, хотя это была прямоугольная, а не шестиугольная сетка.Тем не менее, теория та же самая, и она придумала хорошие смежные области примерно одинакового размера - некоторые были больше, некоторые были меньше, но ни одна не была слишком маленькой или слишком большой.YMMV.

1. Создайте массив указателей на все пробелы в вашей сетке.Перемешать массив.
2. Назначить первые N из них идентификаторов - 1, 2, 3 и т. Д.
3. Пока массив не укажет на пробелы, не имеющие идентификаторов,
4. Итерация по массиву для поиска пространств, которые не имеют идентификаторов
5. Если у пространства есть соседи в сетке, которые имеют идентификаторы, присвойте этому пространству идентификатор из взвешенного случайного выбора идентификаторов его соседей.
6. Если у него нет соседей с идентификаторами, переходите к следующему.
7. Как только нет непустых пробелов, у вас есть карта с достаточным количеством больших областей.

Answer 2

Вот что я хотел бы сделать: использовать алгоритм Вороного.Сначала поместите несколько случайных точек, затем пусть алгоритм Вороного генерирует части.Чтобы понять, как это выглядит, обратитесь к этому апплету .

Answer 3

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

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

Затем создайте сетку, которая будет в два раза больше (в каждом направлении), и скопируйте ваши регионы,Вы, вероятно, можете использовать ближайшего соседа.Затем снова нарушьте границы и повторяйте, пока не достигнете желаемого разрешения.