UM  > 科技學院
Layer-Based Representation of Polyhedrons for Point Containment Tests
Wencheng Wang1; Jing Li1,2; Hanqiu Sun3; Enhua Wu1,4
2008
Source PublicationIEEE Transactions on Visualization and Computer Graphics
ISSN1077-2626
Volume14Issue:1Pages:73-83
Abstract

This paper presents the layer-based representation of polyhedrons and its use for point-in-polyhedron tests. In the representation, the facets and edges of a polyhedron are sequentially arranged, and so, the binary search algorithm is efficiently used to speed up Inclusion tests. In comparison with conventional representation for polyhedrons, the layer-based representation that we propose greatly reduces the storage requirement because It represents much information Implicitly though It still has a storage complexity O(n). It Is simple to implement and robust for Inclusion tests because many singularities are erased In constructing the layer-based representation. By incorporating an octree structure for organizing polyhedrons, our approach can run at a speed comparable with Binary Space Partitioning (BSP)-based inclusion tests and, at the same time, greatly reduce storage and preprocessing time in treating large polyhedrons. We have developed an efficient solution for point-in-polyhedron tests, with the time complexity varying between O(n) and O(logn), depending on the polyhedron shape and the constructed representation, and less than O(log n) in most cases. The time complexity of preprocess is between O(n) and O(n ), varying with polyhedrons, where n is the edge number of a polyhedron. 

KeywordComputational Geometry Point Containment Polyhedron Solid Representation
DOIhttps://doi.org/10.1109/TVCG.2007.70407
URLView the original
Indexed BySCI
Language英语
WOS Research AreaComputer Science
WOS SubjectComputer Science, Software Engineering
WOS IDWOS:000250787500007
PublisherIEEE COMPUTER SOC, 10662 LOS VAQUEROS CIRCLE, PO BOX 3014, LOS ALAMITOS, CA 90720-1314 USA
Fulltext Access
Citation statistics
Cited Times [WOS]:7   [WOS Record]     [Related Records in WOS]
Document TypeJournal article
CollectionFaculty of Science and Technology
Corresponding AuthorWencheng Wang; Jing Li; Hanqiu Sun; Enhua Wu
Affiliation1.State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing 100080, China.
2.Graduate University of the Chinese Academy of Sciences, Beijing, China.
3.Department of Computer Science and Engineering, The Chinese University of Hong Kong, Shatin, N.T., Hong Kong, China.
4.Department of Computer and Information Science, Faculty of S. & T., University of Macau, Macau, China.
Corresponding Author AffilicationUniversity of Macau
Recommended Citation
GB/T 7714
Wencheng Wang,Jing Li,Hanqiu Sun,et al. Layer-Based Representation of Polyhedrons for Point Containment Tests[J]. IEEE Transactions on Visualization and Computer Graphics,2008,14(1):73-83.
APA Wencheng Wang,Jing Li,Hanqiu Sun,&Enhua Wu.(2008).Layer-Based Representation of Polyhedrons for Point Containment Tests.IEEE Transactions on Visualization and Computer Graphics,14(1),73-83.
MLA Wencheng Wang,et al."Layer-Based Representation of Polyhedrons for Point Containment Tests".IEEE Transactions on Visualization and Computer Graphics 14.1(2008):73-83.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Wencheng Wang]'s Articles
[Jing Li]'s Articles
[Hanqiu Sun]'s Articles
Baidu academic
Similar articles in Baidu academic
[Wencheng Wang]'s Articles
[Jing Li]'s Articles
[Hanqiu Sun]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Wencheng Wang]'s Articles
[Jing Li]'s Articles
[Hanqiu Sun]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

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