有给两个多边形。一个人如何能够确定一个多边形是否为内部，外部或相交的其它多边形？ 多边形可以是凹或凸的。

There are two polygons given. how can one determine whether one polygon is inside, outside or intersecting the other polygon? Polygons can be Concave or convex.

推荐答案

您要使用的分离轴定理凸多边形。 基本上，每个多边形的每个面你的项目每个多边形到正常的脸，你看看这些预测相交。

You want to use the separating axis theorem for convex polygons. Basically, for each face of each polygon you project each polygon onto the normal of that face and you see if those projections intersect.

您可以执行各种招数，以减少这些计算，你必须perform-例如数量，可以得出对象周围的矩形，并假设如果两个对象的矩形不相交，他们自己不相交。 （这是更容易，因为它较少计算昂贵的检查这些框的交点，且通常很直观。）

You can perform various tricks to reduce the number of these computations that you have to perform- for example, you can draw a rectangle around the object and assume that if two objects' rectangles do not intersect, they themselves do not intersect. (This is easier because it's less computationally expensive to check the intersection of these boxes, and is generally quite intuitive.)

凹多边形都比较困难。我认为你可以分解多边形为一组凸多边形，并尝试检查路口的每个组合，但我不认为自己在这方面的足够的技术来试试吧。

Concave polygons are more difficult. I think that you could decompose the polygon into a set of convex polygons and attempt to check each combination of intersection, but I wouldn't consider myself skilled enough in this area to try it.

请参阅： http://www.wildbunny.co。英国/博客/ 2011/04/20 /冲突检测换假人/