Processing 1.0 - Processing Discourse - Triangle/Circle collision

We closed this forum 18 June 2010. It has served us well since 2005 as the ALPHA forum did before it from 2002 to 2005. New discussions are ongoing at the new URL http://forum.processing.org. You'll need to sign up and get a new user account. We're sorry about that inconvenience, but we think it's better in the long run. The content on this forum will remain online.

Index › Discussion › Exhibition › Triangle/Circle collision

‹ Previous Topic | Next Topic ›

Pages: 1

Triangle/Circle collision (Read 1728 times)

blindfish

Triangle/Circle collision
Dec 4^th, 2009, 12:06pm

I thought I'd look into slightly more complex collision detection for my asteroids game and came up with a relatively crude method for recording triangle-circle collisions:

http://www.blindfish.co.uk/code/processing/triangle-circle-collision/

It's not perfect and a touch glitchy but it's good enough for my purposes.

The first stage in developing this was understanding point to triangle collision. I found lots of references to dot-products, and other mathematical jargon I was feeling too impatient to get my head round; so was happy when I came across this post which I could understand with no effort. Here it is running in Processing:

http://www.blindfish.co.uk/code/processing/triangle-point-collision/

Part of the reason I post thi sort of stuff is to find out if I'm doing things 'the right way', so any feedback is appreciated

Where is the what if the what is in why?

Quark

Re: Triangle/Circle collision
Reply #1 - Dec 5^th, 2009, 4:45am

Nice demonstration.

Since you are using floats to store the coordinates there is a danger in the line
Code:

  return (totalArea == tArea);

because there is a limit to the precision a float can be stored it is possible for this to return false because of small differences between totalArea and tArea for instance I used the following code to generate the triangle.
Code:

  t = new Triangle(width/2.01,height/4.023,width-width/4.001,height-height/4.00998, width/4.12,height-height/4.055);

If you try this you will see what I mean. The value of (totalArea - tArea) was not always zero even inside the triangle.
Change the return to
Code:

return (abs(totalArea - tArea) < 0.001);

seems to fix it since the difference appeard to be 9.7x10^-4 although you will probably want to do your own experiments with this.

blindfish

Re: Triangle/Circle collision
Reply #2 - Dec 5^th, 2009, 5:02am

I noticed that you could move the circle to certain specific positions within the triangle and it wouldn't register a hit; and had assumed this was due to floating point imprecision. Your workaround seems like the logical solution. Mind you - I've noticed that with high speed motion the circle 'target point' doesn't necessarily keep up with the location of the triangle. In that case the checks against the triangle corner points should hopefully do the trick; though it may also be worth checking against the centre point; or alternatively using another more robust solution...

Where is the what if the what is in why?

Quark

Re: Triangle/Circle collision
Reply #3 - Dec 5^th, 2009, 6:30am

If the triangle and /or or circle are moving rapidly then the order you do the calculations becomes important so in this case it would be

calculate new triangle position
calculate new circle position
calculate circle point
calculate triangle - circle intersection
draw

The 'area' algorithm for identifying whether a point is within the triangle seems to be very accurate apart from floating point precision problems. The crux is the calculation of the circle point nearest the triangle because it depends knowing the centre coordinates of the triangle which depends on the triangles shape.

So for an equilateral triangle the approach used in the second demo is good.

A more generic approach would be to check for the intersection of each triangle side with the circle i.e. a line and a circle, I think you might have already mentioned that. Undecided

Quark

Re: Triangle/Circle collision
Reply #4 - Dec 5^th, 2009, 8:14am

Found a very old geometry book that had an algorithm for a line circle intersection, try the code below, the circle will be centred over the mouse position.

Code:

float x1,y1,x2,y2,cx,cy,r;
boolean intersect;

void setup(){
  size(200,300);
  cx = width/2;
  cy = height/2;
  r = 20;
  x1 = 50;
  y1 = 50;
  x2 = width - 60;
  y2 = height - 60;
  intersect = false;
}

void draw(){
  background(255);
  ellipseMode(CENTER);
  strokeWeight(1);
  stroke(0,255,0);
  fill(255,240,240);
  if(intersect)
    stroke(255,0,0);
  ellipse(cx,cy,2*r,2*r);
  line(x1,y1,x2,y2);
  cx = mouseX;
  cy = mouseY;
  intersect = line2Circle(x1,y1,x2,y2,cx,cy,r);
}

boolean line2Circle(float x0, float y0, float x1, float y1, float cx, float cy, float r){
  float fxgy,t;
  float f = (x1 - x0);
  float g = (y1 - y0);
  float f2 = f*f;
  float g2 = g*g;
  float fg2 = f2 + g2;
  float r2 = r*r;

  float xc0 = cx - x0;
  float yc0 = cy - y0;
  float xj1 = cx - x1;
  float yj1 = cy - y1;

  float fygx = f*yc0 - g*xc0;
  float root = r*r*fg2 - fygx*fygx;

  if(root >= 0){
    fxgy = f*xc0 + g*yc0;
    t = fxgy / fg2;
    return ((t >= 0 && t <= 1) || (xc0*xc0 + yc0*yc0 < r2) || (xj1*xj1 + yj1*yj1 < r2) );
  }
  return false;
}

Of course you would repeat for each side of the triangle stopping if the function returns true. If all sides return false there is no intersection or the circle is inside the triangle!
Cheesy

Pages: 1

‹ Previous Topic | Next Topic ›