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

Question

Вот моя проблема:

• У меня есть куча кругов, что мне нужно, чтобы отобразить внутри холста.
• Существует произвольное количество кругов, каждый из которых имеет предопределенный радиус.
• Суммарная площадь кругов всегда меньше площади холста.

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

Вот пример того, что я пытаюсь достичь:

Моя первая идея «грубая сила» была следующей:

1. Для каждого круга: вычислить кратчайшее расстояние между его границей и границю другого круга; суммируйте все эти расстояния, назовите это X.
2. Рассчитайте сумму всех X.
3. Случайное изменение расстояний между кругами.
4. Повторите 1-3 для заданного количества итераций и возьмите максимальное значение, полученное на этапе (2).

Однако это не выглядит элегантным; Я уверен, что есть лучший способ сделать это. Есть ли какой-либо существующий алгоритм для достижения такого макета? Есть ли какая-нибудь существующая библиотека, которую я мог бы использовать (JavaScript или Ruby) для достижения этой цели?

Редактировать

Вот Javascript version принятого ответа, который использует Рафаэль рисовать круги.

Answer 1

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

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

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

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

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

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

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

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

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

А вот некоторые грубые C++ код (только алгоритм, не ожидаем, что это скомпилировать)

// 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; 
     } 
     } 
    } 

Answer 2

Возможно, будет полезно применение force-directed layout.

Answer 3

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

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

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

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

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