3
\$\begingroup\$

I wrote an implementation of circle - line segment collision detection algorithm. Here is quick demonstration how it works: enter image description here

And here is my implementation in Javascript using HTML canvas:

index.html

<html>
    <head>
        <meta charset="utf-8">
    </head>
    <body>
        <canvas id="canvas" width="600" height="400" style="background-color: #EEE"></canvas>
        <script src="vec2.js"></script>
        <script src="script.js"></script>
    </body>
</html>

vec2.js - contains simple 2D vector implementation

let Vec2 = {
    x: 0,
    y: 0,

    project(normal)
    {
        let projected = Vec2.create();
        let dotProd = this.dot(normal);

        projected.x = dotProd * normal.x;
        projected.y = dotProd * normal.y;

        return projected;
    },

    //return normalized version of vector
    normalize()
    {
        let len = this.getLen();
        let tmp = Vec2.create(this.x / len, this.y / len);

        return tmp;
    },

    setAngle(rad)
    {
        let len = this.getLen();

        this.x = Math.cos(rad) * len;
        this.y = Math.sin(rad) * len;

        return this;
    },

    getAngle()
    {
        return Math.atan2(this.y, this.x);
    },

    //returns length/magnitude
    getLen()
    {
        return Math.sqrt(this.x * this.x + this.y * this.y);
    },

    //returns square length/magnitude
    getSqrLen()
    {
        return this.x * this.x + this.y * this.y;
    },

    setLen(len)
    {
        let normalized = this.normalize();

        normalized.x *= len;
        normalized.y *= len;

        this.x = normalized.x;
        this.y = normalized.y;
    },

    multiply(scalar)
    {
        this.x *= scalar;
        this.y *= scalar;

        return this;
    },

    dot(vec)
    {
        return this.x * vec.x + this.y * vec.y;
    },

    create(x = 0, y = 0, angle = null)
    {
        let obj = Object.create(Vec2);

        if(angle == null)
        {
            obj.x = x;
            obj.y = y;
        }
        else
        {
            obj.x = 1.0; //unit vector
            obj.setAngle(angle);
        }

        return obj;
    },
};

script.js

let canvas = document.getElementById("canvas");
let context = canvas.getContext('2d');

//mouse coords
let mx = 0;
let my = 0;

//circle radius
let r = 30;

//rotation 
let t = 0.0;
let speed = 0.01;

window.onload = function()
{
    update();
}

window.onmousemove = function(e)
{
    mx =  (e.clientX - canvas.width / 2.0) - 5.0;
    my = -(e.clientY - canvas.height / 2.0) + 5.0;
}

function clamp(min, max, val)
{
    return val < min ? min : val > max ? max : val;
}

function getClosestPointToLine(A, B, circleCenter)
{
    //vector from circle center to point B
    let d = Vec2.create(B.x - circleCenter.x, B.y - circleCenter.y);

    //normalized vector from A to B
    let ab = Vec2.create(B.x - A.x, B.y - A.y).normalize();

    //d projected to ab
    let proj = d.project(ab);

    //get closest point to circle
    let closest = Vec2.create(B.x - proj.x, B.y - proj.y);

    return closest;
}

function clampToLine(A, B, point)
{
    //define segment bounding box
    let minX = Math.min(A.x, B.x);
    let minY = Math.min(A.y, B.y);      
    let maxX = Math.max(A.x, B.x);
    let maxY = Math.max(A.y, B.y);

    let inBoundingBox = point.x > minX && point.x < maxX &&
                        point.y > minY && point.y < maxY;

    if(!inBoundingBox)
    {
        let distA = Vec2.create(point.x - A.x, point.y - A.y).getSqrLen();
        let distB = Vec2.create(point.x - B.x, point.y - B.y).getSqrLen();

        //if point is not in bounding box, set it as A or B depending on distances from both
        point = distA < distB ? A : B;
    }

    return point;
}

function pointInCircle(circleCenter, r, point)
{
    //create vector from circle center to closest point
    let sqrDist = Vec2.create(point.x - circleCenter.x, point.y - circleCenter.y).getSqrLen();

    //circle intersects when sqrDist is lower or equal to square radius
    let intersects = sqrDist <= r * r; 

    return intersects;
}

function update()
{
    t += speed; 
    let sr = 125; //line segment radius

    //get segment points from rotation around center
    let A = Vec2.create(Math.cos(t) * sr, Math.sin(t) * sr);
    let B = Vec2.create(Math.cos(t + Math.PI) * sr, Math.sin(t + Math.PI) * sr);

    //circle center position is mouse position
    let circleCenter = Vec2.create(mx, my);

    //get closest point to circle
    let closest = getClosestPointToLine(A, B, circleCenter);

    //clamp it to line segment
    closest = clampToLine(A, B, closest);

    //check that it's in the circle
    let intersects = pointInCircle(circleCenter, r, closest);

    //drawing
    context.clearRect(0, 0, canvas.width, canvas.height);

    context.save();
    //center canvas, and invert y axis
    context.translate(canvas.width / 2.0, canvas.height / 2.0);
    context.scale(1.0, -1.0);

    //circle
    context.beginPath();
    context.arc(mx, my, r, 0, Math.PI * 2);
    context.lineWidth = 2.0;
    if(intersects) context.fillStyle = "#900";
    context.fill();

    //segment
    context.beginPath();
    context.moveTo(A.x, A.y);
    context.lineTo(B.x, B.y);
    context.strokeStyle = "#000";
    context.lineWidth = 1.0;
    context.stroke();

    context.restore();
    requestAnimationFrame(update);
}

run on jsfiddle

\$\endgroup\$
  • \$\begingroup\$ Does it work as intended? Do you have any specific concerns about the code provided? \$\endgroup\$ – Mast Apr 19 '18 at 15:32
  • \$\begingroup\$ @Mast yes it work, you can check it on jsfiddle in the link I added on the end of post. I'm wondering what are you thinking about it's performance and optimalization. I'm not perfectly sure about my clamping to line part correctness. \$\endgroup\$ – Tomek Apr 19 '18 at 15:37
2
\$\begingroup\$

Memory costs CPU cycles.

That is a lot for code for a simple operation.

First some points about vectors, memory and performance.

Vectors are small, short lived, most called, basic building blocks of any graphics / geometry based application.

Vectors also encourage some of the worst JavaScript practices. They feel so much like javascript basic types Number, String, Boolean that you think nothing of creating them as needed. Yet they carry Javascript "Achilles heel", managed objects.

Your code is just pumping out a stream of derefernced objects every frame

  • Create the line end points and circle center once. Not each time you need them you are just creating work for memory management.

  • Use const for all objects that do and should not change

  • Be aware of memory overheads and don't use objects to hold intermediate results.

  • In JavaScript you do not need to explicitly define floats. scale(1.0, -1.0); is the same a scale(1, -1);

  • 2D context save and restore should be avoided if you can. Directly setting only the context state properties you need can save considerable time.

  • 2D context functions translate, scale, and rotate, work by creating a new matrix to represent the transforms which multiply the current transform. You can avoid the overhead by setting the current transform directly using ctx.setTransform

The vector lib has forced you into creating a new object for almost every operation. If you were animating 5 balls interacting with 10 lines you would be generating 3000 un referenced vector objects a second. And that is a very modest scene complexity.

Simpler line-seg circle intercept test

If you get the line as a vector ABand a vector from the line start A to the circle center C you can get the closest point on the line as a unit distance u along the line by dividing the dot product of (AC dot AB) by ) / (AB dot AB)(the unit being the length of the line).

When you have the unit dist you use it to work out what part of the line segment to measure the circle center distance from. if u < 0 then get the length of AC if u > 1 the get length BC else get the distance from (A + AB * u) to C.

If the calculated dist is less than the radius the circle is touching.

Rewrite

Almost zero CG overhead, and much smaller yet does the same thing.

    // request first frame
    requestAnimationFrame(update);
    const ctx = canvas.getContext('2d');
    // We dont need any vector functionality as the operations are so 
    // simple we can just use undefined object.
    const A = {x : 0, y : 0};
    const B = {x : 0, y : 0};    
    const circleCenter = {x : 0, y : 0};
    const halfLineLen = 125;
    var time = 0;
    const mouse = { x : 0, y : 0 }
    const r = 30;
    const speed = 0.01;
    
    addEventListener("mousemove",(e)=>{
        mouse.x =  (e.clientX - canvas.width / 2.0) - 5.0;
        mouse.y = -(e.clientY - canvas.height / 2.0) + 5.0;
    })
    

    // Function to check intercept of line seg and circle
    // A,B end points of line segment
    // C center of circle
    // radius of circle
    // returns true if touching or crossing else false   
    function doesLineInterceptCircle(A, B, C, radius) {
        var dist;
        const v1x = B.x - A.x;
        const v1y = B.y - A.y;
        const v2x = C.x - A.x;
        const v2y = C.y - A.y;
        // get the unit distance along the line of the closest point to
        // circle center
        const u = (v2x * v1x + v2y * v1y) / (v1y * v1y + v1x * v1x);
        
        
        // if the point is on the line segment get the distance squared
        // from that point to the circle center
        if(u >= 0 && u <= 1){
            dist  = (A.x + v1x * u - C.x) ** 2 + (A.y + v1y * u - C.y) ** 2;
        } else {
            // if closest point not on the line segment
            // use the unit distance to determine which end is closest
            // and get dist square to circle
            dist = u < 0 ?
                  (A.x - C.x) ** 2 + (A.y - C.y) ** 2 :
                  (B.x - C.x) ** 2 + (B.y - C.y) ** 2;
        }
        return dist < radius * radius;
     }
  
  
    function update() {     

         ctx.clearRect(0, 0, canvas.width, canvas.height);
         time += speed;
         A.x = - Math.cos(time) * halfLineLen;
         A.y = - Math.sin(time) * halfLineLen;
         B.x =  Math.cos(time) * halfLineLen;
         B.y =  Math.sin(time) * halfLineLen;


         circleCenter.x = mouse.x;
         circleCenter.y = mouse.y;
          
         
         const intersects = doesLineInterceptCircle(A, B, circleCenter, r);

        ctx.setTransform(1, 0, 0, -1, canvas.width / 2, canvas.height / 2);

        ctx.lineWidth = 2.0;
        ctx.fillStyle = intersects ? "#900" : "#000";
     
        ctx.beginPath();
        ctx.arc(circleCenter.x, circleCenter.y, r, 0, Math.PI * 2);
        ctx.fill();

        ctx.strokeStyle = "#000";
        ctx.lineWidth = 1;         

        ctx.beginPath();  // You dont need to use moveTo after beginPath
        ctx.lineTo(A.x, A.y);  
        ctx.lineTo(B.x, B.y);
        ctx.stroke();

        ctx.setTransform(1,0,0,1,0,0);
        requestAnimationFrame(update);
    }
<canvas id="canvas" width = "400" height= "400"></canvas>

\$\endgroup\$
  • \$\begingroup\$ Thanks, I see many things that I didn't know about canvas and JS to now. But I have one question: you wrote that I should use const on every object that does not change, but you declare A, and B and few other variables as const, and you are modyfing their members in every frame, is that tip referring only to directly assignment? \$\endgroup\$ – Tomek Apr 20 '18 at 14:48
  • \$\begingroup\$ @Tomek A, B hold references to the objects (where in memory the object is stored) not the object themselves. Changing the object's properties does not change the object's reference.. Making A and B constants ensures you do not overwrite the references to the object that the variables hold. \$\endgroup\$ – Blindman67 Apr 20 '18 at 15:06
  • \$\begingroup\$ OK, I understand now. \$\endgroup\$ – Tomek Apr 20 '18 at 15:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.