search

hfutrell / BezierKit

Bezier curves and paths in Swift for building vector applications
MIT License
272 stars 26 forks source link

Proposal: Use Sylvester Matrix for finding the intersection of cubic beziers #99

Open edudnyk opened 3 years ago

edudnyk commented 3 years ago

I want to suggest an improvement of intersection finding algorithm - I have a working solution in C++ and ObjC based on this paper: https://mat.polsl.pl/sjpam/zeszyty/z6/Silesian_J_Pure_Appl_Math_v6_i1_str_155-176.pdf which can be ported to swift. The solution uses Jenkins-Traub polynomial (9) solving method by Chris Sweeny which requires complex number math.

Question before I start making the PR: do authors of this library consider adding either Eigen C++ template library or swift-numerics library as a dependency (to have complex number math in place)?

hfutrell commented 3 years ago

@edudnyk I would definitely be interested in what you came up with!

Getting the PR accepted into the codebase would be a bit of a higher bar though. It'd need to be faster than what's there and retain also high accuracy. For the accuracy part, there's a lot of unit tests that will let you know if anything is going wrong. For the speed part there's a couple of useful performance tests like testCubicIntersectionsPerformance and testCubicIntersectionsPerformanceTangentEndpoint to help you understand how your code is comparing.

I'd be ok with adding Swift numerics as a dependency. For C++ and Obj-C code though I'd want to get a Swift replacement.

You might be interested to know that BezierKit has an intersection method based on curve implicitization and polynomial solving ... a method related to the Sylvestor Matrix, which is the method of resultants as described by Thomas W. Sederberg in Computer Aided Geometric Design. Although in theory this approach is very fast, in practice I had difficulty implementing it efficiently. Therefore BezierKit only uses this approach when its divide-and-conquer approach exceeds a maximum number of iterations.