Virginia Tech
    • Log in
    View Item 
    •   VTechWorks Home
    • College of Engineering (COE)
    • Department of Computer Science
    • Computer Science Technical Reports
    • View Item
    •   VTechWorks Home
    • College of Engineering (COE)
    • Department of Computer Science
    • Computer Science Technical Reports
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    An Optimal Boundary to Quadtree Conversion Algorithm

    Thumbnail
    View/Open
    TR-89-16.pdf (1.084Mb)
    Downloads: 110
    TR number
    TR-89-16
    Date
    1989
    Author
    Lattanzi, Mark
    Shaffer, Clifford A.
    Metadata
    Show full item record
    Abstract
    An algorithm is presented for converting a boundary representation for an image to its region quad-tree representation. Our algorithm is designed for operation on the linear quadtree representation, although it can easily be modified for the traditional pointer-based quadtree representation. The algorithm is a two phase process that first creates linear quadtree node records for each of the border pixels. This list of pixels is then sorted by locational code. The second processing phase fills in the nodes interior to the polygons by simulating a traversal of the corresponding pointer-based quadtree. Three previous algorithms [Same80, Mark85a, Atki86] have described similar conversion routines requiring time complexity of O(n.B)for at least one of the two phases, where B is the number of boundary pixels and n is the depth of the final tree for a 2" x 2" image. A fourth algorithm [Webb84] can perform the border construction of this conversion in time O(n+B) with the restriction that the polygon must be positioned at constrained locations in the image space. Our algorithm requires time O(n + B) for the second phase, which is optimal. The first phase can be performed using the algorithm of [Webb84] for total conversion time of O(n + B) with constrained location, or in time O(B log B) using a simple sort to order the border pixels with no restriction in polygon location.
    URI
    http://hdl.handle.net/10919/19512
    Collections
    • Computer Science Technical Reports [1035]

    If you believe that any material in VTechWorks should be removed, please see our policy and procedure for Requesting that Material be Amended or Removed. All takedown requests will be promptly acknowledged and investigated.

    Virginia Tech | University Libraries | Contact Us
     

     

    VTechWorks

    AboutPoliciesHelp

    Browse

    All of VTechWorksCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    Log inRegister

    Statistics

    View Usage Statistics

    If you believe that any material in VTechWorks should be removed, please see our policy and procedure for Requesting that Material be Amended or Removed. All takedown requests will be promptly acknowledged and investigated.

    Virginia Tech | University Libraries | Contact Us