I had to have a look at the collision code since i didn't think the collision polygon was triangulated, and it's not.
the polygon collision code is made up of two parts: a check to see if a point is inside of a polygon and if two line segments overlap. Algo is basically this:
O(1) if A and B in same spacial hash then continue
O(1) if A and B bounding box overlap then continue
O(n) loop over points in A, if any are inside poly B then stop, objects are overlapping
O(m) loop over points in B, if any are inside poly A then stop, objects overlapping
O(n*m) loop over edges in A and edges of B, if any two edges intersect then stop, objects overlap
In general it tries to figure out as soon as possible if the objects overlap or not so it doesn't have to check everything. In front of each line I put the big O notion showing the complexity of each step. It starts with stuff that can be done with one check, then it's proportionate to the number of points, and finally it's proportionate to the number of points multiplied together.
The main complexity that was probably the reasoning of the warning is the edge overlapping check. The max number of checks it can do is the A.pointCount*B.pointCount. So with the standard 8 point polys it's doing a maximum of 64 checks. Two 20 point ones could do a max of 400 checks.
More points would make calculating an object's bounding box take a longer for objects with more points, but it's a linear increase.
And what it's worth the physics object does triangulate the collision poly for it's uses. Actually with box2d it merely converts it into concave polygons.