Circle - Line segment collision

Question 1

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

Question 2

Does it work as intended? Do you have any specific concerns about the code provided?

Question 3

@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.

Question 4

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>

Question 5

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?

Question 6

@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.

Question 7

OK, I understand now.

score 4 · Accepted Answer · 2018-04-19 20:53:03Z

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>

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?
@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.

Stack Exchange Network

Circle - Line segment collision

1 Answer 1

Memory costs CPU cycles.

Simpler line-seg circle intercept test

Rewrite

Your Answer

Sign up or log in

Post as a guest

Post as a guest

Linked

Hot Network Questions

Circle - Line segment collision

1 Answer 1

Memory costs CPU cycles.

Simpler line-seg circle intercept test

Rewrite

Your Answer

Sign up or log in

Post as a guest

Post as a guest

Linked

Related

Hot Network Questions