UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Filling contours on the linear quadtree domain by insertion and traversal Wilke, Lars Martin


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 indicates locally in which direction the region should grow. The technique takes advantage of certain characteristics of LQT location codes 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. The technique avoids explicit sorting of the input pixels or output cells by location code, and no condensation of cells is required. Traversing the regular quadtree in preorder generates the sorted output cells as an LQT.

Item Media

Item Citations and Data


For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.