javascript - How to calculate intersection point of a line on a circle using p5.js - Stack Overflow

admin管理员组

文章数量:1277286

I have a line (se) that I know starts inside a circle, and I know ends outside of a circle. I'm trying to find a point l where the line crosses the circle.

I'm using the p5.js library and have access to all of its Vector functions.

My thoughts were, that if I can make a right angle on the line, to the radius, I can start solving some things.

// Get the vector between s and c
let scVector = p5.Vector.sub(start, circleCenter);
// Get the angle between se and sc
let escAngle = this.v.angleBetween(scVector);
// Get the distance between t (where the right angle hits the center of the circle) and c
let tcDistance = Math.sin(escAngle) * scVector.mag();
// Get the distance between t and where the line intersects the circle
let tlDistance = Math.sqrt(Math.pow(hole.r, 2) - Math.pow(tcDistance, 2));
// Get the distance between the start point and t
let stDistance = Math.sqrt(Math.pow(scVector.mag(), 2) - Math.pow(tcDistance, 2));
// Add the two distances together, giving me the distance between s and l
let totalDistance = tcDistance + stDistance;
// Create a new Vector at this angle, at the totalDistance Magnitude, then add it to the current position
let point = p5.Vector.fromAngle(this.v.heading(), totalDistance).add(start);
// Mark a point (hopefully l) on the edge of the circle.
points.push({
  x: point.x,
  y: point.y,
  fill: '#ffffff'
})

Unfortunately, as my objects pass through the circle, they aren't leaving dots on the edge, but further away from the circle's edge.

The tiny dots are the marked positions, the coloured dots are the objects (which have a start and end point)

I have a demo here, the questionable bit is line 42 onwards:

Any help would be much appreciated.

I have a line (se) that I know starts inside a circle, and I know ends outside of a circle. I'm trying to find a point l where the line crosses the circle.

I'm using the p5.js library and have access to all of its Vector functions.

My thoughts were, that if I can make a right angle on the line, to the radius, I can start solving some things.

// Get the vector between s and c
let scVector = p5.Vector.sub(start, circleCenter);
// Get the angle between se and sc
let escAngle = this.v.angleBetween(scVector);
// Get the distance between t (where the right angle hits the center of the circle) and c
let tcDistance = Math.sin(escAngle) * scVector.mag();
// Get the distance between t and where the line intersects the circle
let tlDistance = Math.sqrt(Math.pow(hole.r, 2) - Math.pow(tcDistance, 2));
// Get the distance between the start point and t
let stDistance = Math.sqrt(Math.pow(scVector.mag(), 2) - Math.pow(tcDistance, 2));
// Add the two distances together, giving me the distance between s and l
let totalDistance = tcDistance + stDistance;
// Create a new Vector at this angle, at the totalDistance Magnitude, then add it to the current position
let point = p5.Vector.fromAngle(this.v.heading(), totalDistance).add(start);
// Mark a point (hopefully l) on the edge of the circle.
points.push({
  x: point.x,
  y: point.y,
  fill: '#ffffff'
})

Unfortunately, as my objects pass through the circle, they aren't leaving dots on the edge, but further away from the circle's edge.

The tiny dots are the marked positions, the coloured dots are the objects (which have a start and end point)

I have a demo here, the questionable bit is line 42 onwards: https://codepen.io/EightArmsHQ/pen/be0461014f9868e3462868776d9c8f1a

Any help would be much appreciated.

• javascript
• math
• geometry
• processing
• p5.js

Share Improve this question Follow edited Sep 11, 2019 at 16:27 Rabbid76 211k3030 gold badges156156 silver badges199199 bronze badges asked Sep 11, 2019 at 14:34 DjaveDjave 9,34988 gold badges7979 silver badges136136 bronze badges 2

• If you increment the position of each ball at discrete time intervals, you cannot (depending on the timestep size, hole radius and velocity) always guarantee that a ball will be inside the hole during a certain timestep, even if it does cross the hole. – meowgoesthedog Commented Sep 11, 2019 at 15:15
• I already know if the ball is inside or outside the hole – Djave Commented Sep 11, 2019 at 15:36

Add a ment  | 

1 Answer 1

Sorted by: Reset to default 13

To find the intersection of a point and a line, I remend to use an existing algorithm, like that one of WolframMathWorld - Circle-Line Intersection.

The algorithm is short, well explained an can be expressed in an short function. The input parameters p1, p2, and cpt are of type p5.Vector, r is a scalar. This parameters define an endless line form p1 to p2 and a circle with the center point cpt and the radius r. The function returns a list of inter section points, with may be empty:

intersectLineCircle = function(p1, p2, cpt, r) {

    let sign = function(x) { return x < 0.0 ? -1 : 1; };

    let x1 = p1.copy().sub(cpt);
    let x2 = p2.copy().sub(cpt);

    let dv = x2.copy().sub(x1)
    let dr = dv.mag();
    let D = x1.x*x2.y - x2.x*x1.y;

    // evaluate if there is an intersection
    let di = r*r*dr*dr - D*D;
    if (di < 0.0)
        return [];
   
    let t = sqrt(di);

    ip = [];
    ip.push( new p5.Vector(D*dv.y + sign(dv.y)*dv.x * t, -D*dv.x + p.abs(dv.y) * t).div(dr*dr).add(cpt) );
    if (di > 0.0) {
        ip.push( new p5.Vector(D*dv.y - sign(dv.y)*dv.x * t, -D*dv.x - p.abs(dv.y) * t).div(dr*dr).add(cpt) ); 
    }
    return ip;
}

If you want to verify, if a point is "in between" to other points, you can use the Dot product. If you know that 3 points on a line, then it is sufficient to calculate the distances between the points, to determine, if 1 point is in between the 2 other points.
p1, p2, and px are of type p5.Vector. The points are on the same line. The function returns true, if px is between p1 and p2 and false else:

inBetween = function(p1, p2, px) {

    let v = p2.copy().sub(p1);
    let d = v.mag();
    v = v.normalize();

    let vx = px.copy().sub(p1);
    let dx = v.dot(vx);
    
    return dx >= 0 && dx <= d;
}

See the example, which I've implemented to test the function. The circle is tracked by the mouse and is intersected by an randomly moving line:

var sketch = function( p ) {

p.setup = function() {
    let sketchCanvas = p.createCanvas(p.windowWidth, p.windowHeight);
    sketchCanvas.parent('p5js_canvas')
}

let points = [];
let move = []

// Circle-Line Intersection
// http://mathworld.wolfram./Circle-LineIntersection.html
p.intersectLineCircle = function(p1, p2, cpt, r) {

    let sign = function(x) { return x < 0.0 ? -1 : 1; };

    let x1 = p1.copy().sub(cpt);
    let x2 = p2.copy().sub(cpt);

    let dv = x2.copy().sub(x1)
    let dr = dv.mag();
    let D = x1.x*x2.y - x2.x*x1.y;

    // evaluate if there is an intersection
    let di = r*r*dr*dr - D*D;
    if (di < 0.0)
        return [];
   
    let t = p.sqrt(di);

    ip = [];
    ip.push( new p5.Vector(D*dv.y + sign(dv.y)*dv.x * t, -D*dv.x + p.abs(dv.y) * t).div(dr*dr).add(cpt) );
    if (di > 0.0) {
        ip.push( new p5.Vector(D*dv.y - sign(dv.y)*dv.x * t, -D*dv.x - p.abs(dv.y) * t).div(dr*dr).add(cpt) ); 
    }
    return ip;
}

p.inBetween = function(p1, p2, px) {

    let v = p2.copy().sub(p1);
    let d = v.mag();
    v = v.normalize();

    let vx = px.copy().sub(p1);
    let dx = v.dot(vx);
    
    return dx >= 0 && dx <= d;
}

p.endlessLine = function(x1, y1, x2, y2) {

    p1 = new p5.Vector(x1, y1);
    p2 = new p5.Vector(x2, y2);

    let dia_len = new p5.Vector(p.windowWidth, p.windowHeight).mag();
    let dir_v = p5.Vector.sub(p2, p1).setMag(dia_len);
    let lp1 = p5.Vector.add(p1, dir_v);
    let lp2 = p5.Vector.sub(p1, dir_v);

    p.line(lp1.x, lp1.y, lp2.x, lp2.y);
}

p.draw = function() {
        
    if (points.length == 0) {

        points = [];
        move = [];
        for (let i=0; i < 2; ++i ) {
            points.push( new p5.Vector(p.random(p.windowWidth-20)+10, p.random(p.windowHeight-20)+10));
            move.push( new p5.Vector(p.random(2)-1, p.random(2)-1) );
        }
        points.push( new p5.Vector(p.mouseX, p.mouseY));
    }
    else
    {
        for (let i=0; i < 2; ++i ) {
            points[i] = points[i].add(move[i]);
            if (points[i].x < 10 || points[i].x > p.windowWidth-10)
                move[i].x *= -1; 
            if (points[i].y < 10 || points[i].y > p.windowHeight-10)
                move[i].y *= -1;    
            move[i].x = Math.max(-1, Math.min(1, move[i].x+p.random(0.2)-0.1))
            move[i].y = Math.max(-1, Math.min(1, move[i].y+p.random(0.2)-0.1))
        }
        points[2].x = p.mouseX;
        points[2].y = p.mouseY;
    }
    let circle_diameter = p.min(p.windowWidth, p.windowHeight) / 2.0;

    let isectP = p.intersectLineCircle(...points, circle_diameter/2.0);

    // draw the scene

    p.background(192);
    
    p.stroke(0, 0, 255);
    p.fill(128, 128, 255);
    for (let i=0; i < points.length; ++i ) {
        p.ellipse(points[i].x, points[i].y, 10, 10);
    }

    for (let i=0; i < isectP.length; ++i ) {
        if (p.inBetween(points[0], points[1], isectP[i])) {
            p.stroke(255, 0, 0);
            p.fill(255, 128, 0);
        } else {
            p.stroke(255, 128, 0);
            p.fill(255, 255, 0);
        }

        p.ellipse(isectP[i].x, isectP[i].y, 10, 10);
    }

    p.stroke(0, 255, 0);
    p.noFill();
    p.endlessLine(points[0].x, points[0].y, points[1].x, points[1].y)
    p.ellipse(points[2].x, points[2].y, circle_diameter, circle_diameter);
}

p.windowResized = function() {
    p.resizeCanvas(p.windowWidth, p.windowHeight);
    points = [];
}

p.mouseClicked = function() {
    points = [];
}

p.keyPressed = function() {
    points = []
}

};

var circle_line = new p5(sketch);

<script src="https://cdnjs.cloudflare./ajax/libs/p5.js/1.3.1/p5.min.js"></script>
<div id="p5js_canvas"></div>

Demo

本文标签： javascriptHow to calculate intersection point of a line on a circle using p5jsStack Overflow