jeffthompson / collisiondetection Goto Github PK

I see many function for circle collision, but do not see any for ellipse.
Here is my version for Point / Ellipse:

function pointEllipse(px, py, cx, cy, r1, r2){
    var dx = px-cx;
    var dy = py-cy;
    return ((dx*dx)/(r1*r1)+(dy*dy)/(r2*r2)<=1);
}

Re: https://github.com/jeffThompson/CollisionDetection/blob/master/CodeExamples/PointPoint/PointPoint.pde#L47

    if (x1 == x2 && y1 == y2) {
        return true;
    }
    return false;

Another sentence could introduce a further simplification:

  return x1 == x2 && y1 == y2;

Even though the book is for beginners, it's useful to teach slightly more advanced techniques that reduce the amount of code a person must read. Having a single exit point is still a good practice.

Why do this?
float len = sqrt( (distXdistX) + (distYdistY) );
And after this
float dot = ( ((cx-x1)(x2-x1)) + ((cy-y1)(y2-y1)) ) / pow(len,2);

You have scalar aa
float len2 = (distXdistX) + (distYdistY);
And
float dot = ( ((cx-x1)(x2-x1)) + ((cy-y1)(y2-y1)) ) / len2;

But what is that ? I am understand projection vector in other vector ab/|b|. But what is : ab/|b|*|b|?

On the page tri-point.php

1. "Heron’s Forumula:"
   ^ Formula is misspelt.

2. Also a visual check of the formula suggests this is actually the Shoelace formula not Heron's formula.

3. Adding up the area is a clever mathematical approach but it suffers from machine arithmetic issues, especially with long skinny triangles. It would be useful to discuss this limitation and how a small delta can be used to address this limitation..

Note the bit of shorthand above: we could specify else { return true; }

Shouldn't be else { return false; }?

So the website actually looks great so far, however, I noticed that the main screen is a little laggy. When you have all the different shapes falling and colliding with the ellipse, sometimes the ellipse freezes for a fraction of a second. Perhaps less objects?

The code here to tests for polygon on polygon collision takes into account that second polygon can be fully inside first polygon. It checks if a point of poly2 is inside poly1. the issue is that it doesn't check if first polygon is inside second.

// POLYGON/POLYGON
boolean polyPoly(PVector[] p1, PVector[] p2) {

  // go through each of the vertices, plus the next
  // vertex in the list
  int next = 0;
  for (int current=0; current<p1.length; current++) {

    // get next vertex in list
    // if we've hit the end, wrap around to 0
    next = current+1;
    if (next == p1.length) next = 0;

    // get the PVectors at our current position
    // this makes our if statement a little cleaner
    PVector vc = p1[current];    // c for "current"
    PVector vn = p1[next];       // n for "next"

    // now we can use these two points (a line) to compare
    // to the other polygon's vertices using polyLine()
    boolean collision = polyLine(p2, vc.x,vc.y,vn.x,vn.y);
    if (collision) return true;

    // optional: check if the 2nd polygon is INSIDE the first
    collision = polyPoint(p1, p2[0].x, p2[0].y);
    if (collision) return true;
  }

  return false;
}

Now some code I wrote in Typescript that allows to test for both cases since you only need to check one vertex of each polygon inside the other one:

public collidesWithPolygon(polygon : PolygonCollider) {
    if (this.collidesWithPoint(polygon.vertices[0]) || polygon.collidesWithPoint(this.vertices[0])) {
      return true;
    }
    for (const s1 of this.edges) {
      for (const s2 of polygon.edges) {
        if (this.segmentsIntersect2(s1, s2)) {
          return true;
        }
      }
    }
    return false;
  }

I noticed that the collision is not detected between two parallel lines

Not using Processing, but task 2 in the Section 2 challenges sounds like a copy paste error:

"As noted, these examples assume the default rectMode(CENTER). Can you make new versions to work with rectMode(CENTER) instead?"

Pretty sure you wanted to name another rectMode there.

Hello ! How can i found position of collision when is it true ?

also i need normal direction .

Hi,

Line 77 is currently:
if ( ((vc.y > py && vn.y < py) || (vc.y < py && vn.y > py)) &&

Would this:
if (((vc.y >= py && vn.y < py) || (vc.y < py && vn.y >= py)) &&
be better?

for example a line completely inside a polygon will yeld no collision.

I haven't really looked into the details, but playing around with the online version, sometimes when the small polygon is fully inside the larger one, a collision is not detected.

Also, maybe related, you run the following code inside the for-loop, which doesn't make much sense, since it doesn't depend on any of the looped vars, only function parameters:

    // optional: check if the 2nd polygon is INSIDE the first
    collision = polyPoint(p1, p2[0].x, p2[0].y);
    if (collision) return true;

(maybe you wanted to iterate over the vertices of p2?)

The polygon rectangle collision page and the code that goes with it misses out on checking whether a rectangle completely engulfs a polygon.

You could do Rectangle Point for all the points of the polygon, but I think it's worth writing this as a possibility just as polygon point is written as a possibility.

Hi,
first: I really like your project and enjoyed reading it and please excuse my englisch I'm no native english speaker.

I got very enthusiastic about trying out your code and analyze your explanations. And found one slight mistakes and want to give you a hint for the Point / Polygon code:

http://www.jeffreythompson.org/collision-detection/line-circle.php

Then, we get a value we’re calling dot. If you’ve done vector math before, this is the same as doing the dot product of two vectors. If this isn’t familiar, no worry! Consider this step a lot of math you can be glad not to have to solve by hand:

Actually it isn't the dot product. It is a scalar projection (or scalar component) of the vector P1->CircleCenter onto the vector P1->P2.
If you want to explain this further :

The dot product of two vectors a and b equals the magnitude of both times the cosine of the angle between them.

You can also find further information here (or link it on your website :) : https://en.wikipedia.org/wiki/Dot_product#Scalar_projection_and_first_properties

For my own project I thought a long time about the shorthand algorithm behind the vertices line segment intersection (http://www.jeffreythompson.org/collision-detection/poly-point.php)

px < (vn.x-vc.x) * (py-vc.y) / (vn.y-vc.y) + vc.x

The Basic Jordan Curve Theorem is working as follows:
You choose a point out of the polygon and send a ray in an arbitrary direction. In your code its the direction of the x-axis (This is given by your first boolean check which you explained very well on your website). Then you test how many intersections with the edges (line segments) of the polygon you have. Therefor you need the current and next Vertex to build a line segment.

I found a decent explanation for the second boolean test after some try and failure:

The magic happens in finding an equation for the line segment and a bit of sorting for better readability.

Everyone knows the equation for the y value of a line segment from school:

A line segment's x value is given with the equation:

with k as the slope of the segment:

Therefore you get the following equation:

The given Y you want the X value for is the point's y coordinate.
In your code m is vc.y therefore the line segments intersects the y axis at the y value of vc which looks something like:

now you have the equation px < (vn.x-vc.x) * (py-vc.y) / (vn.y-vc.y) and the visualization for the line segment of the Polygon (blue) and the equation (green).

The last thing missing is the back transformation to the real coordinates. This happens with adding vc.x.

When your computed x coordinate is smaller than your point's x ...
...then the Point is not "intersecting" (okay a point can't actually intersect but i hope you know what i want to say)
When your computed x coordinate is bigger than your point's x ...
... you can assume an intersection of the Point.

This is names semi-infinite Ray-casting... because as long as your polygon is "existing" the ray extends, but it stops when the polygon does.

This got longer than i expected, but i hope it helps as you mentioned on your website:

(If you understand how this algorithm works, please do let me know!)

There are plenty of places where distances are compared, and both are first calculated using sqrt calculations, which are notoriously slow. Comparing the distances before the square root calculation will still yield accurate results when comparing length.

Not sure if that on purpose or not.

Simply adding a pointRect fixes the issue.

Your code is simple and well explained. I WOULD NOT REPLACE IT. I'm wondering if you wish to add an appendix on simple optimization. I would start the chapter with Donald Knuth's quote about premature optimization being the root of all programming evil.

Optimization could mean removing unnecessary code. A good example is you omitted an "else" in your code. You could show eliminating the "if" too.

Optimization could mean faster execution time. Since a prime target for collision detection is games where speed is king, every msec counts. Detecting collisions between 1,000 particles is a killer. It's reason my google foo lead me to you.

No one should ever optimize
A. without running tests before and after
B. without timing before and after
C. more than one change at a time

FWIW, I expect some of the optimizations below to be the same speed, and at least one to be slower.

Original Function

boolean circleCircle(float c1x, float c1y, float c1r, float c2x, float c2y, float c2r) {

  // get distance between the circle's centers
  // use the Pythagorean Theorem to compute the distance
  float distX = c1x - c2x;
  float distY = c1y - c2y;
  float distance = sqrt( (distX*distX) + (distY*distY) );

  // if the distance is less than the sum of the circle's
  // radii, the circles are touching!
  if (distance <= c1r+c2r) {
    return true;
  }
  return false; // no need for an else
}

Proposed Refactoring 1

boolean circleCircle(float c1x, float c1y, float c1r, float c2x, float c2y, float c2r) {

  float distX = c1x - c2x;
  float distY = c1y - c2y;
  float distance = sqrt( (distX*distX) + (distY*distY) );

  // the condition is exactly the boolean we want to return
  return distance <= c1r+c2r;

// DOES IT GIVE THE SAME RESULTS?
// IS IT THE SAME OR FASTER?
}

Proposed Refactoring 2

boolean circleCircle(float c1x, float c1y, float c1r, float c2x, float c2y, float c2r) {

  float distX = c1x - c2x;
  float distY = c1y - c2y;
  // no need for variable to hold distance

  return sqrt( (distX*distX) + (distY*distY) ) <= c1r+c2r;

// DOES IT GIVE THE SAME RESULTS?
// IS IT THE SAME OR FASTER?
}

Proposed Refactoring 3

boolean circleCircle(float c1x, float c1y, float c1r, float c2x, float c2y, float c2r) {

  float distX = c1x - c2x;
  float distY = c1y - c2y;
  // let's trade the expensive sqrt for a square

  return  (distX*distX) + (distY*distY) ) <= (c1r+c2r) * (c1r+c2r);

// DOES IT GIVE THE SAME RESULTS?
// IS IT THE SAME OR FASTER?
}

Proposed Refactoring 4a

boolean circleCircle(float c1x, float c1y, float c1r, float c2x, float c2y, float c2r) {

  return  (c1x-c2x * c1x-c2x) + (c1y-c2y * c1y-c2y) ) <= (c1r+c2r) * (c1r+c2r);
// good idea, but there's a bug. Can you spot it and fix it?

// DOES IT GIVE THE SAME RESULTS?
// IS IT THE SAME OR FASTER?
}

Proposed Refactoring 4b

boolean circleCircle(float c1x, float c1y, float c1r, float c2x, float c2y, float c2r) {
  // can we make the squaring easier?
  return  Math.pow(c1x-c2x, 2) + Math.pow(c1y-c2y, 2 ) <= Math.pow(c1r+c2r, 2);
// good idea, but there's a bug. Can you spot it and fix it?

// DOES IT GIVE THE SAME RESULTS?
// IS IT THE SAME OR FASTER?
}

The LINE/RECTANGLE article has an incorrect title. It's really about the collision of a rectangle and line segment. Please update the article accordingly. It's really annoying to scour the internet for how to determine the intersection between a line and a rectangle and discover articles with this kind of title but which are really about the collision between a line segment and rectangle.

I was working on code in p5.JS to identify intersections between objects. I came across your most excellent CollisionDetection examples. Subsequently using that as a template, I have written javascript code to return one or more points of intersection between objects and to draw regular polygons using only an x, y origin location, a radius and number of vertices.

It has been a quite awhile since you developed CollisionDetection, but if you would be interested in what I came up with I am happy to give it to you.

You don't need to use sqrt here. Sqrt is expensive.

// POINT/CIRCLE
boolean pointCircle(float px, float py, float cx, float cy, float r) {

  // get distance between the point and circle's center
  // using the Pythagorean Theorem
  float distX = px - cx;
  float distY = py - cy;
  float distance = sqrt( (distX*distX) + (distY*distY) );

  // if the distance is less than the circle's
  // radius the point is inside!
  if (distance <= r) {
    return true;
  }
  return false;
}

You can just compare the squares easier and faster:
return distX*distX + distY*distY <= r*r;

(Thanks for the book!)

The circle can enter halfway into the polygon undetected if you start from the very tip of the vertexes.
Sorry i do not know mathematics well enough to phrase it more exact, although it is very easy to find if you play with it a little.

I have 1000 shapes for which I need to collision check against each other. Big O is killing me. In spite of my previous issue I submitted on optimization, that sort of optimization is minor at best when my bottle neck is n^2 checks. A good way to think about it is "What's better than a very fast collision detection between two circles?" Avoid checking two circles whenever possible.

Again, I WOULD NOT CHANGE ANYTHING in the current book. It's perfect. You may wish to add an appendix on an efficient collection that doesn't need n^2 checks. A quadtree is the only one I know about. I'm sure there are more options.

Hello! For my class (which I teach in Javascript) I converted all of the examples to Javascript. To do so, I also made some major changes to the way things are compiled and organized.

If there is a way to reconcile these code bases, I'd be happy to help but in the meantime, I just wanted to make you aware of this fork: https://github.com/crhallberg/CollisionDetection.

Website: https://crhallberg.com/CollisionDetection/Website/

The code in the documentation page are not exactly the same as in the PolyPoint.pde file.
If you look at
http://www.jeffreythompson.org/collision-detection/poly-point.php
the collision formula should read :

if ( ((vc.y >= py && vn.y < py) || (vc.y <= py && vn.y > py)) &&
         (px < (vn.x-vc.x) * (py-vc.y) / (vn.y-vc.y) + vc.x) ) {
            collision = !collision;
    }

Note the >= and <= operators in first and second conditions, which are necessary to avoid a gap in the detection zone.

I noticed a small error on your website, it reads like this:

Finally, using floats makes it much easier to transition from separate X/Y positions to using using the PVector class,

It should be:

Finally, using floats makes it much easier to transition from separate X/Y positions to using the PVector class

BTW love your book and your examples on p5js!

Collision of rounded rectangle and circle ，
Excuse me, is there a solution ？

There is no problem with the collision detection test! It works! But there is not a collision detection response! I want that when the circle touches the square, and the circle must stay outside of the rectangle! Image =>

Hi,

Thanks for your work on collision detection, it's really helpful and easy to read.
I've noticed a small error in the Section 6 full code : the circle is first declared as "c", but called as "circle" next...

You should return false if the denominators are zero.

btw You can optimize this function by a lot. Denominators for uA and uB are exactly the same so you should compute the denominator once and save it to a variable. Then you can reuse the variable for both uA and uB.
Also certain subtractions is you algorithm are done twice.
This is my C++ version:

fn Intersect
(line Line1, line Line2)
{
    v2 A = Line1.Start;
    v2 B = Line1.End;
    v2 C = Line2.Start;
    v2 D = Line2.End;
    
    v2 BA = B - A;
    v2 DC = D - C;
    v2 AC = A - C;
    
    f32 Denominator = DC.Y*BA.X - DC.X*BA.Y;
    if(Denominator == 0)
        return false;
    
    f32 U1 = (DC.X*AC.Y - DC.Y*AC.X) / Denominator; 
    f32 U2 = (BA.X*AC.Y - BA.Y*AC.X) / Denominator;
    
    return U1 >= 0 && U1 <= 1 && U2 >= 0 && U2 <= 1;
}