线性四元树中轴变换

骨架和中轴变换概念运用于线性四元树,定义线性四元树中轴变换为具有一组棋盘距离值的线性四元树骨架.线性四元树中轴变换提供一种非常紧凑的区域表示法,它导致区域分割成边长为2的幂之和的最大正方形集合.提出两种算法计算一给定线性四元树的线性四元树中轴变换.最坏情况下它们的时间复杂性是O(n~2),其中n为线性四元树中四分形的数目.

A LINEAR QUADTREE MEDIAL AXIS TRANSFORM

The concept of skeleton and medial axis Transform is adapted to linearquadtree representations. The linear quadtree medial axis transform is defined as the linear quadtree skeleton with a set of chessboard distance values. Linear quadtree medial axis transforms provide a very compact region representation. It results in a partition of a region into a set of maximal squares having sides whose lengths are sums of powers of 2. Two algorithms are presented for the computation of the linear quadtree medial axis transform of a given linear quadtree. Worstcase time complexity of the algorithms is O(n2), where n is the number of quadrants in the linear quadtree.