Premium
An augmented spatial digital tree algorithm for contact detection in computational mechanics
Author(s) -
Feng Y. T.,
Owen D. R. J.
Publication year - 2002
Publication title -
international journal for numerical methods in engineering
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.421
H-Index - 168
eISSN - 1097-0207
pISSN - 0029-5981
DOI - 10.1002/nme.502
Subject(s) - rectangle , node (physics) , tree (set theory) , vertex (graph theory) , algorithm , computer science , bounding overwatch , representation (politics) , r tree , theoretical computer science , mathematics , spatial analysis , combinatorics , artificial intelligence , spatial database , engineering , geometry , graph , statistics , structural engineering , politics , law , political science
Based on the understanding of existing spatial digital tree‐based contact detection approaches, and the alternating digital tree (ADT) algorithm in particular, a more efficient algorithm, termed the augmented spatial digital tree (ASDT) algorithm, is proposed in the present work. The ASDT algorithm adopts a different point representation scheme that uses only the lower corner vertex to represent a (hyper‐)rectangle, with the upper corner vertex serving as the augmented information. Consequently, the ASDT algorithm can keep the working space the same as the original n ‐dimensional space and, in general, a much better balanced tree can be expected. This, together with the introduction of an additional bounding subregion for the rectangles associated with each tree node, makes it possible to significantly reduce the number of node visits in the region search, although each node visit may be slightly more expensive. Three examples arising in computational mechanics are presented to provide an assessment of the performance of the ASDT. The numerical results indicate that the ASDT is, at least, over 3.9 times faster than the ADT. Copyright © 2002 John Wiley & Sons, Ltd.