javascript - JS将子元素随机分布在其父元素中，不重叠

Question

我正在尝试制作一些可以动态生成一堆圆圈(具有边框半径的 div)并将其放置在容器中而不重叠的东西。

这是我迄今为止的进展 - https://jsbin.com/domogivuse/2/edit?html,css,js,output

var sizes = [200, 120, 500, 80, 145];
var max = sizes.reduce(function(a, b) {
    return Math.max(a, b);
});
var min = sizes.reduce(function(a, b) {
    return Math.min(a, b);
});
var percentages = sizes.map(function(x) {
    return ((x - min) * 100) / (max - min);
});
percentages.sort(function(a, b) {
    return b-a;
})
var container = document.getElementById('container');
var width = container.clientWidth;
var height = container.clientHeight;
var area = width * height;
var maxCircleArea = (area / sizes.length);
var pi = Math.PI;
var maxRadius = Math.sqrt(maxCircleArea / pi);
var minRadius = maxRadius * 0.50;
var range = maxRadius - minRadius;
var radii = percentages.map(function(x) {
    return ((x / 100) * range) + minRadius;
});
function getRandomArbitrary(min, max) {
    return Math.random() * (max - min) + min;
}

var coords = [];
radii.forEach(function(e, i) {
    var circle = document.createElement('div');
    var randomTop = getRandomArbitrary(0, height);
    var randomLeft = getRandomArbitrary(0, width);
    var top = randomTop + (e * 2) < height ?
        randomTop :
        randomTop - (e * 2) >= 0 ?
        randomTop - (e * 2) :
        randomTop - e;
    var left = randomLeft + (e * 2) < width ?
        randomLeft :
        randomLeft - (e * 2) >= 0 ?
        randomLeft - (e * 2) :
        randomLeft - e;
    var x = left + e;
    var y = top + e;

    coords.push({x: x, y: y, radius: e});
    circle.className = 'bubble';
    circle.style.width = e * 2 + 'px';
    circle.style.height = e * 2 + 'px';
    circle.style.top = top + 'px';
    circle.style.left = left + 'px';
    circle.innerText = i
    container.appendChild(circle);
});

我已将它们添加到父容器中，但正如您所看到的，它们重叠，我真的不知道如何解决这个问题。我尝试实现像 (x1 - x2)^2 + (y1 - y2)^2 < (radius1 + radius2)^2 这样的公式但我对此一无所知。

感谢任何帮助。

Answer 1

您想要做的事情称为“打包”，实际上是一个非常困难的问题。您可以在此处采取几种可能的方法。

首先，您可以随机分布它们(就像您当前所做的那样)，但包括“重试”测试，其中如果一个圆圈与另一个圆圈重叠，您将尝试一个新位置。由于可能会出现不可能的情况，因此您还需要一个重试限制，在该限制时它会放弃，返回到开头，并尝试再次随机放置它们。这种方法相对简单，但缺点是不能将它们包装得非常密集，因为重叠的机会变得非常非常高。如果总面积的 1/3 被圆圈覆盖，这可能有效。

其次，您可以在添加更多圆圈时调整先前放置的圆圈的位置。这更相当于物理上实现的方式——当你添加更多的东西时，你开始不得不把附近的东西推开以适应新的东西。这不仅需要找到当前圆圈击中的物体，还需要找到如果该圆圈移动则会击中的物体。我建议使用类似于“弹性”算法的方法，其中随机放置所有圆圈(不考虑它们是否合适)，然后有一个计算重叠的循环，然后根据重叠对每个圆圈施加力(他们互相推开)。这将使圆圈彼此远离，直到它们停止重叠。它还将支持一个圆圈将第二个圆圈插入第三个圆圈，依此类推。这写起来会更复杂，但会支持更密集的配置(因为它们最终可能会接触)。不过，您可能仍然需要进行“这是不可能的”检查，以防止它陷入困境并永远循环。