On Wed, 2009-02-25 at 01:17 +0000, Peter Clifton wrote: [snip] > As it currently stands though, I can't merge the sped-up polygon > routines anyway, as they actually impact negatively on the dicer > performance. (Even with the GL GUI, the dicer is used for PNG, PS and > gerber export etc..) > > I had a lead on what I thought to be a possible reason for the slowness > (aside from the obvious extra work of keeping an r-tree of contours for > each POLYAREA), however my attempt to fix it resulted in further > slowdown! > > The r-tree search for intersecting contours between a given polygon and > the clipping polygon (used in each dicing step to split a polygon about > the centre of some hole), must fire for every contour in the polygon > which is enclosed in, or intersects the large clipping polygon. > > Most of those returns from r_search are not actually going to be > intersections, and we do work for no reason checking in more detail. The > obvious attempt to fix this looks out for the single contour, four sided > cliping polygon, and if it finds that case, it searches for > intersections of the main polygon contours and the boxes bounding each > individual edge on the clipping polygon. > > IE.. test for |, _, - and | boxes separately, rather than a larger area > box. |_|
Grr.. of course, as soon as the intersection routine adds the first point, the polygon we're clipping with isn't a quad any more. The code still treats it as if it is though, as the contour segment count doesn't appear to be updated when the new point is inserted. I don't think that really breaks anything, but it does mean my simple idea that "its only four sides to test, so will be quick" isn't true once it has found some intersections. Still.. I can't quite see why it is slower than the case I had before, where I "think" I would have been getting a whole load of false-positives. -> Sleep.. working on-site with the wave machine tomorrow ;) -- Peter Clifton Electrical Engineering Division, Engineering Department, University of Cambridge, 9, JJ Thomson Avenue, Cambridge CB3 0FA Tel: +44 (0)7729 980173 - (No signal in the lab!) _______________________________________________ geda-user mailing list [email protected] http://www.seul.org/cgi-bin/mailman/listinfo/geda-user
