Comparison of a regular and an irregular decomposition of regions and volumes

摘要

A comparison is made between K-trees, (i.e. quadtrees and octrees,) which are regular decompositions of volumes, and new, irregular decompositions called R-trees. This comparison is made within the context of the representation problems that might be associated with a robotic system. The results show that the irregular decomposition is independent of object position and can provide a more efficient encoding for certain shapes. However, detecting intersections between R-trees requires an algorithm of greater complexity than that of interference detection for octrees due to the irregularity of the R-tree decomposition.