Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/26826
Title: An algebraic algorithm for point inclusion query
Authors: Wu, H
Gong, J
Li, D
Shi, W 
Keywords: Complexity
Geometric algorithm
Point-in-polygon test
Issue Date: 2000
Publisher: Pergamon Press
Source: Computers & graphics, 2000, v. 24, no. 4, p. 517-522 How to cite?
Journal: Computers & graphics 
Abstract: 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 arc, a plane subdivision, a three-dimensional shape, a three-dimensional object and a three-dimensional space subdivision. An algebraic algorithm for the point-in-polygon test is devised on the base of the generalized linking number. The algorithm 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 processed. Detailed time complexity analysis shows that this algorithm greatly improves currently existing algorithms for the point-in-polygon test. Another achievement of this paper is the consistent and successful extension of the algebraic algorithm for the point-in-polygon test to point inclusion queries in two-dimensional objects, plane subdivisions, three-dimensional shapes, three-dimensional objects and three-dimensional space subdivisions. All these algorithms retain the algebraic character.
URI: http://hdl.handle.net/10397/26826
ISSN: 0097-8493
DOI: 10.1016/S0097-8493(00)00054-6
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

13
Last Week
0
Last month
0
Citations as of Nov 6, 2018

WEB OF SCIENCETM
Citations

7
Last Week
0
Last month
0
Citations as of Nov 14, 2018

Page view(s)

94
Last Week
0
Last month
Citations as of Nov 12, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.