A general framework for error analysis in measurement-based GIS Part 2: The algebra-based probability model for point-in-polygon analysis

This is the second paper of a four-part series of papers on the development of a general framework for error analysis in measurement-based geographic information systems (MBGIS). In this paper, we discuss the problem of point-in-polygon analysis under randomness, i.e., with random measurement error (ME). It is well known that overlay is one of the most important operations in GIS, and point-in-polygon analysis is a basic class of overlay and query problems. Though it is a classic problem, it has, however, not been addressed appropriately. With ME in the location of the vertices of a polygon, the resulting random polygons may undergo complex changes, so that the point-in-polygon problem may become theoretically and practically ill-defined. That is, there is a possibility that we cannot answer whether a random point is inside a random polygon if the polygon is not simple and cannot form a region. For the point-in-triangle problem, however, such a case need not be considered since any triangle always forms an interior or region. To formulate the general point-in-polygon problem in a suitable way, a conditional probability mechanism is first introduced in order to accurately characterize the nature of the problem and establish the basis for further analysis. For the point-in-triangle problem, four quadratic forms in the joint coordinate vectors of a point and the vertices of the triangle are constructed. The probability model for the point-in-triangle problem is then established by the identification of signs of these quadratic form variables. Our basic idea for solving a general point-in-polygon (concave or convex) problem is to convert it into several point-in-triangle problems under a certain condition. By solving each point-in-triangle problem and summing the solutions, the probability model for a general point-in-polygon analysis is constructed. The simplicity of the algebra-based approach is that from using these quadratic forms, we can circumvent the complex geometrical relations between a random point and a random polygon (convex or concave) that one has to deal with in any geometric method when probability is computed. The theoretical arguments are substantiated by simulation experiments. Copyright Springer-Verlag Berlin Heidelberg 2004