Re: gEDA-user: PCB Polygon code (with r-tree speedups) triggers GCC bug...

[Peter Clifton <pcjc2@xxxxxxxxx>]

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
geda-user@xxxxxxxxxxxxxx
http://www.seul.org/cgi-bin/mailman/listinfo/geda-user