Page 378 - Excel for Scientists and Engineers: Numerical Methods

CHAPTER 15 RANDOM NUMBERS & MONTE CARLO METHOD 355

The standard method to determine whether a point lies inside or outside the
figure is to draw a "ray" from the point extending out to infinity. In this example,
illustrated in Figure 15-1 5, a "ray" is drawn vertically upwards from the point. If
the ray crosses the boundary line(s) of the figure an odd number of times, the
point lies

0 10 20 30 40 50
X coordinate of point
Figure 15-15. Determining whether a point lies inside or outside an irregular polygon.

The procedure to test whether a point XA, y~ lies within the figure is as
follows:
For each of the N edges that make up the figure:
(1) If the x coordinates of both ends of the edge lie to the left of xA, then go
to the next edge.
(2) If the x coordinates of both ends of the edge are to the right of xA, then go
to the next edge.
(3) If the y coordinates of both ends of the edge are below yA, then go to the
next edge.
(4) If none of the above is true, the y coordinates of one or both ends of the
edge are above the point. Determine the y coordinate of the "crossing
point" where the vertical ray and the edge cross, using the formula
YR -YL
Yc = YL +
xR - 'L
(5) If yc > YA, the ray crosses the edge of the polygon, so add one to the
number of crossings found, and go to the next edge.