7.2 GEOMETRICAL RELATIONS IN URBAN SIMULATION
In the course of simulating urban service systems, questions of the following type arise repeatedly:
These questions and many others of a similar nature are obviously concerned with two-dimensional geometrical relations in urban environments. Most of them could be answered by inspection by a person equipped with a detailed map. However, the computer does not possess the visual and conceptual capabilities of human beings and so must be "told" in precise algorithmic terms how to answer these questions. It is important, moreover, that these algorithms be as efficient as possible, for it may be necessary for a computer to answer questions such as (1) or (2) above, several million times in the course of a typical set of simulation experiments.
In this section we shall discuss such techniques and algorithms. Most of them are of interest by themselves, independently of the simulation context, for they can be used with any computer package that processes geographically oriented data (e.g., "GEO-CODED" data). We shall begin our presentation with a seemingly unrelated problem, that of sorting a list of numbers and of searching through that list.