Circle Line Intersection points

Question

public static ArrayList<IntPoint> getCircleLineIntersectionPoint(IntPoint pointA, IntPoint pointB, IntPoint center, int radius) {
    // returns a list of intersection points between a line which passes through given points,
    // pointA and pointB, and a circle described by given radius and center coordinate

    double disc, A, B, C, slope, c;
    double x1, x2, y1, y2;
    IntPoint point1, point2;
    ArrayList<IntPoint> intersections = new ArrayList<IntPoint>();  
    try{
        slope = Util.calculateSlope(pointA, pointB);
    }catch (UndefinedSlopeException e){         
        C =  Math.pow(center.y, 2) + Math.pow(pointB.x, 2) - 2 * pointB.x * center.x + Math.pow(center.x, 2) - Math.pow(radius, 2);
        B = -2 * center.y;
        A = 1;
        disc = Math.pow(B, 2) - 4 * 1 * C;
        if (disc < 0){
            return intersections;
        }
        else{
            y1 = (-B + Math.sqrt(disc)) / (2 * A);
            y2 = (-B - Math.sqrt(disc)) / (2 * A);

            x1 = pointB.x;
            x2 = pointB.x;
        }
        point1 = new IntPoint((int)x1, (int)y1);
        point2 = new IntPoint((int)x2, (int)y2);
        if (Util.euclideanDistance(pointA,  point2) > Util.euclideanDistance(pointA, point1)){
            intersections.add(point1);
        }
        else{
            intersections.add(point2);
        }
        return intersections;
    }
    if (slope == 0){
        C =  Math.pow(center.x, 2)  + Math.pow(center.y, 2) + Math.pow(pointB.y, 2) - 2 * pointB.y * center.y  - Math.pow(radius, 2);
        B = -2 * center.x;
        A = 1;
        disc = Math.pow(B, 2) - 4 * 1 * C;
        if (disc < 0){
            return intersections;
        }
        else{
            x1 = (-B + Math.sqrt(disc)) / (2*A);
            x2 = (-B - Math.sqrt(disc)) / (2*A);
            y1 = pointB.y;
            y2 = pointB.y;
        }
    }
    else{
        c = slope * pointA.x + pointA.y;
        B = (2 * center.x + 2 * center.y * slope  + 2 * c * slope);
        A = 1 + Math.pow(slope, 2);
        C = (Math.pow(center.x, 2) + Math.pow(c, 2) + 2 * center.y * c + Math.pow(center.y, 2) - Math.pow(radius, 2));
        disc = Math.pow(B, 2) - (4 * A * C);

        if (disc < 0){
            return intersections;
        }
        else{
            x1 = (-B + Math.sqrt(disc)) / (2 * A);
            x2 = (-B - Math.sqrt(disc)) / (2 * A);

            y1 = slope * x1 - c;
            y2 = slope * x2 - c;
        }
    }

    point1 = new IntPoint((int)x1, (int)y1);
    point2 = new IntPoint((int)x2, (int)y2);
    if (Util.euclideanDistance(pointA,  point2) > Util.euclideanDistance(pointA, point1)){
        //if (Util.angleBetween(pointA, pointB, point1) < Math.PI/2){
            intersections.add(point1);
        //}
    }
    else{
        //if (Util.angleBetween(pointA, pointB, point1) < Math.PI/2){
            intersections.add(point2);
        //}
    }       
    return intersections;
}

I am using the above algorithm to test for intersection between a circle and a line. It works fine sometimes but at other times it fails. The code represents the equation which is derived from solving for x simultaneously from circle and line equations (x-a)^+(y-b)^2=r^2 and y = mx - mx1 + y1. Has anyone got an idea where I am going wrong either in my maths or elsewhere?

Can you give an example of some lines and circles that cause it to fail? And why do you convert your x,y coordinates to integers? — Roddy of the Frozen Peas, Oct 24 '12 at 16:07
Could you try to declare your variables where you use them, and not somewhere else entirely? And give them more meaningful names? (`slope` is a good start, though.) That aside, I also would not expect the points you are looking for to have integer coordinates, so the casting seems very dubious. — arne.b, Oct 24 '12 at 16:09
The IntPoint class being used is provided by a library and the coordinates have to be in int — cobie, Oct 24 '12 at 16:12
Then maybe you are better off finding the integer points on the circle (2 horizontally aligned with the center, 2 vertically aligned with the center, more only if the radius is the largest number in a Pythagorean triple) and check whether any of these is on the line... ;-) — arne.b, Oct 24 '12 at 16:21
+1 for the triple, but that doesn't cover all solutions? [e.g.](http://www.wolframalpha.com/input/?i=x%5E2%2By%5E2+%3D2+%2C+y%3Dx) — linski, Oct 24 '12 at 16:48
@linski The OP's method takes an `int radius` argument. I believe only the radius's square is an integer in your example. — arne.b, Oct 24 '12 at 16:53
See also [this question](http://stackoverflow.com/questions/1073336/circle-line-collision-detection?rq=1) and [this question](http://stackoverflow.com/questions/4651248/circle-line-intersection-not-working-properly?rq=1). — Roddy of the Frozen Peas, Oct 24 '12 at 18:04

arne.b · Accepted Answer · 2012-10-25T07:30:02.813

Your calculations seem quite long, and I do not see the use of the different cases you test. Anyway, since I found the problem interesting I attempted to solve it myself and came up with the following. Feel free to replace double radius by int radius and use IntPoints, but be aware that every time you cast, as discussed in the comments, results that are not exact integer intersection points will become wrong.

The background of the calculations performed is this: From point A, a scaled version of vector AB points to a point on the circle. That point has distance radius from center. Hence, |AC + scalingFactor * AB|=r.

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class CircleLine {

    public static List<Point> getCircleLineIntersectionPoint(Point pointA,
            Point pointB, Point center, double radius) {
        double baX = pointB.x - pointA.x;
        double baY = pointB.y - pointA.y;
        double caX = center.x - pointA.x;
        double caY = center.y - pointA.y;

        double a = baX * baX + baY * baY;
        double bBy2 = baX * caX + baY * caY;
        double c = caX * caX + caY * caY - radius * radius;

        double pBy2 = bBy2 / a;
        double q = c / a;

        double disc = pBy2 * pBy2 - q;
        if (disc < 0) {
            return Collections.emptyList();
        }
        // if disc == 0 ... dealt with later
        double tmpSqrt = Math.sqrt(disc);
        double abScalingFactor1 = -pBy2 + tmpSqrt;
        double abScalingFactor2 = -pBy2 - tmpSqrt;

        Point p1 = new Point(pointA.x - baX * abScalingFactor1, pointA.y
                - baY * abScalingFactor1);
        if (disc == 0) { // abScalingFactor1 == abScalingFactor2
            return Collections.singletonList(p1);
        }
        Point p2 = new Point(pointA.x - baX * abScalingFactor2, pointA.y
                - baY * abScalingFactor2);
        return Arrays.asList(p1, p2);
    }

    static class Point {
        double x, y;

        public Point(double x, double y) { this.x = x; this.y = y; }

        @Override
        public String toString() {
            return "Point [x=" + x + ", y=" + y + "]";
        }
    }


    public static void main(String[] args) {
        System.out.println(getCircleLineIntersectionPoint(new Point(-3, -3),
                new Point(-3, 3), new Point(0, 0), 5));
        System.out.println(getCircleLineIntersectionPoint(new Point(0, -2),
                new Point(1, -2), new Point(1, 1), 5));
        System.out.println(getCircleLineIntersectionPoint(new Point(1, -1),
                new Point(-1, 0), new Point(-1, 1), 5));
        System.out.println(getCircleLineIntersectionPoint(new Point(-3, -3),
                new Point(-2, -2), new Point(0, 0), Math.sqrt(2)));
    }

could you give a little more clarification on what is happening in this piece of code — cobie, Oct 24 '12 at 18:29
well, `a`, b and `c` are coefficients of thequadratic equation to solve, although I prefer the version with (1,) p and `q`. Since the actual b includes 2 as a factor, and so would p, but p would then have to be divided by 2, I actually used only half of b and p for the intermediate variables. As for how to get to a,b and c...well, what is the vector AC (from A to circle center), coordinate wise? What is AB? Square the equation given above, transform... ;-) — arne.b, Oct 24 '12 at 21:26
+1 and upvote for the p q variant, and a very elegant vector solution :) — linski, Oct 25 '12 at 19:01
Your solution returns an intersection (where there shouldn't be one) for the following case: `System.out.println(getCircleLineIntersectionPoint(new Point(0, -3), new Point(0, 2), new Point(0, 0), 10));` — Clemens Sum, Mar 09 '13 at 08:40
The solution I found working for me was this one: http://keith-hair.net/blog/2008/08/05/line-to-circle-intersection-data/ Was easy porting to my target language, too. — Clemens Sum, Mar 09 '13 at 14:16
@HulaBula Strange, when I run your code, I get two points, not one, exactly where they should be: (0,-10) and (0,10). — arne.b, Mar 09 '13 at 18:16
@arne.b To my understanding, there should be no intersection as the circle contains the line without intersecting it, no? Well, at least if the points define the start and end of the line.. — Clemens Sum, Mar 10 '13 at 07:50
@HulaBula A line does not start or end. You seem to be talking about line segments, and so does the article you linked to (which I did not realize before from the misleading word "line" in the title). For segments, one of course needs additional checks regarding where on the line the segment is. — arne.b, Mar 10 '13 at 21:56
Okay, you're right. I am talking about line segments then - sorry about the confusion and thanks for putting it right! — Clemens Sum, Mar 11 '13 at 07:25

score 0 · Answer 2 · answered Mar 15 '15 at 22:43

Here a solution with import javax.vecmath.Vector2d;

static Vector2d[] circleLineIntersection1(Vector2d a, Vector2d b, Vector2d o, double radius) {

    Vector2d p1 = new Vector2d(a);
    Vector2d p2 = new Vector2d(b);
    p1.sub(o);
    p2.sub(o);

    Vector2d d = new Vector2d();
    d.sub(p2, p1);

    double det = p1.x * p2.y - p2.x * p1.y;

    double dSq = d.lengthSquared();

    double discrimant = radius * radius * dSq - det * det;

    if (discrimant < 0) {
        return new Vector2d[0];
    }

    if (discrimant == 0) {
        Vector2d[] t = new Vector2d[1];
        t[0] = new Vector2d(det * d.y / dSq + o.x, -det * d.x / dSq + o.y);

        return t;
    }

    double discSqrt = Math.sqrt(discrimant);

    double sgn = 1;
    if (d.y < 0) {
        sgn = -1;
    }

    Vector2d[] t = new Vector2d[2];
    t[0] = new Vector2d((det * d.y + sgn * d.x * discSqrt) / dSq + o.x, (-det * d.x + Math.abs(d.y) * discSqrt) / dSq + o.y);
    t[1] = new Vector2d((det * d.y - sgn * d.x * discSqrt) / dSq + o.x, (-det * d.x - Math.abs(d.y) * discSqrt) / dSq + o.y);
    return t;

}

Circle Line Intersection points

2 Answers2

Linked