An algebraic algorithm for point inclusion query

Linking number is a basic invariant of a closed curve in topology. In this paper, linking number is generalized in a computational way to reflect the spatial relationship between a point and a line segment, an are, a plane su bdivision, a three-dimensional shape, a three-dimensional object and a thre e-dimensional space subdivision. An algebraic algorithm for the point-in-po lygon test is devised on the base of the generalized linking number. The al gorithm is characterized by the algebraic property that the linking number of a point to a polygon is merely the arithmetic sum of the linking numbers of the point to all the line segments of the polygon. The algorithm takes intersection into consideration, but no intersection is actually computed. It calculates the linking number, but no trigonometric function is processe d. Detailed time complexity analysis shows that this algorithm greatly impr oves currently existing algorithms for the point-in-polygon test. Another a chievement of this paper is the consistent and successful extension of the algebraic algorithm for the point-in-polygon test to point inclusion querie s in two-dimensional objects, plane subdivisions, three-dimensional shapes, three-dimensional objects and three-dimensional space subdivisions. All th ese algorithms retain the algebraic character. (C) 2000 Elsevier Science Lt d. All rights reserved.