Description Colin Sharples 2016-06-15 17:05:16 EDT

Created attachment 262475 [details]
Demonstrates slow performance of Ring

The performance of constructing a Ring from a number of Polygons is very slow. The time taken also seems to grow exponentially with the number of polygons being added, rather than linearly.

I attach an example of constructing a "fat" outline from a PolyBezier by two different methods. Both work on an approximation of the PolyBezier as a Polyline, so the construction of the Polyline is excluded from the timing.

The first method just works out the points on either side of each of the intermediate points of the line, and then just draws a Polyline outline through each of those points, going up one side of the line and back down the other. This handles the general outline reasonable well, although on the inner side of a curve it leads to some overlap because it doesn't account for the intersections between adjacent parts of the curve.

The second method creates a more accurate outline by turning each section of the Polyline into a Polygon of the appropriate width, and constructing a Ring from those Polygons. It additionally creates wedge shaped Polygons to fill in the gap between two adjacent sections on a curve. This gives a much more accurate outline than the first method.

In my performance test, I use two PolyBeziers of 16 and 32 segments. I run each test 5 times to allow for compiler optimization etc. Discarding the first iteration, I got average times of 0.2324ms and 3,998.3827ms for the two methods using the 16-segment line. For the 32-segment line, the average times were 0.4806ms and 60,923.5286ms. Not only is the Ring method slower by several orders of magnitude, but it appears to scale exponentially rather than linearly - it increase by a factor of 15 for double the segments, whereas the first method doubled in time, as expected.