0

我试图找出两个凸多边形是否相交。我读到最有效的方法之一是使用分离轴的方法。我在这本书http://www.geometrictools.com/Documentation/MethodOfSeparatingAxes.pdf中找到了一些代码，但我有点困惑。函数 Dot 有什么作用？

    int WhichSide(PointSet S, Point D, Point P)
    {
// S vertices are projected to the form P+t*D. Return value is +1 if all t > 0,
// -1 if all t < 0, 0 otherwise, in which case the line splits the polygon.
         positive = 0; negative = 0;
         for (i = 0; i < C.N; i++)
         {
             t = Dot(D,S.V(i)-P);
             if(t>0) 
             {
                 positive++;
             } 
                 else if(t<0)
             {
                 negative++;
             }
             if(positive && negative)
             {
                 return 0;
             }
        }
        return (positive ? +1 : -1);
     }
     bool TestIntersection2D (ConvexPolygon C0, ConvexPolygon C1)
     {
// Test edges of C0 for separation. Because of the counterclockwise ordering,
// the projection interval for C0 is [m,0] where m <= 0. Only try to determine
// if C1 is on the ‘positive’ side of the line.
          for (i0 = 0, i1 = C0.N-1; i0 < C0.N; i1 = i0, i0++)
          {
              D = Perp(C0.V(i0) - C0.V(i1));
              if(WhichSide(C1.V,D,C0.V(i0)) > 0)
              { // C1 is entirely on ‘positive’ side of line C0.V(i0)+t*D
                    return false;
              }
          }
// Test edges of C1 for separation. Because of the counterclockwise ordering,
// the projection interval for C1 is [m,0] where m <= 0. Only try to determine
// if C0 is on the ‘positive’ side of the line.
        for (i0 = 0, i1 = C1.N-1; i0 < C1.N; i1 = i0, i0++)
        {
            D = Perp(C1.V(i0) - C1.V(i1));
            if (WhichSide(C0.V,D,C1.V(i0)) > 0)
            { // C0 is entirely on ‘positive’ side of line C1.V(i0)+t*D
                 return false;
            }
         }
         return true;
     }
4

0 回答 0