|
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
Major Reynaldo
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 (X-J)^2 + (Y-K)^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. My Website! | EAGLE GUI Library Demos | My Deviant Art Gallery | Spiraloid Preview | A4 FontMaker | Skyline! (Missile Defense) Eagle and Allegro 5 binaries | Older Allegro 4 and 5 binaries | Allegro 5 compile guide |
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
Major Reynaldo
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. My Website! | EAGLE GUI Library Demos | My Deviant Art Gallery | Spiraloid Preview | A4 FontMaker | Skyline! (Missile Defense) Eagle and Allegro 5 binaries | Older Allegro 4 and 5 binaries | Allegro 5 compile guide |
Polybios
Member #12,293
October 2010
|
See your line as a vector given by lambda*v+b Then you want Let d = b-c. 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
Major Reynaldo
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 re-derive 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 thing-a-ma-jiggys are the best to work with. Kompozer sucks. I now hand-edit 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. My Website! | EAGLE GUI Library Demos | My Deviant Art Gallery | Spiraloid Preview | A4 FontMaker | Skyline! (Missile Defense) Eagle and Allegro 5 binaries | Older Allegro 4 and 5 binaries | Allegro 5 compile guide |
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 = e-b. 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 Phaser-object "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
Major Reynaldo
May 2007
|
Polybios said:
See your line as a vector given by lambda*v+b Then you want Let d = b-c. Now enter
Bunch of wacky crap I can't understand. Why does the solution involve i?
My Website! | EAGLE GUI Library Demos | My Deviant Art Gallery | Spiraloid Preview | A4 FontMaker | Skyline! (Missile Defense) Eagle and Allegro 5 binaries | Older Allegro 4 and 5 binaries | Allegro 5 compile guide |
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. |
|