у менять прямоугольник MxN и также есть число, на которое нужно разбить прямоугольник при помощи маленьких прямоугольник. Вопрос заключается в следующем как узнать ширину и высоту прямоугольника(при условии что прямоугольник будет разбиваться на равные прямоугольники) а также какие существуют алгоритмы разбиения прямоугольника на неравные прямоугольники или треугольники при помощи того же числа на разбиение и MxN размеров большого прямоугольника?
2 ответа
как узнать ширину и высоту прямоугольника(при условии что прямоугольник будет разбиваться на равные прямоугольники)
Так как никаких других ограничений не приведено, алгоритм разбиения очевиден и тривиален: просто сделайте необходимое количество вертикальных или горизонтальных разрезов. Готово.
Можно предложить тривиальную модификацию: если количество целевых прямоугольников не является простым числом, то его можно разложить на два множителя и выполнить соответствующее количество вертикальных и горизонтальных разрезов.
какие существуют алгоритмы разбиения прямоугольника на неравные прямоугольники
В этой задаче еще меньше ограничений. Делайте то же, что и выше, но резмещайте разрезы неравномерно.
Иди просто выполняйте произвольные вертикальные или горизонтальные гильотинные (от края до края) разрезы промежуточных прямоугольников, пока не получится требуемое число частей.
или треугольники
Абсолютно тем же тривиальным подходом. Первый разрез - диагональ, разрезает исходный прямоугольник на два треугольника. Последующие разрезы просто режут промежуточный промежуточный треугольник на два треугольника, пока не получится требуемое число частей.
как узнать ширину и высоту прямоугольника(при условии что прямоугольник будет разбиваться на равные прямоугольники)
Ширину полученных равных прямоугольников можно узнать так:
w = W/n
Здесь n - число разбиения, W - ширина разбиваемого прямогульника, w - ширина получаемого прямогольника (в данном случае, всех получаемых прямоугольников). Высота получается аналогично.
какие существуют алгоритмы разбиения прямоугольника на неравные прямоугольники или треугольники при помощи того же числа на разбиение и MxN размеров большого прямоугольника
Назову только простые способы, более сложные можно найти покопавшись в спец.литературе.
Вы можете применить какой-либо закон изненения шага, или количество разбиений в зависимости от конкретной задачи.
Например, пример линейного разбиения, шаг разбиения уменьшается вдвое (по ширине, или по-высоте, или в обоих направлениях), втрое, вчетверо и так далее. Другой вариант, это менять количество разбиений, в зависимости от реальных значений размеров "оставшихся" прямоугольников.
Кроме линейных вы можете задать, например, экспоненциальный, логарифмический, синусоидальный (любой тригонометрический), табличный (по заранее составленным таблицам) закон разбиения, или изменения числа разбиений, прямогольника (например, все это применяется в численных методах решения задач движения сплошных сред - там где мы не ожидаем каких-либо сложных процессов, расчетная сетка пореже, а там где ожидается - погуще).
Если разбивка пространства требуется треугольниками, то рассмотрите Триангуляция Делоне
.
-
Если у меня есть прямоугольник скажем 2х4 и мне допустим нужно его разбить на 4 равных части, то получается что h = 4 / 4 = 1 и w = 2 / 4 = 0.5. В итоге получится что 75% прямоугольника не будет заполнено... В моем случае при таких исходных данных у меня должно было бы получится что w = 1 и h = 2 или наоборот, но не так, как в вашем алгоритме. 22 фев 2019 в 8:48
-
1@QuickDzen упустил ключевое слово "равные". Но старшие товарищи уже ответили правильно 22 фев 2019 в 9:41