
a fast way to get the intersectionpoint of a line and a circle 
Ariesnl
Member #2,902
November 2002

I'm seeking a fast way to get the intersection point of a line and a circle closest to the startingpoint of a line. any ideas ? Who's a math guru ? Perhaps one day we will find that the human factor is more complicated than space and time (Jean luc Picard) 
Edgar Reynaldo
Member #8,592
May 2007

I don't know of a faster way than solving the equation. It's messy, but you come up with this : If you have line Ax+By+C=0 and circle (XJ)^2 + (YK)^2 = R^2 then you solve for the y of the line and substitute it into the circle equation you get this for x : (A^2 + B^2) X^2 + (2AC + 2ABK  2JB^2) X^1 + (R^2 + C^2 + (B^2)(J^2 + K^2) + 2BCK) = 0 Solve that with the quadratic equation, and then find y on the line where x on the circle intersects. You will have 0,1, or 2 solutions. Also, a line has no starting or ending point. Unless you're talking about a line segment. 
Ariesnl
Member #2,902
November 2002

It should be a line segment actually... Perhaps one day we will find that the human factor is more complicated than space and time (Jean luc Picard) 
Edgar Reynaldo
Member #8,592
May 2007

I made a long post and then lost it. I'm gonna make some wiki tutorials for this stuff. Seems silly to have to post it over and over again. Something you can do quickly to check if the line segment overlaps the circle is to do an AABB check. The line segment forms the diagonal of a rectangle, and if you superscribe a square around the circle you can compare them quickly and easily. 
Polybios
Member #12,293
October 2010

See your line as a vector given by lambda*v+b Then you want Let d = bc. Now enter 
SiegeLord
Member #7,827
October 2006

Edgar Reynaldo said: I made a long post and then lost it. I'm gonna make some wiki tutorials for this stuff. Seems silly to have to post it over and over again. I'd trust allegro.cc over the wiki for not randomly losing it... maybe start your own blog. "For in much wisdom is much grief: and he that increases knowledge increases sorrow."Ecclesiastes 1:18 
Edgar Reynaldo
Member #8,592
May 2007

I got hit by the login timeout posting bug. And hitting back in my browser didn't work. And allegro.cc's auto restore lost over an hour of work. Good thing I've got all my notes on paper in pen! ( I hate having to rederive the general first degree form of a line equation over and over again. I just can't remember what A, B, and C are without getting out pen and paper. ;P ) As for starting a blog, I've got my own website, but I don't know which blogging thingamajiggys are the best to work with. Kompozer sucks. I now handedit all my html files in CB. JS too. Haven't updated my allegro.cc member website in a while now either. My website comes with WordPress installed, but it makes my home directory look like it got napalmed and I don't use it. Been thinking of uninstalling it to clean up the directory structure. 
Chris Katko
Member #1,881
January 2002

Edgar Reynaldo said: And allegro.cc's auto restore lost over an hour of work. I've lost so many posts to accidentally flicking the back button on my damn track pad. sig: 
Polybios
Member #12,293
October 2010

Refererring to my post above: If e is the endpoint of your line (b was the start), you can simply do v = eb. Now compute the lambdas (if the mess under the sqrt is negative, there is no solution). If lambda is between 0 and 1, the point is on your line segment. If both lambdas are between 0 and 1, the smaller one indicates the one closer to the starting point. Now simply insert the computed lambdas back into the line equation p = lambda*v+b to get the points. Alternatively or additional to bounding boxes, you could use the distance from the circle center to the line as a preliminary step to see whether an intersection is at all possible (compare squared distances). However, I don't think it is way faster than the computation of the term under the sqrt. 
Ariesnl
Member #2,902
November 2002

@ Polybios I didn't know about that site.. it's like good old "Derive" but online Perhaps one day we will find that the human factor is more complicated than space and time (Jean luc Picard) 
beoran
Member #12,636
March 2011

For performance, you could add a "broad phase" to the collision detection. In the broad phase any impossible collisions are ruled out. Then only the possible ones are checked in detail. One way to do a broad phase is to divide the game world or level into a grid, and then only check collisions between objects that are in the same cells of the grid. 
Chris Katko
Member #1,881
January 2002

Yeah, that's very common. Just use a quadtree. sig: 
Ariesnl
Member #2,902
November 2002

This works fine. I guess if it can be optimized further... 1SPoint getClosestIntersection(double a_dCX, double a_dCY, double R, double a_dStartX, double a_dStartY,double a_dEndX, double a_dEndY)
2{
3 SPoint Intersection;
4 Intersection.m_nX = 1;
5 Intersection.m_nY = 1;
6 SPoint LP1;
7 LP1.m_nX = a_dStartX  a_dCX;
8 LP1.m_nY = a_dStartY a_dCY;
9
10 SPoint LP2;
11 LP2.m_nX = a_dEndX  a_dCX;
12 LP2.m_nY = a_dEndY a_dCY;
13
14 SPoint P2minP1;
15 P2minP1.m_nX = LP2.m_nX  LP1.m_nX;
16 P2minP1.m_nY = LP2.m_nY  LP1.m_nY;
17
18 double dA = (P2minP1.m_nX * P2minP1.m_nX) + (P2minP1.m_nY * P2minP1.m_nY);
19 double dB = 2 * ((P2minP1.m_nX * LP1.m_nX) + (P2minP1.m_nY * LP1.m_nY));
20 double dC = (LP1.m_nX * LP1.m_nX) + (LP1.m_nY * LP1.m_nY)  (R * R);
21
22 double dD = dB * dB (4 * dA * dC);
23
24 double dIX;
25 double dIY;
26 double dU;
27 if (dD < 0)
28 {
29 // No Solution 1,1
30 return Intersection;
31 }
32 else if (dD > 0)
33 {
34 double dSquareRootDelta = sqrt(dD);
35 dU = (dB  dSquareRootDelta) / (2 * dA);
36 }
37 else
38 {
39 dU = dB / (2 * dA);
40 }
41
42 if ((dU >= 0) && (dU <= 1))
43 {
44 Intersection.m_nX = a_dStartX + (dU * P2minP1.m_nX);
45 Intersection.m_nY = a_dStartY + (dU * P2minP1.m_nY);
46 }
47
48 return Intersection;
49}
This is only for Phaserobject "collision" So I wonder if building a quadTree would not take more time ( steal more performance) than just doing the collisions only. Perhaps one day we will find that the human factor is more complicated than space and time (Jean luc Picard) 
Edgar Reynaldo
Member #8,592
May 2007

Polybios said:
See your line as a vector given by lambda*v+b Then you want Let d = bc. Now enter
Bunch of wacky crap I can't understand. Why does the solution involve i?

Polybios
Member #12,293
October 2010

Because the stuff under the sqrt can become negative. Then you'd have complex solutions with an imaginary part != 0; but we are not interested in those here. The first 2 ones are the real solutions. @AriesNL: Another thing I was thinking of is if you couldn't transform everything into a coordinate system starting in the phaser starting point, pointing along its direction and orthogonal, basically rotated and translated. You'd have to keep some sort of matrix for every line segment. Checking then should be rather trivial. Don't know. 
