Algorithm to expand regions represented by linear quadtrees

摘要

An algorithm is presented that changes to ‘black’ those ‘white’ pixels within a specified distance of any ‘black’ pixel in an image represented by a linear quadtree. This function is useful for answering queries in a geographic information system such as ‘Find all wheat fields within five miles of a flood plain.’ The algorithm works by computing the chessboard distance to nearby black pixels for large white nodes, and either leaves them white, changes them to black or repeats the process on each subquadrant, as required. Small white nodes are a priori within the given radius and require no further calculation. Thus only a small percentage of the nodes of the quadtree need extensive processing. The algorithm is easily applied to multicoloured images by treating all nonwhite colours as ‘black’.