The Dangers of Floating Point ArithmeticThe following two examples illustrate the dangers of floating point arithmetic in geometric computation. Convex HullsThis example was suggested by Stefan Schirra. We define a segment Since all points in #include <LEDA/geo/point.h> #include <LEDA/geo/segment.h> #include <LEDA/core/list.h> #include <LEDA/geo/line.h> #include <LEDA/geo/geo_alg.h> using namespace leda; int main() { point p0(-LEDA_PI,-LEDA_PI); point p1(+LEDA_PI,+LEDA_PI); std::cout << "p0: (" << p0.xcoord() << "," << p0.ycoord() << ")\n"; std::cout << "p1: (" << p1.xcoord() << "," << p1.ycoord() << ")\n"; segment s(p0,p1); list<point> L; L.append(p0); L.append(p1); for (int i=0; i<10000;i++) { double ax,ay; rand_int >> ax; rand_int >> ay; point p(ax*LEDA_PI,ay*LEDA_PI); rand_int >> ax; rand_int >> ay; point q(ax*LEDA_PI,ay*LEDA_PI); line l(p,q); point r; if (l.intersection(s,r)) L.append(r); } list<point> CH=CONVEX_HULL(L); std::cout << "convex hull: "; while (!CH.empty()) { point p=CH.pop(); std::cout << "(" << p.xcoord() << "," << p.ycoord() << ")"; } std::cout << endl; return 0; } Braided Lines (Verzopfte Geraden)The second example was suggested by Lyle Ramshaw. Consider the linesl1: y=9833x/9454 l2:y=9366x/9005. Both lines path through the origin and the slope of The program outputs that #include <iostream.h> int main() { cout.precision(12); float delta=0.001f; int last_comp=-1; float a=9833,b=9454,c=9366,d=9005; float x; for (x=0;x<0.1;x=x+delta) { float y1=a*x/b; float y2=c*x/d; int comp; if (y1<y2) comp=-1; else if (y1==y2) comp=0; else comp=1; if (comp!=last_comp) { cout << endl << x << ": "; if (comp==-1) cout << "l1 is below l2"; if (comp==0) cout << "l1 intersects l2"; else cout << "l1 is above l2"; } last_comp=comp; } cout << endl << endl; return 0; } |
See also:Data Types for 2-Dimensional Geometry |