Hi Noah, just a couple of early observations....
On 8 Mar 2014, at 3:26 pm, Noah Desch <desc...@me.com> wrote: > Graham, I’d be glad to see how it performs with your additional test cases. > Although I spent quite a bit of time handling special cases this is very much > a work in progress and I appreciate any help anyone is willing to throw in. One of my test cases immediately tripped up your code. This is nothing to be ashamed of, every other algorithm seems to fail or perform poorly on the same test as well. (Essentially the paths are round-cornered rectangles that have the same height and width, but one is displaced horizontally, but not vertically, from the other. This means they share long stretches of edges). Essentially, your recursive routine WFGeometryCurveCurveIntersection_Recursive doesn't terminate for this case - I haven't looked any deeper yet. I notice that your code insists on paths having the NSNonZeroWindingRule. Is there a good reason for that? It's no biggie but I often use the other one. > I didn’t follow a specific algorithm, although much of the cubic bezier curve > handling (bounding box computation, line-curve & curve-curve intersections, > curve derivatives, etc) is based on the descriptions here: > http://pomax.github.io/bezierinfo/ Ah yes, I know that page. > Finding intersections between the two paths uses the naive n^2 algorithm. I’m > aware there are better ones but the descriptions I could find mention only > line segments and I am not sure how they generalize to curves. Yup, this seems to be the downfall of most attempts. You may be familiar with General Polygon Clipper (GPC) http://www.cs.man.ac.uk/~toby/gpc/ which works on polygons only, but is extremely reliable. I've often wondered whether its intersection finder can be used with a different way to split and combine the bezier elements. (in other words flatten the paths to find the intersections, but then use those points with the unflattened paths. The difficulty might be that colocating the point on the original path from the flattened path could end up being just as hard). GPC is extremely reliable and very fast, but unfortunately the code itself is terse, virtually uncommented and largely impenetrable. Apparently it's based on the Vatti algorithm. I think (not 100% sure) the one you've used is sometimes referred to as the Greiner-Hormann algorithm. It would be great to get this nailed. If you would be interested in my test cases perhaps we could figure out a way to share bezier paths (code snippets are one obvious way, but I tend to create the paths interactively so extracting the paths as code is not so straightforward). I really liked your demo/test app by the way, very neat. Though I fear that the paths used there aren't pathological enough :) If this is getting too off-topic for Cocoa, feel free to take this up off-list. --Graham _______________________________________________ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: https://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
