文章基本信息

标题：Point-in-polyhedra test with direct handling of degeneracies
本地全文：下载
作者：Shulin Cui ; Shuqing Zhang ; Xuanxi Chen 等
期刊名称：Geo-spatial Information Science
印刷版ISSN：1009-5020
电子版ISSN：1993-5153
出版年度：2011
卷号：14
期号：2
页码：91-97
DOI：10.1007/s11806-011-0453-8
出版社：Taylor and Francis Ltd
摘要：The Point-In-Polyhedron problem is to check whether a point is inside or outside of a given polyhedron. When a degenerate case is detected, the traditional ray-crossing algorithms avoid the case by selecting a different ray or erase the case by perturbing input data. This paper introduces a Threshold-Based Ray-Crossing (TBRC) algorithm for solving the Point-In-Polyhedron problem. The TBRC algorithm copes directly with degenerate cases by checking whether to count the face intersecting with the ray. It is worth mentioning that the TBRC algorithm can handle all degeneracies without extra computation and storage. Moreover, we analyze the basic algorithm and examine how to accelerate it. The experimental results show that TBRC algorithm is highly efficient and robust for the Point-In-Polyhedron problem, compared to a classical tetrahedron-based algorithm without pre-processing.
关键词：TBRC; the edge-face problem; Point-In-Polyhedron