Java-Gaming.org Hi !
 Featured games (83) games approved by the League of Dukes Games in Showcase (539) Games in Android Showcase (132) games submitted by our members Games in WIP (603) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
 Home Help Search Login Register
Pages: [1]
 ignore  |  Print
 Collision between circle and line  (Read 2964 times) 0 Members and 1 Guest are viewing this topic.
Aaron

Junior Newbie

Java games rock!

 « Posted 2005-06-04 01:31:12 »

I'm working on a collision method that detects at what time a moving circle makes contact with a line over the interval [0, 1] (it returns 1.0 if there's no collision).  I'm able to determine whether or not the circle is moving toward the line and if the circle's velocity could ever move itself close enough to the line for there to be collision.  However, I can't figure out how to find the distance the circle would have to go to hit the line, which I'd get my time from.

Here's pseudo code for the part of my method that works.  I assume the line is infinite:

*****

double calculateCollisionTime(Line2D line, Circle circle) {

// Get unit vector of line's normal pointing to side of line circle is on,
// as well as shortest distance between line and circle's centre coordinate.

if (circle.velocityMagnitude() < circle_line_distance - circle.radius())
return 1.0;

// Get unit vector of circle's velocity.
// Get dot product of circle's unit velocity vector and line's unit normal vector.
// This corresponds to the angle between the circle's velocity and the line.

if (dotprod <= 0) // Circle parallel to or going away from line.
return 1.0;

// This is the part I'm having trouble with.
// Find distance between circle and line parallel to circle's velocity.  If it's less
// than the circle's velocity, expect a collision.  Divide this distance by the circle's
// velocity to get time.

return time.

}

*****

I have searched on the internet, and the few articles I found didn't help me.  Does anyone here have any suggestions?

Thank you.
c_lilian

Senior Devvie

Projects: 1

Java games will probably rock someday...

 « Reply #1 - Posted 2005-06-04 06:48:30 »

Here is a usefull resource :

http://www.c-program.com/c-g-a-faq1.html

a "simple" method to find the intersection is :
- find the point on the circle closest to the line :
* find the perpendicular projection of the center of the circle on the line
* draw a line from the center to this point
* find the point on this line at radius distance from the center.
- find the intersection of a line going through this point and whith the same direction as the circle speed (line - line intersection : easy)

Hope it helps

Lilian

Aaron

Junior Newbie

Java games rock!

 « Reply #2 - Posted 2005-06-04 14:33:21 »

Thanks for the site, Lilian.

I've been looking at the "distance from a point to a line" part with interest, but what do they mean by "L**2"?  Is that L squared?
 Games published by our own members! Check 'em out!
c_lilian

Senior Devvie

Projects: 1

Java games will probably rock someday...

 « Reply #3 - Posted 2005-06-04 15:41:39 »

Yes

Aaron

Junior Newbie

Java games rock!

 « Reply #4 - Posted 2005-06-04 21:49:40 »

Thanks.

Anyway, that link you gave me helped me optimize some of my code, but I'm still having problems.

What I'm doing now is look for the possible intersection point on the circle's radius, which is where the line normal would cross if reaching for the circle's centre.  I came up with two ways of calculating the distance between the line and this intersection point parallel to the circle's velocity; one from the web site you gave me Lilian and another site at http://www.gamespp.com/algorithms/collisionDetectionTutorial02.html.

First I get the intersection point:
 1  2  3 `// Point of possible intersection on ball.double intsect1X = A.x() + (-Nx * A.radius());double intsect1Y = A.y() + (-Ny * A.radius());`

Getting the distance based on the second site:
 1  2 `double d = (line.getX1() * Nx) + (line.getY1() * Ny);double actDist = d - ((intsect1X * Nx) + (intsect1Y * Ny));`

Getting the distance based on the first site:
 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18 `double intsect2X = A.x() + (-Nx * A.radius()) + A.dx();double intsect2Y = A.y() + (-Ny * A.radius()) + A.dy();// Find distance between intersection point on ball and line parallel to ball velocity.        double denom = ((line.getX2() - line.getX1()) * (intsect2Y -  intsect1Y)) - ((line.getY2() - line.getY1()) * (intsect2X - intsect1X));        if (denom == 0) // Lines are parallel.    return 1.0;        double r2 = (((line.getY1() - intsect1Y) * (intsect2X - intsect1X)) - ((line.getX1() - intsect1X) * (intsect2Y - intsect1Y))) / denom;        // Z is intersection point.double Zx = line.getX1() + (r2 * (line.getX2() - line.getX1())) - intsect1X;double Zy = line.getY1() + (r2 * (line.getY2() - line.getY1())) - intsect1Y;        // Distance ball actually has to move.double actDist = Math.sqrt((Zx * Zx) + (Zy * Zy));`

Both of these are followed by this:
 1  2  3  4 `if (dV <= Math.abs(actDist))    return 1.0;        return Math.abs(actDist) / dV;`

The problem is first of all that it looks like my line is "one-sided," the ball is only blocked from one side.  It can still pass through the other side.  Even on the side where it's blocked, it seems to be still possible for the ball to pass through if I press the forward key long enough (I'm controlling the ball with the keyboard).
Pages: [1]
 ignore  |  Print

You cannot reply to this message, because it is very, very old.

 Add your game by posting it in the WIP section, or publish it in Showcase. The first screenshot will be displayed as a thumbnail.
 rwatson462 (35 views) 2014-12-15 09:26:44 Mr.CodeIt (26 views) 2014-12-14 19:50:38 BurntPizza (59 views) 2014-12-09 22:41:13 BurntPizza (94 views) 2014-12-08 04:46:31 JscottyBieshaar (54 views) 2014-12-05 12:39:02 SHC (70 views) 2014-12-03 16:27:13 CopyableCougar4 (72 views) 2014-11-29 21:32:03 toopeicgaming1999 (132 views) 2014-11-26 15:22:04 toopeicgaming1999 (123 views) 2014-11-26 15:20:36 toopeicgaming1999 (34 views) 2014-11-26 15:20:08
 Rayvolution 37x basil_ 30x LiquidNitrogen 27x HeroesGraveDev 27x kpars 18x BurntPizza 18x kevglass 17x appel 17x Gibbo3771 15x gouessej 14x princec 13x SHC 11x Ecumene 10x Riven 10x KevinWorkman 9x VIrtueeL 9x
 Resources for WIP gamesby kpars2014-12-18 10:26:14Understanding relations between setOrigin, setScale and setPosition in libGdx2014-10-09 22:35:00Definite guide to supporting multiple device resolutions on Android (2014)2014-10-02 22:36:02List of Learning Resources2014-08-16 10:40:00List of Learning Resources2014-08-05 19:33:27Resources for WIP games2014-08-01 16:20:17Resources for WIP games2014-08-01 16:19:50List of Learning Resources2014-07-31 16:29:50
 java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org