Hits:

Indexed by:期刊论文

Date of Publication:2008-02-19

Journal:INTERNATIONAL JOURNAL FOR NUMERICAL METHODS IN ENGINEERING

Included Journals:SCIE、EI

Volume:73

Issue:8

Page Number:1061-1076

ISSN No.:0029-5981

Key Words:point location; counter clockwise wise search; barycentric coordinates search; walk-through; backward search

Abstract: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.