Laith Laith - 26 days ago 6
C# Question

What is the algorithm behind the PDF cloud annotation?

I've noticed that several PDF Annotation applications (Adobe Acrobat, Bluebeam, etc) have an algorithm for creating a cloud pattern around a polygon:

Cloud Annotation in PDF

When you drag the vertices of this polygon, the cloud pattern is recalculated:

Modified Cloud Annotation in PDF

Notice how the arcs are recalculated to wrap around the polygon. They are not being stretched or warped. Whatever algorithm used to define this seems to be an industry standard. Several PDF editors allow you to create this, and in each one the cloud arcs look the same when dragging the vertices.

I am trying to create a WPF sample application that replicates this, but I can't seem to find the documentation anywhere for generating the cloud pattern.

I'm quite fluent with graphic design and 2D programming, and I'm capable of creating the tool to drag the vertices around, but I need help with figuring out how to draw these arcs. It looks like a series of

ArcSegments
in a
PathGeometry
.

So my question would be, what's the algorithm to create these arcs around a polygon?

or

Where can I find the documentation for these industry-standard PDF patterns, drawings, and/or annotations? (Cloud, arrows, borders, etc)

Answer

The clouds in your sketches are just a series of circles drawn along each polygon edge with a certain overlap.

An easy way to draw the filled basic cloud shape would be to first fill the polygon and then draw the circles on top of the filled polygon.

That approach falls flat when you want to fill the cloud with a partially transparent colour, because the overlap of the circles with each other and with the base polygon will be painted twice. It will also miss the small cartoon-style overshoots on the cloud curves.

A better way to draw the cloud is to create all circles first and then determine the intersecting angles of each circle with its next neighbour. You can then create a path with circle segments, which you can fill. The outline consists of independent arcs with a small offset for the end angle.

In your example, the distance between the cloud arcs is static. It is easy to make the arcs at polygon vertices coincide with by making that distance variable and by enforcing that the polygon edge is evenly divisible by that distance.

An example implementation in JavaScript (without the polygon dragging) is below. I'm not familiar with C#, but I think the basic algorithm is clear. The code is a complete web page, that you can save and display in browser that supports the canvas; I've tested it in Firefox.

The function to draw the cloud takes an object of options such as the radius, the arc distance and the overshoot in degrees. I haven't tested degenerate cases like small polygons, but in the extreme case the algorithm should just draw a single arc for each polygon vertex.

The polygon must be defined clockwise. Otherwise, the cloud will be more like a hole in cloud cover. That would be a nice feature, if there weren't any artefacts around the corner arcs.

Edit: I've provided a simple online test page for the cloud algorithm below. The page allows you to play with the various parameters. It also shows the shortcomings of the algorithm nicely. (Tested in FF and Chrome.)

The artefacts occur when the start and end angles are not determined properly. With very obtuse angles, there may also be intersections between the arcs next to the corner. I haven't fixed that, but I also haven't given that too muczh thought.)

<!DOCTYPE html>

<html>
<head>
<meta charset="utf-8" />
<title>Cumulunimbus</title>
<script type="text/javascript">

    function Point(x, y) {
        this.x = x;
        this.y = y;
    }

    function get(obj, prop, fallback) {
        if (obj.hasOwnProperty(prop)) return obj[prop];
        return fallback;
    }

    /*
     *      Global intersection angles of two circles of the same radius
     */
    function intersect(p, q, r) {
        var dx = q.x - p.x;
        var dy = q.y - p.y;

        var len = Math.sqrt(dx*dx + dy*dy);
        var a = 0.5 * len / r;

        if (a < -1) a = -1;
        if (a > 1) a = 1;

        var phi = Math.atan2(dy, dx);
        var gamma = Math.acos(a);

        return [phi - gamma, Math.PI + phi + gamma];
    }

    /*
     *      Draw a cloud with the given options to the given context
     */
    function cloud(cx, poly, opt) {        
        var radius = get(opt, "radius", 20);
        var overlap = get(opt, "overlap", 5/6);
        var stretch = get(opt, "stretch", true);



        // Create a list of circles

        var circle = [];        
        var delta = 2 * radius * overlap;

        var prev = poly[poly.length - 1];
        for (var i = 0; i < poly.length; i++) {
            var curr = poly[i];

            var dx = curr.x - prev.x;
            var dy = curr.y - prev.y;

            var len = Math.sqrt(dx*dx + dy*dy);

            dx = dx / len;
            dy = dy / len;

            var d = delta;

            if (stretch) {
                var n = (len / delta + 0.5) | 0;

                if (n < 1) n = 1;
                d = len / n;
            }

            for (var a = 0; a + 0.1 * d < len; a += d) {
                circle.push({
                    x: prev.x + a * dx,
                    y: prev.y + a * dy,
                });
            }

            prev = curr;
        }



        // Determine intersection angles of circles

        var prev = circle[circle.length - 1];
        for (var i = 0; i < circle.length; i++) {
            var curr = circle[i];
            var angle = intersect(prev, curr, radius);

            prev.end = angle[0];
            curr.begin = angle[1];

            prev = curr;
        }



        // Draw the cloud

        cx.save();

        if (get(opt, "fill", false)) {
            cx.fillStyle = opt.fill;

            cx.beginPath();
            for (var i = 0; i < circle.length; i++) {
                var curr = circle[i];

                cx.arc(curr.x, curr.y, radius, curr.begin, curr.end);
            }
            cx.fill();
        }

        if (get(opt, "outline", false)) {
            cx.strokeStyle = opt.outline;
            cx.lineWidth = get(opt, "width", 1.0);

            var incise = Math.PI * get(opt, "incise", 15) / 180;

            for (var i = 0; i < circle.length; i++) {
                var curr = circle[i];

                cx.beginPath();
                cx.arc(curr.x, curr.y, radius,
                    curr.begin, curr.end + incise);
                cx.stroke();
            }
        }

        cx.restore();
    }

    var poly = [
        new Point(250, 50),
        new Point(450, 150),
        new Point(350, 450),
        new Point(50, 300),
    ];

    window.onload = function() {
        cv = document.getElementById("cv");
        cx = cv.getContext("2d");

        cloud(cx, poly, {
            fill: "lightblue",        // fill colour
            outline: "black",         // outline colour
            incise: 15,               // overshoot in degrees
            radius: 20,               // arc radius
            overlap: 0.8333,          // arc distance relative to radius
            stretch: false,           // should corner arcs coincide?
        });
    }

</script>
</head>

<body>
<canvas width="500" height="500" id="cv"></canvas>
</body>

</html>