Performance issue when handling the horizontal coedges

[cwangbh]

Hi, Angus and Clipper2 community,

After profiling the union operation of Clipper2/CPP using vtune, I found two hotspots in the operation. Here is my preliminary wrap-up about the findings for your information, hopefully some potential improvement plan can come out of discussion in this community:

case 1: overlapped horizontal rectangles

case 2: coedge fence-shape rectangles and i also posted a pr here

Some preliminary thoughts:

1. use a tree data structure (like segment tree ) to maintain the active edge list, so that the time for checking the valid edge order IsValidAelOrder can be reduced
2. make a mapping between each vertex and its corresponding maxima, so that the GetMaximaPair time can be reduced
3. cut the horizontal edges and process different parts simultaneously
4. use the Disjoint-set data structure to maintain the owner of each outrect, so that the time for GetRealOutRec can be reduced

[AngusJohnson]

Thanks Wang Chao, I really do appreciate your suggestions. And changing the active edge list to some sort of binary tree would certainly be a consideration, but it's a bigger job than I'm prepared to consider in the short term. I've spent many months on Clipper2 and I'm looking forward to having a break, once I've tidied up remaining bugs and added one or two minor embellishments. Of course if you (or someone else) were to contribute a PR with this or other changes that demonstrated significant performance gains, of course I'd be keen to merge those into the library. Regarding your point 4, I don't know what a disjoint-set structure is, I'd have to look it up. But I'd be reluctant to do much more there (without a PR) unless changes could be easily implemented and performance gains had be demonstrated.