An algebraic algorithm for point inclusion query

Huayi Wu, Jianya Gong, Deren Li, Wen Zhong Shi

Research output: Journal article publicationJournal articleAcademic researchpeer-review

14 Citations (Scopus)

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.
Original languageEnglish
Pages (from-to)517-522
Number of pages6
JournalComputers and Graphics (Pergamon)
Volume24
Issue number4
Publication statusPublished - 1 Dec 2000

Keywords

  • Complexity
  • Geometric algorithm
  • Point-in-polygon test

ASJC Scopus subject areas

  • Engineering(all)
  • Human-Computer Interaction
  • Computer Graphics and Computer-Aided Design

Cite this