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?

Sergei

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? – Salomone

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. – Letha

The IntPoint class being used is provided by a library and the coordinates have to be in int – Sergei

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... ;-) – Letha

+1 for the triple, but that doesn't cover all solutions? e.g. – Leighleigha

@Leighleigha The OP's method takes an int radius argument. I believe only the radius's square is an integer in your example. – Letha

missed the int radius! :/ exactly, my bad. – Leighleigha

See also this question and this question. – Salomone

Answer 1

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)));
    }

Letha

could you give a little more clarification on what is happening in this piece of code – Sergei

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... ;-) – Letha

+1 and upvote for the p q variant, and a very elegant vector solution :) – Leighleigha

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)); – Oboe

The solution I found working for me was this one: keith-hair.net/blog/2008/08/05/line-to-circle-intersection-data Was easy porting to my target language, too. – Oboe

@HulaBula Strange, when I run your code, I get two points, not one, exactly where they should be: (0,-10) and (0,10). – Letha

@Letha 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.. – Oboe

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

Okay, you're right. I am talking about line segments then - sorry about the confusion and thanks for putting it right! – Oboe

Answer 2

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;

}

Pyrogen