7.2.2 Simulating the Locations of Urban Events

We now turn to what is perhaps the most fundamental geometrical question in the simulation of urban service systems: How do we simulate the locations of incidents, requests for service, or other events of interest which are distributed according to some prespecified probability law?

Suppose that the city (or part of the city) which is to be simulated is partitioned into small-area reporting zones, such as census blocks or police reporting areas or voting districts. If each reporting zone is small enough to be considered homogeneous, it would not be unreasonable to assume that locations of events within each zone are uniformly distributed. The concept of the zone is identical to the concept of the atom (Chapter 5) or of the demand-generating node (Chapter 6). We choose to use the term "zone" here because it conveys better the idea of geographical entities of varying areas and shapes with which we are now dealing.

To obtain a sample location from within the city, the following two-step procedure can be used:
STEP 1: To decide in which zone the event location will be, obtain a sample from the probability mass function depicting the relative likelihood of events among zones.
STEP 2: To identify the exact location of the event, obtain a sample from a uniform distribution over the zone selected.

The second step is by no means trivial if we allow the zones to have arbitrary shapes-as we should to allow for maximum flexibility. An approach that works well in this respect is the use of the rejection method of sampling (Section 7.1) to generate sample values for two random variables simultaneously. We assume that any given zone can be modeled as a polygon with n sides (n arbitrary) having no special properties such as convexity.5 Suppose that we enclose that polygon in the smallest rectangle fully containing it, with the sides of the rectangle constrained to be parallel to some prespecified set of coordinate axes (Figure 7.14). Then, using two random

numbers, a candidate point that has a uniform distribution over the rectangle is obtained. If this point is also within the polygon, it is accepted as the sample value; otherwise, it is rejected and new points are generated until one is accepted. The probability that any candidate point will be accepted is equal to the ratio of the area of the polygon (AP) to the area of the rectangle of accuracy, zones of any shape as polygons. (AR). The number of candidate points that have to be generated until one is accepted is a geometrically distributed random variable with mean AR/AP. For reasonably compact polygons, this number, reflecting sampling efficiency, is usually less than 2 (and often quite close to 1).

How does the computer determine whether a particular candidate point in the rectangle is inside or outside the polygon of interest? An effective way to deal with this problem is the point-polygon method.

Point-polygon method. The point-polygon method answers the following question: "Given a point (x, y) and a polygon specified by the n clockwise ordered vertices (x1, y1), (x2, y2), . . . , (xn, yn), is the point (x, y) contained within the polygon?" The basic idea of the method is to extend a ray in any direction from the point in question; if the ray intersects the sides of the polygon an odd (even) number of times, the point is (is not) within the polygon [NORD 62, BROW 68]. Figure 7.15 illustrates this idea. The method "works" because if the point is outside the polygon, the ray will exit the polygon each time that it enters it, since it must end up outside the polygon; the number of exits equaling the number of entries implies that the total number of intersections must be an even number. If, on the other hand, the point is within the polygon, then the number of exits e must be one greater than the number of entrances (e - 1), because the initial exit is not paired with an entrance; the total number of intersections 2e - I is clearly an odd number.

The method is completely general and does not require any special properties of the polygon. It is particularly well suited for machine implementation, since the tests for intersection are quickly performed on a computer (see also Problem 7.4).

5 This is a reasonable assumption, since we can approximate, to any desirable degree