Ответ 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;
}
}
}