CONFERENCE PROCEEDINGS
Advanced Search
Home > Proceedings > Volume 7496 > Article
Paper
30 October 2009 Algorithm for point inclusion testing based on vector
Xianbin Sun, Dehua Li
Author Affiliations +
Proceedings Volume 7496, MIPPR 2009: Pattern Recognition and Computer Vision; 74962C (2009) https://doi.org/10.1117/12.833127
Event: Sixth International Symposium on Multispectral Image Processing and Pattern Recognition, 2009, Yichang, China
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.
© (2009) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Citation Download Citation
Xianbin Sun and Dehua Li "Algorithm for point inclusion testing based on vector", Proc. SPIE 7496, MIPPR 2009: Pattern Recognition and Computer Vision, 74962C (30 October 2009); https://doi.org/10.1117/12.833127
ACCESS THE FULL ARTICLE
ORGANIZATIONAL
Sign in with credentials provided by your organization.
INSTITUTIONAL
Select your institution to access the SPIE Digital Library.
SELECT YOUR INSTITUTION
PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.
PERSONAL SIGN IN
No SPIE Account? Create one
PURCHASE THIS CONTENT
SUBSCRIBE TO DIGITAL LIBRARY
50 downloads per 1-year subscription
Members: $195
Non-members: $335 ADD TO CART
25 downloads per 1 - year subscription
Members: $145
Non-members: $250 ADD TO CART
PURCHASE SINGLE ARTICLE
Includes PDF, HTML & Video, when available
Members: $17.00
Non-members: $21.00 ADD TO CART
PROCEEDINGS
 6 PAGES
DOWNLOAD PAPER SAVE TO MY LIBRARY
GET CITATION
Advertisement
Advertisement
RIGHTS & PERMISSIONS
Get copyright permission  Get copyright permission on Copyright Marketplace
KEYWORDS
Detection and tracking algorithms
Evolutionary algorithms
Silicon
Computer graphics
Computer aided design
Image processing algorithms and systems
Pattern recognition
RELATED CONTENT
Subscribe to Digital Library
Receive Erratum Email Alert
Back to Top