检测矩形和多边形之间的交点的方法？
检测红色矩形是否与黑色多边形重叠的最佳方法是什么？请参考此图片：
What is the best method to detect whether the red rectangle overlaps the black polygon? Please refer to this image:
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
有四种情况。
首先：对照多边形检查矩形中的任意点（请参阅多边形中的点）。如果它在内部，那么就完成了，因为它要么是情况 3，要么是情况 2。
如果在外部，则排除情况 3。
第二：检查多边形与矩形的任意点以验证/排除情况 4。
第三：检查矩形与多边形的线是否相交，以验证/排除情况 2。
这也适用于多边形与多边形（凸面和凹面）但这样更易读。
There are four cases.
First: check an arbitrary point in your Rect against the Poly (see Point in Polygon). If it's inside you are done, because it's either case 3 or 2.
If it's outside case 3 is ruled out.
Second: check an arbitrary point of your Poly against the Rect to validate/rule out case 4.
Third: check the lines of your Rect against the Poly for intersection to validate/rule out case 2.
This should also work for Polygon vs. Polygon (convex and concave) but this way it's more readable.
如果您的多边形不是凸的，您可以使用 曲面细分 将其细分为凸子部分。由于您正在寻找检测可能发生碰撞的方法，我认为您可以看看 GJK 算法 也是如此。即使您不需要那么强大的东西（它提供有关两个凸形状和相关见证点之间的最小距离的信息），如果您决定处理更多不同的凸形状，它也可能会很有用。
如果您想了解有关此算法的更多信息，Christer Ericson 制作了一个精彩的 Powerpoint 演示。您还可以看一下他的书《实时碰撞检测》，该书既完整又适合发现碰撞检测算法的任何人。
If your polygon is not convex, you can use tessellation to subdivide it into convex subparts. Since you are looking for methods to detect a possible collision, I think you could have a look at the GJK algorithm too. Even if you do not need something that powerful (it provides information on the minimum distance between two convex shapes and the associated witness points), it could prove to be useful if you decide to handle more different convex shapes.
Christer Ericson made a nice Powerpoint presentation if you want to know more about this algorithm. You could also take a look at his book, Real-Time Collision Detection, which is both complete and accessible for anyone discovering collision detection algorithms.
如果您知道红色矩形始终是轴对齐的，并且黑色区域由几个轴对齐的矩形组成（我不确定这是否只是巧合，或者是否是问题所固有的），那么您可以使用矩形对矩形交集算法来非常有效地计算是否两个形状重叠，如果重叠，则重叠的位置。
If you know for a fact that the red rectangle is always axis-aligned and that the black region consists of several axis-aligned rectangles (I'm not sure if this is just a coincidence or if it's inherent to the problem), then you can use the rectangle-on-rectangle intersection algorithm to very efficiently compute whether the two shapes overlap and, if so, where they overlap.
如果您使用轴对齐的矩形并且多边形仅由矩形组成，则 templatetypedef 的答案就是您所需要的。
如果您使用任意多边形，这是一个更加复杂的问题。
首先，您需要将多边形细分为凸部分，然后使用例如SAT 算法
If you use axis-aligned rectangles and polygons consist of rectangles only, templatetypedef's answer is what you need.
If you use arbitrary polygons, it's a much more complex problem.
First, you need to subdivide polygons into convex parts, then perform collision detection using, for example, the SAT algorithm
简单地查找是否存在交集，我认为您也许可以结合两种算法。
1）光线投射算法。使用每个多边形的顶点，确定其中一个顶点是否在另一个顶点中。假设您不担心实际的交叉区域，而只是担心它的存在。 http://en.wikipedia.org/wiki/Point_in_polygon
2) 线相交。如果步骤 1 没有产生任何结果，请检查线相交。
我不确定这是否 100% 正确或最优。
如果您实际上需要确定相交区域，那就更复杂了，请参阅之前的答案：
一种简单的多边形相交算法
Simply to find whether there is an intersection, I think you may be able to combine two algorithms.
1) The ray casting algorithm. Using the vertices of each polygon, determine if one of the vertices is in the other. Assuming you aren't worried about the actual intersection region, but just the existence of it. http://en.wikipedia.org/wiki/Point_in_polygon
2) Line intersection. If step 1 produces nothing, check line intersection.
I'm not certain this is 100% correct or optimal.
If you actually need to determine the region of the intersection, that is more complex, see previous SO answer:
A simple algorithm for polygon intersection