kicad-developers team mailing list archive

[Jeff Young <jeff@xxxxxxxxx>]

I’ve pushed new bits.  So far these just address the performance issues, not the anomalies.

JP, could you give it another run and see if it improves things enough?

Cheers,
Jeff.


> On 21 Jun 2019, at 16:59, jp charras <jp.charras@xxxxxxxxxx> wrote:
> 
> 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