Good algorithm for determination of non convex 2D figures collision

Question

could you please provide me with some information (or suggest an article) on good collision detection algorithm for 2D non convex figures?

Thanks!

Answer 1

Try this:
http://www.cs.man.ac.uk/~toby/alan/software/
Note that it isn't free for commercial use.

For more details you can continue to this similar question:

A simple algorithm for polygon intersection

---

To determine if two simple polygons intersect :

If two simple polygons have a non-void intersection then one of the following will happen:

A) One of them has a corner inside the interior of the other one.
B) One of them has a whole edge inside the interior of the other one (the corners of that edge may not necessarily be in the interior). This means the middle of that edge will be inside the interior.
C) The polygons are identical.
D) There are two edges that intersect at an angle. The intersection point not being a corner to any of the polygons.

What you need to do is check if the polygons are identical (have the same corners), or one of the corners or one of the middle of the edges lies inside the interior of the other polygon or if there are two edges that intersect somewhere else than in a corner.

Determining if a point lies on the interior of a polygon.

Answer 2

I always found the wikipedia pages to be quite useful for my needs:

Sutherland Hodgman

Liang Barsky

Weiler Atherton

As well as this paper on the Weiler Atherton algorithm.