10

I know how to check if a circle is about to collide with a square, and I know how to detect if a square is about to collide with a square, but how would I go about detecting if a polygon is about to collide with a square?

Or better yet, when a polygon is about to collide with a polygon.

OR better yet, when a shape made up of lines that are not straight collides with another similar shape, a polygon, or a circle/rectangle

Is there any way to get the pixels a shape would take up maybe and the pixels another shape would take up and check if any of them are the same?

I am hoping there is some solution that doesn't require a ton of shape specific calculation.

I am using javascript and html5 canvas to do this.

Max Hudson
  • 9,961
  • 14
  • 57
  • 107
  • possible duplicate of [Javascript: Collision detection](http://stackoverflow.com/questions/2440377/javascript-collision-detection) – jbabey Jul 06 '12 at 19:02
  • 3
    @jbabey, I'm not sure this is aduplicate of that question -- here, the OP specifies a polygon-to-polygon requirement, whereas the proposed duplicate seems (implicitly) concerned with only rectangular collisions. I admit it is difficult to judge, though, since the linked question omits the scope of shapes used; I assume they are strictly rectangular because the asker there mentions `div`s in particular. – apsillers Jul 06 '12 at 19:12

2 Answers2

3

This is not a simple stuff. If you are satisfied that a function can tell if two polygons are colliding (and you can roll back them), then the solution is not so hard. You just need to check if any two of the polygon's sides are crossing each other or not. This can be done by some math, and with big shapes or lot polygons it can eat away the performance. To solve this, you may use space partitioning and bounding volumes.

UPDATE: You can calculate the intersection of lines based on this. Then you need to check if this point is in both segment or not. To do this, you can use the endpoints of the segments, and the ua and ub variables will be between 0-1 if the segment actually contains the point.

Theraot
  • 31,890
  • 5
  • 57
  • 86
Matzi
  • 13,770
  • 4
  • 33
  • 50
  • 4
    thank you but what kind of math? that doesn't really help me as there's no way you could 'do it without some math' – Max Hudson Jul 06 '12 at 19:08
  • included some clue to start, is this enough? – Matzi Jul 06 '12 at 19:14
  • i like it, ill give it an upvote, but it doesn't quite solve my issue. I need to check not only if a line is intersecting, but if an object is already inside the object and needs to be moved out of it. – Max Hudson Jul 06 '12 at 19:15
  • 1
    I also need this to work with shapes that don't have straight 'lines' as sides/borders. – Max Hudson Jul 06 '12 at 19:17
  • 1
    curved arbitrary polygons too? Theres weighty PHD papers written about this topic, its very complex. You might like to look at http://gamma.cs.unc.edu/research/collision/ - but also depending on what its for, you might want to start considering some approximations such the bounding box idea already mentioned, or maybe you could try to triangulate the polygons and do it that way using basic geometry – carpii Jul 07 '12 at 23:34
0

The simplest is to use a bounding box, just find the mins and maxs of the object and make a box from that. To do polygon to polygon you need a way to store the edges of the polygon and another method to determine which points or edges have collided with another object. From here you can then determine how to react to the collision.

Bounding boxes are simple to implement, but not very accurate. Using the actual edges of the polygon itself is more accurate but more difficult to handle and is much slower.

sean
  • 3,955
  • 21
  • 28
  • 2
    bounding boxes are an obvious and extremely inaccurate solution unless you have a polygon very close to a rectangle. in any case a polygon with a standard shape (ie hexagon, pentagon) will be much closer to a circle than a box... – Max Hudson Jul 06 '12 at 19:12
  • Agreed, in that case the you can decide before runtime what to do or do a per edge collision model, or use a circle or ellipse as the bounding volume. – sean Jul 06 '12 at 19:13