Share Email Print

Proceedings Paper

Algorithm for point inclusion testing based on vector
Author(s): Xianbin Sun; Dehua Li
Format Member Price Non-Member Price
PDF $14.40 $18.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper Abstract

Point inclusion testing is to test the relationship of a fixed point and a polygon, an algorithm for this problem is presented. A ray was drawn from the fixed point, the ray may have crossing point with the edge of the polygon, two vectors were given from the fixed point to the endpoints of the edge which has crossing point with the ray, then calculate their vector product. Two functions were defined according to the vector product, the decision for point inclusion testing was based on this two functions. calculate the vector product for each edge that has crossing point with the ray from the fixed point, If the amount of positive vector product and negative vector product are the same, the point is outside the polygon; otherwise, the point is inside the polygon. This method can decrease computing time and can avoid some mistakes of other algorithm, and the main part of algorithm only needs 5n times subtraction, 2n times multiplication, n times *judgement, its algorithm complexity is 0(n). this algorithm is suitable for some other cases including self-intersection polygon and polygon with hole.

Paper Details

Date Published: 30 October 2009
PDF: 6 pages
Proc. SPIE 7496, MIPPR 2009: Pattern Recognition and Computer Vision, 74962C (30 October 2009); doi: 10.1117/12.833127
Show Author Affiliations
Xianbin Sun, Huazhong Univ. of Science and Technology (China)
Hubei Univ. of Technology (China)
Dehua Li, Huazhong Univ. of Science and Technology (China)

Published in SPIE Proceedings Vol. 7496:
MIPPR 2009: Pattern Recognition and Computer Vision
Mingyue Ding; Bir Bhanu; Friedrich M. Wahl; Jonathan Roberts, Editor(s)

© SPIE. Terms of Use
Back to Top