Hopefully you remember the post I made back in Oct. 2007 about Rigorous Geometry. It turns out the CGAL project has a whole page devoted to this subject see CGAL/Philosophy. I suggest you read their thoughts on the subject since they’ve devoted considerable time to the problem.

Their solution to simplify considerably is to compute with numbers of arbitrary precision. They do this using either the GNU Multiple Precision Library or their own internal code.

I’ve decided to try implementing my project to solve Tanagram puzzles using the CGAL library. The downside is that CGAL is written in C++.

### Like this:

Like Loading...

The problem to which you are referring here–inexact floating point and its geometric consequences–is commonly referred to as the Geometric Robustness problem. The majority of work on and attention to the problem has come from the Computational Geometry community. As a result they have a number of software packages and surveys on the topic. Personally, I would recommend taking a look at Jonathan Shewchuk’s class page. He provides a good list of packages available, as well as one of the most readable introductions to the topic I have seen. (It’s given as a “Lecture Notes” link on the syllabus) For a more theoretical perspective, try Chee Yap’s survey. For a historical survey, try Hoffman’s. (available through IEEE Xplore if you’re at a university)

Chee Yap’s Survey: (scroll down to Handbook of Computational Geometry)

http://cs.nyu.edu/exact/papers.html

Jonathan Shewchuk’s Computational Geometry course page:

http://www.cs.berkeley.edu/~jrs/274/

Thanks for the links and the pointer to Chee Yap’s survey.

Bryan Bell

No problem.

I just realized one other point from your earlier example of the rotating square. The point (0.5, 0) lies on the boundary of the square given by vertices (0,0), (1,0), (1,1), and (0,1). So, technically it’s ambiguous whether (0.5,0) lies inside or outside the square. In fact, one could say it lies both inside and outside, or neither inside nor outside. It all depends whether we consider the square to be “open” or “closed” in the same sense as we refer to (0,1) and [0,1] as open and closed intervals on the real line.

Thank you for posting!

you are right it is ambiguous, but (0.5, 0) is definitely on the boundary of the square.