Optimizing arcs to draw sectors only visible on canvas

Question

I have an arc which is rather large in size with a stroke that uses rgba values. It has a 50% alpha value and because of that, it is causing a big hit on my cpu profile for my browser.

So i want to find a way to optimize this so that where ever the arc is drawn in a canvas, it will only draw from one angle to another of which is visible on screen.

What i am having difficulty with, is working out the correct angle range.

Here is a visual example:

The top image is what the canvas actually does even if you don't see it, and the bottom one is what I am trying to do to save processing time.

I created a JSFiddle where you can click and drag the circle, though, the two angles are currently fixed: https://jsfiddle.net/44tawd81/

Here is the draw code:

var canvas = document.getElementById('canvas');
var ctx    = canvas.getContext('2d');
    ctx.strokeStyle = 'red';

var radius = 50;
var pos    = {
              'x': canvas.width - 20,
              'y': canvas.height /2
             };


function draw(){
    ctx.clearRect(0,0,canvas.width,canvas.height);
    ctx.beginPath();

    ctx.arc(pos.x,pos.y,radius,0,2*Math.PI); //need to adjust angle range
    ctx.stroke();

    requestAnimationFrame(draw);
}

draw();

What is the simplest way to find the angle range to draw based on it's position and size in a canvas?

Answer 1

Clipping a Circle

This is how to clip a circle to a rectangular region aligned to the x and y axis.

To clip the circle I search for the list of points where the circle intersects the clipping region. Starting from one side I go in a clockwise direction adding clip points as they are found. When all 4 sides are tested I then draw the arc segments that join the points found.

To find if a point has intercepted a clipping edge you find the distance the circle center is from that edge. Knowing the radius and the distance you can complete the right triangle to find the coordinates of the intercept.

For the left edge

// define the clip edge and circle
var clipLeftX = 100;
var radius = 200;
var centerX = 200;
var centerY = 200; 

var dist = centerX - clipLeftX;
if(dist > radius) { // circle inside }
if(dist < -radius) {// circle completely outside}
// we now know the circle is clipped 

Now calculate the distance from the circle y that the two clip points will be

// the right triangle with hypotenuse and one side know can be solved with
var clipDist = Math.sqrt(radius * radius - dist * dist);

So the points where the circle intercept the clipping line

var clipPointY1 = centerY - clipDist;
var clipPointY2 = centerY + clipDist;

With that you can work out if the two points are inside or outside the left side top or bottom by testing the two points against the top and bottom of the left line.

You will end up with either 0,1 or 2 clipping points.

Because arc requires angles to draw you need to calculate the angle from the circle center to the found points. You already have all the info needed

// dist is the x distance from the clip
var angle = Math.acos(radius/dist); // for left and right side

The hard part is making sure all the angles to the clipping point are in the correct order. The is a little fiddling about with flags to ensure that the arcs are in the correct order.

After checking all four sides you will end up with 0,2,4,6, or 8 clipping points representing the start and ends of the various clipped arcs. It is then simply iterating the arc segments and rendering them.

// Helper functions are not part of the answer
var canvas;
var ctx;
var mouse;
var resize = function(){
    /** fullScreenCanvas.js begin **/
    canvas = (function(){
        var canvas = document.getElementById("canv");
        if(canvas !== null){
            document.body.removeChild(canvas);
        }
        // creates a blank image with 2d context
        canvas = document.createElement("canvas"); 
        canvas.id = "canv";    
        canvas.width = window.innerWidth;
        canvas.height = window.innerHeight; 
        canvas.style.position = "absolute";
        canvas.style.top = "0px";
        canvas.style.left = "0px";
        canvas.style.zIndex = 1000;
        canvas.ctx = canvas.getContext("2d"); 
        document.body.appendChild(canvas);
        return canvas;
    })();
    ctx = canvas.ctx;
    /** fullScreenCanvas.js end **/
    /** MouseFull.js begin **/
    var canvasMouseCallBack = undefined;  // if needed
    mouse = (function(){
        var mouse = {
            x : 0, y : 0, w : 0, alt : false, shift : false, ctrl : false,
            interfaceId : 0, buttonLastRaw : 0,  buttonRaw : 0,
            over : false,  // mouse is over the element
            bm : [1, 2, 4, 6, 5, 3], // masks for setting and clearing button raw bits;
            getInterfaceId : function () { return this.interfaceId++; }, // For UI functions
            startMouse:undefined,
        };
        function mouseMove(e) {
            var t = e.type, m = mouse;
            m.x = e.offsetX; m.y = e.offsetY;
            if (m.x === undefined) { m.x = e.clientX; m.y = e.clientY; }
            m.alt = e.altKey;m.shift = e.shiftKey;m.ctrl = e.ctrlKey;
            if (t === "mousedown") { m.buttonRaw |= m.bm[e.which-1];
            } else if (t === "mouseup") { m.buttonRaw &= m.bm[e.which + 2];
            } else if (t === "mouseout") { m.buttonRaw = 0; m.over = false;
            } else if (t === "mouseover") { m.over = true;
            } else if (t === "mousewheel") { m.w = e.wheelDelta;
            } else if (t === "DOMMouseScroll") { m.w = -e.detail;}
            if (canvasMouseCallBack) { canvasMouseCallBack(m.x, m.y); }
            e.preventDefault();
        }
        function startMouse(element){
            if(element === undefined){
                element = document;
            }
            "mousemove,mousedown,mouseup,mouseout,mouseover,mousewheel,DOMMouseScroll".split(",").forEach(
            function(n){element.addEventListener(n, mouseMove);});
            element.addEventListener("contextmenu", function (e) {e.preventDefault();}, false);
        }
        mouse.mouseStart = startMouse;
        return mouse;
    })();
    if(typeof canvas === "undefined"){
        mouse.mouseStart(canvas);
    }else{
        mouse.mouseStart();
    }
}
/** MouseFull.js end **/
resize();
// Answer starts here
var w = canvas.width;
var h = canvas.height;
var d = Math.sqrt(w * w + h * h); // diagnal size
var cirLWidth = d * (1 / 100);
var rectCol = "black";
var rectLWidth = d * (1 / 100);
const PI2 = Math.PI * 2;
const D45_LEN = 0.70710678;
var angles = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]; // declared outside to stop GC


// create a clipArea
function rectArea(x, y, x1, y1) {
    return {
        left : x,
        top : y,
        width : x1 - x,
        height : y1 - y
    };
}
// create a arc
function arc(x, y, radius, start, end, col) {
    return {
        x : x,
        y : y,
        r : radius,
        s : start,
        e : end,
        c : col
    };
}

// draws an arc
function drawArc(arc, dir) {
    ctx.strokeStyle = arc.c;
    ctx.lineWidth = cirLWidth;
    ctx.beginPath();
    ctx.arc(arc.x, arc.y, arc.r, arc.s, arc.e, dir);
    ctx.stroke();
}

// draws a clip area
function drawRect(r) {
    ctx.strokeStyle = rectCol;
    ctx.lineWidth = rectLWidth;
    ctx.strokeRect(r.left, r.top, r.width, r.height);

}



// clip and draw an arc
// arc is the arc to clip
// clip is the clip area
function clipArc(arc, clip){
    var count, distTop, distLeft, distBot, distRight, dist, swap, radSq, bot,right;

   // cir1 is used to draw the clipped circle
   cir1.x = arc.x;
   cir1.y = arc.y;   

   count = 0;  // number of clip points found;

   bot = clip.top + clip.height;  // no point adding these two over and over
   right = clip.left + clip.width;

   // get distance from all edges
   distTop = arc.y - clip.top;
   distBot = bot - arc.y;
   distLeft = arc.x - clip.left;
   distRight = right - arc.x;
   
   radSq = arc.r * arc.r; // get the radius squared
   
   // check if outside
   if(Math.min(distTop, distBot, distRight, distLeft) < -arc.r){
       return; // nothing to see so go home
   }
   // check inside
   if(Math.min(distTop, distBot, distRight, distLeft) > arc.r){
       drawArc(cir1);  
       return;
   }
   swap = true;
   if(distLeft < arc.r){
       // get the distance up and down to clip
       dist = Math.sqrt(radSq - distLeft * distLeft);
       // check the point is in the clip area
       if(dist + arc.y < bot && arc.y + dist > clip.top){
           // get the angel
           angles[count] = Math.acos(distLeft / -arc.r);
           count += 1;
       }
       if(arc.y - dist < bot && arc.y - dist > clip.top){
           angles[count] = PI2 - Math.acos(distLeft / -arc.r); // get the angle
           if(count === 0){  // if first point then set direction swap
               swap = false;
           }
           count += 1;
       }
   }
   if(distTop < arc.r){
       dist = Math.sqrt(radSq - distTop * distTop);
       if(arc.x - dist < right && arc.x - dist > clip.left){
           angles[count] = Math.PI + Math.asin(distTop / arc.r);
           count += 1;
       }
       if(arc.x+dist < right && arc.x+dist > clip.left){
           angles[count] = PI2-Math.asin(distTop/arc.r);
           if(count === 0){
               swap = false;
           }
           count += 1;
       }
   }
   if(distRight < arc.r){
       dist = Math.sqrt(radSq - distRight * distRight);
       if(arc.y - dist < bot && arc.y - dist > clip.top){
           angles[count] = PI2 - Math.acos(distRight / arc.r);
           count += 1;
       }
       if(dist + arc.y < bot && arc.y + dist > clip.top){
           angles[count] = Math.acos(distRight / arc.r);
           if(count === 0){
               swap = false;
           }
           count += 1;
       }
   }
   if(distBot < arc.r){
       dist = Math.sqrt(radSq - distBot * distBot);
       if(arc.x + dist < right && arc.x + dist > clip.left){
           angles[count] = Math.asin(distBot / arc.r);
           count += 1;
       }
       if(arc.x - dist < right && arc.x - dist > clip.left){
           angles[count] =  Math.PI + Math.asin(distBot / -arc.r);
           if(count === 0){
               swap = false;
           }
           count += 1;
       }
   }
   //  now draw all the arc segments
   if(count === 0){
       return;
   }
   if(count === 2){
        cir1.s = angles[0];
        cir1.e = angles[1];
        drawArc(cir1,swap);
   }else
   if(count === 4){
        if(swap){
            cir1.s = angles[1];
            cir1.e = angles[2];
            drawArc(cir1);
            cir1.s = angles[3];
            cir1.e = angles[0];
            drawArc(cir1);
        }else{
            cir1.s = angles[2];
            cir1.e = angles[3];
            drawArc(cir1);
            cir1.s = angles[0];
            cir1.e = angles[1];
            drawArc(cir1);
        }
   }else
   if(count === 6){
        cir1.s = angles[1];
        cir1.e = angles[2];
        drawArc(cir1);
        cir1.s = angles[3];
        cir1.e = angles[4];
        drawArc(cir1);
        cir1.s = angles[5];
        cir1.e = angles[0];
        drawArc(cir1);
        
   }else
   if(count === 8){
        cir1.s = angles[1];
        cir1.e = angles[2];
        drawArc(cir1);
        cir1.s = angles[3];
        cir1.e = angles[4];
        drawArc(cir1);
        cir1.s = angles[5];
        cir1.e = angles[6];
        drawArc(cir1);
        cir1.s = angles[7];
        cir1.e = angles[0];
        drawArc(cir1);
        
   }
   return;
}


var rect = rectArea(50, 50, w - 50, h - 50);
var circle = arc(w * (1 / 2), h * (1 / 2), w * (1 / 5), 0, Math.PI * 2, "#AAA");
var cir1 = arc(w * (1 / 2), h * (1 / 2), w * (1 / 5), 0, Math.PI * 2, "red");
var counter = 0;
var countStep = 0.03;
function update() {
    var x, y;
    ctx.clearRect(0, 0, w, h);
    circle.x = mouse.x;
    circle.y = mouse.y;
    drawArc(circle, "#888"); // draw unclipped arc
    x = Math.cos(counter * 0.1);
    y = Math.sin(counter * 0.3);
    rect.top = h / 2 - Math.abs(y * (h * 0.4)) - 5;
    rect.left = w / 2 - Math.abs(x * (w * 0.4)) - 5;
    rect.width = Math.abs(x * w * 0.8) + 10;
    rect.height = Math.abs(y * h * 0.8) + 10;
    cir1.col = "RED";  
    clipArc(circle, rect); // draw the clipped arc
    
    drawRect(rect); // draw the clip area. To find out why this method
                    // sucks move this to before drawing the clipped arc.
    requestAnimationFrame(update);
    if(mouse.buttonRaw !== 1){
        counter += countStep;
    }
    ctx.font = Math.floor(w * (1 / 50)) + "px verdana";
    ctx.fillStyle = "white";
    ctx.strokeStyle = "black";
    ctx.lineWidth = Math.ceil(w * (1 / 300));
    ctx.textAlign = "center";
    ctx.lineJoin = "round";
    ctx.strokeText("Left click and hold to pause", w/ 2, w * (1 / 40));
    ctx.fillText("Left click and hold to pause", w/ 2, w * (1 / 40));
}

update();
window.addEventListener("resize",function(){
   resize();
   w = canvas.width;
   h = canvas.height;
   rect = rectArea(50, 50, w - 50, h - 50);
   circle = arc(w * (1 / 2), h * (1 / 2), w * (1 / 5), 0, Math.PI * 2, "#AAA");
   cir1 = arc(w * (1 / 2), h * (1 / 2), w * (1 / 5), 0, Math.PI * 2, "red");
});

The quickest way to clip a circle.

That is the quickest I could manage to do it in code. There is some room for optimization but not that much in the agorithum.

The best solution is of course to use the canvas 2D context API clip() method.

ctx.save();
ctx.rect(10,10,200,200); // define the clip region
ctx.clip();  // activate the clip.

//draw your circles

ctx.restore(); // remove the clip.

This is much quicker than the method I showed above and should be used unless you have a real need to know the clip points and arcs segments that are inside or outside the clip region.

Answer 2

To find the angle to draw based on circle position, canvas position, circle size, and canvas size:

1. Determine intersection of circle and canvas
2. Calculate points on the circle at which intersection occurs

You then have an isosceles triangle.

You can use cosine formula for calculation of the angle.

c^2=a^2+b^2−2abcos(α) a and b are sides adjacent to the angle α, which are the radius of the center r. c is the distance between the two points P1 and P2. So we get:

|P1−P2|^2=2r^2−2r^2cos(α)

2r^2−|P1−P2|^2/2r2=cos(α)

α=cos−1(2r^2−|P1−P2|^2/2r^2)