Java-Gaming.org Hi !
 Featured games (84) games approved by the League of Dukes Games in Showcase (593) Games in Android Showcase (168) games submitted by our members Games in WIP (646) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1]
 ignore  |  Print
 Collision between circle and line  (Read 3302 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?
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.

 Riven (12 views) 2015-07-03 11:22:16 deepthought (41 views) 2015-06-30 15:39:44 deepthought (45 views) 2015-06-30 15:39:09 deepthought (55 views) 2015-06-30 15:36:52 Za\'Anzabar (24 views) 2015-06-29 05:44:54 TritonDreyja (41 views) 2015-06-24 17:10:40 CopyableCougar4 (40 views) 2015-06-23 00:34:45 BurntPizza (44 views) 2015-06-21 20:36:46 cookiecompiler (86 views) 2015-06-11 15:42:53 cookiecompiler (49 views) 2015-06-11 15:41:14
 princec 34x wessles 24x BurntPizza 19x opiop65 18x CopyableCougar4 18x theagentd 15x Riven 15x nsigma 15x KaiHH 14x EgonOlsen 14x SauronWatchesYou 11x KevinWorkman 11x sunburn 11x Archive 10x NegativeZero 10x ags1 10x
 How Do I Expand My Game?by bashfrog2015-06-14 11:34:43List of Learning Resources2015-05-31 05:37:30Intersection Methodsby Roquen2015-05-29 08:19:33List of Learning Resources2015-05-05 10:20:32How to: JGO Wikiby Mac702015-02-17 20:56:162D Dynamic Lighting2015-01-01 20:25:42How do I start Java Game Development?by gouessej2014-12-27 19:41:21Resources for WIP gamesby kpars2014-12-18 10:26:14
 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