Форма головоломки решить с помощью программирования

Ответ 1

Я думаю, что ваша проблема - это конкретный случай " Проблема режущего материала.

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

Более конкретно, он вписывается в двухмерное подмножество. И в вашем случае потерянная площадь в растворе должна быть равна нулю.

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

Ответ 2

Кубическая упаковка (разрезать куб в меньших прямоугольных кубоидах и найти алгоритм для их объединения) считалась алгоритмически неразрешимой проблемой в те дни, когда я был студентом. Я не проверял, что-то изменилось.

О упаковке прямоугольника - вот дипломная работа с прошлого года по теме: https://arxiv.org/pdf/1711.07851.pdf

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

Ответ 3

Я написал что-то вроде этого класса AI в 1971 году. Настоящий флегер памяти.

Я описал каждый прямоугольник с таким же рисунком (2 L 1 L 2 L 1 L) (подумайте о черепахе. Затем, учитывая два блока, вы можете разместить их смежными по фиксированному числу способов и вычислить новый шаблон. Я просто разместил их наугад и создал решетку всех возможных шагов. Если бы я использовал все прямоугольники, а результат был прямоугольником, у меня было решение.

Ответ 4

Вы можете сделать это, обратившись назад.

Вы можете рекурсивно вызвать следующий шаблон:

bool RecursiveFunction(RemainingArea, RemainingShapes) 
{
  Check RemainingShapes empty
  {
    return true
  }
  for all ShapeCandidate in RemainingShapes
  {
    for all Rotations of ShapeCandidate 
    {
       Try if ShapeCandidate fits at bottom most leftmost corner of RemainingArea
       {
          Compute NewRemainingArea
          Try if RecursiveFunction( NewRemainingArea, RemainingShapes - ShapeCandidate ) returns true
          {
             return true;
          }
       }
    }
  }
  return false
}

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

Ответ 5

Сначала мне кажется, что мы должны выбрать самый большой прямоугольник (длина максимальной длины которого больше, чем остальные прямоугольники с максимальной длиной) и "выровнять" другие прямоугольники вокруг него. Пример.

Выберите самый большой прямоугольник.

Создайте список ваших прямоугольников. Их порядок в списке будет устанавливать порядок расположения снизу вверх первого прямоугольника.

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

Выберите следующий прямоугольник прямо над предыдущим прямоугольником, пока не будет выполнено одно из двух условий:

• Вы выбрали все прямоугольники.
• Общая длина вертикальных длин меньших прямоугольников больше, чем вертикальная сторона первого прямоугольника.

Обработчик первого условия: Создайте рекурсивную функцию, которая будет поворачивать каждый прямоугольник на 90 градусов, уникальным образом изменяет порядок в списке и найдет область прямоугольника минимального размера, которая будет содержать все ваши прямоугольники. Если эта минимальная область равна суммарной площади ваших прямоугольников, мы делаем здесь. Если он не делает то же самое для верхней части первого прямоугольника. (Выровняйте прямоугольники не с правой стороны, а с верхней стороны). Если вы не нашли решение, ваш вход не был "идеальным" и не существует никакого решения.

Второе условие немного сложнее. В настоящее время я не знаю, как с этим справиться. Надеюсь, это поможет вам найти решение.

Ответ 6

Я хотел бы указать на общую проблему, которую вы видите NP-hard/complete.

Таким образом, для упаковки прямоугольника-бина доступны ровно нулевые и эффективные алгоритмы. Проблема может быть решена, но время выполнения не определено и/или очень медленно.

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

См. (пока) еще одну бумагу здесь и некоторый фактический код в здесь (доступно в общественном достоянии) Автор статьи предоставляет некоторые полезные коды и многие алгоритмы в этой проблеме.

Поскольку вам требуется идеальная настройка прямоугольников, большинство этих алгоритмов не подходят. (Это aproximate решения!)

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

bool tetris_rectangle_fit(int w, int h, list<Rect> rects, list<Rect> & freespace) {
    Compute bottom-left-most position x,y in free-space.
    While rects not empty:
        Pop Rect R from rects;
        If R fits into the freespace at x,y:
            list<Rect> tmp = freespace;
            Subtract R from freespace; (append it into the list)
            If freespace equals to zero:
                freespace = tmp
                Return True;
            If tetris_rectangle_fit(w,h, rects, tmp):
                freespace = tmp;
                Return True;
            Else:
                Return False;
        Else:
            Swap R width and height;
            <Try fit R again into freespace>;
    Return False;
}

Ответ 7

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

   struct box
{
   int left;                                        // Top-left point
   int top;                                     // coordinate pair

   int right;                                       // Bottom right point
   int bottom;                                      // coordinate pair
};

Я также отметил, что вы не указали координаты или размеры этих ящиков. Поэтому я их буду изобретать.

Я даю область слева вверху (0,0) и внизу справа (70, 100)... tis, где находятся упакованные коробки.

Это оригинальный макет...

#include <iostream>

using namespace std;

// Definition of a struct to represent boxs
struct box
{
    int left;                                       // Top-left point
    int top;                                        // coordinate pair
    int right;                                      // Bottom-right point
    int bottom;                                     // coordinate pair
};
// Prototype of function to calculate the area of a box
long area(const box& aBox);
// Prototype of a function to move a box
void moveBox(box& aBox, const int x, const int y);

int main()
{
    box A{ 0, 0, 30, 100 };
    box B{ 30, 60, 60, 100 };
    box C{ 60, 65, 100, 100 };
    box D{ 100, 60, 135, 100 };

    moveBox(A, 40, 0);

    moveBox(C, 0, 30);  // Now move it to the new position

    D = C;              // Define box D the same as C

    moveBox(D, 0, 65);  // Now move it parallel to C

    B = { 30, 70, 70, 100 };

    moveBox(B, 0, 0);


    cout << "Coordinates of A are "
        << A.left << " from the left" << ", " << A.top << " Down, " << A.right << " to the right " << "and " << A.bottom << " to the bottom of A " << endl;

    cout << "Coordinates of B are "
        << B.left << " from the left" << ", " << B.top << " Down, " << B.right << " to the right " << "and " << B.bottom << " to the bottom of B " << endl;

    cout << "Coordinates of C are "
        << C.left << " from the left" << ", " << C.top << " Down, " << C.right << " to the right " << "and " << C.bottom << " to the bottom of C " << endl;

    cout << "Coordinates of D are "
        << D.left << " from the left" << ", " << D.top << " Down, " << D.right << " to the right " << "and " << D.bottom << " to the bottom of D " << endl;
    return 0;
}
// Function to calculate the area of a box
 long area(const box& aBox)
{
    return (aBox.right - aBox.left)*(aBox.bottom - aBox.top);
}
// Function to Move a box
void moveBox(box& aBox, const int x, const int y)
{
    const int length{ aBox.right - aBox.left }; // Get length of box
    const int width{ aBox.bottom - aBox.top }; // Get width of box
    aBox.left = x; // Set top-left point
    aBox.top = y; // to new position
    aBox.right = x + length; // Get bottom-right point as
    aBox.bottom = y + width; // increment from new position
   return;
}

Ответ 8

Это немного грубо по краям, но я не мог не иметь немного веселья и кодирования подхода грубой силы в MATLAB в качестве примера. Функция pack_shapes приведена ниже и описана ниже. Он принимает массив структуры с двумя полями: 'Vertices', матрица вершин (2 координаты в верхней строке, y координаты в нижней строке) и 'Face', 1-by-M вектора индексов в столбцы 'Vertices', который определяет ребра многоугольника (по часовой стрелке или против часовой стрелки). Вот пример с тремя четырехугольными формами:

% Define a structure array of polygons:
s1 = struct('Vertices', [0 0 1 1; 0 3 3 0], 'Face', 1:4);
s2 = struct('Vertices', [2 2 3 3; 0 1 1 0], 'Face', 1:4);
s3 = struct('Vertices', [4 4 5 5; 0 2 2 0], 'Face', 1:4);
shapes = [s1 s2 s3];

% Plot the initial shapes:
subplot(1, 2, 1);
patch('Faces', shapes(1).Face, 'Vertices', shapes(1).Vertices.', 'FaceColor', 'r');
hold on;
patch('Faces', shapes(2).Face, 'Vertices', shapes(2).Vertices.', 'FaceColor', 'g');
patch('Faces', shapes(3).Face, 'Vertices', shapes(3).Vertices.', 'FaceColor', 'b');
axis equal;
title('Before packing');

% Pack and plot the results:
packed = pack_shapes(shapes);
subplot(1, 2, 2);
patch('Faces', packed(1).Face, 'Vertices', packed(1).Vertices.', 'FaceColor', 'r');
hold on;
patch('Faces', packed(2).Face, 'Vertices', packed(2).Vertices.', 'FaceColor', 'g');
patch('Faces', packed(3).Face, 'Vertices', packed(3).Vertices.', 'FaceColor', 'b');
axis equal;
title('After packing');

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

Вот код. Я написал его очень общим способом, позволяя использовать многоугольники с различным числом вершин, хотя я, по-видимому, еще не полностью протестировал его для всех случаев (только четырехугольники):

function packedShapes = pack_shapes(unpackedShapes, packedShapes)
% Inputs are structure arrays with fields 'Vertices' (2-by-N) and 'Face'
% (1-by-M).
  persistent absoluteMinArea minArea bestShapes;

  if (nargin == 1)
    if (numel(unpackedShapes) <= 1)
      packedShapes = unpackedShapes;
    else
      oldState = warning('off', 'all');
      absoluteMinArea = 0;
      minArea = Inf;
      for iShape = 1:numel(unpackedShapes)
        index = unpackedShapes(iShape).Face;
        if (index(1) ~= index(end))
          index = index([1:end 1]);
          unpackedShapes(iShape).Face = index;
        end
        vertices = unpackedShapes(iShape).Vertices(:, index);
        absoluteMinArea = absoluteMinArea+polyarea(vertices(1, :), vertices(2, :));
        unpackedShapes(iShape).Index = iShape;
      end
      pack_shapes(unpackedShapes(2:end), unpackedShapes(1));
      [~, index] = sort([bestShapes.Index]);
      bestShapes = rmfield(bestShapes(index), 'Index');
      packedShapes = bestShapes;
      warning(oldState);
    end
    return;
  end

  vertices = [packedShapes.Vertices];
  nVertices = 0;
  packedEdges = [];
  for iShape = 1:numel(packedShapes)
    packedEdges = [packedEdges ...
                   packedShapes(iShape).Face([1:(end-1); 2:end])+nVertices];
    nVertices = nVertices+size(packedShapes(iShape).Vertices, 2);
  end
  nShapes = numel(unpackedShapes);

  for iPV = 1:nVertices
    pEdges = packedEdges(:, any(packedEdges == iPV, 1));
    pEdges = [iPV iPV; pEdges(pEdges ~= iPV).'];
    for iShape = 1:nShapes
      currentShape = unpackedShapes(iShape);
      currentEdges = currentShape.Face([1:(end-1); 2:end]);
      constrainedEdges = [packedEdges currentEdges+nVertices].';
      for iCV = 1:size(currentShape.Vertices, 2)
        cEdges = currentEdges(:, any(currentEdges == iCV, 1));
        cEdges = [iCV iCV; cEdges(cEdges ~= iCV).'];
        for iEdge = [1 1 2 2; 1 2 1 2]
          u = diff(currentShape.Vertices(:, cEdges(:, iEdge(2))), 1, 2);
          v = diff(vertices(:, pEdges(:, iEdge(1))), 1, 2);
          theta = acos(dot(u,v)/(norm(u)*norm(v)));
          R = [cos(theta) -sin(theta); sin(theta) cos(theta)];
          newVertices = R*bsxfun(@minus, currentShape.Vertices, ...
                                 currentShape.Vertices(:, iCV));
          newVertices = bsxfun(@plus, newVertices, vertices(:, iPV));
          if shapes_overlap()
            continue;
          else
            newShapes = [packedShapes currentShape];
            newShapes(end).Vertices = newVertices;
            shapeIndex = setdiff(1:nShapes, iShape);
            if isempty(shapeIndex)
              newVertices = [vertices newVertices].';
              K = convhull(newVertices);
              newArea = polyarea(newVertices(K, 1), newVertices(K, 2));
              if (newArea < minArea)
                minArea = newArea;
                bestShapes = newShapes;
              end
            else
              pack_shapes(unpackedShapes(shapeIndex), newShapes);
            end
            if (minArea <= absoluteMinArea+100*eps(absoluteMinArea))
              return;
            end
          end
        end
      end
    end
  end

  function bool = shapes_overlap
    DT = delaunayTriangulation([vertices newVertices].', constrainedEdges);
    dtFaces = DT.ConnectivityList;
    dtVertices = DT.Points;
    meanX = mean(reshape(dtVertices(dtFaces, 1), size(dtFaces)), 2);
    meanY = mean(reshape(dtVertices(dtFaces, 2), size(dtFaces)), 2);
    xyPoly = newVertices(:, currentShape.Face);
    nInside = inpolygon(meanX, meanY, xyPoly(1, :), xyPoly(2, :));
    for iCheck = 1:numel(packedShapes)
      xyPoly = packedShapes(iCheck).Vertices(:, packedShapes(iCheck).Face);
      nInside = nInside + inpolygon(meanX, meanY, xyPoly(1, :), xyPoly(2, :));
    end
    bool = any(nInside > 1);
  end

end

Алгоритм сначала начинается с одной формы (назовем ее фиксированной формой). Затем он перебирает все вершины фиксированной формы, затем поверх всех оставшихся фигур (т.е. Подвижных фигур), затем по всем вершинам каждой из этих фигур. Упаковка форм предполагает, что они присоединятся к их вершинам и выравнивают их края, поэтому для каждой пары неподвижных и подвижных вершин мы найдем ребра, которые соединяются с этими вершинами (2 ребра для фиксированной формы и 2 ребра для подвижной формы). Для каждого из 4 возможных спариваний этих ребер вычисляется угол поворота, чтобы выровнять подвижный край с фиксированным краем. Вершины перемещаемой формы затем переводятся и вращаются, поэтому заданные вершины перекрываются, и данные ребра выравниваются.

Затем вступает в игру вложенная функция shapes_overlap. Эта функция предназначена для проверки того, перекрывает ли подвижная форма фиксированную форму. Если это так, это недействительно, и мы переходим к следующей комбинации вершин и ребер. Код в shapes_overlap можно написать любым количеством способов. Более поздние версии MATLAB (R2017b или новее) имеют intersect метод для polyshape. Обсуждаются дополнительные методы поиска перекрытий многоугольников здесь. Подход, который я адаптировал, заключался в создании триангуляции Delaunay фиксированных и подвижных вершин с использованием краев многоугольника как ограниченные края. Затем центроид каждой треугольной грани проверяется с помощью inpolygon, чтобы увидеть, сколько из многоугольников (фиксированных или подвижных) находится внутри. Если любые треугольные центроиды находятся внутри более чем одного полигона, это означает, что полигоны перекрываются.

Если нет перекрытия, мы затем проверяем, есть ли какие-либо другие формы для упаковки. Если нет, мы вычисляем выпуклый корпус фиксированной и подвижной фигуры вместе, подразумевая предположение, что идеальный результат упаковки даст выпуклую форму, Если вычисленный area корпуса меньше текущей лучшей области, мы сохраняем это расположение фигуры. Если есть больше форм для упаковки, мы вызываем pack_shapes рекурсивно, причем фиксированная форма фактически становится большим набором фиксированных фигур на каждом уровне рекурсии. Если минимальная площадь всегда находится в пределах некоторого допуска оптимальной минимальной площади (то есть идеальной упаковки), алгоритм останавливается там.

Есть несколько улучшений, которые могут быть сделаны. Некоторые другие показатели формы, помимо общей площади, могут быть включены в критерии остановки, чтобы избежать решения "стопку блоков", которое я получил выше в пользу решений с более компактными результатами. Кроме того, функция shapes_overlap потенциально может быть улучшена путем поиска пересечений сегментов линии вместо использования триангуляции Delaunay.

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