0

возникла проблема с реализацией следующей задачи(у меня есть прямоугольник скажем со случайными шириной и высотой и количеством на которое нужно его разбить):

// W=2 H=4 n=8

      |---------| (2;4)
      |         |
      |         |
      |         |
(0;0) |---------|

Я решил использовать бинарное дерево для этого:

function TreeNode(geometry) {
    this.leftChildNode = null;
    this.rightChildNode = null;
    this.geometry = geometry;
}

function createSquareGeometry(beginX, beginY, endX, endY) {
    return [
         [beginX, beginY],
         [endX, beginY],
         [endX, endY],
         [beginX, endY]
    ];
}

function generate(beginX, beginY, endX, endY, countFigures) {
    let treeNode = new TreeNode(createSquareGeometry(beginX, beginY, endX, endY));
    if (countFigures !== 1) {
        treeNode.leftChildNode = generate(beginX, beginY, endX / 2, endY / 2, countFigures / 2);
        treeNode.rightChildNode = generate(endX / 2, endY / 2, endX, endY, countFigures / 2);
    }
    return treeNode
}

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

1)    |---------| (2;4)
      |         |
      |         |
      |         |
(0;0) |---------|


2)    |---------| (2;4)
      |         |
      |---------|
      |         |
(0;0) |---------|

3)    |---------| (2;4)
      |         |
      |---------|
      |    |    |
(0;0) |---------|


4)    |---------| (2;4)
      |    |    |
      |---------|
      |    |    |
(0;0) |---------|

5) ...

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


Обновлено для @tym32167

Вот мой код:

function divideRectangle(rectangle, countParts, geometry){
    if (countParts === 0) {
        return;
    }
    if (countParts === 1) {
        geometry.push(rectangle);
        return;
    }

    const leftCountParts = Math.floor(countParts / 2);
    const rightCountParts = countParts - 1;

    let newRectangle = null;
    if (rectangle.width > rectangle.height) {
        newRectangle = new Rectangle(rectangle.width / 2, rectangle.height);
    } else {
        newRectangle = new Rectangle(rectangle.width, rectangle.height / 2);
    }

    divideRectangle(newRectangle, leftCountParts, geometry);
    divideRectangle(newRectangle, rightCountParts, geometry);
}


const geometry = [];
const rectangle = new Rectangle(sheetWidth, sheetHeight);
divideRectangle(rectangle, 8, geometry);
console.log(geometry);
4
  • 1
    О каком "случае нечетности" идет речь? "Нечетности" чего? 11 мар 2019 в 10:35
  • 1
    @AnT я так понимаю когда нужно разбить на 5 прямоугольников область 11 мар 2019 в 10:36
  • Если W=2 H=4, и скажем количество фигур = 4, то должно получиться 4 одинаковых прямоугольника, а если количество скажем равно 3, то должно получиться(я прямоугольник равный 1/2 всей площади и два прямоугольника равных по 1/4 всей площади)
    – QuickDzen
    11 мар 2019 в 10:38
  • 1
    скажем количество фигур = 4, то должно получиться 4 одинаковых прямоугольника Почему одинаковых? Не вижу такого условия в исходной формулировке. Я решил использовать бинарное дерево Почему? я не могу правильно сконфигурировать рекурсию Задача в общем нерекурсионная - так что рекурсия при её решении как бы и не нужна.
    – Akina
    11 мар 2019 в 10:49

1 ответ 1

2

Писал на C#, надеюсь, будет и так всё ясно.

Определим класс прямоугольника

public class Rect
{
    public int Width { get; set; }
    public int Height { get; set; }
}

Рекурсивная функция будет принимать прямоугольник, что надо разделить, количество частей, на сколько разделить, и аккумулятор, куда результат складывать.

public void DivideSquare(Rect source, int n, List<Rect> result)
{
    if (n == 0) return;
    if (n == 1)
    {
        result.Add(source);
        return;
    }

    var l = n / 2;
    var r = n - l;

    Rect newSource = null;

    if (source.Width > source.Height)
        newSource = new Rect() { Width = source.Width / 2, Height = source.Height };
    else
        newSource = new Rect() { Width = source.Width, Height = source.Height / 2 };

    DivideSquare(newSource, l, result);
    DivideSquare(newSource, r, result);
}

Получается, делим на каждам шаге прямоугольник на 2. Проверка:

var ret = new List<Rect>();
var source = new Rect() {Height = 4, Width = 2};    
DivideSquare(source, 8, ret);   
foreach(var r in ret)
        Console.WriteLine($"{r.Width} - {r.Height}");   

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

1 - 1
1 - 1
1 - 1
1 - 1
1 - 1
1 - 1
1 - 1
1 - 1

На 7 частей

2 - 1
1 - 1
1 - 1
1 - 1
1 - 1
1 - 1
1 - 1

На 3 части

2 - 2
2 - 1
2 - 1

и тд


UPD

Конечно, если париться по расходу памяти, то можно на каждый чих и не создавать новый Rect, тогда функция будет выглядеть как то так

public void DivideSquare(int width, int height, int n, List<Rect> result)
{
    if (n == 0) return;
    if (n == 1)
    {
        result.Add(new Rect() { Width = width, Height = height });
        return;
    }

    var l = n / 2;
    var r = n - l;

    int newWidth = width; 
    int newHeight = height; 

    if (width > height)
        newWidth/=2;
    else
        newHeight/=2;

    DivideSquare(newWidth, newHeight, l, result);
    DivideSquare(newWidth, newHeight, r, result);
}

Вызов будет как то так

var ret = new List<Rect>(); 
DivideSquare(2, 4, 8, ret);
foreach (var r in ret)
    Console.WriteLine($"{r.Width} - {r.Height}");

Результат будет идентичен


UPD 2

Добавляем координаты к нашему решению (добавлю ко второму варианту, добавление к певрому будет домашним заданием)

Класс будет выглядеть так

public class Rect
{
    public int Width { get; set; }
    public int Height { get; set; } 
    public int Top { get; set; }
    public int Left { get; set; }
}

Метод для разбиения

public void DivideSquare(int width, int height, int top, int left, int n, List<Rect> result)
{
    if (n == 0) return;
    if (n == 1)
    {
        result.Add(new Rect() { Width = width, Height = height, Top = top, Left = left });
        return;
    }

    var l = n / 2;
    var r = n - l;

    int newWidth = width;
    int newHeight = height;

    if (width > height)
    {
        newWidth /= 2;

        DivideSquare(newWidth, newHeight, top, left, l, result);
        DivideSquare(newWidth, newHeight, top, left + newWidth, r, result);

    }
    else
    {
        newHeight /= 2;
        DivideSquare(newWidth, newHeight, top, left, l, result);
        DivideSquare(newWidth, newHeight, top + newHeight, left, r, result);
    }
}

Тест

var ret = new List<Rect>();
DivideSquare(2, 4, 0, 0, 3, ret);
foreach (var r in ret)
    Console.WriteLine($"{r.Top}:{r.Left}  {r.Width} - {r.Height}");

Результат

0:0  2 - 2
2:0  2 - 1
3:0  2 - 1 
16
  • 1
    @QuickDzen не знаю, как вы получаете 18 наборов, вы же ни кода, ничего не показываете. Вот если вы просто сопируете мой код и запустите, вы получите именно тот результат, что я указал.
    – tym32167
    11 мар 2019 в 11:31
  • 1
    @QuickDzen в меньшую. То есть 3/2=1. НО это компенсируется здесь var r = n - l;
    – tym32167
    11 мар 2019 в 11:55
  • 1
    @QuickDzen const rightCountParts = countParts - 1; ==> const rightCountParts = countParts - leftCountParts ;
    – tym32167
    11 мар 2019 в 11:56
  • 1
    @QuickDzen я бы просто поля добавил, что то типа Top и Left или X, Y
    – tym32167
    11 мар 2019 в 11:59
  • 1
    @QuickDzen обновил ответ
    – tym32167
    11 мар 2019 в 12:07

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.