How to calculate bezier curve control points that avoid objects?

Question

Specifically, I'm working in canvas with javascript.

Basically, I have objects which have boundaries that I want to avoid, but still surround with a bezier curve. However, I'm not even sure where to begin to write an algorithm that would move control points to avoid colliding.

The problem is in the image below, even if you're not familiar with music notation, the problem should still be fairly clear. The points of the curve are the red dots

Also, I have access to the bounding boxes of each note, which includes the stem.

So naturally, collisions must be detected between the bounding boxes and the curves (some direction here would be good, but I've been browsing and see that there's a decent amount of info on this). But what happens after collisions have been detected? What would have to happen to calculate control points locations to make something that looked more like:

Answer 1

Bezier approach

Initially the question is a broad one - perhaps even to broad for SO as there are many different scenarios that needs to be taken into consideration to make a "one solution that fits them all". It's a whole project in its self. Therefor I will present a basis for a solution which you can build upon - it's not a complete solution (but close to one..). I added some suggestions for additions at the end.

The basic steps for this solutions are:

Group the notes into two groups, a left and a right part.

The control points are then based on the largest angle from the first (end) point and distance to any of the other notes in that group, and the last end point to any point in the second group.

The resulting angles from the two groups are then doubled (max 90°) and used as basis to calculate the control points (basically a point rotation). The distance can be further trimmed using a tension value.

The angle, doubling, distance, tension and padding offset will allow for fine-tuning to get the best over-all result. There might be special cases which need additional conditional checks but that is out of scope here to cover (it won't be a full key-ready solution but provide a good basis to work further upon).

A couple of snapshots from the process:

The main code in the example is split into two section, two loops that parses each half to find the maximum angle as well as the distance. This could be combined into a single loop and have a second iterator to go from right to middle in addition to the one going from left to middle, but for simplicity and better understand what goes on I split them into two loops (and introduced a bug in the second half - just be aware. I'll leave it as an exercise):

var dist1 = 0,  // final distance and angles for the control points
    dist2 = 0,
    a1 = 0,
    a2 = 0;

// get min angle from the half first points
for(i = 2; i < len * 0.5 - 2; i += 2) {

    var dx = notes[i  ] - notes[0],      // diff between end point and
        dy = notes[i+1] - notes[1],      // current point.
        dist = Math.sqrt(dx*dx + dy*dy), // get distance
        a = Math.atan2(dy, dx);          // get angle

    if (a < a1) {                        // if less (neg) then update finals
        a1 = a;
        dist1 = dist;
    }
}

if (a1 < -0.5 * Math.PI) a1 = -0.5 * Math.PI;      // limit to 90 deg.

And the same with the second half but here we flip around the angles so they are easier to handle by comparing current point with end point instead of end point compared with current point. After the loop is done we flip it 180°:

// get min angle from the half last points
for(i = len * 0.5; i < len - 2; i += 2) {

    var dx = notes[len-2] - notes[i],
        dy = notes[len-1] - notes[i+1],
        dist = Math.sqrt(dx*dx + dy*dy),
        a = Math.atan2(dy, dx);

    if (a > a2) {
        a2 = a;
        if (dist2 < dist) dist2 = dist;            //bug here*
    }
}

a2 -= Math.PI;                                     // flip 180 deg.
if (a2 > -0.5 * Math.PI) a2 = -0.5 * Math.PI;      // limit to 90 deg.

(the bug is that longest distance is used even if a shorter distance point has greater angle - I'll let it be for now as this is meant as an example. It can be fixed by reversing the iteration.).

The relationship I found works good is the angle difference between the floor and the point times two:

var da1 = Math.abs(a1);                            // get angle diff
var da2 = a2 < 0 ? Math.PI + a2 : Math.abs(a2);

a1 -= da1*2;                                       // double the diff
a2 += da2*2;

Now we can simply calculate the control points and use a tension value to fine tune the result:

var t = 0.8,                                       // tension
    cp1x = notes[0]     + dist1 * t * Math.cos(a1),
    cp1y = notes[1]     + dist1 * t * Math.sin(a1),
    cp2x = notes[len-2] + dist2 * t * Math.cos(a2),
    cp2y = notes[len-1] + dist2 * t * Math.sin(a2);

And voila:

ctx.moveTo(notes[0], notes[1]);
ctx.bezierCurveTo(cp1x, cp1y, cp2x, cp2y, notes[len-2], notes[len-1]);
ctx.stroke();

Adding tapering effect

To create the curve more visually pleasing a tapering can be added simply by doing the following instead:

Instead of stroking the path after the first Bezier curve has been added adjust the control points with a slight angle offset. Then continue the path by adding another Bezier curve going from right to left, and finally fill it (fill() will close the path implicit):

// first path from left to right
ctx.beginPath();
ctx.moveTo(notes[0], notes[1]);                    // start point
ctx.bezierCurveTo(cp1x, cp1y, cp2x, cp2y, notes[len-2], notes[len-1]);

// taper going from right to left
var taper = 0.15;                                  // angle offset
cp1x = notes[0] + dist1*t*Math.cos(a1-taper);
cp1y = notes[1] + dist1*t*Math.sin(a1-taper);
cp2x = notes[len-2] + dist2*t*Math.cos(a2+taper);
cp2y = notes[len-1] + dist2*t*Math.sin(a2+taper);

// note the order of the control points
ctx.bezierCurveTo(cp2x, cp2y, cp1x, cp1y, notes[0], notes[1]);
ctx.fill();                                        // close and fill

Final result (with pseudo notes - tension = 0.7, padding = 10)

FIDDLE

Suggested improvements:

• If both groups' distances are large, or angles are steep, they could probably be used as a sum to reduce tension (distance) or increase it (angle).
• A dominance/area factor could affect the distances. Dominance indicating where the most tallest parts are shifted at (does it lay more in the left or right side, and affects tension for each side accordingly). This could possibly/potentially be enough on its own but needs to be tested.
• Taper angle offset should also have a relationship with the sum of distance. In some cases the lines crosses and does not look so good. Tapering could be replaced with a manual approach parsing Bezier points (manual implementation) and add a distance between the original points and the points for the returning path depending on array position.

Hope this helps!