确定非凸二维图形碰撞的良好算法

Question

您能给我提供一些关于二维非凸图形的良好碰撞检测算法的信息（或推荐一篇文章）吗？

谢谢！

Answer 1

Try this:

http://www.cs.man.ac.uk/~toby/alan/software/

Note that it isn't free for commercial use.

有关更多详细信息，您可以继续这个类似的问题：

多边形相交的简单算法

---

确定两个简单多边形是否相交：

如果两个简单多边形具有非空交集，则将发生以下情况之一：

A) 其中一个多边形在另一个多边形的内部有一个角。
B) 其中一个的整个边缘位于另一个的内部（该边缘的角不一定位于内部）。这意味着该边缘的中间将位于内部。
C) 多边形是相同的。
D) 有两条边以一定角度相交。交点不是任何多边形的角。

您需要做的是检查多边形是否相同（具有相同的角），或者其中一个角或其中一条边的中间位于另一个多边形的内部，或者是否有两条边在其他地方相交比在一个角落里。

确定一个点是否位于多边形的内部。

Answer 2

我总是发现维基百科页面对我的需求非常有用：

Sutherland Hodgman

梁·巴尔斯基

Weiler Atherton

以及 本文介绍 Weiler Atherton 算法。