Anyhow, reworking the data with the correct number of edges, the equation for this (near worst case) test polygon returns an equation of y = 1E-08x^1.4821 . If I generate the squiggly lines vertically in my test polygon (and destress the vatti algorithm) which is likely to be closer to normal use, I suspect this equation will drop further.
OK, when I rotated the test polygon 90 deg the trendline equation becomes : y = 2E-07x^1.0841 I would suggest that in normal use, my clipping library would perform somewhere between O(n^1.0841) and O(n^1.4821) though I suspect nearer to the lower value. Here's the function that produces my test polygons (generating what I believe would be near worst case vertices for the Vatti algorithm): //struct TDoublePoint { double X; double Y; }; //typedef std::vector< TDoublePoint > TPolygon; TPolygon MakeTestPoly(int startX, int startY, int boxSize){ int k,x,y; TPolygon result; result.resize(boxSize * boxSize +2); x = startX+4; y = startY; k = 0; for (int i = 1; i <= boxSize; ++i) { for (int j = 1; j <= boxSize; ++j) { x = x +(i % 2)*4 -2; y = y + (j % 2)*2 -1; result[k].X = x; result[k].Y = y; k++; } y = y + 4; x = x +(i % 2)*4 -2; } result[k].X = startX; result[k].Y = y -4; result[k+1].X = startX; result[k+1].Y = startY; return result; }