Hi Jon, Thanks for your reply, I will try to work on it, but I'm not sure that I can fix.
Sincerely Liang On Wed, 3 Dec 2025 at 21:53, Jon Evans <[email protected]> wrote: > 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 > <https://groups.google.com/a/kicad.org/d/msgid/devlist/CA%2BqGbCD7rXPKY1C5qg0wPUzVnCePdJniOnZ8waC8Q9XDsEAd7A%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/CAE0Ak8azJjf423xndEAZdUT5ED%3Dkk7eBuryib-T22NV%2B%2BDPJfQ%40mail.gmail.com.
