Beginning Algorithms

Chapter 18. Computational Geometry

This chapter gives you a taste of a fascinating area of algorithm design known as computational geometry. This topic could fill dozens of books on its own, so we will only be scratching the surface here. If you want to know more, check out the references or search the Internet for more material.

Computational geometry is one of the foundations of computer graphics, so if you intend to pursue an interest in developing software for games or other graphical areas, you'll need a solid understanding of computational geometry.

All topics covered in this chapter are limited to two-dimensional geometry. You will need to grasp the concepts in two dimensions before understanding three dimensions, a topic beyond the scope of this chapter. There are many excellent books that specialize in the explanation of the algorithms used in three-dimensional graphics. Check the references section in Appendix A or a good computer bookstore.

This chapter discusses the following topics:

• A quick geometry refresher

• Finding the intersection point of two straight lines

• Finding the closest pair of points among a large set of scattered points

A Quick Geometry Refresher

This section saves you the trouble of digging out your high school mathematics textbook by quickly recapping some of the concepts you'll need to understand to make sense of the rest of the chapter.

Coordinates and Points

Two-dimensional spatial concepts are usually described using an x-y coordinate system. This system is ...