绘制随机漫画风格云的算法

Question

我想找出一种算法来绘制这种随机形状，知道可以刻在它们中的最大矩形的大小:

我想让可变文本适合云层，其中一些可能很短，而另一些可能只有几句话；这就是为什么我不能选择预定义尺寸的原因。

我目前的做法如下:

1. 创建可以内切在矩形中的最大圆，使用它的最短边作为圆的直径。
2. 创建另一个大小随机的圆，圆心位于第一个圆的边缘某处。
3. 找到两个圆之间的交点并随机选择一个。
4. 以所选点为中心放置另一个大小随机的圆圈。查找与先前圆圈的交点(被圆圈覆盖的除外)并重复，直到所有剩余的交点都出现在矩形之外。

我希望，通过将圆圈放置在其他圆圈之间的交点处，与将圆圈放置在矩形内的随机位置相比，我将以更少的步骤覆盖所有需要的区域，方法是最大限度地减少放置的圆圈数量在先前的圈子已经完全覆盖的区域。

第一次试验产生了这个丑陋的东西:

但我发现其中有几个问题:

1. 尽管所有剩余的交叉点都出现在矩形之外，但并非所有交叉点都被覆盖，因为它的左下角在白色圆圈下方以蓝色可见。
2. 我不知道如何用小缺口画出轮廓。

有人知道随机绘制这些形状的机制吗？谢谢。

编辑:

按照 et_l 的极好建议，我将这个次优的实现放在一起，仍然没有达到预期的结果，但比我自己的初始试验好得多:

function vector(a, b)
{
    if (!(this instanceof vector)) return new vector(a, b);
    if (a instanceof vector && b instanceof vector) {
        this.x = b.x - a.x;
        this.y = b.y - a.y;
    }
    else {
        this.x = a;
        this.y = b;
    }
}

vector.prototype =
{
    get lengthSq()
    {
        return this.x * this.x + this.y * this.y;
    },
    get length()
    {
        return Math.sqrt(this.lengthSq);
    },
    get angle()
    {
        return (Math.PI / 2) + Math.atan2(this.x, this.y);
    },
    distanceTo:function(x, y)
    {
        if (arguments.length == 1) return new vector(this, arguments[0]).length; 
        return new vector(this, new vector(x, y)).length;
    },
    clone: function()
    {
        return new vector(this.x, this.y);
    },
    normalize: function()
    {
        var l = this.length;
        this.x /= l;
        this.y /= l;
        return this;
    },
    get normalized()
    {
        return this.clone().normalize();
    },
    add: function(x, y)
    {
        if (x instanceof vector) return this.add(x.x, x.y);
        this.x += x;
        this.y += y;
        return this;
    },
    scale: function(x, y)
    {
        if (y === undefined) y = x;
        this.x *= x;
        this.y *= y;
        return this;
    },
    scaled: function(x, y)
    {
        return this.clone().scale(x, y);
    }
};

vector.add = function(v1, v2)
{
    return v1.clone().add(v2);
};

vector.dot = function(v1, v2)
{
    return v1.x * v2.x + v1.y * v2.y;
};

vector.cross = function(v1, v2)
{
    return v1.x * v2.y - v1.y * v2.x;
}

function line(p1, p2)
{
    if (!(this instanceof line)) {
        if (arguments.length == 0) return new line();
        if (arguments.length == 2) return new line(arguments[0], arguments[1]);
        if (arguments.length == 4) return new line(arguments[0], arguments[1], arguments[2], arguments[3])
    }
    if (arguments.length == 0) {
        this.p1 = new vector(0, 0);
        this.p2 = new vector(0, 0);    
    }
    else if (arguments.length == 2) {
        this.p1 = p1;
        this.p2 = p2;    
    }
    else if (arguments.length == 4) {
        this.p1 = new vector(arguments[0], arguments[1]);
        this.p2 = new vector(arguments[2], arguments[3]);
    }
}

line.prototype =
{
    get angle()
    {
        return new vector(this.p1, this.p2).angle;
    },
    get lengthSq()
    {
        return new vector(this.p1, this.p2).lengthSq;
    },
    get length()
    {
        return new vector(this.p1, this.p2).length;
    },
    distanceTo: function(p, extend)
    {
        var pp;
        var v1 = new vector(this.p1, p);
        var v2 = new vector(this.p1, this.p2);
        var v2len2 = v2.lengthSq;
        var disc = v2len2 == 0 ? -1 : vector.dot(v1, v2) / v2len2;
        if (!extend && disc < 0) pp = this.p1;
        else if (!extend && disc > 1) pp = this.p2;
        else pp = vector.add(this.p1, v2.scaled(disc));
        return new vector(p, pp).length;
    },
    intersect:function(other)
    {
        var otx, oty, tdx, tdy, odx, ody, cross1, cross2, cross3, t;
        tdx = this.p2.x - this.p1.x;
        tdy = this.p2.y - this.p1.y;
        odx = other.p2.x - other.p1.x;
        ody = other.p2.y - other.p1.y;
        cross1 = tdx * ody - odx * tdy;
        if (cross1 == 0) return null;
        var overZero = cross1 > 0;
        otx = this.p1.x - other.p1.x;
        oty = this.p1.y - other.p1.y;
        cross2 = tdx * oty - tdy * otx;
        if (cross2 < 0 == overZero) return null;
        cross3 = odx * oty - ody * otx;
        if ((cross3 < 0) == overZero) return null;
        if ((cross2 > cross1 == overZero) || (cross3 > cross1 == overZero)) return null;
        t = cross3 / cross1;
        var r = { x:undefined, y:undefined };
        r.x = this.p1.x + (t * tdx);
        r.y = this.p1.y + (t * tdy);
        return r;
    }
};

function ellipse(x, y, width, height, angle, stroke, fill, precision)
{
    this.x = x;
    this.y = y;
    this.width = width;
    this.height = height;
    this.angle = angle;
    if (stroke) {
        var els = stroke.split(' ');
        this.stroke = els[0];
        if (els.length > 1) this.lineWidth = parseFloat(els[1]);
    }
    this.fill = fill;
    this.precision = precision || 5;
}

ellipse.prototype =
{
    get center()
    {
        return new vector(this.x, this.y);
    },
    setStroke: function(value)
    {
        var els = value.split(' ');
        this.stroke = els[0];
        if (els.length > 1) this.lineWidth = parseFloat(els[1]);
        return this;
    },
    setFill: function(value)
    {
        this.fill = value;
        return this;
    },
    clone: function()
    {
        return new ellipse(this.x, this.y, this.width, this.height, this.angle, this.stroke + (this.lineWidth !== undefined ? ' ' + this.lineWidth : ''), this.fill, this.precision)
    },
    angleAt: function(x, y)
    {
        if (arguments.length == 1) return new vector(x.x - this.x, x.y - this.y).angle;
        return new vector(x - this.x, y - this.y).angle;
    },
    pointAt: function(angle)
    {
        var cost = Math.cos(this.angle), sint = Math.sin(this.angle);
        var cosa = Math.cos(angle), sina = Math.sin(angle);
        var x = this.x + (this.width * cosa * cost - this.height * sina * sint);
        var y = this.y + (this.width * cosa * sint + this.height * sina * cost);
        return new vector(x, y);
    },
    inflate: function(x, y)
    {
        if (y === undefined) y = x;
        if (typeof x == 'string') {
            if (x.substr(-1) == '%') this.width *= 1 + parseFloat(x) / 100;
            else this.width += parseFloat(x);
        }
        else this.width += x;
        if (typeof y == 'string') {
            if (y.substr(-1) == '%') this.height *= 1 + parseFloat(y) / 100;
            else this.height += parseFloat(y);
        }
        else this.height += y;
        return this;
    },
    randomPoint: function()
    {
        return this.pointAt(Math.random() * Math.PI * 2);
    },
    intersect: function(other)
    {
        var r = [];
        var lt = new line(), ot = new line();
        var tcos = Math.cos(this.angle), tsin = Math.sin(this.angle);
        var ocos = Math.cos(other.angle), osin = Math.sin(other.angle);
        lt.p1 = { x:this.x + (this.width * tcos), y:this.y + (this.width * tsin) };
        var o0 = { x:other.x + (other.width * ocos), y:other.y + (other.width * osin) };
        for (var ta = 1; ta < 360; ta += this.precision) {
            var x, y, trads = ta * Math.PI / 180;
            x = this.x + (this.width * Math.cos(trads) * tcos - this.height * Math.sin(trads) * tsin);
            y = this.y + (this.width * Math.cos(trads) * tsin + this.height * Math.sin(trads) * tcos);
            lt.p2 = { x:x, y:y };
            ot.p1 = o0;
            for (var oa = 1; oa < 360; oa += other.precision) {
                var orads = oa * Math.PI / 180;
                x = other.x + (other.width * Math.cos(orads) * ocos - other.height * Math.sin(orads) * osin);
                y = other.y + (other.width * Math.cos(orads) * osin + other.height * Math.sin(orads) * ocos);
                ot.p2 = { x:x, y:y };
                var i = lt.intersect(ot);
                if (i) r.push(i);
                ot.p1 = ot.p2;
            }
            ot.p2 = { x:other.x + (other.width * ocos), y:other.y + (other.width * osin) };
            var i = lt.intersect(ot);
            if (i) r.push(i);
            lt.p1 = lt.p2;
        }
        lt.p2 = { x:this.x + (this.width * tcos), y:this.y + (this.width * tsin) };
        ot.p1 = o0;
        for (var oa = 1; oa < 360; oa += other.precision) {
            var orads = oa * Math.PI / 180;
            x = other.x + (other.width * Math.cos(orads) * ocos - other.height * Math.sin(orads) * osin);
            y = other.y + (other.width * Math.cos(orads) * osin + other.height * Math.sin(orads) * ocos);
            ot.p2 = { x:x, y:y };
            var i = lt.intersect(ot);
            if (i) r.push(i);
            ot.p1 = ot.p2;
        }
        ot.p2 = { x:other.x + (other.width * ocos), y:other.y + (other.width * osin) };
        var i = lt.intersect(ot);
        if (i) r.push(i);
        return r;
    },
    draw: function(ctx)
    {
        var cos = Math.cos(this.angle), sin = Math.sin(this.angle);
        var p0 = { x:this.x + (this.width * cos), y:this.y + (this.width * sin) };
        ctx.beginPath();
        ctx.moveTo(p0.x, p0.y);
        for (var a = 1; a < 360; a += this.precision) {
            var rads = a * Math.PI / 180;
            var x = this.x + (this.width * Math.cos(rads) * cos - this.height * Math.sin(rads) * sin);
            var y = this.y + (this.width * Math.cos(rads) * sin + this.height * Math.sin(rads) * cos);
            var p1 = { x:x, y:y };
            ctx.lineTo(p1.x, p1.y);
        }
        ctx.closePath();
        if (this.fill) {
            ctx.fillStyle = this.fill;
            ctx.fill();
        }
        if (this.stroke) {
            if (this.lineWidth) ctx.lineWidth = this.lineWidth;
            ctx.strokeStyle = this.stroke;
            ctx.stroke();
        }
    },
    drawIntersections:function(other, ctx, color, width)
    {
        var intersections = this.intersect(other);
        ctx.fillStyle = color || 'white';
        if (width === undefined) width = 5;
        for (var i = 0; i < intersections.length; ++i) {
            ctx.fillRect(intersections[i].x - width / 2, intersections[i].y - width / 2, width, width);
        }
    }
};

function cloud(x, y, width, height)
{
    this.x = x;
    this.y = y;
    this.width = width;
    this.height = height;

    var center = { x: x + width / 2, y: y + height / 2 };
    if (Math.random() >= .5) {
        var diagonal = new line(x, y, x + width, y + height);
        var disth = diagonal.distanceTo(new vector(this.x + width, this.y), true);
    }
    else {
        var diagonal = new line(x + width, y, x, y + height);
        var disth = diagonal.distanceTo(new vector(this.x, this.y), true);
    }
    var distw = diagonal.length / 2;
    var angle = diagonal.angle;
    this.cover = new ellipse(center.x, center.y, distw, disth, angle, 'white', 'white');
    this.body = this.cover.clone().inflate(5).setStroke('black 1px');
    this.puffs = [];
    var a = Math.random() * Math.PI / 12;
    while (a < Math.PI * 7) {
        var p = this.cover.pointAt(a);
        var w = (.1 + Math.random() * .2) * (distw + disth) / 2;
        this.puffs.push(new ellipse(p.x, p.y, w, w, 0, 'black 1px', 'white'));
        a += .75;
    }
}

cloud.prototype =
{
    draw:function(ctx)
    {
        this.body.draw(ctx);
        for (var i = 0; i < this.puffs.length; ++i) {
            this.puffs[i].draw(ctx);
        }
        this.cover.draw(ctx);
    }
};

var canvas = document.querySelector('canvas'), ctx = canvas.getContext('2d');
canvas.width = canvas.offsetWidth;
canvas.height = canvas.offsetHeight;
var cloud = new cloud((canvas.width - 300) / 2, (canvas.height - 100) / 2, 300, 100);
cloud.draw(ctx);

body {
  margin: 0;
  width: 100vw;
  height: 100vh;
  overflow: hidden;
  background-image: linear-gradient(to bottom, #2688FF, #94C4FF 75%, #B8D8FF);
}

canvas {
  width: 100vw;
  height: 100vh
}

<canvas></canvas>

注意事项:

1. 我选择了一个倾斜的椭圆，认为数学会很简单。男孩我错了!数学可能很简单，但我的数学技能很垃圾。我尝试了几次推导方程来找到两个可能旋转的椭圆之间的交点，但我总是得到一个我不知道如何简化的有理表达式:-(最后我放弃了并决定近似椭圆作为一系列线段，找到它们之间的交点。非常感谢任何推导正确方程式的帮助。

2. 同样，一旦我找到每个添加的“粉扑”和较大的“ body ”椭圆之间的交点，我就会尝试找到它们相对于椭圆中心的相应“角度”，以便我可以选择角度大一点的，一直顺时针方向乱喷，直到绕过整个 body 椭圆。但是，我不知道如何计算该角度，所以我以与 π 无关的固定间隔放置随机大小的泡芙并旋转几圈，因此泡芙在明显随机的地方重叠。

Answer 1

我喜欢你的方法。这是一个改进它的想法，因此结果将覆盖矩形并具有所需的凹口:

1. 创建一个有一些倾斜但覆盖整个矩形的椭圆。如果您不想为倾斜烦恼，可以使用答案 here得到一个覆盖矩形的椭圆。例如，使用 the insight基本椭圆方程实际上是单位圆的拉伸(stretch)方程，您可以根据矩形将其与参数一起使用:(x/a)^2+(y/b)^2=1 ，其中 a:=rectangle.width/sqrt(2) 和 b:=rectangle.height/sqrt(2)。

2. 复制椭圆并在两个轴上稍微放大(拉伸(stretch))。您可以使用百分比，例如在两个轴上拉伸(stretch) 5%。

3. 用你之前做的大椭圆做 - 从圆周上的随机点开始，放一个随机大小的圆，计算它与椭圆的交点，并放上新的随机大小在那里有一个中心的圆圈并继续，直到你覆盖了整个圆周。 这次 - 使用带有黑色描边的圆圈。

4. 将原始椭圆(小的)放在整个形状集合的前面。

所以最后你留下了原来的较小的椭圆覆盖了矩形并阻碍了圆圈的其余笔画，放大的椭圆和圆圈一起形成了所需的轮廓，形状内有凹口。