 |
Author |
Topic: circle - line intersection (Read 529 times) |
|
Koenie
  
 
|
circle - line intersection
« on: Sep 29th, 2003, 9:18pm » |
|
Ok, I've got a little problem with circles and lines math here. I got a circle with radius 90 with centerpoint at (125, 110), and a line with corner a and a point on the line (Xb, Yb). Corner a, and points (Xb, Yb) are known, but variable. Where do the circle and the line intersect? I've also made a drawing of it, so the problem (hopefully) becomes more clear: http://koeniedesign.com/circle.gif
Help me!
Koenie
|
http://koeniedesign.com
|
|
|
arielm
|
Re: circle - line intersection
« Reply #1 on: Sep 29th, 2003, 11:53pm » |
|
if your plans don't include to take time in count (i.e when the intersection will happen), the following link should help you:
http://www.ferris.edu/faculty/burtchr/sure215/lin-cir/lin-cir.htm
(it doesn't include any ready made java algorithm, but rather the required maths to solve the problem)
hints:
1) the cotangent of an angle "a" is equal to 1.0 / tan(a)
2) once you find (using the "quadratic") two possible (x,y) solutions, you still have to check if these point lie on the circle (using simple pythagoras theorem stuff), but be sure to take in count "the rounding of the numbers in intermediate steps":
for example, if you have a circle of radius r centered at (0,0) _ in order to know if a point (x,y) is on the circle _ instead of checking for
x * x + y * y == r * r
you could check for
abs(x * x + y * y - r * r) > EPSILON
where EPSILON is a very small value (predefined in processing), but yet not zero...
hth
|
| « Last Edit: Sep 30th, 2003, 12:25am by arielm » |
|
Ariel Malka | www.chronotext.org
|
|
|
toxi
|
Re: circle - line intersection
« Reply #2 on: Sep 30th, 2003, 2:32pm » |
|
a slightly more straight forward solution is below, code based on the C version of my all-time fave peter bourke. code also works in 3D - for 2D cases just set the Z coordinates to 0, also see comments below...
Code:void setup() {
size(300,300);
ellipseMode(CENTER_DIAMETER);
rectMode(CENTER_DIAMETER);
}
void loop() {
background(200,204,200);
stroke(0);
fill(255);
// first draw circle, size is mouse controlled
float d=sqrt(sq(width/2-mouseX)+sq(height/2-mouseY))*2;
ellipse(width/2,height/2,d,d);
// now draw intersection line we want to check
line(0,30,width,150);
// compute intersection between the two
float[] iSectPoints=sphere_line_iSect(0,30,0,width,150,0,width/2,height/2,0,(int )d/2);
// check if there're any points returned
if (iSectPoints[0]>0) {
// mark them with red
fill(255,0,0);
for(int i=0; i<iSectPoints[0]; i++) {
rect(iSectPoints[1+i*3],iSectPoints[2+i*3],5,5);
}
}
}
// computes 2d/3d circle/sphere - line intersection points
// based on code by peter bourke (http://astronomy.swin.edu.au/~pbourke/geometry/sphereline/ )
// returns array of floats, where first item specifies number of intersection points found {0, 1 or 2}
// set Z coordinates to 0 for 2D intersection checks
// line defined by points {x1;y1;z1} -> {x2;y2;z2}
// circle/sphere defined by center point at {x3;y3;z3} and radius r
float[] sphere_line_iSect(int x1, int y1, int z1,int x2, int y2, int z2,int x3, int y3, int z3, int r) {
float[] points=new float[7];
float a = sq(x2 - x1) + sq(y2 - y1) + sq(z2 - z1);
float b = 2* ( (x2 - x1)*(x1 - x3) + (y2 - y1)*(y1 - y3) + (z2 - z1)*(z1 - z3) ) ;
float c = x3*x3 + y3*y3 + z3*z3 + x1*x1 + y1*y1 + z1*z1 - 2* ( x3*x1 + y3*y1 + z3*z1 ) - r*r ;
float i = b * b - 4 * a * c;
if ( i < 0.0 ) {
// no intersection
points[0] = 0;
return(points);
} else if ( i == 0.0 ) {
// one intersection
points[0] = 1;
float mu = -b/(2*a) ;
points[1] = x1 + mu*(x2-x1);
points[2] = y1 + mu*(y2-y1);
points[3] = z1 + mu*(z2-z1);
return(points);
} else {
// two intersections
points[0] = 2;
// first intersection
float mu = (-b + sqrt( b*b - 4*a*c )) / (2*a);
points[1] = x1 + mu*(x2-x1);
points[2] = y1 + mu*(y2-y1);
points[3] = z1 + mu*(z2-z1);
// second intersection
mu = (-b - sqrt(b*b - 4*a*c )) / (2*a);
points[4] = x1 + mu*(x2-x1);
points[5] = y1 + mu*(y2-y1);
points[6] = z1 + mu*(z2-z1);
return(points);
}
} |
|
|
| « Last Edit: Sep 30th, 2003, 2:32pm by toxi » |
|
http://toxi.co.uk/
|
|
|
Koenie
|
Re: circle - line intersection
« Reply #3 on: Sep 30th, 2003, 5:46pm » |
|
Toxi, you the man! Ariel, you the man! Thanks a lot for that stuff, it's a real help. I haven't totally read the article Ariel posted, but I will when I've got some time. Oh and just one more thing......
Thank you!
Koenie
|
http://koeniedesign.com
|
|
|
|
