Points on Circumference

Fri May 02 2025 15:06:07 GMT+0100 (British Summer Time) geometry function javascript archived

Circle boundary points

Given a circle with a centre point at cx, cy, with a radius cr, this function returns a list of coordinates that make the pixel positions, or integer positions, of the edge of the circle (the circles circumference).

View example

This is known as Bresenhams Circle Algorithm, and is a form of midpoint-circle algorithm that is particularly efficient as it only calculates an 8^th of the circles circumference and simply mirrors and flips the generated coordinates 8 times, massively reducing computational costs.


function pointsOnCircumference(cx, cy, cr)
{
    var list = new Array();
    
    var x = cr;
    var y = 0;
    var o2 = Math.floor(1 - x);

    while(y <= x)
    {
        list.push([ x + cx,  y + cy]);
        list.push([ y + cx,  x + cy]);
        list.push([-x + cx,  y + cy]);
        list.push([-y + cx,  x + cy]);
        list.push([-x + cx, -y + cy]);
        list.push([-y + cx, -x + cy]);
        list.push([ x + cx, -y + cy]);
        list.push([ y + cx, -x + cy]);

        y+= 1;

        if(o2 <= 0) { o2+= (2 * y) + 1; }
        else
        {
            x-= 1;
            o2+= (2 * (y - x)) + 1;
        }
    }

    return list;
}

Example source code


<!DOCTYPE html>
<html>
<head>

<script type="text/javascript">
var ctx = null, game = null;
var mouseX = 30, mouseY = 20, radius = 5;
var pointList = null;

window.onload = function() {
    game = document.getElementById('game');
    ctx = game.getContext('2d');
    ctx.font = "bold 10pt sans-serif";

    pointList = pointsOnCircumference(mouseX, mouseY, radius);

    game.addEventListener('mouseup', function(e) {
        // Store the position of the last mouse click for reference
        var prevX = mouseX;
        var prevY = mouseY;

        // Get the position of the mouse click on the page
        mouseX = e.pageX;
        mouseY = e.pageY;

        // Find the offset of the Canvas relative to the document top, left,
        // and modify the mouse position to account for this
        var p = game;
        do
        {
            mouseX-= p.offsetLeft;
            mouseY-= p.offsetTop;

            p = p.offsetParent;
        } while(p!=null);

        // fit the real mouse position to our 10x10 grid
        mouseX = Math.floor(mouseX / 10);
        mouseY = Math.floor(mouseY / 10);

        // If the previous grid click was the same tile as this one, change the radius
        if(prevX == mouseX && prevY == mouseY) { radius = (radius < 12 ? radius+1 : 3); }

        // Update the list of points on the circles circumference
        pointList = pointsOnCircumference(mouseX, mouseY, radius);

        // Show a list of points for information
        var htm = '';
        for(p in pointList)
        {
            htm+= '<li>' + pointList[p][0] + ', ' + pointList[p][1] + '</li>';
        }
        document.getElementById('pointList').innerHTML = htm;
    });

    requestAnimationFrame(drawGame);
};

function pointsOnCircumference(cx, cy, cr)
{
    var list = new Array();
    
    var x = cr;
    var y = 0;
    var o2 = Math.floor(1 - x);

    while(y <= x)
    {
        list.push([ x + cx,  y + cy]);
        list.push([ y + cx,  x + cy]);
        list.push([-x + cx,  y + cy]);
        list.push([-y + cx,  x + cy]);
        list.push([-x + cx, -y + cy]);
        list.push([-y + cx, -x + cy]);
        list.push([ x + cx, -y + cy]);
        list.push([ y + cx, -x + cy]);

        y+= 1;

        if(o2 <= 0) { o2+= (2 * y) + 1; }
        else
        {
            x-= 1;
            o2+= (2 * (y - x)) + 1;
        }
    }

    return list;
}

function drawGame()
{
    if(ctx==null) { return; }

    // Clear the Canvas
    ctx.fillStyle = "#ffffff";
    ctx.fillRect(0, 0, 600, 400);

    // Draw the grid
    ctx.strokeStyle = "#999999";
    ctx.beginPath();
    for(y = 0; y < (400/10); ++y)
    {
        for(x = 0; x < (600/10); ++x)
        {
            ctx.rect((x*10), (y*10), 10, 10);
        }
    }
    ctx.closePath();
    ctx.stroke();
    
    // Draw the points on the circles edge
    ctx.fillStyle = "#ff9999";
    ctx.strokeStyle = "#ff3333";
    ctx.beginPath();
    for(p in pointList)
    {
        ctx.rect(pointList[p][0] * 10, pointList[p][1] * 10, 10, 10);
    }
    ctx.closePath();
    ctx.fill();
    ctx.stroke();

    // Show some information...
    ctx.fillStyle = "#ff0000";
    ctx.fillText("Circle at " + mouseX + "," + mouseY + " radius " + radius, 10, 20);

    // Ask for the next animation frame
    requestAnimationFrame(drawGame);
}
</script>
</head>
<body>

<p>Click on the grid to draw a circle there.  Click repeatedly on the same point to resize the circle.</p>

<canvas id="game" width="600" height="400"></canvas>
<ul id="pointList" style="font-family:monospace;"></ul>

</body>
</html>