Monday, May 4, 2009

Rounding Error Are an Important Consideration

My background includes a lot of mathematical analysis. I took a lot of numerical analysis at the University of Utah. Many more classes than were actually required because I enjoyed the combination of math and programming. In addition, I was a teaching assistant for the computational physics classes taught as part of the master's of instrumentation program of the physics department. My first job when I left the University of Utah was working on mathematical educational software. My assignment was part of a group creating a system that symbolically solved mathematical problems. I learned a lot. One of the challenges was checking the work of the system. I spent months doing nothing but math. After giving the system a problem it would generate an answer. Often the answer didn't match the solution printed in the book. We had to determine if the computer's answer was actually the correct answer. The system may not have simplified the answer, or not done some trigonometric substitution or maybe the answer in the book was wrong. It was a lot of work. That taught me the importance of mathematical simplification.

Years ago I worked on a respiratory therapy patient demographic and therapy management system. The company's core intellectual property was the set of equations modeling the treatment efficacy. The equations took the raw numbers provided by the medical instruments and the patient demography and created a meaningful human understandable diagnosis. My task was implementing those equations on a new system. I took one look at the equations and knew something was wrong with them. My background in numerical analysis told me curve fitting software created the equations. The curve fitting software mathematically matched the curve but did not simplify the equations. I convinced the professor that created the equations I could simplify them. For the next month I proved symbolically and numerically my simplification of the equations was correct. Imagine working on a month long math test. I proved the error analysis of my equations was significantly smaller than the original equations. More importantly, the resulting program ran more than ten times as fast.

What does all that have to do with XAML, hex grids, and user controls? You would think I would know better. I start working on making a hexagon a user control and what bites me? Rounding errors! I should have known that rounding errors would cause problems.

I started working on converting the shaded hexagon from my previous blog into a user control. I needed to work out the coordinates where to put each hexagon to create a hex grid. I created a column of hexagons. They looked good. I then added a second column, a third, and a fourth. Things looked great as you can see below.

Then I zoomed in a bit. Then I noticed that the hexagons did not always touch. I immediately knew the problem: rounding errors. You can see that below.

Hexagons tile the plane. Unfortunately you cannot tile them in XAML because you can only tile using simple rectangular patterns. I could use more precision. That would make the problem less likely to appear. The other option is just to make the hexagon grid as a series of polygons; each one calculated using as much accuracy as possible. You can see that below.

It looks like all is well with the hex grid. Until I made a simple change: I changed the stroke width to zero. You can see the result below.

Rounding errors are still visible. What does that mean? The short answer is you cannot expect to perfectly replicate a hexagon grid.

No comments: