TY - GEN
T1 - Complete subdivision algorithms, I
T2 - 22nd Annual Symposium on Computational Geometry 2006, SCG'06
AU - Yap, Chee K.
PY - 2006
Y1 - 2006
N2 - We give the first complete subdivision algorithm for the intersection of two Bezier curves F, G, possibly with tangential intersections. Our approach to robust subdivision algorithms is based on geometric separation bounds, and using a criterion for detecting non-crossing intersection of curves. Our algorithm is adaptive, being based only on exact bigfloat computations. In particular, we avoid manipulation of algebraic numbers and resultant computations. It is designed to be competitive with current algorithms on "nice" inputs. All standard algorithms assume F, G to be relatively prime - our algorithm needs a generalization of this.
AB - We give the first complete subdivision algorithm for the intersection of two Bezier curves F, G, possibly with tangential intersections. Our approach to robust subdivision algorithms is based on geometric separation bounds, and using a criterion for detecting non-crossing intersection of curves. Our algorithm is adaptive, being based only on exact bigfloat computations. In particular, we avoid manipulation of algebraic numbers and resultant computations. It is designed to be competitive with current algorithms on "nice" inputs. All standard algorithms assume F, G to be relatively prime - our algorithm needs a generalization of this.
KW - Bezier curves
KW - Computational geometry
KW - Curve intersection
KW - Exact geometric computation
KW - Robust numerical algorithms
KW - Subdivision method
UR - http://www.scopus.com/inward/record.url?scp=33748060965&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33748060965&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:33748060965
SN - 1595933409
SN - 9781595933409
T3 - Proceedings of the Annual Symposium on Computational Geometry
SP - 217
EP - 226
BT - Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06
Y2 - 5 June 2006 through 7 June 2006
ER -