Я бы попытался вставить сферу за сферой (первой по величине).Каждый из них добавляется в самое большое доступное пространство со случайным дрожанием.
Один из относительно простых способов найти (более или менее) самое большое доступное пространство - представить сетку точек на вашем виде и сохранить длякаждая точка сетки (в двумерном массиве) является ближайшим расстоянием к любому элементу: краю или сфере, в зависимости от того, что ближе всего.Этот массив обновляется по мере добавления каждой новой сферы.
Чтобы добавить новую сферу, просто возьмите точку сетки с наибольшим расстоянием и примените случайное дрожание (вы на самом деле знаете, сколько вы можете дрожать, потому что вы знаете расстояние до ближайшего элемента).(Я бы рандомизировал не более чем (dr) / 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;
}
}
}