Line circle intersection: Difference between revisions

{{trans|Go}}

<lang zkl>const EPS=1e-14; // a close-ness to zero

// p1,p2 are (x,y), circle is ( (x,y),r )

fcn intersectLineCircle(p1,p2, circle, segment=False) // assume line

{

cx,cy := circle[0].apply("toFloat");

r := circle[1].toFloat();

x1,y1 := p1.apply("toFloat"); x2,y2 := p2.apply("toFloat");

A,B,C,a := (y2 - y1), (x1 - x2), (x2*y1 - x1*y2), (A*A + B*B);

b,c,bnz := 0,0,True;

if(B.closeTo(0,EPS)){ // B is zero or close to it

b = 2.0 * (B*C + A*B*cx - A*A*cy);

c = C*C + 2.0*A*C*cx - A*A*(r*r - cx*cx - cy*cy);

bnz = False

}else{

b = 2.0*( A*C + A*B*cy - B*B*cx );

c = C*C + 2.0*B*C*cy - B*B*( r*r - cx*cx - cy*cy );

}

d := b*b - 4.0*a*c; // discriminant

if(d<0.0){ // no real solution? zero --> one solution

if (d>-0.005) d=0.0; // close enough to zero

else return(T); // no intersection

}

d=d.sqrt();

reg ux,uy, vx,vy;

if(bnz){

ux,vx = (-b + d) / (2*a), (-b - d) / (2*a);

uy,vy = -(A*ux + C) / B, -(A*vx + C) / B;

}else{

uy,vy = (-b + d) / (2*a), (-b - d) / (2*a);

ux,vx = -(B*uy + C) / A, -(B*vy + C) / A;

}

if(segment){

within:='wrap(x,y){ // is (x,y) within segment p1 p2?

d1:=( (x2 - x1).pow(2) + (y2 - y1).pow(2) ).sqrt();

d2:=( (x - x1).pow(2) + (y - y1).pow(2) ).sqrt();

d3:=( (x2 - x) .pow(2) + (y2 - y) .pow(2) ).sqrt();

(d1 - d2 - d3).closeTo(0,EPS);

};

i1,i2 := within(ux,uy), within(vx,vy);

if(d==0) return(if(i1) T(ux,uy) else T);

return(T( i1 and T(ux,uy), i2 and T(vx,vy) ).filter())

}

if(d==0) return( T( T(ux,uy) ) );

return( T(ux,uy), T(vx,vy) )

}</lang>

<lang zkl>circle:=T( T(3,-5),3 ); p1,p2 := T(-10,11), T( 10,-9);

println("Circle @ ",circle); lcpp(p1,p2,circle);

p2:=T(-11,12); lcpp(p1,p2,circle,True);

p1,p2 := T(3,-2), T(7,-2); lcpp(p1,p2,circle);

circle:=T( T(0,0),4 ); p1,p2 := T(0,-3), T(0,6);

println("\nCircle @ ",circle);

lcpp(p1,p2,circle);

lcpp(p1,p2,circle,True);

circle:=T( T(4,2),5 ); p1,p2 := T(6,3), T(10,7);

println("\nCircle @ ",circle);

lcpp(p1,p2,circle);

p1,p2 := T(7,4), T(11,8); lcpp(p1,p2,circle,True);

fcn lcpp(p1,p2,circle,segment=False){

println(" %s %s -- %s intersects at %s"

.fmt(segment and "Segment" or "Line ",

p1,p2,intersectLineCircle(p1,p2, circle,segment)));

}</lang>

Circle @ L(L(3,-5),3)

Line L(-10,11) -- L(10,-9) intersects at L(L(6,-5),L(3,-2))

Segment L(-10,11) -- L(-11,12) intersects at L()

Line L(3,-2) -- L(7,-2) intersects at L(L(3,-2))

Circle @ L(L(0,0),4)

Line L(0,-3) -- L(0,6) intersects at L(L(0,4),L(0,-4))

Segment L(0,-3) -- L(0,6) intersects at L(L(0,4))

Circle @ L(L(4,2),5)

Line L(6,3) -- L(10,7) intersects at L(L(8,5),L(1,-2))

Segment L(7,4) -- L(11,8) intersects at L(L(8,5))