a fast way to get the intersectionpoint of a line and a circle

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 ?

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.

It should be a line segment actually...

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.

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

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.

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.

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.

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.

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.

@ Polybios I didn't know about that site.. it's like good old "Derive" but online

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.

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.

Yeah, that's very common.

Just use a quadtree.

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

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)

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

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*?

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.

@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.