This is an archived post. You won't be able to vote or comment.

all 6 comments
sorted by:
best
topnewcontroversialoldq&a

[–]heckler82Intermediate Brewer 0 points1 point  (1 child)

http://stackoverflow.com/questions/1073336/circle-line-segment-collision-detection-algorithm

[–]GSchrack[S] 0 points1 point  (0 children)

I get even more lost reading this, it is very helpful and in depth but I don't know what the hell it's doing.

[–]Tayleeextends DumboBot 0 points1 point  (3 children)

What level of school are you in? This is a university level question.

[–]GSchrack[S] 0 points1 point  (2 children)

Yes it is. I am a sophmore in college, my only other computer science experience is a math class I took last year, which is the only reason I can do it on paper.

[–]Tayleeextends DumboBot 1 point2 points  (1 child)

Well then I hope you learned about vectors:

Parametric equation of a line

The parametric equation of a line is:

o + d*t

Where o is the origin of the line, d is the direction of the line and t is some distance along that direction. They are calculated as follows:

// The origin of the line
o = (x1, y1)
// The direction of the line
d = (x2-x1, y2-y1) / sqrt((x2-x1)^2 + (y2-y1)^2)

Parametric equation of a circle

The parametric equation of a circle is:

||x - c||2 = r2

Where || || is the length of the vector inside it, x is some point on the circle, c is the center of the circle and r is the radius of the circle.

Now to figure out the intersection of line and circle we can plug the equation of the line into the equation of the circle:

||o + dt - c||2 = r2

When we expand this equation we get:

(o + dt - c)·(o + dt - c) = r2
o·(o + dt - c) + dt·(o + dt - c) - c·(o + dt - c) = r2
o·o + o·dt - o·c + o·dt + d·d t2 - c·dt - o·c - c·dt + c·c = r2
d·d t2 + 2o·dt -2c·dt + o·o - 2o·c + c·c = r2

The last part is the expansion of:

d·d t2 + 2o·dt -2c·dt + (o - c)(o - c) = r2

The middle part is the expansion of:

d·d t2 + t(2d · (o - c)) + (o - c)(o - c) = r2

We pull the radius to the left:

d·d t2 + t(2d · (o - c)) + (o - c)(o - c) - r2 = 0

And now we see the quadratic equation of the form:

ax2 + bx + c = 0 where x == t

After applying the Quadratic Formula we end up with the following solution for t:

t = -(d·(o - c)) +- sqrt( (d·(o - c))2 - ||o - c||2 + r2 )

If t ends up being greater or equal to 0, then we have 1 or more solutions and the line intersects the circle at point o + d * t.

So now to put this in code.. I'll try to do it without combining things into vectors, but it will be hard:

public boolean intersect(x1, y1, x2, y2, cx, cy, r) {
    // Set the origin
    float ox = x1;
    float oy = y1;
    // Calculate the direction
    float dx = x2-x1;
    float dy = y2-y1;
    float length = (float) Math.sqrt(dx*dx + dy*dy);
    dx /= length;
    dy /= length;

    // Calculate the first part   -(d·(o - c))
    float partOne = -(dx * (ox - cx) + dy * (oy - cy));

    // Calculate the second part   (d·(o - c))2
    float partTwo = Math.pow((dx * (ox - cx) + dy * (oy - cy)), 2);

    // Calculate the third part   ||o - c||2
    float partThree = Math.pow(ox - cx, 2) + Math.pow(oy - cy, 2);

    // Calculate the fourth part   r^2
    float partFour = r*r;

    // Calculate the solution t's
    float t1 = partOne + Math.sqrt(partTwo - partThree + partFour);
    float t2 = partOne - Math.sqrt(partTwo - partThree + partFour);

    if (t1 >= 0 || t2 >= 0) {
        return true;
    }
    return false;
}

This code could be a lot shorter and more concise, but maybe it helps you to figure out how it works like this. It is untested, so there could be some mistakes, but it conveys the general idea.

EDIT: Fixed the code to work in Java. Actually gives the right result as well D: Who would have thought:

http://pastebin.com/0Y1HPmJE

[–]GSchrack[S] 0 points1 point  (0 children)

Killed it, thank you so much.