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.
