多边形到多边形碰撞检测问题

Question

我在实现窄相位碰撞检测时遇到了一些问题。 Broadphase 运行完美。

我有一组多边形，它们的顶点有一个 stl::vector 数组，按顺时针顺序排列。每个周期，我都会检查它们是否发生碰撞。

我从这里借用了以下多边形测试中的点 并使用我的点数据结构更改了它：

int InsidePolygon(std::vector <Point> poly, Point p) {
  int i, j, c = 0;
  int nvert = poly.size();

  for (i = 0, j = nvert-1; i < nvert; j = i++) {

    if ( ((poly[i].y> p.y) != (poly[j].y> p.y)) && (p.x < (poly[j].x-poly[i].x) * (p.y-poly[i].y) / (poly[j].y-poly[i].y) + poly[i].x) )
       c = !c;

  }
  return c;
}

我已扩展它以包含 PolygonPolygon 函数，该函数将 1 个多边形的所有点与另一个多边形进行检查，然后将其反转以进行相反的检查。

int PolygonPolygon(std::vector <Point> polygon1, std::vector <Point> polygon2) {

    for(int i=0; i<polygon1.size();i++) {    
     if(InsidePolygon(polygon2, polygon1[i])) {
         return 1;
     }
    }
    for(int j=0; j<polygon2.size();j++) {       
     if(InsidePolygon(polygon1, polygon2[j])) {
         return 1;
     }
    }

  return 0;

}

奇怪的是，我的 PolygonPolygon 函数总是返回 1。所以我有几个问题：

1. 我是否在某个地方搞砸了逻辑？我应该以不同的方式编写 PolygonPolygon 函数吗？

2. 是否有更好的 Polygon 测试方法，多边形本身不能保证是凸的，这就是为什么我选择多边形中的点方法。我还希望确定最终哪个点发生碰撞，如果我能通过这一点。

3. 我应该在 InsidePolygon 测试中以特定顺序呈现我的点吗？

Answer 1

您可能需要考虑尝试在多边形之间画一条线作为替代碰撞检测方法。

[编辑] 哎呀，我错过了一个事实，即那里也有非凸多边形。也许“确定一个点是否位于多边形的内部”会更好吗？或者您可以先将非凸多边形分解为凸多边形。

此外，StackOverflow 上至少有一个类似的问题。

Answer 2

谢谢你们的帮助！但我已经自己解决了。

将顶点平移到世界空间并旋转它们的重要性不应被忽视，特别是当它们发生碰撞时。