Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Collision detection of irregular shapes

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.

like image 456
Max Hudson Avatar asked Jul 06 '12 18:07

Max Hudson


People also ask

What are different collision detection techniques?

One of the most primitive ways of doing collision detection is to approximate each object or a part of the object with a sphere, and then check whether spheres intersect each other. This method is widely used even today because it's computationally inexpensive.

What is collision detection used for?

Continuous collision detection techniques attempt to find when two bodies collided between the previous and the current step of the simulation. They compute the time of impact, so we can then go back in time and process the collision at that point.

What is collision detection in data structure?

Collision detection is the computational problem of detecting the intersection of two or more objects.

Is collision detection possible in simulation software?

In simulation initially collision detection and avoidance between two robots are proposed. Later this approach is extended to detect collision between multiple moving robots.


1 Answers

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.

like image 91
Matzi Avatar answered Oct 24 '22 11:10

Matzi