19 - Computer graphics and computational geometry

Summary

Z can describe data structures. In this chapter we'll use Z to define the fundamental objects of computer graphics and computational geometry: points, line segments, contours, and polygons.

Consider the distinction between a contour, which is any sequence of connected line segments, and a polygon, which is a closed contour that has an inside and an outside (Figure 19.1). Your eye can see the difference immediately, and the distinction is vital for many computations of great practical importance.

Figure 19.2 is a computer graphic that shows a view of a patient's anatomy and radiation beam geometry, used to plan this patient's radiation treatment for cancer. Cross-sections of anatomical structures must be polygons, not just contours, and the physics calculations that compute the radiation dose depend on this. If some contours are not closed, or cross over themselves, the dose calculations may be incorrect.

The difference between contours and polygons is vital, but there is no way to express this distinction in most programming languages: You have to represent both as mere sequences (arrays or lists) of points. Data types in programming languages correspond closely to the way data are represented in computer memory: If two objects are stored in the same format, they belong to the same data type. Z is far more expressive because we can distinguish data types based on their values and constraints between the values of their components. This enables us to define data types that capture such requirements as “a closed contour that doesn't cross over itself.”