Re: [Boost-users] [Polygon] Test among 3 libraries

Subject: Re: [Boost-users] [Polygon] Test among 3 libraries
From: Angus Johnson (angus_at_[hidden])
Date: 2010-09-09 16:58:51

> 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;
}