What the mathematicians balk at isn't the pathological cases; rather,
getting exact results.
But the real problem is that these two are related. I spent several
years fixing the Boolean operations for a major CAD company's solid
modeler (the long-gone ComputerVision) which is essentially the same
problem made much more difficult by doing it in three dimensions.
The basic algorithm is conceptually simple:
1.) find all the intersections
2.) break into pieces at the intersections
3.) decide which pieces you need on the basis of some in/out tests and
which set operation you are doing.
4.) assemble the final result
The hitch is that #3 is a bunch of yes/no decisions that you must make
on the basis of imprecise floating point operations in #1. And all the
results of #3 have to be consistent or #4 won't work properly. This is
trivial in the easy cases (curves intersecting at reasonable angles,
no tiny pieces) but *VERY* hard to get right for the arbitrary case
(tangencies, near-tangencies, overlaps, pieces of curve that come out
smaller than whatever numerical tolerance you are using for your
floating point approximations, etc.). Essentially you have to have
some checks on the final result and be prepared to fail gracefully.
RObert Clair
_______________________________________________
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:
http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com
This email sent to [EMAIL PROTECTED]
