Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » a fast way to get the intersectionpoint of a line and a circle

This thread is locked; no one can reply to it. rss feed Print
a fast way to get the intersectionpoint of a line and a circle
Ariesnl
Member #2,902
November 2002
avatar

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 ?
so I do not care about getting both intersectionpoints I just want the one closest to the start of a linepiece or none if no intersection exists.

Who's a math guru ? 8-)

Perhaps one day we will find that the human factor is more complicated than space and time (Jean luc Picard)
Current project: [Star Trek Project ] Join if you want ;-)

Edgar Reynaldo
Member #8,592
May 2007
avatar

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.

Ariesnl
Member #2,902
November 2002
avatar

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)
Current project: [Star Trek Project ] Join if you want ;-)

Edgar Reynaldo
Member #8,592
May 2007
avatar

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
(v is the direction)
and your circle given by c and radius r.

Then you want <math>||\lambda v + b - c||_2^2 = r^2</math>

Let d = b-c.

Now enter
"Solve (lamda*v_1 + d_1)^2 + (lambda*v_2 + d_2)^2 = r^2 for lambda"
at wolframalpha.com
It's better to set v to a unit vector, maybe you can simplify a bit. You see the two solutions are almost identical.
If you set b to the start of your line segment and v is a unit vector, lambda tells you how many units you have to go on your line in direction of v to either intersection point. Too late now, good night.

SiegeLord
Member #7,827
October 2006
avatar

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
[SiegeLord's Abode][Codes]:[DAllegro5]:[RustAllegro]

Edgar Reynaldo
Member #8,592
May 2007
avatar

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! 8-) ( 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.

Chris Katko
Member #1,881
January 2002
avatar

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:
“Programs should be written for people to read, and only incidentally for machines to execute.” - Structure and Interpretation of Computer Programs
"Political Correctness is fascism disguised as manners" --George Carlin

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
avatar

@ Polybios I didn't know about that site.. it's like good old "Derive" but online ;D
Gonna try this tonight..
I need it for the phasers in my startrek game so if your target is obscured by something else it will hit that thing instead. It never was a big issue UNTIL I made asteroid belts where you can hide.

Perhaps one day we will find that the human factor is more complicated than space and time (Jean luc Picard)
Current project: [Star Trek Project ] Join if you want ;-)

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
avatar

Yeah, that's very common.

Just use a quadtree.

-----sig:
“Programs should be written for people to read, and only incidentally for machines to execute.” - Structure and Interpretation of Computer Programs
"Political Correctness is fascism disguised as manners" --George Carlin

Ariesnl
Member #2,902
November 2002
avatar

This works fine. I guess if it can be optimized further...
I'll be checking a lot of objects against just a few lines (1 to 4,.. max 8)
anything out of range can be skipped anyway

#SelectExpand
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.
(I never used Quad trees before, so I'm no expert)

Perhaps one day we will find that the human factor is more complicated than space and time (Jean luc Picard)
Current project: [Star Trek Project ] Join if you want ;-)

Edgar Reynaldo
Member #8,592
May 2007
avatar

Polybios said:

See your line as a vector given by lambda*v+b
(v is the direction)
and your circle given by c and radius r.

Then you want <math>||\lambda v + b - c||_2^2 = r^2</math>

Let d = b-c.

Now enter
"Solve (lamda*v_1 + d_1)^2 + (lambda*v_2 + d_2)^2 = r^2 for lambda"
at wolframalpha.com

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.
I haven't verified it manually, but doing so would certainly help understanding it. :P

@AriesNL:
Glad it worked. I don't know how long your line segments are, but maybe simple grid cells would be enough? Just keep an updated list of objects that currently are within a grid-cell, then, for each line, only check objects that are in nearby cells. You'd have to figure out a sensible grid size depending on the size of your circles and lines.

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.

Go to: