Пространство, заполняемое кругами неравного размера

Ответ 1

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

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

Чтобы добавить новую сферу, просто возьмите точку сетки с наибольшим расстоянием и примените некоторый случайный дрожание (вы действительно знаете, как сильно вы дрожите, потому что знаете расстояние до ближайшего предмета). (Я бы рандомизировал не более (d-r)/2, где d - расстояние в массиве, а r - радиус добавляемой сферы.

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

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

Вот некоторые результаты этой реализации (мне потребовалось около 100 строк кода)

• 100 Кругов различного размера

• 500 Круги разного размера

• 100 кругов одинакового размера

И вот какой-то грубый код на С++ (просто алгоритм, не ожидайте, что это скомпилируется)

    // INITIALIZATION

    // Dimension of canvas
    float width = 768;
    float height = 1004;

    // The algorithm creates a grid on the canvas
    float gridSize=10;

    int gridColumns, gridRows;
    float *dist;

    void initDistances()
    {
      // Determine grid dimensions and allocate array
      gridColumns = width/gridSize;
      gridRows = height/gridSize;

      // We store a 2D array as a 1D array:
      dist = new float[ gridColumns * gridRows ];

      // Init dist array with shortest distances to the edges
      float y = gridSize/2.0;
      for (int row=0; row<gridRows; row++)
      {
        float distanceFromTop = y;
        float distanceFromBottom = height-y;
        for (int col=0; col<gridColumns; col++)
        {
          int i = row*gridColumns+col;
          dist[i]=(distanceFromTop<distanceFromBottom?distanceFromTop:distanceFromBottom);
        }
        y+=gridSize;
      }
      float x = gridSize/2.0;
      for (int col=0; col<gridColumns; col++)
      {
        float distanceFromLeft = x;
        float distanceFromRight = width-x;
        for (int row=0; row<gridRows; row++)
        {
          int i = row*gridColumns+col;
          if (dist[i]>distanceFromLeft) dist[i] = distanceFromLeft;
          if (dist[i]>distanceFromRight) dist[i] = distanceFromRight;
        }
        x+=gridSize;
      }
    }

    void drawCircles()
    {
      for (int circle = 0; circle<getNrOfCircles(); circle++)
      {
        // We assume circles are sorted large to small!
        float radius = getRadiusOfCircle( circle ); 

        // Find gridpoint with largest distance from anything
        int i=0;
        int maxR = 0;
        int maxC = 0;
        float maxDist = dist[0];

        for (int r=0; r<gridRows; r++) 
          for (int c=0; c<gridColumns; c++)
          {
            if (maxDist<dist[i]) {
              maxR= r; maxC= c; maxDist = dist[i];
            }
            i++;
          }

        // Calculate position of grid point
        float x = gridSize/2.0 + maxC*gridSize;
        float y = gridSize/2.0 + maxR*gridSize;

        // Apply some random Jitter
        float offset = (maxDist-radius)/2.0;
        x += (rand()/(float)RAND_MAX - 0.5) * 2 * offset;
        y += (rand()/(float)RAND_MAX - 0.5) * 2 * offset;


        drawCircle(x,y,radius);


        // Update Distance array with new circle;
        i=0;
        float yy = gridSize/2.0;
        for (int r=0; r<gridRows; r++)
        {
          float xx = gridSize/2.0;
          for (int c=0; c<gridColumns; c++)
          {
            float d2 = (xx-x)*(xx-x)+(yy-y)*(yy-y);

            // Naive implementation
            // float d = sqrt(d2) - radius;
            // if (dist[i]>d) dist[i] = d;

            // Optimized implementation (no unnecessary sqrt)
            float prev2 = dist[i]+radius;
            prev2 *= prev2;
            if (prev2 > d2)
            {
              float d = sqrt(d2) - radius;
              if (dist[i]>d) dist[i] = d;
            }



            xx += gridSize;
            i++;
          }
          yy += gridSize;
        }
      }
    }

Ответ 2

Возможно, будет полезно применение форсированного макета.

Ответ 3

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

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

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

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

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