kicad-developers team mailing list archive

[jp charras <jp.charras@xxxxxxxxxx>]

Le 21/06/2019 à 17:41, Jeff Young a écrit :
> Question for you polygon folks:
> 
> The old algorithm used to add a lot of pads to a “holes” polygon, then did a Simplify() on it, and then a BooleanSubtract() from the filled area.
> 
> The new code does a Simplify() and BooleanSubtract() per pad.  Since the holes are all discrete in either case (ie: not overlapping or otherwise interacting with each other), I thought this would have similar performance, and it makes the code easier to understand. But perhaps this is the source of the performance issue?
> 
> Cheers,
> Jeff.

Operations between polygons use fast algorithms and AFAIK scan only once
the full set of segments, and calculation time is something like N log N
for N segments.
(But I am not a polygon specialist)

If you subtract holes by pad to the zone, the cost is N log N x pad
count, with a value for N similar to the full segment count.

Moreover Simplify() can be costly in calculation time (according to the
Clipper doc).

I always saw (when I tried this kind of calculations) the calculation
time exploding, or at least much higher than a global calculation made
only once.

-- 
Jean-Pierre CHARRAS