Mastering Algorithms with Perl

Chapter 10. Geometric Algorithms

Do not disturb my circles!

—Archimedes (287-212 B.C.E.)

Geometry needs no introduction. This most visual branch of mathematics is used whenever you see pictures on your computer screen, and in this chapter we’ll explore algorithms useful for tasks such as these:

Web image maps

How can you tell whether the mouse click fell within an oddly shaped area? See Section 10.5.

Arranging windows

How do you open up new windows so that they obscure existing windows as little as possible? See Section 10.6.

Cartography

You have a set of scattered points (say, fenceposts) and want to draw the region that they define. See Section 10.6.

Simulations

Which pair of 10,000 points are closest to each other and therefore in danger of colliding? See Section 10.7.

In this chapter, we explore geometric formulas and algorithms. We can only provide building blocks for you to improve upon; as usual, we can’t anticipate every use you’ll have for these techniques. We’ll restrict ourselves to two dimensions in almost all of the code we show. We don’t cover the advanced topics you’ll find in a book devoted solely to computer graphics, such as ray tracing, radiosity, lighting, animation, or texture mapping, although we do cover splines in Section 16.3.2 in Chapter 16. For deeper coverage of these topics, we recommend Computer Graphics: Principles and Practice, by Foley, van Dam, Feiner, and Hughes, and the Graphics Gems books. Those of a more practical persuasion will find information ...