[metapost] accurate computation of path intersections

Nelson H. F. Beebe beebe at math.utah.edu
Tue Jan 11 14:31:51 CET 2005


The problem of accurate computation of path intersections is a
difficult one, and in extreme cases, errors can be large and highly
visible.  Limited precision of ordinary computer arithmetic is a
significant problem.

I recommend looking at the work of Jonathan Shewchuk at Berkeley:

	Adaptive Precision Floating-Point Arithmetic and Fast Robust
	Predicates for Computational Geometry

	http://www-2.cs.cmu.edu/~quake/robust.html

That page contains references to publications, and online versions of
articles, as well as C code for accurate solution of certain path
intersection problems.

-------------------------------------------------------------------------------
- Nelson H. F. Beebe                    Tel: +1 801 581 5254                  -
- University of Utah                    FAX: +1 801 581 4148                  -
- Department of Mathematics, 110 LCB    Internet e-mail: beebe at math.utah.edu  -
- 155 S 1400 E RM 233                       beebe at acm.org  beebe at computer.org -
- Salt Lake City, UT 84112-0090, USA    URL: http://www.math.utah.edu/~beebe  -
-------------------------------------------------------------------------------



More information about the metapost mailing list