确定任何2D多边形（包括凸或凹形多边形）是否与AABB边界相交
我正在开发一个2D程序，该程序需要大量判断多边形（用户生成或导入的，可以是凸或凹）与AABBS相交（重叠）。我与KDTREE实施的数据结构部分，我现在需要一种方法来确定多边形是否与AABB框相交。
我已经在网络上看到了许多讨论，但是它们都是关于凸多边形的，而且我还看到了使用多边形的每个行段来确定它是否与AABB相交的方法害怕这种方法太贵了。
1多边形由以逆时针顺序存储的一系列vector2列表定义，AABB框由列表[MINX，MINY，MAXX，MAXY]定义。
2我只关心它们是否相交，我不需要返回重叠的范围或交叉点。
3多边形的任何预处理。
4所使用的语言是C＃，欢迎任何可用的库。
I'm developing a 2D program that requires a lot of judgment on whether a polygon (generated or imported by the user, could be either convex or concave) is intersecting (overlaping) with AABBs. The data structure part I've implemented with kdtree, and I now need a way to determine whether a polygon intersects with an AABB box.
I have seen many discussions on the web, but they are all about convex polygons, and I have also seen methods that use each line segment of a polygon to determine if it intersects with an AABB, but since it is an AABB box, I am afraid this method is too expensive.
1 The polygon is defined by a series of Vector2 list stored in counterclockwise order, AABB Box is defined by List[minx,miny,maxx,maxy].
2 I only care whether they intersect or not, I don't need to return overlaping ranges or intersection points.
3 Any pre-processing of polygons is possible.
4 The language used is C#, and any available libraries are welcome.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
可以将任何多边形转换为三角形，这称为 triangulation 。然后，您可以使用所需的任何三角形/AABB交点算法。
除此之外，您还可以在多边形周围绘制AABB，并首先对另一个AABB进行检查。如果那些不相交，则不必单独检查所有三角形。
此外，您可以使用边界卷层次结构来防止对三角形和AABB进行不必要的碰撞检查。 this 是一个很好的解释和实现，但它是在射线跟踪的背景下。不过，您可以轻松适应它。
It is possible to convert any polygon into triangles, this is called triangulation. Then you can use any triangle/aabb intersection algorithm you want.
In addition to this, you can draw an aabb around the polygon and check that against the other aabb first. If those don't intersect you don't have to check all the triangles separately.
Furthermore, you can use a bounding volume hierarchy to prevent doing unnecessary collision checks of the triangles and aabb. This is a nice explanation and implementation but it's in the context of raytracing. You can easily adapt it for your purposes though.