Hello Liang, The current implementation was added in a merge request last year: https://gitlab.com/kicad/code/kicad/-/merge_requests/1891 I don't think that anyone on the core team has studied the performance deeply. There are many places where KiCad could do better handling very large designs, and we welcome contributions to improve these areas. With regards to your proposed algorithm, I think a prototype showing performance differences is a good next step. The best way to do this would be to work in a branch and then open a merge request when you are ready for others to look at it and test with various designs. We will need to do careful testing of any new algorithm before it is released in a stable version, as we have seen subtle bugs show up related to polygon fracturing in the past.
Best, Jon On Wed, Dec 3, 2025 at 6:18 AM Liang Jia <[email protected]> wrote: > Dear KiCad Developers, > > I have a big project with 50000 holes within one copper zone, I found the > performance for fill zones is not very good. > > So after some digging into the geometry processing code in KiCad, > specifically the fractureSingleCacheFriendly and processHole functions. > > I noticed that the current implementation for handling polygon holes > relies on *a linear search(maybe)* within processHole. For every hole, > the algorithm iterates through the existing edges (up to the > provokingIndex) to perform ray-casting and find the nearest left-side > neighbor for the bridge connection. > > While I understand the current implementation is highly optimized for *memory > locality* (as the function name suggests), the algorithmic complexity > appears to be roughly *O(N * M)*, where N is the number of outline edges > and M is the number of holes. > > *My observation:* > In scenarios involving complex geometries with a massive number of holes > (e.g., large BGA footprints, or complex thermal reliefs), this linear > approach might become a performance bottleneck as the edge list grows with > every processed hole. > > *My question:* > Has the team considered implementing a *Plane Sweep (Scanline) algorithm* > combined > with an *Active Edge List (e.g., using a Balanced BST or Interval Tree)* for > this task? > Standard computational geometry literature suggests this could reduce the > complexity to *O((N+M) log N)*, which would theoretically offer > significant speedups for high-complexity polygons. > > I am curious if the current linear approach was chosen specifically to > avoid the overhead of pointer-based structures (to maintain cache > friendliness) or if it is simply a case where optimization hasn't been > necessary yet. > > Would the team be interested in a patch or a prototype that attempts to > implement a sweep-line or spatial indexing approach here, or are there > specific constraints that make the current implementation preferable? > > Thank you for your time and for the great work on KiCad. > > Sincerely > > Liang > > -- > You received this message because you are subscribed to the Google Groups > "KiCad Developers" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To view this discussion visit > https://groups.google.com/a/kicad.org/d/msgid/devlist/CAE0Ak8bBLP_3b14nTSZ7LRLuXXiB1VfOmDbFoG4WhCc_gy%2BqmA%40mail.gmail.com > <https://groups.google.com/a/kicad.org/d/msgid/devlist/CAE0Ak8bBLP_3b14nTSZ7LRLuXXiB1VfOmDbFoG4WhCc_gy%2BqmA%40mail.gmail.com?utm_medium=email&utm_source=footer> > . > -- You received this message because you are subscribed to the Google Groups "KiCad Developers" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion visit https://groups.google.com/a/kicad.org/d/msgid/devlist/CA%2BqGbCD7rXPKY1C5qg0wPUzVnCePdJniOnZ8waC8Q9XDsEAd7A%40mail.gmail.com.
