Conf3tti Conf3tti - 2 months ago 8
Java Question

Decide if a circle intersects with an infinite line

So, I need to check if a circle is intersected by a line algebraically. I've attempted to do this by taking a perpendicular line to the infinite that passes through the center of the circle. I then measure the perpendicular against the radius of the circle, and it states that the line does not intersect if d > r.

import java.util.Scanner;
public class LineCircle_Intersection {

public static void main(String[] args) {
Scanner in = new Scanner(System.in);

double p1x, p2x, p1y, p2y, cx, cy, r;

System.out.print("Enter p1x: ");
p1x = in.nextDouble();
System.out.print("Enter p1y: ");
p1y = in.nextDouble();
System.out.print("Enter p2x: ");
p2x = in.nextDouble();
System.out.print("Enter p2y: ");
p2y = in.nextDouble();
System.out.print("Enter cx: ");
cx = in.nextDouble();
System.out.print("Enter cy: ");
cy = in.nextDouble();
System.out.print("Enter r: ");
r = in.nextDouble();

double m = (p2y-p1y)/(p2x-p1x);
double pem = -1/m;
double pey = pem + p1y; // pe = perpendicular line (used E instead of L because lowercase l looks too much like 1)
double pex = (pey - p1y)/pem;
double d = Math.sqrt((pex-cx) * (pex-cx) + (pey-cy) * (pey-cy));

if (d <= r)
if (d == r)
System.out.println("Line intersects the circle at one point.");
else
System.out.println("Line intersects the circle at two points.");
else
if (m == 1)
if (d <= r) // There's a problem in this area. I'm not sure what, or how to fix it.
if (d == r)
System.out.println("The line intersects the circle at one point.");
else
System.out.println("Line intersects the circle at two points.");
else
System.out.println("Line does not intersect the circle.");
else
System.out.println("Else."); //This says "Else" for testing purposes.
}

}


Here's where things start to go wrong. There are several points that can be input that clearly should intersect or not intersect, but the program frequently says otherwise.

Will be working on this for a few hours, so if I solve it before someone else I'll post an update and how I solved it.

Answer

The principle is correct, but I won't verify your computations.

In short:

boolean intersects=false;
double p2p1x=p2x-p1x, p2p1y=p2y-p1y;
double p1p2DistSq=p2p1x*p2p1x+p2p1y*p2p1y;
if(p1p2DistSq > 1e-12) { // well-behaved line 
  double p1cx=p1x-cx, p1cy=p1y-cy;
  double crossprod=p2p1x*p1cy-p2p1y*p1cx;
  double distCenterToLineSquare=crossprod*crossprod/p1p2DistSq;
  intersects = (distCenterToLineSquare <= r*r); // r is radius
} // cowardly refusing to deal with ill-configured lines

In details:

Preliminary (and take this as an easy way to deduce the distance between a point and a line if you don't have internet at the moment)

The cross-product between two vectors

{ax, ay} x {bx, by} = |a|*|b|*sin(angle_between_dir_a_and_b)

Also this cross-product is (ax*by-ay*bx)


Now, assume a line passing through P1 with direction defined by the unitary vector {ux, uy}. The distance of a point {cx. cy} to this line will be

dist=sin(alpha)*|P1-C|

where |P1-C| is the distance between C and P1 and alpha is the angle between the direction {ux, uy} and the direction of the line {P1,C}. Let's denote with {vx,vy} the unitary direction of {P1,C} line. In this case, since u and v are unitary (|u|=|v|=1)

 sin(alpha)=ux*vy-uy*vx

Thus

dist=(ux*vy-uy*vx)*|P1-C|

Plugging in the vx, vy using

vx=(P1x-Cx)/|P1-C| // it's a unitary vector
vy=(P1y-Cy)/|P1-C|

results in

dist=ux*(P1y-Cy)-uy*(P1x-Cx)

Now, the only thing that remains, is ux and uy. Since your line is defined by P1 and P2

ux=(P2x-P1x)/|P1-P2|
uy=(P2y-P1y)/|P1-P2|

(with |P1-P2| again, the distance between P1 and P2)

dist=( (P2x-P1x)*(P1y-Cy)-(P2y-P1y)*(P1x-Cx) )/ |P1-P2|

Ok, |P1-P2| requires an sqrt evaluation and we can get rid of it by comparing your dist^2 with the radius^2

The 'line intersect circle' then becomes

double p1cx=p1x-cx, p1cy=p1y-cy;
double p2p1x=p2x-p1x, p2p1y=p2y-p1y;
double crossprod=p2p1x*p1cy-p2p1y*p1cx;
double distCenterToLineSquare=crossprod*crossprod/(p2p1x*p2p1x+p2p1y*p2p1y);
boolean intersects= (distCenterToLineSquare <= r*r); // r is radius
Comments