8.1 The Method of Separating Axes 409
{
return 0;
}
}
return posCount?1:-1;
}
In the worst case, the polygons do intersect. We have processed N
0
edge normals of
C
0
, each requiring N
1
projections for C
1
, and N
1
edge normals of C
1
, each requiring
N
0
projections for C
0
. The total number of projections is 2N
0
N
1
, still a quadratic
quantity but considerably smaller than (N
0
+ N
1
)
2
.
We can do even better in an asymptotic sense as the number of vertices becomes
large, using the extremal query for convex polygons mentioned in Section 8.1.1. For
a polygon of N
0
vertices, the bisection is of order O(log N
0
), so the total algorithm
is O(max{N
0
log N
1
, N
1
log N
0
}). However, in practice the values of N
0
and N
1
are
sufficiently small that the asymptotic performance is not relevant. ...