点击次数：

论文类型：期刊论文

发表时间：2008-02-19

发表刊物：INTERNATIONAL JOURNAL FOR NUMERICAL METHODS IN ENGINEERING

收录刊物：SCIE、EI

卷号：73

期号：8

页面范围：1061-1076

ISSN号：0029-5981

关键字：point location; counter clockwise wise search; barycentric coordinates search; walk-through; backward search

摘要：Point location is one of the most basic searching problems in computational geometry. It has been largely studied on the aspect of query time in the worst case, and many methods have been proposed, such as counter clockwise wise search and barycentric coordinates search. However, most of them aim at the convex field. For a non-convex problem, such as a concave field or a convex field with holes, these searching schemes may fail. The numerical experience shows that, even for a convex problem, the searching path may lead to an infinite loop for some special case and may not find the element containing the query point. In this paper, a robust backward search method based on Walk-through algorithm is proposed to deal with the searching problems in non-convex fields and to avoid the problems of infinite loop. Another important improvement is to locate the query point on a 3D surface mesh. Several examples demonstrate that the present method is efficient and robust for the workpieces of complex geometry. Copyright (C) 2007 John Wiley & Sons, Ltd.