Please can anyone help me with a reasonably straightforward algorithm for determining whether a point is inside or outside a region defined by a polygon? I have searched previous posts, but what I've found (e.g. on determining whether a mouse click is within a region) doesn't seem to offer the answer I need for my purposes.

The context is a spatial simulation model for a fishery. Individual fish move within a spatial arena, parts of which may be closed to fishing. If the closed areas are simple shapes, such as rectangles, circles or triangles, it is easy to determine whether a fish at a given coordinate (x,y) is inside or outside a closed area. Convex polygons are slightly less easy, but I could still see how to determine a simple rule for inside/outside. Where I'm stuck is with defining rules for more complicated closed areas, the edges of which may contain both convexities and concavities.

One possible approach to these more complex shapes is to approximate them on a fine-scale grid. Inside/outside determination is then just a matter of determining the identity of the current grid square and looking up the status of this square in an array. This might cause some edge effects, since (except for exact N-S or E-W directions) there will no longer be straight lines between the vertices of the polygon. Possibly this doesn't matter provided that the grid squares are small with respect to the scale of fish movements within any time step of the model, but I can see that this might give rise to some very large arrays.

So far I have just been working with areas defined as blocks on a grid, but I would be interested to know if there is a more elegant and exact solution that I could use for modelling more complex shapes. I suspect that this type of problem may be fairly trivial for someone with experience of GIS and mapping applications ...? For my purposes it needs to be fast to execute, since the program involves simulation of the movements of millions of individuals over, say, daily time steps for a hundred or more years (required to equilibrate for a given fishery management scenario). I won't be wanting to display the movements on the screen (except for some basic checking work to make sure I'm doing what I think I am).

Thanks in advance for any enlightenment. For information: I program with PB/CC5, but I'm by no means a programmer.

Cheers

Mike

The context is a spatial simulation model for a fishery. Individual fish move within a spatial arena, parts of which may be closed to fishing. If the closed areas are simple shapes, such as rectangles, circles or triangles, it is easy to determine whether a fish at a given coordinate (x,y) is inside or outside a closed area. Convex polygons are slightly less easy, but I could still see how to determine a simple rule for inside/outside. Where I'm stuck is with defining rules for more complicated closed areas, the edges of which may contain both convexities and concavities.

One possible approach to these more complex shapes is to approximate them on a fine-scale grid. Inside/outside determination is then just a matter of determining the identity of the current grid square and looking up the status of this square in an array. This might cause some edge effects, since (except for exact N-S or E-W directions) there will no longer be straight lines between the vertices of the polygon. Possibly this doesn't matter provided that the grid squares are small with respect to the scale of fish movements within any time step of the model, but I can see that this might give rise to some very large arrays.

So far I have just been working with areas defined as blocks on a grid, but I would be interested to know if there is a more elegant and exact solution that I could use for modelling more complex shapes. I suspect that this type of problem may be fairly trivial for someone with experience of GIS and mapping applications ...? For my purposes it needs to be fast to execute, since the program involves simulation of the movements of millions of individuals over, say, daily time steps for a hundred or more years (required to equilibrate for a given fishery management scenario). I won't be wanting to display the movements on the screen (except for some basic checking work to make sure I'm doing what I think I am).

Thanks in advance for any enlightenment. For information: I program with PB/CC5, but I'm by no means a programmer.

Cheers

Mike

## Comment