Filling boundaries by insertion and traversal in a linear quadtree domain
Lars Martin Wilke, G. Schrack · 2002
An algorithm is presented which fills contours described by a set of pixels whose locations are given in unsorted linear quadtree (LQT) form. Each pixel requires an associated blocking code which determines locally in which direction the region should grow. The technique takes advantage of some observations in LQT code arithmetic to determine if the boundary pixels fall on the edges or vertices of lower resolution LQT cells. This information allows for the automatic determination of boundary cells after the pixels have been inserted into a regular quadtree. Remaining uncoloured cells are coloured using conventional techniques. The algorithm compares favourably with existing LQT filling algorithms both in time and space complexity.