CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-sticky-header-enabled vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Quadtree - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-sticky-header-enabled vector-toc-available";var cookie=document.cookie.match(/(?:^|; )enwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy","wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgRequestId":"b6fbaaf5-ad44-49cd-a4e3-6e492542d1de","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Quadtree","wgTitle":"Quadtree","wgCurRevisionId":1280122514,"wgRevisionId":1280122514,"wgArticleId":577097,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["CS1: long volume value","Articles with short description","Short description is different from Wikidata","Wikipedia references cleanup from April 2015","All articles needing references cleanup","Articles covered by WikiProject Wikify from April 2015","All articles covered by WikiProject Wikify","All articles with unsourced statements","Articles with unsourced statements from June 2015","CS1 maint: multiple names: authors list","Trees (data structures)","Database index techniques","Geometric data structures","Rectangular subdivisions"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Quadtree","wgRelevantArticleId":577097,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false,"wgFlaggedRevsParams":{"tags":{"status":{"levels":1}}},"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":30000,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q934791","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false}; RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.cite.styles":"ready","ext.math.styles":"ready","ext.pygments":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","jquery.makeCollapsible.styles":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","ext.pygments.view","mediawiki.page.media","site","mediawiki.page.ready","jquery.makeCollapsible","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.switcher","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=en&modules=ext.cite.styles%7Cext.math.styles%7Cext.pygments%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediamessages.styles%7Cjquery.makeCollapsible.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=en&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.19"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/8/8b/Point_quadtree.svg/1200px-Point_quadtree.svg.png"> <meta property="og:image:width" content="1200"> <meta property="og:image:height" content="1200"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/8/8b/Point_quadtree.svg/800px-Point_quadtree.svg.png"> <meta property="og:image:width" content="800"> <meta property="og:image:height" content="800"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/8/8b/Point_quadtree.svg/640px-Point_quadtree.svg.png"> <meta property="og:image:width" content="640"> <meta property="og:image:height" content="640"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Quadtree - Wikipedia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//en.m.wikipedia.org/wiki/Quadtree"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Quadtree&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipedia (en)"> <link rel="EditURI" type="application/rsd+xml" href="//en.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://en.wikipedia.org/wiki/Quadtree"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en"> <link rel="alternate" type="application/atom+xml" title="Wikipedia Atom feed" href="/w/index.php?title=Special:RecentChanges&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-Quadtree rootpage-Quadtree skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Jump to content</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" title="Main menu" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Main menu" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Main menu</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Main menu</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">hide</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigation </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z"><span>Main page</span></a></li><li id="n-contents" class="mw-list-item"><a href="/wiki/Wikipedia:Contents" title="Guides to browsing Wikipedia"><span>Contents</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Portal:Current_events" title="Articles related to current events"><span>Current events</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Special:Random" title="Visit a randomly selected article [x]" accesskey="x"><span>Random article</span></a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:About" title="Learn about Wikipedia and how it works"><span>About Wikipedia</span></a></li><li id="n-contactpage" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia"><span>Contact us</span></a></li> </ul> </div> </div> <div id="p-interaction" class="vector-menu mw-portlet mw-portlet-interaction" > <div class="vector-menu-heading"> Contribute </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-help" class="mw-list-item"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia"><span>Help</span></a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/Help:Introduction" title="Learn how to edit Wikipedia"><span>Learn to edit</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Community_portal" title="The hub for editors"><span>Community portal</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Special:RecentChanges" title="A list of recent changes to Wikipedia [r]" accesskey="r"><span>Recent changes</span></a></li><li id="n-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_upload_wizard" title="Add images or other media for use on Wikipedia"><span>Upload file</span></a></li><li id="n-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages"><span>Special pages</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Main_Page" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="The Free Encyclopedia" src="/static/images/mobile/copyright/wikipedia-tagline-en.svg" width="117" height="13" style="width: 7.3125em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Special:Search" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Search Wikipedia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia" aria-label="Search Wikipedia" autocapitalize="sentences" title="Search Wikipedia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Personal tools"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Appearance" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Appearance</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="https://donate.wikimedia.org/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=en.wikipedia.org&uselang=en" class=""><span>Donate</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:CreateAccount&returnto=Quadtree" title="You are encouraged to create an account and log in; however, it is not mandatory" class=""><span>Create account</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:UserLogin&returnto=Quadtree" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o" class=""><span>Log in</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Log in and more options" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Personal tools" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">Personal tools</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="User menu" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="https://donate.wikimedia.org/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=en.wikipedia.org&uselang=en"><span>Donate</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&returnto=Quadtree" title="You are encouraged to create an account and log in; however, it is not mandatory"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Create account</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:UserLogin&returnto=Quadtree" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Log in</span></a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Pages for logged out editors <a href="/wiki/Help:Introduction" aria-label="Learn more about editing"><span>learn more</span></a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Special:MyContributions" title="A list of edits made from this IP address [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Special:MyTalk" title="Discussion about edits from this IP address [n]" accesskey="n"><span>Talk</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Contents" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Contents</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">hide</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">(Top)</div> </a> </li> <li id="toc-Types" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Types"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Types</span> </div> </a> <button aria-controls="toc-Types-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Types subsection</span> </button> <ul id="toc-Types-sublist" class="vector-toc-list"> <li id="toc-Region_quadtree" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Region_quadtree"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.1</span> <span>Region quadtree</span> </div> </a> <ul id="toc-Region_quadtree-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Point_quadtree" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Point_quadtree"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.2</span> <span>Point quadtree</span> </div> </a> <ul id="toc-Point_quadtree-sublist" class="vector-toc-list"> <li id="toc-Node_structure_for_a_point_quadtree" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Node_structure_for_a_point_quadtree"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.2.1</span> <span>Node structure for a point quadtree</span> </div> </a> <ul id="toc-Node_structure_for_a_point_quadtree-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Point-region_(PR)_quadtree" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Point-region_(PR)_quadtree"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.3</span> <span>Point-region (PR) quadtree</span> </div> </a> <ul id="toc-Point-region_(PR)_quadtree-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Edge_quadtree" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Edge_quadtree"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.4</span> <span>Edge quadtree</span> </div> </a> <ul id="toc-Edge_quadtree-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Polygonal_map_(PM)_quadtree" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Polygonal_map_(PM)_quadtree"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.5</span> <span>Polygonal map (PM) quadtree</span> </div> </a> <ul id="toc-Polygonal_map_(PM)_quadtree-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Compressed_quadtrees" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Compressed_quadtrees"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.6</span> <span>Compressed quadtrees</span> </div> </a> <ul id="toc-Compressed_quadtrees-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Some_common_uses_of_quadtrees" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Some_common_uses_of_quadtrees"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Some common uses of quadtrees</span> </div> </a> <ul id="toc-Some_common_uses_of_quadtrees-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Image_processing_using_quadtrees" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Image_processing_using_quadtrees"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Image processing using quadtrees</span> </div> </a> <button aria-controls="toc-Image_processing_using_quadtrees-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Image processing using quadtrees subsection</span> </button> <ul id="toc-Image_processing_using_quadtrees-sublist" class="vector-toc-list"> <li id="toc-Image_union_/_intersection" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Image_union_/_intersection"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.1</span> <span>Image union / intersection</span> </div> </a> <ul id="toc-Image_union_/_intersection-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Connected_component_labelling" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Connected_component_labelling"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.2</span> <span>Connected component labelling</span> </div> </a> <ul id="toc-Connected_component_labelling-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Mesh_generation_using_quadtrees" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Mesh_generation_using_quadtrees"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Mesh generation using quadtrees</span> </div> </a> <ul id="toc-Mesh_generation_using_quadtrees-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Pseudocode" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Pseudocode"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Pseudocode</span> </div> </a> <button aria-controls="toc-Pseudocode-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Pseudocode subsection</span> </button> <ul id="toc-Pseudocode-sublist" class="vector-toc-list"> <li id="toc-Prerequisites" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Prerequisites"> <div class="vector-toc-text"> <span class="vector-toc-numb">5.1</span> <span>Prerequisites</span> </div> </a> <ul id="toc-Prerequisites-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-QuadTree_class" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#QuadTree_class"> <div class="vector-toc-text"> <span class="vector-toc-numb">5.2</span> <span>QuadTree class</span> </div> </a> <ul id="toc-QuadTree_class-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Insertion" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Insertion"> <div class="vector-toc-text"> <span class="vector-toc-numb">5.3</span> <span>Insertion</span> </div> </a> <ul id="toc-Insertion-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Query_range" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Query_range"> <div class="vector-toc-text"> <span class="vector-toc-numb">5.4</span> <span>Query range</span> </div> </a> <ul id="toc-Query_range-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-See_also" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#See_also"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>See also</span> </div> </a> <ul id="toc-See_also-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-References" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#References"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>References</span> </div> </a> <button aria-controls="toc-References-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle References subsection</span> </button> <ul id="toc-References-sublist" class="vector-toc-list"> <li id="toc-Notes" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Notes"> <div class="vector-toc-text"> <span class="vector-toc-numb">7.1</span> <span>Notes</span> </div> </a> <ul id="toc-Notes-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-General_references" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#General_references"> <div class="vector-toc-text"> <span class="vector-toc-numb">7.2</span> <span>General references</span> </div> </a> <ul id="toc-General_references-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" title="Table of Contents" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Quadtree</span></h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Go to an article in another language. Available in 13 languages" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-13" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span> <span class="vector-dropdown-label-text">13 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-ca mw-list-item"><a href="https://ca.wikipedia.org/wiki/Quadtree" title="Quadtree – Catalan" lang="ca" hreflang="ca" data-title="Quadtree" data-language-autonym="Català" data-language-local-name="Catalan" class="interlanguage-link-target"><span>Català</span></a></li><li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Quadtree" title="Quadtree – German" lang="de" hreflang="de" data-title="Quadtree" data-language-autonym="Deutsch" data-language-local-name="German" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-et mw-list-item"><a href="https://et.wikipedia.org/wiki/Kvadropuu" title="Kvadropuu – Estonian" lang="et" hreflang="et" data-title="Kvadropuu" data-language-autonym="Eesti" data-language-local-name="Estonian" class="interlanguage-link-target"><span>Eesti</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/Quadtree" title="Quadtree – Spanish" lang="es" hreflang="es" data-title="Quadtree" data-language-autonym="Español" data-language-local-name="Spanish" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%DA%86%D8%A7%D8%B1%D8%AF%D8%B1%D8%AE%D8%AA" title="چاردرخت – Persian" lang="fa" hreflang="fa" data-title="چاردرخت" data-language-autonym="فارسی" data-language-local-name="Persian" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/Quadtree" title="Quadtree – French" lang="fr" hreflang="fr" data-title="Quadtree" data-language-autonym="Français" data-language-local-name="French" class="interlanguage-link-target"><span>Français</span></a></li><li class="interlanguage-link interwiki-it mw-list-item"><a href="https://it.wikipedia.org/wiki/Albero_quadramentale" title="Albero quadramentale – Italian" lang="it" hreflang="it" data-title="Albero quadramentale" data-language-autonym="Italiano" data-language-local-name="Italian" class="interlanguage-link-target"><span>Italiano</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E5%9B%9B%E5%88%86%E6%9C%A8" title="四分木 – Japanese" lang="ja" hreflang="ja" data-title="四分木" data-language-autonym="日本語" data-language-local-name="Japanese" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-pl mw-list-item"><a href="https://pl.wikipedia.org/wiki/Drzewo_czw%C3%B3rkowe" title="Drzewo czwórkowe – Polish" lang="pl" hreflang="pl" data-title="Drzewo czwórkowe" data-language-autonym="Polski" data-language-local-name="Polish" class="interlanguage-link-target"><span>Polski</span></a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BA%D0%B2%D0%B0%D0%B4%D1%80%D0%B0%D0%BD%D1%82%D0%BE%D0%B2" title="Дерево квадрантов – Russian" lang="ru" hreflang="ru" data-title="Дерево квадрантов" data-language-autonym="Русский" data-language-local-name="Russian" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-sr mw-list-item"><a href="https://sr.wikipedia.org/wiki/Kvadratno_stablo" title="Kvadratno stablo – Serbian" lang="sr" hreflang="sr" data-title="Kvadratno stablo" data-language-autonym="Српски / srpski" data-language-local-name="Serbian" class="interlanguage-link-target"><span>Српски / srpski</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BA%D0%B2%D0%B0%D0%B4%D1%80%D0%B0%D0%BD%D1%82%D1%96%D0%B2" title="Дерево квадрантів – Ukrainian" lang="uk" hreflang="uk" data-title="Дерево квадрантів" data-language-autonym="Українська" data-language-local-name="Ukrainian" class="interlanguage-link-target"><span>Українська</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E5%9B%9B%E5%8F%89%E6%A0%91" title="四叉树 – Chinese" lang="zh" hreflang="zh" data-title="四叉树" data-language-autonym="中文" data-language-local-name="Chinese" class="interlanguage-link-target"><span>中文</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q934791#sitelinks-wikipedia" title="Edit interlanguage links" class="wbc-editpage">Edit links</a></span></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Namespaces"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Quadtree" title="View the content page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Talk:Quadtree" rel="discussion" title="Discuss improvements to the content page [t]" accesskey="t"><span>Talk</span></a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Change language variant" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">English</span> </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Views"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Quadtree"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Quadtree&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Quadtree&action=history" title="Past revisions of this page [h]" accesskey="h"><span>View history</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Tools" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">Tools</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Tools</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">hide</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="More options" > <div class="vector-menu-heading"> Actions </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/Quadtree"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Quadtree&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Quadtree&action=history"><span>View history</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> General </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Special:WhatLinksHere/Quadtree" title="List of all English Wikipedia pages containing links to this page [j]" accesskey="j"><span>What links here</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Special:RecentChangesLinked/Quadtree" rel="nofollow" title="Recent changes in pages linked from this page [k]" accesskey="k"><span>Related changes</span></a></li><li id="t-upload" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Quadtree&oldid=1280122514" title="Permanent link to this revision of this page"><span>Permanent link</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Quadtree&action=info" title="More information about this page"><span>Page information</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Special:CiteThisPage&page=Quadtree&id=1280122514&wpFormIdentifier=titleform" title="Information on how to cite this page"><span>Cite this page</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Special:UrlShortener&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FQuadtree"><span>Get shortened URL</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Special:QrCode&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FQuadtree"><span>Download QR code</span></a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Print/export </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Special:DownloadAsPdf&page=Quadtree&action=show-download-screen" title="Download this page as a PDF file"><span>Download as PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Quadtree&printable=yes" title="Printable version of this page [p]" accesskey="p"><span>Printable version</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> In other projects </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="wb-otherproject-link wb-otherproject-commons mw-list-item"><a href="https://commons.wikimedia.org/wiki/Category:Quadtrees" hreflang="en"><span>Wikimedia Commons</span></a></li><li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q934791" title="Structured data on this page hosted by Wikidata [g]" accesskey="g"><span>Wikidata item</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Appearance</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">hide</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> </div> <div id="siteSub" class="noprint">From Wikipedia, the free encyclopedia</div> </div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><div class="shortdescription nomobile noexcerpt noprint searchaux" style="display:none">Tree data structure in which each internal node has exactly four children, to partition a 2D area</div> <style data-mw-deduplicate="TemplateStyles:r1251242444">.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}</style><table class="box-Citation_style plainlinks metadata ambox ambox-style ambox-citation_style" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><span><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/40px-Edit-clear.svg.png" decoding="async" width="40" height="40" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/60px-Edit-clear.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/80px-Edit-clear.svg.png 2x" data-file-width="48" data-file-height="48" /></span></span></div></td><td class="mbox-text"><div class="mbox-text-span">This article <b>has an unclear <a href="/wiki/Wikipedia:Citing_sources#Citation_style" title="Wikipedia:Citing sources">citation style</a></b>.<span class="hide-when-compact"> The references used may be made clearer with a different or consistent style of <a href="/wiki/Wikipedia:Citing_sources" title="Wikipedia:Citing sources">citation</a> and <a href="/wiki/Help:Footnotes" title="Help:Footnotes">footnoting</a>.</span> <span class="date-container"><i>(<span class="date">April 2015</span>)</i></span><span class="hide-when-compact"><i> (<small><a href="/wiki/Help:Maintenance_template_removal" title="Help:Maintenance template removal">Learn how and when to remove this message</a></small>)</i></span></div></td></tr></tbody></table> <style data-mw-deduplicate="TemplateStyles:r1257001546">.mw-parser-output .infobox-subbox{padding:0;border:none;margin:-3px;width:auto;min-width:100%;font-size:100%;clear:none;float:none;background-color:transparent}.mw-parser-output .infobox-3cols-child{margin:auto}.mw-parser-output .infobox .navbar{font-size:100%}@media screen{html.skin-theme-clientpref-night .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .infobox-full-data:not(.notheme) div:not(.notheme){background:#1f1f23!important;color:#f8f9fa}}@media(min-width:640px){body.skin--responsive .mw-parser-output .infobox-table{display:table!important}body.skin--responsive .mw-parser-output .infobox-table>caption{display:table-caption!important}body.skin--responsive .mw-parser-output .infobox-table>tbody{display:table-row-group}body.skin--responsive .mw-parser-output .infobox-table tr{display:table-row!important}body.skin--responsive .mw-parser-output .infobox-table th,body.skin--responsive .mw-parser-output .infobox-table td{padding-left:inherit;padding-right:inherit}}</style><table class="infobox"><tbody><tr><th colspan="2" class="infobox-above">Quadtree</th></tr><tr><th scope="row" class="infobox-label"><a href="/wiki/List_of_data_structures" title="List of data structures">Type</a></th><td class="infobox-data">Tree</td></tr><tr><th scope="row" class="infobox-label">Invented</th><td class="infobox-data">1974</td></tr><tr><th scope="row" class="infobox-label">Invented by</th><td class="infobox-data"><a href="/wiki/Raphael_Finkel" title="Raphael Finkel">Raphael Finkel</a> and <a href="/wiki/J.L._Bentley" class="mw-redirect" title="J.L. Bentley">J.L. Bentley</a></td></tr><tr><td colspan="2" class="infobox-full-data"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1257001546" /><table class="infobox-subbox infobox-3cols-child infobox-table"><tbody><tr><th colspan="4" class="infobox-header"><a href="/wiki/Time_complexity" title="Time complexity">Time complexity</a> in <a href="/wiki/Big_O_notation" title="Big O notation">big O notation</a></th></tr><tr><th scope="row" class="infobox-label" style="white-space:nowrap;">Operation</th><td class="infobox-data infobox-data-a"> <b>Average</b></td><td class="infobox-data infobox-data-b"> <b>Worst case</b></td></tr><tr><th colspan="4" class="infobox-header"><a href="/wiki/Space_complexity" title="Space complexity">Space complexity</a></th></tr></tbody></table></td></tr></tbody></table> <figure typeof="mw:File/Thumb"><a href="/wiki/File:Point_quadtree.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/8/8b/Point_quadtree.svg/300px-Point_quadtree.svg.png" decoding="async" width="300" height="300" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/8/8b/Point_quadtree.svg/450px-Point_quadtree.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/8/8b/Point_quadtree.svg/600px-Point_quadtree.svg.png 2x" data-file-width="500" data-file-height="500" /></a><figcaption>A point-region quadtree with point data. Bucket capacity 1.</figcaption></figure> <figure typeof="mw:File/Thumb"><a href="/wiki/File:Quadtree_compression_of_an_image.gif" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/d/d7/Quadtree_compression_of_an_image.gif/330px-Quadtree_compression_of_an_image.gif" decoding="async" width="300" height="150" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/d/d7/Quadtree_compression_of_an_image.gif/500px-Quadtree_compression_of_an_image.gif 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/d/d7/Quadtree_compression_of_an_image.gif/960px-Quadtree_compression_of_an_image.gif 2x" data-file-width="1050" data-file-height="525" /></a><figcaption>Quadtree compression of an image step by step. Left shows the compressed image with the tree bounding boxes while the right shows just the compressed image</figcaption></figure> <p>A <b>quadtree</b> is a <a href="/wiki/Tree_data_structure" class="mw-redirect" title="Tree data structure">tree data structure</a> in which each internal node has exactly four children. Quadtrees are the two-dimensional analog of <a href="/wiki/Octree" title="Octree">octrees</a> and are most often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions. The data associated with a leaf cell varies by application, but the leaf cell represents a "unit of interesting spatial information". </p><p>The subdivided regions may be square or rectangular, or may have arbitrary shapes. This data structure was named a quadtree by <a href="/wiki/Raphael_Finkel" title="Raphael Finkel">Raphael Finkel</a> and <a href="/wiki/J.L._Bentley" class="mw-redirect" title="J.L. Bentley">J.L. Bentley</a> in 1974.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> A similar partitioning is also known as a <i>Q-tree</i>. </p><p>All forms of quadtrees share some common features: </p> <ul><li>They decompose space into adaptable cells.</li> <li>Each cell (or bucket) has a maximum capacity. When maximum capacity is reached, the bucket splits.</li> <li>The tree directory follows the spatial decomposition of the quadtree.</li></ul> <p>A <b>tree-pyramid</b> (<b>T-pyramid</b>) is a "complete" tree; every node of the T-pyramid has four child nodes except leaf nodes; all leaves are on the same level, the level that corresponds to individual pixels in the image. The data in a tree-pyramid can be stored compactly in an array as an <a href="/wiki/Implicit_data_structure" title="Implicit data structure">implicit data structure</a> similar to <a href="/wiki/Binary_heap#Heap_implementation" title="Binary heap">the way a complete binary tree can be stored compactly in an array</a>.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Types">Types</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quadtree&action=edit&section=1" title="Edit section: Types"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/File:2D_Binary_Index.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/c/c2/2D_Binary_Index.svg/220px-2D_Binary_Index.svg.png" decoding="async" width="220" height="220" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/c/c2/2D_Binary_Index.svg/330px-2D_Binary_Index.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/c/c2/2D_Binary_Index.svg/440px-2D_Binary_Index.svg.png 2x" data-file-width="512" data-file-height="512" /></a><figcaption>An example of a recursive <a href="/wiki/Binary_space_partitioning" title="Binary space partitioning">binary space partitioning</a> quadtree for a 2D index.</figcaption></figure> <p>Quadtrees may be classified according to the type of data they represent, including areas, points, lines and curves. Quadtrees may also be classified by whether the shape of the tree is independent of the order in which data is processed. The following are common types of quadtrees. </p> <div class="mw-heading mw-heading3"><h3 id="Region_quadtree">Region quadtree</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quadtree&action=edit&section=2" title="Edit section: Region quadtree"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The region quadtree represents <a href="/wiki/Space_partitioning" title="Space partitioning">a partition of space</a> in two dimensions by decomposing the region into four equal quadrants, subquadrants, and so on with each leaf node containing data corresponding to a specific subregion. Each node in the tree either has exactly four children, or has no children (a leaf node). The height of quadtrees that follow this decomposition strategy (i.e. subdividing subquadrants as long as there is interesting data in the subquadrant for which more refinement is desired) is sensitive to and dependent on the spatial distribution of interesting areas in the space being decomposed. The region quadtree is a type of <a href="/wiki/Trie" title="Trie">trie</a>. </p><p>A region quadtree with a depth of n may be used to represent an image consisting of 2<sup>n</sup> × 2<sup>n</sup> pixels, where each pixel value is 0 or 1. The root node represents the entire image region. If the pixels in any region are not entirely 0s or 1s, it is subdivided. In this application, each leaf node represents a block of pixels that are all 0s or all 1s. Note the potential savings in terms of space when these trees are used for storing images; images often have many regions of considerable size that have the same colour value throughout. Rather than store a big 2-D array of every pixel in the image, a quadtree can capture the same information potentially many divisive levels higher than the pixel-resolution sized cells that we would otherwise require. The tree resolution and overall size is bounded by the pixel and image sizes. </p><p>A region quadtree may also be used as a variable resolution representation of a data field. For example, the temperatures in an area may be stored as a quadtree, with each leaf node storing the average temperature over the subregion it represents. </p> <div class="mw-heading mw-heading3"><h3 id="Point_quadtree">Point quadtree</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quadtree&action=edit&section=3" title="Edit section: Point quadtree"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The point quadtree<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> is an adaptation of a <a href="/wiki/Binary_tree" title="Binary tree">binary tree</a> used to represent two-dimensional point data. It shares the features of all quadtrees but is a true tree as the center of a subdivision is always on a point. It is often very efficient in comparing two-dimensional, ordered data points, usually operating in <a href="/wiki/Big_O_notation" title="Big O notation">O(log n)</a> time. Point quadtrees are worth mentioning for completeness, but they have been surpassed by <a href="/wiki/K-d_tree" title="K-d tree"><i>k</i>-d trees</a> as tools for generalized binary search.<sup id="cite_ref-Aluru2004_4-0" class="reference"><a href="#cite_note-Aluru2004-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> </p><p>Point quadtrees are constructed as follows. Given the next point to insert, we find the cell in which it lies and add it to the tree. The new point is added such that the cell that contains it is divided into quadrants by the vertical and horizontal lines that run through the point. Consequently, cells are rectangular but not necessarily square. In these trees, each node contains one of the input points. </p><p>Since the division of the plane is decided by the order of point-insertion, the tree's height is sensitive to and dependent on insertion order. Inserting in a "bad" order can lead to a tree of height linear in the number of input points (at which point it becomes a linked-list). If the point-set is static, pre-processing can be done to create a tree of balanced height. </p> <div class="mw-heading mw-heading4"><h4 id="Node_structure_for_a_point_quadtree">Node structure for a point quadtree</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quadtree&action=edit&section=4" title="Edit section: Node structure for a point quadtree"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A node of a point quadtree is similar to a node of a <a href="/wiki/Binary_tree" title="Binary tree">binary tree</a>, with the major difference being that it has four pointers (one for each quadrant) instead of two ("left" and "right") as in an ordinary binary tree. Also a key is usually decomposed into two parts, referring to x and y coordinates. Therefore, a node contains the following information: </p> <ul><li>four pointers: quad[‘NW’], quad[‘NE’], quad[‘SW’], and quad[‘SE’]</li> <li>point; which in turn contains: <ul><li>key; usually expressed as x, y coordinates</li> <li>value; for example a name</li></ul></li></ul> <div class="mw-heading mw-heading3"><h3 id="Point-region_(PR)_quadtree"><span id="Point-region_.28PR.29_quadtree"></span>Point-region (PR) quadtree</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quadtree&action=edit&section=5" title="Edit section: Point-region (PR) quadtree"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Point-region (PR) quadtrees<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> are very similar to region quadtrees. The difference is the type of information stored about the cells. In a region quadtree, a uniform value is stored that applies to the entire area of the cell of a leaf. The cells of a PR quadtree, however, store a list of points that exist within the cell of a leaf. As mentioned previously, for trees following this decomposition strategy the height depends on the spatial distribution of the points. Like the point quadtree, the PR quadtree may also have a linear height when given a "bad" set. </p> <div class="mw-heading mw-heading3"><h3 id="Edge_quadtree">Edge quadtree</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quadtree&action=edit&section=6" title="Edit section: Edge quadtree"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Edge quadtrees<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> (much like PM quadtrees) are used to store lines rather than points. Curves are approximated by subdividing cells to a very fine resolution, specifically until there is a single line segment per cell. Near corners/vertices, edge quadtrees will continue dividing until they reach their maximum level of decomposition. This can result in extremely unbalanced trees which may defeat the purpose of indexing. </p> <div class="mw-heading mw-heading3"><h3 id="Polygonal_map_(PM)_quadtree"><span id="Polygonal_map_.28PM.29_quadtree"></span>Polygonal map (PM) quadtree</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quadtree&action=edit&section=7" title="Edit section: Polygonal map (PM) quadtree"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The polygonal map quadtree (or PM Quadtree) is a variation of quadtree which is used to store collections of polygons that may be degenerate (meaning that they have isolated vertices or edges).<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> <sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> A big difference between PM quadtrees and edge quadtrees is that the cell under consideration is not subdivided if the segments meet at a vertex in the cell. </p><p>There are three main classes of PM Quadtrees, which vary depending on what information they store within each black node. PM3 quadtrees can store any amount of non-intersecting edges and at most one point. PM2 quadtrees are the same as PM3 quadtrees except that all edges must share the same end point. Finally PM1 quadtrees are similar to PM2, but black nodes can contain a point and its edges or just a set of edges that share a point, but you cannot have a point and a set of edges that do not contain the point. </p> <div class="mw-heading mw-heading3"><h3 id="Compressed_quadtrees">Compressed quadtrees</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quadtree&action=edit&section=8" title="Edit section: Compressed quadtrees"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>This section summarizes a subsection from a book by <a href="/wiki/Sariel_Har-Peled" title="Sariel Har-Peled">Sariel Har-Peled</a>.<sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> </p><p>If we were to store every node corresponding to a subdivided cell, we may end up storing a lot of empty nodes. We can cut down on the size of such sparse trees by only storing subtrees whose leaves have interesting data (i.e. "important subtrees"). We can actually cut down on the size even further. When we only keep important subtrees, the pruning process may leave long paths in the tree where the intermediate nodes have degree two (a link to one parent and one child). It turns out that we only need to store the node <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>u</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle u}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3e6bb763d22c20916ed4f0bb6bd49d7470cffd8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle u}" /></span> at the beginning of this path (and associate some meta-data with it to represent the removed nodes) and attach the subtree rooted at its end to <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>u</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle u}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3e6bb763d22c20916ed4f0bb6bd49d7470cffd8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle u}" /></span>. It is still possible for these compressed trees to have a linear height when given "bad" input points. </p><p>Although we trim a lot of the tree when we perform this compression, it is still possible to achieve logarithmic-time search, insertion, and deletion by taking advantage of <a href="/wiki/Z-order_curve" title="Z-order curve"><i>Z</i>-order curves</a>. The <i>Z</i>-order curve maps each cell of the full quadtree (and hence even the compressed quadtree) in <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(1)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(1)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e66384bc40452c5452f33563fe0e27e803b0cc21" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.745ex; height:2.843ex;" alt="{\displaystyle O(1)}" /></span> time to a one-dimensional line (and maps it back in <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(1)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(1)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e66384bc40452c5452f33563fe0e27e803b0cc21" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.745ex; height:2.843ex;" alt="{\displaystyle O(1)}" /></span> time too), creating a total order on the elements. Therefore, we can store the quadtree in a data structure for ordered sets (in which we store the nodes of the tree). </p><p>We must state a reasonable assumption before we continue: we assume that given two real numbers <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha ,\beta \in [0,1)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>α</mi> <mo>,</mo> <mi>β</mi> <mo>∈</mo> <mo stretchy="false">[</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \alpha ,\beta \in [0,1)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6021592a035c2548997fb8d86328c3d063459fca" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.605ex; height:2.843ex;" alt="{\displaystyle \alpha ,\beta \in [0,1)}" /></span> expressed as binary, we can compute in <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(1)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(1)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e66384bc40452c5452f33563fe0e27e803b0cc21" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.745ex; height:2.843ex;" alt="{\displaystyle O(1)}" /></span> time the index of the first bit in which they differ. We also assume that we can compute in <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(1)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(1)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e66384bc40452c5452f33563fe0e27e803b0cc21" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.745ex; height:2.843ex;" alt="{\displaystyle O(1)}" /></span> time the lowest common ancestor of two points/cells in the quadtree and establish their relative <i>Z</i>-ordering, and we can compute the floor function in <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(1)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(1)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e66384bc40452c5452f33563fe0e27e803b0cc21" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.745ex; height:2.843ex;" alt="{\displaystyle O(1)}" /></span> time. </p><p>With these assumptions, point location of a given point <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>q</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle q}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/06809d64fa7c817ffc7e323f85997f783dbdf71d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.07ex; height:2.009ex;" alt="{\displaystyle q}" /></span> (i.e. determining the cell that would contain <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>q</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle q}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/06809d64fa7c817ffc7e323f85997f783dbdf71d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.07ex; height:2.009ex;" alt="{\displaystyle q}" /></span>), insertion, and deletion operations can all be performed in <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log {n})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>log</mi> <mo>⁡</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(\log {n})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/653ab6d6fd99537d220f179d2591955ff4f37b99" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.336ex; height:2.843ex;" alt="{\displaystyle O(\log {n})}" /></span> time (i.e. the time it takes to do a search in the underlying ordered set data structure). </p><p>To perform a point location for <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>q</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle q}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/06809d64fa7c817ffc7e323f85997f783dbdf71d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.07ex; height:2.009ex;" alt="{\displaystyle q}" /></span> (i.e. find its cell in the compressed tree): </p> <ol><li>Find the existing cell in the compressed tree that comes before <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>q</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle q}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/06809d64fa7c817ffc7e323f85997f783dbdf71d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.07ex; height:2.009ex;" alt="{\displaystyle q}" /></span> in the <i>Z</i>-order. Call this cell <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>v</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e07b00e7fc0847fbd16391c778d65bc25c452597" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" /></span>.</li> <li>If <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q\in v}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>q</mi> <mo>∈</mo> <mi>v</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle q\in v}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/899b2c7b5a59ed5fa421d6d977e35814d1d37b5f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.038ex; height:2.176ex;" alt="{\displaystyle q\in v}" /></span>, return <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>v</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e07b00e7fc0847fbd16391c778d65bc25c452597" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" /></span>.</li> <li>Else, find what would have been the lowest common ancestor of the point <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>q</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle q}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/06809d64fa7c817ffc7e323f85997f783dbdf71d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.07ex; height:2.009ex;" alt="{\displaystyle q}" /></span> and the cell <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>v</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e07b00e7fc0847fbd16391c778d65bc25c452597" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" /></span> in an uncompressed quadtree. Call this ancestor cell <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>u</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle u}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3e6bb763d22c20916ed4f0bb6bd49d7470cffd8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle u}" /></span>.</li> <li>Find the existing cell in the compressed tree that comes before <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>u</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle u}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3e6bb763d22c20916ed4f0bb6bd49d7470cffd8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle u}" /></span> in the <i>Z</i>-order and return it.</li></ol> <p>Without going into specific details, to perform insertions and deletions we first do a point location for the thing we want to insert/delete, and then insert/delete it. Care must be taken to reshape the tree as appropriate, creating and removing nodes as needed. </p> <div class="mw-heading mw-heading2"><h2 id="Some_common_uses_of_quadtrees">Some common uses of quadtrees</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quadtree&action=edit&section=9" title="Edit section: Some common uses of quadtrees"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/File:Quad_tree_bitmap.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/a/a0/Quad_tree_bitmap.svg/370px-Quad_tree_bitmap.svg.png" decoding="async" width="370" height="152" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/a/a0/Quad_tree_bitmap.svg/555px-Quad_tree_bitmap.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/a/a0/Quad_tree_bitmap.svg/740px-Quad_tree_bitmap.svg.png 2x" data-file-width="680" data-file-height="280" /></a><figcaption>A bitmap and its compressed quadtree representation</figcaption></figure> <ul><li>Image representation</li> <li><a href="#Image_processing_using_quadtrees">Image processing</a></li> <li><a href="#Mesh_generation_using_quadtrees">Mesh generation</a><sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup></li> <li><a href="/wiki/Spatial_index" class="mw-redirect" title="Spatial index">Spatial indexing</a>, point location queries, and range queries</li> <li>Efficient <a href="/wiki/Collision_detection" title="Collision detection">collision detection</a> in two dimensions</li> <li><a href="/wiki/Hidden_face_removal#Viewing_frustum_culling" class="mw-redirect" title="Hidden face removal">View frustum culling</a> of terrain data</li> <li>Storing sparse data, such as a formatting information for a <a href="/wiki/Spreadsheet" title="Spreadsheet">spreadsheet</a><sup id="cite_ref-13" class="reference"><a href="#cite_note-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup> or for some matrix calculations<sup class="noprint Inline-Template Template-Fact" style="white-space:nowrap;">[<i><a href="/wiki/Wikipedia:Citation_needed" title="Wikipedia:Citation needed"><span title="This claim needs references to reliable sources. (June 2015)">citation needed</span></a></i>]</sup></li> <li>Solution of multidimensional <a href="/wiki/Field_(physics)" title="Field (physics)">fields</a> (<a href="/wiki/Computational_fluid_dynamics" title="Computational fluid dynamics">computational fluid dynamics</a>, <a href="/wiki/Electromagnetism" title="Electromagnetism">electromagnetism</a>)</li> <li><a href="/wiki/Conway%27s_Game_of_Life" title="Conway's Game of Life">Conway's Game of Life</a> simulation program.<sup id="cite_ref-14" class="reference"><a href="#cite_note-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup></li> <li><a href="/wiki/State_estimation" class="mw-redirect" title="State estimation">State estimation</a><sup id="cite_ref-15" class="reference"><a href="#cite_note-15"><span class="cite-bracket">[</span>15<span class="cite-bracket">]</span></a></sup></li> <li>Quadtrees are also used in the area of fractal image analysis</li> <li><a href="/wiki/Maximum_disjoint_set#Fat_objects_with_arbitrary_sizes:_PTAS" title="Maximum disjoint set">Maximum disjoint sets</a></li></ul> <div class="mw-heading mw-heading2"><h2 id="Image_processing_using_quadtrees">Image processing using quadtrees</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quadtree&action=edit&section=10" title="Edit section: Image processing using quadtrees"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Quadtrees, particularly the <a href="#Region_quadtree">region quadtree</a>, have lent themselves well to image processing applications. We will limit our discussion to binary image data, though region quadtrees and the image processing operations performed on them are just as suitable for colour images.<sup id="cite_ref-Aluru2004_4-1" class="reference"><a href="#cite_note-Aluru2004-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-:0_16-0" class="reference"><a href="#cite_note-:0-16"><span class="cite-bracket">[</span>16<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Image_union_/_intersection"><span id="Image_union_.2F_intersection"></span>Image union / intersection</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quadtree&action=edit&section=11" title="Edit section: Image union / intersection"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>One of the advantages of using quadtrees for image manipulation is that the set operations of union and intersection can be done simply and quickly.<sup id="cite_ref-Aluru2004_4-2" class="reference"><a href="#cite_note-Aluru2004-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-17" class="reference"><a href="#cite_note-17"><span class="cite-bracket">[</span>17<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-18" class="reference"><a href="#cite_note-18"><span class="cite-bracket">[</span>18<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-19" class="reference"><a href="#cite_note-19"><span class="cite-bracket">[</span>19<span class="cite-bracket">]</span></a></sup> <sup id="cite_ref-20" class="reference"><a href="#cite_note-20"><span class="cite-bracket">[</span>20<span class="cite-bracket">]</span></a></sup> Given two binary images, the image union (also called <i>overlay</i>) produces an image wherein a pixel is black if either of the input images has a black pixel in the same location. That is, a pixel in the output image is white only when the corresponding pixel in <i>both</i> input images is white, otherwise the output pixel is black. Rather than do the operation pixel by pixel, we can compute the union more efficiently by leveraging the quadtree's ability to represent multiple pixels with a single node. For the purposes of discussion below, if a subtree contains both black and white pixels we will say that the root of that subtree is coloured grey. </p><p>The algorithm works by traversing the two input quadtrees (<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2f304724948a3ef606c4a92459e22b87a954d993" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{1}}" /></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d1ba5f12fbb0ff766aec6e22148b429373608555" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{2}}" /></span>) while building the output quadtree <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}" /></span>. Informally, the algorithm is as follows. Consider the nodes <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{1}\in T_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>∈</mo> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v_{1}\in T_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e01cea50601988fb04d83193a115846ec18a7349" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.434ex; height:2.509ex;" alt="{\displaystyle v_{1}\in T_{1}}" /></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{2}\in T_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>∈</mo> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v_{2}\in T_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/177f07cab7f56d4ca5853833fda8cecc92037795" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.434ex; height:2.509ex;" alt="{\displaystyle v_{2}\in T_{2}}" /></span> corresponding to the same region in the images. </p> <ul><li>If <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/98d33f5d498d528bd8c10edc8ac8c34347f32b3a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.182ex; height:2.009ex;" alt="{\displaystyle v_{1}}" /></span> or <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/eb04c423c2cb809c30cac725befa14ffbf4c85f3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.182ex; height:2.009ex;" alt="{\displaystyle v_{2}}" /></span> is black, the corresponding node is created in <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}" /></span> and is colored black. If only one of them is black and the other is gray, the gray node will contain a subtree underneath. This subtree need not be traversed.</li> <li>If <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/98d33f5d498d528bd8c10edc8ac8c34347f32b3a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.182ex; height:2.009ex;" alt="{\displaystyle v_{1}}" /></span> (respectively, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/eb04c423c2cb809c30cac725befa14ffbf4c85f3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.182ex; height:2.009ex;" alt="{\displaystyle v_{2}}" /></span>) is white, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/eb04c423c2cb809c30cac725befa14ffbf4c85f3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.182ex; height:2.009ex;" alt="{\displaystyle v_{2}}" /></span> (respectively, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/98d33f5d498d528bd8c10edc8ac8c34347f32b3a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.182ex; height:2.009ex;" alt="{\displaystyle v_{1}}" /></span>) and the subtree underneath it (if any) is copied to <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}" /></span> .</li> <li>If both <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/98d33f5d498d528bd8c10edc8ac8c34347f32b3a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.182ex; height:2.009ex;" alt="{\displaystyle v_{1}}" /></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/eb04c423c2cb809c30cac725befa14ffbf4c85f3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.182ex; height:2.009ex;" alt="{\displaystyle v_{2}}" /></span> are gray, then the corresponding children of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/98d33f5d498d528bd8c10edc8ac8c34347f32b3a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.182ex; height:2.009ex;" alt="{\displaystyle v_{1}}" /></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/eb04c423c2cb809c30cac725befa14ffbf4c85f3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.182ex; height:2.009ex;" alt="{\displaystyle v_{2}}" /></span> are considered.</li></ul> <p>While this algorithm works, it does not by itself guarantee a minimally sized quadtree. For example, consider the result if we were to union a checkerboard (where every tile is a pixel) of size <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{k}\times 2^{k}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msup> <mo>×</mo> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 2^{k}\times 2^{k}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/74414f6e3b8d63d6dd77867ecfa6ff45b88296f4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.343ex; height:2.676ex;" alt="{\displaystyle 2^{k}\times 2^{k}}" /></span> with its complement. The result is a giant black square which should be represented by a quadtree with just the root node (coloured black), but instead the algorithm produces a full 4-ary tree of depth <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>k</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" /></span>. To fix this, we perform a bottom-up traversal of the resulting quadtree where we check if the four children nodes have the same colour, in which case we replace their parent with a leaf of the same colour.<sup id="cite_ref-Aluru2004_4-3" class="reference"><a href="#cite_note-Aluru2004-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> </p><p>The intersection of two images is almost the same algorithm. One way to think about the intersection of the two images is that we are doing a union with respect to the <i>white</i> pixels. As such, to perform the intersection we swap the mentions of black and white in the union algorithm. </p> <div class="mw-heading mw-heading3"><h3 id="Connected_component_labelling">Connected component labelling</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quadtree&action=edit&section=12" title="Edit section: Connected component labelling"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Consider two neighbouring black pixels in a binary image. They are <i>adjacent</i> if they share a bounding horizontal or vertical edge. In general, two black pixels are <i>connected</i> if one can be reached from the other by moving only to adjacent pixels (i.e. there is a path of black pixels between them where each consecutive pair is adjacent). Each maximal set of connected black pixels is a <i>connected component</i>. Using the quadtree representation of images, <a href="/wiki/Hanan_Samet" title="Hanan Samet">Samet</a><sup id="cite_ref-21" class="reference"><a href="#cite_note-21"><span class="cite-bracket">[</span>21<span class="cite-bracket">]</span></a></sup> showed how we can find and label these connected components in time proportional to the size of the quadtree.<sup id="cite_ref-Aluru2004_4-4" class="reference"><a href="#cite_note-Aluru2004-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-:1_22-0" class="reference"><a href="#cite_note-:1-22"><span class="cite-bracket">[</span>22<span class="cite-bracket">]</span></a></sup> This algorithm can also be used for polygon colouring. </p><p>The algorithm works in three steps: </p> <ol><li>establish the adjacency relationships between black pixels</li> <li>process the equivalence relations from the first step to obtain one unique label for each connected component</li> <li>label the black pixels with the label associated with their connected component</li></ol> <p>To simplify the discussion, let us assume the children of a node in the quadtree follow the <a href="/wiki/Z-order_curve" title="Z-order curve"><i>Z</i>-order</a> (SW, NW, SE, NE). Since we can count on this structure, for any cell we know how to navigate the quadtree to find the adjacent cells in the different levels of the hierarchy. </p><p>Step one is accomplished with a <a href="/wiki/Tree_traversal#Post-order" title="Tree traversal">post-order traversal</a> of the quadtree. For each black leaf <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>v</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e07b00e7fc0847fbd16391c778d65bc25c452597" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" /></span> we look at the node or nodes representing cells that are Northern neighbours and Eastern neighbours (i.e. the Northern and Eastern cells that share edges with the cell of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>v</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e07b00e7fc0847fbd16391c778d65bc25c452597" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" /></span>). Since the tree is organized in <i>Z</i>-order, we have the invariant that the Southern and Western neighbours have already been taken care of and accounted for. Let the Northern or Eastern neighbour currently under consideration be <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>u</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle u}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3e6bb763d22c20916ed4f0bb6bd49d7470cffd8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle u}" /></span>. If <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>u</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle u}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3e6bb763d22c20916ed4f0bb6bd49d7470cffd8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle u}" /></span> represents black pixels: </p> <ul><li>If only one of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>u</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle u}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3e6bb763d22c20916ed4f0bb6bd49d7470cffd8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle u}" /></span> or <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>v</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e07b00e7fc0847fbd16391c778d65bc25c452597" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" /></span> has a label, assign that label to the other cell</li> <li>If neither of them have labels, create one and assign it to both of them</li> <li>If <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>u</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle u}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3e6bb763d22c20916ed4f0bb6bd49d7470cffd8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle u}" /></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>v</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e07b00e7fc0847fbd16391c778d65bc25c452597" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" /></span> have different labels, record this label equivalence and move on</li></ul> <p>Step two can be accomplished using the <a href="/wiki/Disjoint-set_data_structure" title="Disjoint-set data structure">union-find data structure</a>.<sup id="cite_ref-23" class="reference"><a href="#cite_note-23"><span class="cite-bracket">[</span>23<span class="cite-bracket">]</span></a></sup> We start with each unique label as a separate set. For every equivalence relation noted in the first step, we union the corresponding sets. Afterwards, each distinct remaining set will be associated with a distinct connected component in the image. </p><p>Step three performs another post-order traversal. This time, for each black node <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>v</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e07b00e7fc0847fbd16391c778d65bc25c452597" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" /></span> we use the union-find's <i>find</i> operation (with the old label of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>v</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e07b00e7fc0847fbd16391c778d65bc25c452597" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" /></span>) to find and assign <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>v</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e07b00e7fc0847fbd16391c778d65bc25c452597" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" /></span> its new label (associated with the connected component of which <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>v</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e07b00e7fc0847fbd16391c778d65bc25c452597" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" /></span> is part). </p> <div class="mw-heading mw-heading2"><h2 id="Mesh_generation_using_quadtrees">Mesh generation using quadtrees</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quadtree&action=edit&section=13" title="Edit section: Mesh generation using quadtrees"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>This section summarizes a chapter from a book by Har-Peled and de Berg et al.<sup id="cite_ref-:2_24-0" class="reference"><a href="#cite_note-:2-24"><span class="cite-bracket">[</span>24<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-25" class="reference"><a href="#cite_note-25"><span class="cite-bracket">[</span>25<span class="cite-bracket">]</span></a></sup> </p><p><a href="/wiki/Mesh_generation" title="Mesh generation">Mesh generation</a> is essentially the <a href="/wiki/Point-set_triangulation" title="Point-set triangulation">triangulation of a point set</a> for which further processing may be performed. As such, it is desirable for the resulting triangulation to have certain properties (like non-uniformity, triangles that are not "too skinny", large triangles in sparse areas and small triangles in dense ones, etc.) to make further processing quicker and less error-prone. Quadtrees built on the point set can be used to create meshes with these desired properties. </p> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/File:Fig-mesh-gen-balanced-leaves.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/e/e0/Fig-mesh-gen-balanced-leaves.svg/220px-Fig-mesh-gen-balanced-leaves.svg.png" decoding="async" width="220" height="147" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/e/e0/Fig-mesh-gen-balanced-leaves.svg/330px-Fig-mesh-gen-balanced-leaves.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/e/e0/Fig-mesh-gen-balanced-leaves.svg/440px-Fig-mesh-gen-balanced-leaves.svg.png 2x" data-file-width="185" data-file-height="124" /></a><figcaption>A balanced leaf has at most one corner in a side.</figcaption></figure> <p>Consider a leaf of the quadtree and its corresponding cell <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>v</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e07b00e7fc0847fbd16391c778d65bc25c452597" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" /></span>. We say <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>v</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e07b00e7fc0847fbd16391c778d65bc25c452597" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" /></span> is <i>balanced</i> (for mesh generation) if the cell's sides are intersected by the corner points of neighbouring cells at most once on each side. This means that the quadtree levels of leaves adjacent to <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>v</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e07b00e7fc0847fbd16391c778d65bc25c452597" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" /></span> differ by at most one from the level of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>v</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e07b00e7fc0847fbd16391c778d65bc25c452597" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" /></span>. When this is true for all leaves, we say the whole quadtree is balanced (for mesh generation). </p><p>Consider the cell <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>v</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e07b00e7fc0847fbd16391c778d65bc25c452597" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" /></span> and the <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 5\times 5}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>5</mn> <mo>×</mo> <mn>5</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 5\times 5}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8dc635bb09101d63ece07af4a1a3883f75368dd8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.165ex; height:2.176ex;" alt="{\displaystyle 5\times 5}" /></span> neighbourhood of same-sized cells centred at <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>v</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e07b00e7fc0847fbd16391c778d65bc25c452597" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" /></span>. We call this neighbourhood the <i>extended cluster</i>. We say the quadtree is <i>well-balanced</i> if it is balanced, and for every leaf <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>u</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle u}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3e6bb763d22c20916ed4f0bb6bd49d7470cffd8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle u}" /></span> that contains a point of the point set, its extended cluster is also in the quadtree and the extended cluster contains no other point of the point set. </p><p>Creating the mesh is done as follows: </p> <ol><li>Build a quadtree on the input points.</li> <li>Ensure the quadtree is balanced. For every leaf, if there is a neighbour that is too large, subdivide the neighbour. This is repeated until the tree is balanced. We also make sure that for a leaf with a point in it, the nodes for each leaf's extended cluster are in the tree.</li> <li>For every leaf node <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>v</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e07b00e7fc0847fbd16391c778d65bc25c452597" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" /></span> that contains a point, if the extended cluster contains another point, we further subdivide the tree and rebalance as necessary. If we needed to subdivide, for each child <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>u</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle u}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3e6bb763d22c20916ed4f0bb6bd49d7470cffd8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle u}" /></span> of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>v</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e07b00e7fc0847fbd16391c778d65bc25c452597" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" /></span> we ensure the nodes of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>u</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle u}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3e6bb763d22c20916ed4f0bb6bd49d7470cffd8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle u}" /></span>'s extended cluster are in the tree (and re-balance as required).</li> <li>Repeat the previous step until the tree is well-balanced.</li> <li>Transform the quadtree into a triangulation.</li></ol> <p>We consider the corner points of the tree cells as vertices in our triangulation. Before the transformation step we have a bunch of boxes with points in some of them. The transformation step is done in the following manner: for each point, warp the closest corner of its cell to meet it and triangulate the resulting four quadrangles to make "nice" triangles (the interested reader is referred to chapter 12 of Har-Peled<sup id="cite_ref-:2_24-1" class="reference"><a href="#cite_note-:2-24"><span class="cite-bracket">[</span>24<span class="cite-bracket">]</span></a></sup> for more details on what makes "nice" triangles). </p><p>The remaining squares are triangulated according to some simple rules. For each regular square (no points within and no corner points in its sides), introduce the diagonal. Due to the way in which we separated points with the well-balancing property, no square with a corner intersecting a side is one that was warped. As such, we can triangulate squares with intersecting corners as follows. If there is one intersected side, the square becomes three triangles by adding the long diagonals connecting the intersection with opposite corners. If there are four intersected sides, we split the square in half by adding an edge between two of the four intersections, and then connect these two endpoints to the remaining two intersection points. For the other squares, we introduce a point in the middle and connect it to all four corners of the square as well as each intersection point. </p><p>At the end of it all, we have a nice triangulated mesh of our point set built from a quadtree. </p> <div class="mw-heading mw-heading2"><h2 id="Pseudocode">Pseudocode</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quadtree&action=edit&section=14" title="Edit section: Pseudocode"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The following pseudo code shows one means of implementing a quadtree which handles only points. There are other approaches available. </p> <div class="mw-heading mw-heading3"><h3 id="Prerequisites">Prerequisites</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quadtree&action=edit&section=15" title="Edit section: Prerequisites"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>It is assumed these structures are used. </p> <div class="mw-highlight mw-highlight-lang-c++ mw-content-ltr" dir="ltr"><pre><span></span><span class="w"> </span><span class="c1">// Simple coordinate object to represent points and vectors</span> <span class="w"> </span><span class="k">struct</span><span class="w"> </span><span class="nc">XY</span> <span class="w"> </span><span class="p">{</span> <span class="w"> </span><span class="kt">float</span><span class="w"> </span><span class="n">x</span><span class="p">;</span> <span class="w"> </span><span class="kt">float</span><span class="w"> </span><span class="n">y</span><span class="p">;</span> <span class="w"> </span> <span class="w"> </span><span class="n">function</span><span class="w"> </span><span class="nf">__construct</span><span class="p">(</span><span class="kt">float</span><span class="w"> </span><span class="n">_x</span><span class="p">,</span><span class="w"> </span><span class="kt">float</span><span class="w"> </span><span class="n">_y</span><span class="p">)</span><span class="w"> </span><span class="p">{...}</span> <span class="w"> </span><span class="p">}</span> <span class="w"> </span> <span class="w"> </span><span class="c1">// Axis-aligned bounding box with half dimension and center</span> <span class="w"> </span><span class="k">struct</span><span class="w"> </span><span class="nc">AABB</span> <span class="w"> </span><span class="p">{</span> <span class="w"> </span><span class="n">XY</span><span class="w"> </span><span class="n">center</span><span class="p">;</span> <span class="w"> </span><span class="kt">float</span><span class="w"> </span><span class="n">halfDimension</span><span class="p">;</span> <span class="w"> </span> <span class="w"> </span><span class="n">function</span><span class="w"> </span><span class="nf">__construct</span><span class="p">(</span><span class="n">XY</span><span class="w"> </span><span class="n">_center</span><span class="p">,</span><span class="w"> </span><span class="kt">float</span><span class="w"> </span><span class="n">_halfDimension</span><span class="p">)</span><span class="w"> </span><span class="p">{...}</span> <span class="w"> </span><span class="n">function</span><span class="w"> </span><span class="nf">containsPoint</span><span class="p">(</span><span class="n">XY</span><span class="w"> </span><span class="n">point</span><span class="p">)</span><span class="w"> </span><span class="p">{...}</span> <span class="w"> </span><span class="n">function</span><span class="w"> </span><span class="nf">intersectsAABB</span><span class="p">(</span><span class="n">AABB</span><span class="w"> </span><span class="n">other</span><span class="p">)</span><span class="w"> </span><span class="p">{...}</span> <span class="w"> </span><span class="p">}</span> </pre></div> <div class="mw-heading mw-heading3"><h3 id="QuadTree_class">QuadTree class</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quadtree&action=edit&section=16" title="Edit section: QuadTree class"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>This class represents both one quad tree and the node where it is rooted. </p> <div class="mw-highlight mw-highlight-lang-c++ mw-content-ltr" dir="ltr"><pre><span></span><span class="w"> </span><span class="k">class</span><span class="w"> </span><span class="nc">QuadTree</span> <span class="w"> </span><span class="p">{</span> <span class="w"> </span><span class="c1">// Arbitrary constant to indicate how many elements can be stored in this quad tree node</span> <span class="w"> </span><span class="n">constant</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">QT_NODE_CAPACITY</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="mi">4</span><span class="p">;</span> <span class="w"> </span> <span class="w"> </span><span class="c1">// Axis-aligned bounding box stored as a center with half-dimensions</span> <span class="w"> </span><span class="c1">// to represent the boundaries of this quad tree</span> <span class="w"> </span><span class="n">AABB</span><span class="w"> </span><span class="n">boundary</span><span class="p">;</span> <span class="w"> </span> <span class="w"> </span><span class="c1">// Points in this quad tree node</span> <span class="w"> </span><span class="n">Array</span><span class="w"> </span><span class="n">of</span><span class="w"> </span><span class="n">XY</span><span class="w"> </span><span class="p">[</span><span class="n">size</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">QT_NODE_CAPACITY</span><span class="p">]</span><span class="w"> </span><span class="n">points</span><span class="p">;</span> <span class="w"> </span> <span class="w"> </span><span class="c1">// Children</span> <span class="w"> </span><span class="n">QuadTree</span><span class="o">*</span><span class="w"> </span><span class="n">northWest</span><span class="p">;</span> <span class="w"> </span><span class="n">QuadTree</span><span class="o">*</span><span class="w"> </span><span class="n">northEast</span><span class="p">;</span> <span class="w"> </span><span class="n">QuadTree</span><span class="o">*</span><span class="w"> </span><span class="n">southWest</span><span class="p">;</span> <span class="w"> </span><span class="n">QuadTree</span><span class="o">*</span><span class="w"> </span><span class="n">southEast</span><span class="p">;</span> <span class="w"> </span> <span class="w"> </span><span class="c1">// Methods</span> <span class="w"> </span><span class="n">function</span><span class="w"> </span><span class="nf">__construct</span><span class="p">(</span><span class="n">AABB</span><span class="w"> </span><span class="n">_boundary</span><span class="p">)</span><span class="w"> </span><span class="p">{...}</span> <span class="w"> </span><span class="n">function</span><span class="w"> </span><span class="nf">insert</span><span class="p">(</span><span class="n">XY</span><span class="w"> </span><span class="n">p</span><span class="p">)</span><span class="w"> </span><span class="p">{...}</span> <span class="w"> </span><span class="n">function</span><span class="w"> </span><span class="nf">subdivide</span><span class="p">()</span><span class="w"> </span><span class="p">{...}</span><span class="w"> </span><span class="c1">// create four children that fully divide this quad into four quads of equal area</span> <span class="w"> </span><span class="n">function</span><span class="w"> </span><span class="nf">queryRange</span><span class="p">(</span><span class="n">AABB</span><span class="w"> </span><span class="n">range</span><span class="p">)</span><span class="w"> </span><span class="p">{...}</span> <span class="w"> </span><span class="p">}</span> </pre></div> <div class="mw-heading mw-heading3"><h3 id="Insertion">Insertion</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quadtree&action=edit&section=17" title="Edit section: Insertion"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The following method inserts a point into the appropriate quad of a quadtree, splitting if necessary. </p> <div class="mw-highlight mw-highlight-lang-c++ mw-content-ltr" dir="ltr"><pre><span></span><span class="w"> </span><span class="k">class</span><span class="w"> </span><span class="nc">QuadTree</span> <span class="w"> </span><span class="p">{</span> <span class="w"> </span><span class="p">...</span> <span class="w"> </span> <span class="w"> </span><span class="c1">// Insert a point into the QuadTree</span> <span class="w"> </span><span class="n">function</span><span class="w"> </span><span class="n">insert</span><span class="p">(</span><span class="n">XY</span><span class="w"> </span><span class="n">p</span><span class="p">)</span> <span class="w"> </span><span class="p">{</span> <span class="w"> </span><span class="c1">// Ignore objects that do not belong in this quad tree</span> <span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="o">!</span><span class="n">boundary</span><span class="p">.</span><span class="n">containsPoint</span><span class="p">(</span><span class="n">p</span><span class="p">))</span> <span class="w"> </span><span class="k">return</span><span class="w"> </span><span class="nb">false</span><span class="p">;</span><span class="w"> </span><span class="c1">// object cannot be added</span> <span class="w"> </span> <span class="w"> </span><span class="c1">// If there is space in this quad tree and if it doesn't have subdivisions, add the object here</span> <span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">points</span><span class="p">.</span><span class="n">size</span><span class="w"> </span><span class="o"><</span><span class="w"> </span><span class="n">QT_NODE_CAPACITY</span><span class="w"> </span><span class="o">&&</span><span class="w"> </span><span class="n">northWest</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="n">null</span><span class="p">)</span> <span class="w"> </span><span class="p">{</span> <span class="w"> </span><span class="n">points</span><span class="p">.</span><span class="n">append</span><span class="p">(</span><span class="n">p</span><span class="p">);</span> <span class="w"> </span><span class="k">return</span><span class="w"> </span><span class="nb">true</span><span class="p">;</span> <span class="w"> </span><span class="p">}</span> <span class="w"> </span> <span class="w"> </span><span class="c1">// Otherwise, subdivide and then add the point to whichever node will accept it</span> <span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">northWest</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="n">null</span><span class="p">)</span> <span class="w"> </span><span class="n">subdivide</span><span class="p">();</span> <span class="w"> </span><span class="c1">// We have to add the points/data contained in this quad array to the new quads if we only want</span> <span class="w"> </span><span class="c1">// the last node to hold the data</span> <span class="w"> </span> <span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">northWest</span><span class="o">-></span><span class="n">insert</span><span class="p">(</span><span class="n">p</span><span class="p">))</span><span class="w"> </span><span class="k">return</span><span class="w"> </span><span class="nb">true</span><span class="p">;</span> <span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">northEast</span><span class="o">-></span><span class="n">insert</span><span class="p">(</span><span class="n">p</span><span class="p">))</span><span class="w"> </span><span class="k">return</span><span class="w"> </span><span class="nb">true</span><span class="p">;</span> <span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">southWest</span><span class="o">-></span><span class="n">insert</span><span class="p">(</span><span class="n">p</span><span class="p">))</span><span class="w"> </span><span class="k">return</span><span class="w"> </span><span class="nb">true</span><span class="p">;</span> <span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">southEast</span><span class="o">-></span><span class="n">insert</span><span class="p">(</span><span class="n">p</span><span class="p">))</span><span class="w"> </span><span class="k">return</span><span class="w"> </span><span class="nb">true</span><span class="p">;</span> <span class="w"> </span> <span class="w"> </span><span class="c1">// Otherwise, the point cannot be inserted for some unknown reason (this should never happen)</span> <span class="w"> </span><span class="k">return</span><span class="w"> </span><span class="nb">false</span><span class="p">;</span> <span class="w"> </span><span class="p">}</span> <span class="w"> </span><span class="p">}</span> </pre></div> <div class="mw-heading mw-heading3"><h3 id="Query_range">Query range</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quadtree&action=edit&section=18" title="Edit section: Query range"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The following method finds all points contained within a range. </p> <div class="mw-highlight mw-highlight-lang-c++ mw-content-ltr" dir="ltr"><pre><span></span><span class="w"> </span><span class="k">class</span><span class="w"> </span><span class="nc">QuadTree</span> <span class="w"> </span><span class="p">{</span> <span class="w"> </span><span class="p">...</span> <span class="w"> </span> <span class="w"> </span><span class="c1">// Find all points that appear within a range</span> <span class="w"> </span><span class="n">function</span><span class="w"> </span><span class="n">queryRange</span><span class="p">(</span><span class="n">AABB</span><span class="w"> </span><span class="n">range</span><span class="p">)</span> <span class="w"> </span><span class="p">{</span> <span class="w"> </span><span class="c1">// Prepare an array of results</span> <span class="w"> </span><span class="n">Array</span><span class="w"> </span><span class="n">of</span><span class="w"> </span><span class="n">XY</span><span class="w"> </span><span class="n">pointsInRange</span><span class="p">;</span> <span class="w"> </span> <span class="w"> </span><span class="c1">// Automatically abort if the range does not intersect this quad</span> <span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="o">!</span><span class="n">boundary</span><span class="p">.</span><span class="n">intersectsAABB</span><span class="p">(</span><span class="n">range</span><span class="p">))</span> <span class="w"> </span><span class="k">return</span><span class="w"> </span><span class="n">pointsInRange</span><span class="p">;</span><span class="w"> </span><span class="c1">// empty list</span> <span class="w"> </span> <span class="w"> </span><span class="c1">// Check objects at this quad level</span> <span class="w"> </span><span class="k">for</span><span class="w"> </span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">p</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="mi">0</span><span class="p">;</span><span class="w"> </span><span class="n">p</span><span class="w"> </span><span class="o"><</span><span class="w"> </span><span class="n">points</span><span class="p">.</span><span class="n">size</span><span class="p">;</span><span class="w"> </span><span class="n">p</span><span class="o">++</span><span class="p">)</span> <span class="w"> </span><span class="p">{</span> <span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">range</span><span class="p">.</span><span class="n">containsPoint</span><span class="p">(</span><span class="n">points</span><span class="p">[</span><span class="n">p</span><span class="p">]))</span> <span class="w"> </span><span class="n">pointsInRange</span><span class="p">.</span><span class="n">append</span><span class="p">(</span><span class="n">points</span><span class="p">[</span><span class="n">p</span><span class="p">]);</span> <span class="w"> </span><span class="p">}</span> <span class="w"> </span> <span class="w"> </span><span class="c1">// Terminate here, if there are no children</span> <span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">northWest</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="n">null</span><span class="p">)</span> <span class="w"> </span><span class="k">return</span><span class="w"> </span><span class="n">pointsInRange</span><span class="p">;</span> <span class="w"> </span> <span class="w"> </span><span class="c1">// Otherwise, add the points from the children</span> <span class="w"> </span><span class="n">pointsInRange</span><span class="p">.</span><span class="n">appendArray</span><span class="p">(</span><span class="n">northWest</span><span class="o">-></span><span class="n">queryRange</span><span class="p">(</span><span class="n">range</span><span class="p">));</span> <span class="w"> </span><span class="n">pointsInRange</span><span class="p">.</span><span class="n">appendArray</span><span class="p">(</span><span class="n">northEast</span><span class="o">-></span><span class="n">queryRange</span><span class="p">(</span><span class="n">range</span><span class="p">));</span> <span class="w"> </span><span class="n">pointsInRange</span><span class="p">.</span><span class="n">appendArray</span><span class="p">(</span><span class="n">southWest</span><span class="o">-></span><span class="n">queryRange</span><span class="p">(</span><span class="n">range</span><span class="p">));</span> <span class="w"> </span><span class="n">pointsInRange</span><span class="p">.</span><span class="n">appendArray</span><span class="p">(</span><span class="n">southEast</span><span class="o">-></span><span class="n">queryRange</span><span class="p">(</span><span class="n">range</span><span class="p">));</span> <span class="w"> </span> <span class="w"> </span><span class="k">return</span><span class="w"> </span><span class="n">pointsInRange</span><span class="p">;</span> <span class="w"> </span><span class="p">}</span> <span class="w"> </span><span class="p">}</span> </pre></div> <div class="mw-heading mw-heading2"><h2 id="See_also">See also</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quadtree&action=edit&section=19" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Adaptive_mesh_refinement" title="Adaptive mesh refinement">Adaptive mesh refinement</a></li> <li><a href="/wiki/Binary_space_partitioning" title="Binary space partitioning">Binary space partitioning</a></li> <li><a href="/wiki/Binary_tiling" title="Binary tiling">Binary tiling</a></li> <li><a href="/wiki/K-d_tree" title="K-d tree"><i>k</i>-d tree</a></li> <li><a href="/wiki/Octree" title="Octree">Octree</a></li> <li><a href="/wiki/R-tree" title="R-tree">R-tree</a></li> <li><a href="/wiki/UB-tree" title="UB-tree">UB-tree</a></li> <li><a href="/wiki/Spatial_database" title="Spatial database">Spatial database</a></li> <li><a href="/wiki/Subpaving" title="Subpaving">Subpaving</a></li> <li><a href="/wiki/Z-order_curve" title="Z-order curve">Z-order curve</a></li></ul> <div class="mw-heading mw-heading2"><h2 id="References">References</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quadtree&action=edit&section=20" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Surveys by Aluru<sup id="cite_ref-Aluru2004_4-5" class="reference"><a href="#cite_note-Aluru2004-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> and Samet<sup id="cite_ref-:1_22-1" class="reference"><a href="#cite_note-:1-22"><span class="cite-bracket">[</span>22<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-:0_16-1" class="reference"><a href="#cite_note-:0-16"><span class="cite-bracket">[</span>16<span class="cite-bracket">]</span></a></sup> give a nice overview of quadtrees. </p> <div class="mw-heading mw-heading3"><h3 id="Notes">Notes</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quadtree&action=edit&section=21" title="Edit section: Notes"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1239543626">.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}</style><div class="reflist"> <div class="mw-references-wrap mw-references-columns"><ol class="references"> <li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text"><style data-mw-deduplicate="TemplateStyles:r1238218222">.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}</style><cite id="CITEREFFinkelBentley1974" class="citation journal cs1">Finkel, R. A.; Bentley, J. L. (1974). <a rel="nofollow" class="external text" href="https://www.researchgate.net/publication/220197855">"Quad trees a data structure for retrieval on composite keys"</a>. <i>Acta Informatica</i>. <b>4</b> (1): <span class="nowrap">1–</span>9. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF00288933">10.1007/BF00288933</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:33019699">33019699</a><span class="reference-accessdate">. Retrieved <span class="nowrap">6 November</span> 2019</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Acta+Informatica&rft.atitle=Quad+trees+a+data+structure+for+retrieval+on+composite+keys&rft.volume=4&rft.issue=1&rft.pages=%3Cspan+class%3D%22nowrap%22%3E1-%3C%2Fspan%3E9&rft.date=1974&rft_id=info%3Adoi%2F10.1007%2FBF00288933&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A33019699%23id-name%3DS2CID&rft.aulast=Finkel&rft.aufirst=R.+A.&rft.au=Bentley%2C+J.+L.&rft_id=https%3A%2F%2Fwww.researchgate.net%2Fpublication%2F220197855&rfr_id=info%3Asid%2Fen.wikipedia.org%3AQuadtree" class="Z3988"></span></span> </li> <li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"> Milan Sonka, Vaclav Hlavac, Roger Boyle. <a rel="nofollow" class="external text" href="https://books.google.com/books?id=DcETCgAAQBAJ">"Image Processing, Analysis, and Machine Vision"</a>. 2014. p. 108-109.</span> </li> <li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFFinkelBentley1974" class="citation journal cs1">Finkel, R. A.; Bentley, J. L. (1974). "Quad Trees A Data Structure for Retrieval on Composite Keys". <i>Acta Informatica</i>. <b>4</b>. Springer-Verlag: <span class="nowrap">1–</span>9. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fbf00288933">10.1007/bf00288933</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:33019699">33019699</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Acta+Informatica&rft.atitle=Quad+Trees+A+Data+Structure+for+Retrieval+on+Composite+Keys&rft.volume=4&rft.pages=%3Cspan+class%3D%22nowrap%22%3E1-%3C%2Fspan%3E9&rft.date=1974&rft_id=info%3Adoi%2F10.1007%2Fbf00288933&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A33019699%23id-name%3DS2CID&rft.aulast=Finkel&rft.aufirst=R.+A.&rft.au=Bentley%2C+J.+L.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AQuadtree" class="Z3988"></span></span> </li> <li id="cite_note-Aluru2004-4"><span class="mw-cite-backlink">^ <a href="#cite_ref-Aluru2004_4-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Aluru2004_4-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-Aluru2004_4-2"><sup><i><b>c</b></i></sup></a> <a href="#cite_ref-Aluru2004_4-3"><sup><i><b>d</b></i></sup></a> <a href="#cite_ref-Aluru2004_4-4"><sup><i><b>e</b></i></sup></a> <a href="#cite_ref-Aluru2004_4-5"><sup><i><b>f</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFAluru2004" class="citation book cs1">Aluru, S. (2004). "Quadtrees and octrees". In D. Mehta and S. Sahni (ed.). <i>Handbook of Data Structures and Applications</i>. Chapman and Hall/CRC. pp. 19-1 -- 19-26. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/9781584884354" title="Special:BookSources/9781584884354"><bdi>9781584884354</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Quadtrees+and+octrees&rft.btitle=Handbook+of+Data+Structures+and+Applications&rft.pages=19-1+--+19-26&rft.pub=Chapman+and+Hall%2FCRC&rft.date=2004&rft.isbn=9781584884354&rft.aulast=Aluru&rft.aufirst=S.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AQuadtree" class="Z3988"></span></span> </li> <li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFOrenstein1982" class="citation journal cs1">Orenstein, J. A. (1982). "Multidimensional tries used for associative searching". <i>Information Processing Letters</i>. <b>14</b> (4). Elsevier: <span class="nowrap">150–</span>157. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0020-0190%2882%2990027-8">10.1016/0020-0190(82)90027-8</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Information+Processing+Letters&rft.atitle=Multidimensional+tries+used+for+associative+searching&rft.volume=14&rft.issue=4&rft.pages=%3Cspan+class%3D%22nowrap%22%3E150-%3C%2Fspan%3E157&rft.date=1982&rft_id=info%3Adoi%2F10.1016%2F0020-0190%2882%2990027-8&rft.aulast=Orenstein&rft.aufirst=J.+A.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AQuadtree" class="Z3988"></span></span> </li> <li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFSamet1984" class="citation journal cs1">Samet, H. (1984). <a rel="nofollow" class="external text" href="http://www.cs.umd.edu/~hjs/pubs/SameCSUR84-ocr.pdf">"The quadtree and related hierarchical data structures"</a> <span class="cs1-format">(PDF)</span>. <i>ACM Computing Surveys</i>. <b>16</b> (2). ACM: <span class="nowrap">187–</span>260. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F356924.356930">10.1145/356924.356930</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:10319214">10319214</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=ACM+Computing+Surveys&rft.atitle=The+quadtree+and+related+hierarchical+data+structures&rft.volume=16&rft.issue=2&rft.pages=%3Cspan+class%3D%22nowrap%22%3E187-%3C%2Fspan%3E260&rft.date=1984&rft_id=info%3Adoi%2F10.1145%2F356924.356930&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A10319214%23id-name%3DS2CID&rft.aulast=Samet&rft.aufirst=H.&rft_id=http%3A%2F%2Fwww.cs.umd.edu%2F~hjs%2Fpubs%2FSameCSUR84-ocr.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AQuadtree" class="Z3988"></span></span> </li> <li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFWarnock1969" class="citation journal cs1 cs1-prop-long-vol">Warnock, J. E. (1969). "A hidden surface algorithm for computer generated halftone pictures". <i>Computer Science Department, University of Utah</i>. TR 4-15.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Computer+Science+Department%2C+University+of+Utah&rft.atitle=A+hidden+surface+algorithm+for+computer+generated+halftone+pictures&rft.volume=TR+4-15&rft.date=1969&rft.aulast=Warnock&rft.aufirst=J.+E.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AQuadtree" class="Z3988"></span></span> </li> <li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFSchneier1981" class="citation journal cs1">Schneier, M. (1981). "Two hierarchical linear feature representations: edge pyramids and edge quadtrees". <i>Computer Graphics and Image Processing</i>. <b>17</b> (3). Elsevier: <span class="nowrap">211–</span>224. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0146-664X%2881%2990002-2">10.1016/0146-664X(81)90002-2</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Computer+Graphics+and+Image+Processing&rft.atitle=Two+hierarchical+linear+feature+representations%3A+edge+pyramids+and+edge+quadtrees&rft.volume=17&rft.issue=3&rft.pages=%3Cspan+class%3D%22nowrap%22%3E211-%3C%2Fspan%3E224&rft.date=1981&rft_id=info%3Adoi%2F10.1016%2F0146-664X%2881%2990002-2&rft.aulast=Schneier&rft.aufirst=M.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AQuadtree" class="Z3988"></span></span> </li> <li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><a href="/wiki/Hanan_Samet" title="Hanan Samet">Hanan Samet</a> and Robert Webber. "Storing a Collection of Polygons Using Quadtrees". <i>ACM Transactions on Graphics</i> July 1985: 182-222. <i>InfoLAB</i>. Web. 23 March 2012</span> </li> <li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFNelsonSamet1986" class="citation journal cs1">Nelson, R. C.; Samet, H. (1986). <a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F15886.15908">"A consistent hierarchical representation for vector data"</a>. <i>ACM SIGGRAPH Computer Graphics</i>. <b>20</b> (4): <span class="nowrap">197–</span>206. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F15886.15908">10.1145/15886.15908</a></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=ACM+SIGGRAPH+Computer+Graphics&rft.atitle=A+consistent+hierarchical+representation+for+vector+data&rft.volume=20&rft.issue=4&rft.pages=%3Cspan+class%3D%22nowrap%22%3E197-%3C%2Fspan%3E206&rft.date=1986&rft_id=info%3Adoi%2F10.1145%2F15886.15908&rft.aulast=Nelson&rft.aufirst=R.+C.&rft.au=Samet%2C+H.&rft_id=https%3A%2F%2Fdoi.org%2F10.1145%252F15886.15908&rfr_id=info%3Asid%2Fen.wikipedia.org%3AQuadtree" class="Z3988"></span></span> </li> <li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFHar-Peled2011" class="citation book cs1"><a href="/wiki/Sariel_Har-Peled" title="Sariel Har-Peled">Har-Peled, S.</a> (2011). "Quadtrees - Hierarchical Grids". <i>Geometric approximation algorithms</i>. Mathematical Surveys and Monographs Vol. 173, American mathematical society.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Quadtrees+-+Hierarchical+Grids&rft.btitle=Geometric+approximation+algorithms&rft.pub=Mathematical+Surveys+and+Monographs+Vol.+173%2C+American+mathematical+society&rft.date=2011&rft.aulast=Har-Peled&rft.aufirst=S.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AQuadtree" class="Z3988"></span></span> </li> <li id="cite_note-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-12">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFWantaSmolikKryszynWróblewski2021" class="citation journal cs1">Wanta, Damian; Smolik, Waldemar T.; Kryszyn, Jacek; Wróblewski, Przemysław; Midura, Mateusz (2021). <a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs40010-021-00748-7">"A Finite Volume Method using a Quadtree Non-Uniform Structured Mesh for Modeling in Electrical Capacitance Tomography"</a>. <i>Proceedings of the National Academy of Sciences, India Section A</i>. <b>92</b> (3): <span class="nowrap">443–</span>452. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs40010-021-00748-7">10.1007/s40010-021-00748-7</a></span>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:244224810">244224810</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Proceedings+of+the+National+Academy+of+Sciences%2C+India+Section+A&rft.atitle=A+Finite+Volume+Method+using+a+Quadtree+Non-Uniform+Structured+Mesh+for+Modeling+in+Electrical+Capacitance+Tomography&rft.volume=92&rft.issue=3&rft.pages=%3Cspan+class%3D%22nowrap%22%3E443-%3C%2Fspan%3E452&rft.date=2021&rft_id=info%3Adoi%2F10.1007%2Fs40010-021-00748-7&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A244224810%23id-name%3DS2CID&rft.aulast=Wanta&rft.aufirst=Damian&rft.au=Smolik%2C+Waldemar+T.&rft.au=Kryszyn%2C+Jacek&rft.au=Wr%C3%B3blewski%2C+Przemys%C5%82aw&rft.au=Midura%2C+Mateusz&rft_id=https%3A%2F%2Fdoi.org%2F10.1007%252Fs40010-021-00748-7&rfr_id=info%3Asid%2Fen.wikipedia.org%3AQuadtree" class="Z3988"></span></span> </li> <li id="cite_note-13"><span class="mw-cite-backlink"><b><a href="#cite_ref-13">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFSestoft2014" class="citation book cs1">Sestoft, Peter (2014). <i>Spreadsheet Implementation Technology: Basics and Extensions</i>. The MIT Press. pp. <span class="nowrap">60–</span>63. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/9780262526647" title="Special:BookSources/9780262526647"><bdi>9780262526647</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Spreadsheet+Implementation+Technology%3A+Basics+and+Extensions&rft.pages=%3Cspan+class%3D%22nowrap%22%3E60-%3C%2Fspan%3E63&rft.pub=The+MIT+Press&rft.date=2014&rft.isbn=9780262526647&rft.aulast=Sestoft&rft.aufirst=Peter&rfr_id=info%3Asid%2Fen.wikipedia.org%3AQuadtree" class="Z3988"></span></span> </li> <li id="cite_note-14"><span class="mw-cite-backlink"><b><a href="#cite_ref-14">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFTomas_G._Rokicki2006" class="citation web cs1">Tomas G. Rokicki (2006-04-01). <a rel="nofollow" class="external text" href="http://www.ddj.com/hpc-high-performance-computing/184406478">"An Algorithm for Compressing Space and Time"</a><span class="reference-accessdate">. Retrieved <span class="nowrap">2009-05-20</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=An+Algorithm+for+Compressing+Space+and+Time&rft.date=2006-04-01&rft.au=Tomas+G.+Rokicki&rft_id=http%3A%2F%2Fwww.ddj.com%2Fhpc-high-performance-computing%2F184406478&rfr_id=info%3Asid%2Fen.wikipedia.org%3AQuadtree" class="Z3988"></span></span> </li> <li id="cite_note-15"><span class="mw-cite-backlink"><b><a href="#cite_ref-15">^</a></b></span> <span class="reference-text">Henning Eberhardt, Vesa Klumpp, Uwe D. Hanebeck, <i>Density Trees for Efficient Nonlinear State Estimation</i>, Proceedings of the 13th International Conference on Information Fusion, Edinburgh, United Kingdom, July, 2010.</span> </li> <li id="cite_note-:0-16"><span class="mw-cite-backlink">^ <a href="#cite_ref-:0_16-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:0_16-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFSamet1989" class="citation journal cs1">Samet, H. (1989). "Hierarchical spatial data structures". <i>Symposium on Large Spatial Databases</i>: <span class="nowrap">191–</span>212.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Symposium+on+Large+Spatial+Databases&rft.atitle=Hierarchical+spatial+data+structures&rft.pages=%3Cspan+class%3D%22nowrap%22%3E191-%3C%2Fspan%3E212&rft.date=1989&rft.aulast=Samet&rft.aufirst=H.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AQuadtree" class="Z3988"></span></span> </li> <li id="cite_note-17"><span class="mw-cite-backlink"><b><a href="#cite_ref-17">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFHunter1978" class="citation book cs1">Hunter, G. M. (1978). <i>Efficient Computation and Data Structures for Graphics</i>. Ph.D. dissertation, Department of Electrical Engineering and Computer Science, Princeton University.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Efficient+Computation+and+Data+Structures+for+Graphics&rft.pub=Ph.D.+dissertation%2C+Department+of+Electrical+Engineering+and+Computer+Science%2C+Princeton+University&rft.date=1978&rft.aulast=Hunter&rft.aufirst=G.+M.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AQuadtree" class="Z3988"></span></span> </li> <li id="cite_note-18"><span class="mw-cite-backlink"><b><a href="#cite_ref-18">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFHunterSteiglitz1979" class="citation journal cs1">Hunter, G. M.; Steiglitz, K. (1979). "Operations on images using quad trees". <i>IEEE Transactions on Pattern Analysis and Machine Intelligence</i>. <b>2</b> (2): <span class="nowrap">145–</span>153. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2Ftpami.1979.4766900">10.1109/tpami.1979.4766900</a>. <a href="/wiki/PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/21868843">21868843</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2544535">2544535</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=IEEE+Transactions+on+Pattern+Analysis+and+Machine+Intelligence&rft.atitle=Operations+on+images+using+quad+trees&rft.volume=2&rft.issue=2&rft.pages=%3Cspan+class%3D%22nowrap%22%3E145-%3C%2Fspan%3E153&rft.date=1979&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A2544535%23id-name%3DS2CID&rft_id=info%3Apmid%2F21868843&rft_id=info%3Adoi%2F10.1109%2Ftpami.1979.4766900&rft.aulast=Hunter&rft.aufirst=G.+M.&rft.au=Steiglitz%2C+K.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AQuadtree" class="Z3988"></span></span> </li> <li id="cite_note-19"><span class="mw-cite-backlink"><b><a href="#cite_ref-19">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFSchneier1981" class="citation journal cs1">Schneier, M. (1981). "Calculations of geometric properties using quadtrees". <i>Computer Graphics and Image Processing</i>. <b>16</b> (3): <span class="nowrap">296–</span>302. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0146-664X%2881%2990042-3">10.1016/0146-664X(81)90042-3</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Computer+Graphics+and+Image+Processing&rft.atitle=Calculations+of+geometric+properties+using+quadtrees&rft.volume=16&rft.issue=3&rft.pages=%3Cspan+class%3D%22nowrap%22%3E296-%3C%2Fspan%3E302&rft.date=1981&rft_id=info%3Adoi%2F10.1016%2F0146-664X%2881%2990042-3&rft.aulast=Schneier&rft.aufirst=M.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AQuadtree" class="Z3988"></span></span> </li> <li id="cite_note-20"><span class="mw-cite-backlink"><b><a href="#cite_ref-20">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFMehta2007" class="citation book cs1">Mehta, Dinesh (2007). <i>Handbook of Data Structures and Applications</i>. Chapman and Hall/CRC Press. p. 397.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Handbook+of+Data+Structures+and+Applications&rft.pages=397&rft.pub=Chapman+and+Hall%2FCRC+Press&rft.date=2007&rft.aulast=Mehta&rft.aufirst=Dinesh&rfr_id=info%3Asid%2Fen.wikipedia.org%3AQuadtree" class="Z3988"></span></span> </li> <li id="cite_note-21"><span class="mw-cite-backlink"><b><a href="#cite_ref-21">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFSamet1981" class="citation journal cs1"><a href="/wiki/Hanan_Samet" title="Hanan Samet">Samet, H.</a> (1981). "Connected component labeling using quadtrees". <i>Journal of the ACM</i>. <b>28</b> (3): <span class="nowrap">487–</span>501. <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.77.2573">10.1.1.77.2573</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F322261.322267">10.1145/322261.322267</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:17485118">17485118</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+the+ACM&rft.atitle=Connected+component+labeling+using+quadtrees&rft.volume=28&rft.issue=3&rft.pages=%3Cspan+class%3D%22nowrap%22%3E487-%3C%2Fspan%3E501&rft.date=1981&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.77.2573%23id-name%3DCiteSeerX&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A17485118%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1145%2F322261.322267&rft.aulast=Samet&rft.aufirst=H.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AQuadtree" class="Z3988"></span></span> </li> <li id="cite_note-:1-22"><span class="mw-cite-backlink">^ <a href="#cite_ref-:1_22-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:1_22-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFSamet1988" class="citation book cs1">Samet, H. (1988). "An overview of quadtrees, octrees, and related hierarchical data structures". In Earnshaw, R. A. (ed.). <i>Theoretical Foundations of Computer Graphics and CAD</i>. Springer-Verlag. pp. <span class="nowrap">51–</span>68.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=An+overview+of+quadtrees%2C+octrees%2C+and+related+hierarchical+data+structures&rft.btitle=Theoretical+Foundations+of+Computer+Graphics+and+CAD&rft.pages=%3Cspan+class%3D%22nowrap%22%3E51-%3C%2Fspan%3E68&rft.pub=Springer-Verlag&rft.date=1988&rft.aulast=Samet&rft.aufirst=H.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AQuadtree" class="Z3988"></span></span> </li> <li id="cite_note-23"><span class="mw-cite-backlink"><b><a href="#cite_ref-23">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFTarjan1975" class="citation journal cs1">Tarjan, R. E. (1975). <a rel="nofollow" class="external text" href="http://www.csd.uwo.ca/~eschost/Teaching/07-08/CS445a/p215-tarjan.pdf">"Efficiency of a good but not linear set union algorithm"</a> <span class="cs1-format">(PDF)</span>. <i>Journal of the ACM</i>. <b>22</b> (2): <span class="nowrap">215–</span>225. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F321879.321884">10.1145/321879.321884</a>. <a href="/wiki/Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://hdl.handle.net/1813%2F5942">1813/5942</a></span>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:11105749">11105749</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+the+ACM&rft.atitle=Efficiency+of+a+good+but+not+linear+set+union+algorithm&rft.volume=22&rft.issue=2&rft.pages=%3Cspan+class%3D%22nowrap%22%3E215-%3C%2Fspan%3E225&rft.date=1975&rft_id=info%3Ahdl%2F1813%2F5942&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A11105749%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1145%2F321879.321884&rft.aulast=Tarjan&rft.aufirst=R.+E.&rft_id=http%3A%2F%2Fwww.csd.uwo.ca%2F~eschost%2FTeaching%2F07-08%2FCS445a%2Fp215-tarjan.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AQuadtree" class="Z3988"></span></span> </li> <li id="cite_note-:2-24"><span class="mw-cite-backlink">^ <a href="#cite_ref-:2_24-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:2_24-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFHar-Peled2011" class="citation book cs1">Har-Peled, S. (2011). "Good Triangulations and Meshing". <i>Geometric approximation algorithms</i>. Mathematical Surveys and Monographs Vol. 173, American mathematical society.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Good+Triangulations+and+Meshing&rft.btitle=Geometric+approximation+algorithms&rft.pub=Mathematical+Surveys+and+Monographs+Vol.+173%2C+American+mathematical+society&rft.date=2011&rft.aulast=Har-Peled&rft.aufirst=S.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AQuadtree" class="Z3988"></span></span> </li> <li id="cite_note-25"><span class="mw-cite-backlink"><b><a href="#cite_ref-25">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFde_BergCheongvan_KreveldOvermars2008" class="citation book cs1">de Berg, M.; Cheong, O.; van Kreveld, M.; Overmars, M. H. (2008). "Quadtrees Non-Uniform Mesh Generation". <i>Computational Geometry Algorithms and Applications</i> (3rd ed.). Springer-Verlag.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Quadtrees+Non-Uniform+Mesh+Generation&rft.btitle=Computational+Geometry+Algorithms+and+Applications&rft.edition=3rd&rft.pub=Springer-Verlag&rft.date=2008&rft.aulast=de+Berg&rft.aufirst=M.&rft.au=Cheong%2C+O.&rft.au=van+Kreveld%2C+M.&rft.au=Overmars%2C+M.+H.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AQuadtree" class="Z3988"></span></span> </li> </ol></div></div> <div class="mw-heading mw-heading3"><h3 id="General_references">General references</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Quadtree&action=edit&section=22" title="Edit section: General references"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ol><li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFRaphael_Finkel_and_J.L._Bentley1974" class="citation journal cs1"><a href="/wiki/Raphael_Finkel" title="Raphael Finkel">Raphael Finkel</a> and <a href="/wiki/J.L._Bentley" class="mw-redirect" title="J.L. Bentley">J.L. Bentley</a> (1974). "Quad Trees: A Data Structure for Retrieval on Composite Keys". <i>Acta Informatica</i>. <b>4</b> (1): <span class="nowrap">1–</span>9. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF00288933">10.1007/BF00288933</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:33019699">33019699</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Acta+Informatica&rft.atitle=Quad+Trees%3A+A+Data+Structure+for+Retrieval+on+Composite+Keys&rft.volume=4&rft.issue=1&rft.pages=%3Cspan+class%3D%22nowrap%22%3E1-%3C%2Fspan%3E9&rft.date=1974&rft_id=info%3Adoi%2F10.1007%2FBF00288933&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A33019699%23id-name%3DS2CID&rft.au=Raphael+Finkel+and+J.L.+Bentley&rfr_id=info%3Asid%2Fen.wikipedia.org%3AQuadtree" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFMark_de_Berg,_Marc_van_Kreveld,_Mark_Overmars,_and_Otfried_Schwarzkopf2000" class="citation book cs1"><a href="/wiki/Mark_de_Berg" title="Mark de Berg">Mark de Berg</a>, <a href="/wiki/Marc_van_Kreveld" title="Marc van Kreveld">Marc van Kreveld</a>, <a href="/wiki/Mark_Overmars" title="Mark Overmars">Mark Overmars</a>, and <a href="/wiki/Otfried_Schwarzkopf" class="mw-redirect" title="Otfried Schwarzkopf">Otfried Schwarzkopf</a> (2000). <span class="id-lock-registration" title="Free registration required"><a rel="nofollow" class="external text" href="https://archive.org/details/computationalgeo00berg"><i>Computational Geometry</i></a></span> (2nd revised ed.). <a href="/wiki/Springer-Verlag" class="mw-redirect" title="Springer-Verlag">Springer-Verlag</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/3-540-65620-0" title="Special:BookSources/3-540-65620-0"><bdi>3-540-65620-0</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Computational+Geometry&rft.edition=2nd+revised&rft.pub=Springer-Verlag&rft.date=2000&rft.isbn=3-540-65620-0&rft.au=Mark+de+Berg%2C+Marc+van+Kreveld%2C+Mark+Overmars%2C+and+Otfried+Schwarzkopf&rft_id=https%3A%2F%2Farchive.org%2Fdetails%2Fcomputationalgeo00berg&rfr_id=info%3Asid%2Fen.wikipedia.org%3AQuadtree" class="Z3988"></span><span class="cs1-maint citation-comment"><code class="cs1-code">{{<a href="/wiki/Template:Cite_book" title="Template:Cite book">cite book</a>}}</code>: CS1 maint: multiple names: authors list (<a href="/wiki/Category:CS1_maint:_multiple_names:_authors_list" title="Category:CS1 maint: multiple names: authors list">link</a>)</span> Chapter 14: Quadtrees: pp. 291–306.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFSametWebber1985" class="citation web cs1"><a href="/wiki/Hanan_Samet" title="Hanan Samet">Samet, Hanan</a>; Webber, Robert (July 1985). <a rel="nofollow" class="external text" href="http://infolab.usc.edu/csci585/Spring2008/den_ar/p182-samet.pdf">"Storing a Collection of Polygons Using Quadtrees"</a> <span class="cs1-format">(PDF)</span><span class="reference-accessdate">. Retrieved <span class="nowrap">23 March</span> 2012</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Storing+a+Collection+of+Polygons+Using+Quadtrees&rft.date=1985-07&rft.aulast=Samet&rft.aufirst=Hanan&rft.au=Webber%2C+Robert&rft_id=http%3A%2F%2Finfolab.usc.edu%2Fcsci585%2FSpring2008%2Fden_ar%2Fp182-samet.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AQuadtree" class="Z3988"></span></li></ol> <div class="navbox-styles"><style data-mw-deduplicate="TemplateStyles:r1129693374">.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}</style><style data-mw-deduplicate="TemplateStyles:r1236075235">.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}</style></div><div role="navigation" class="navbox" aria-labelledby="Tree_data_structures237" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374" /><style data-mw-deduplicate="TemplateStyles:r1239400231">.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}</style><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:CS_trees" title="Template:CS trees"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:CS_trees" title="Template talk:CS trees"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:CS_trees" title="Special:EditPage/Template:CS trees"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Tree_data_structures237" style="font-size:114%;margin:0 4em"><a href="/wiki/Tree_(abstract_data_type)" title="Tree (abstract data type)">Tree data structures</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Search_tree" title="Search tree">Search trees</a><br />(<a href="/wiki/Set_(abstract_data_type)" title="Set (abstract data type)">dynamic sets</a>/<a href="/wiki/Associative_array" title="Associative array">associative arrays</a>)</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/2%E2%80%933_tree" title="2–3 tree">2–3</a></li> <li><a href="/wiki/2%E2%80%933%E2%80%934_tree" title="2–3–4 tree">2–3–4</a></li> <li><a href="/wiki/AA_tree" title="AA tree">AA</a></li> <li><a href="/wiki/(a,b)-tree" class="mw-redirect" title="(a,b)-tree">(a,b)</a></li> <li><a href="/wiki/AVL_tree" title="AVL tree">AVL</a></li> <li><a href="/wiki/B-tree" title="B-tree">B</a></li> <li><a href="/wiki/B%2B_tree" title="B+ tree">B+</a></li> <li><a href="/wiki/B*-tree" class="mw-redirect" title="B*-tree">B*</a></li> <li><a href="/wiki/Bx-tree" title="Bx-tree">B<sup>x</sup></a></li> <li>(<a href="/wiki/Optimal_binary_search_tree" title="Optimal binary search tree">Optimal</a>) <a href="/wiki/Binary_search_tree" title="Binary search tree">Binary search</a></li> <li><a href="/wiki/Dancing_tree" title="Dancing tree">Dancing</a></li> <li><a href="/wiki/HTree" title="HTree">HTree</a></li> <li><a href="/wiki/Interval_tree" title="Interval tree">Interval</a></li> <li><a href="/wiki/Order_statistic_tree" title="Order statistic tree">Order statistic</a></li> <li><a href="/wiki/Palindrome_tree" title="Palindrome tree">Palindrome</a></li> <li>(<a href="/wiki/Left-leaning_red%E2%80%93black_tree" title="Left-leaning red–black tree">Left-leaning</a>) <a href="/wiki/Red%E2%80%93black_tree" title="Red–black tree">Red–black</a></li> <li><a href="/wiki/Scapegoat_tree" title="Scapegoat tree">Scapegoat</a></li> <li><a href="/wiki/Splay_tree" title="Splay tree">Splay</a></li> <li><a href="/wiki/T-tree" title="T-tree">T</a></li> <li><a href="/wiki/Treap" title="Treap">Treap</a></li> <li><a href="/wiki/UB-tree" title="UB-tree">UB</a></li> <li><a href="/wiki/Weight-balanced_tree" title="Weight-balanced tree">Weight-balanced</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Heap_(data_structure)" title="Heap (data structure)">Heaps</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Binary_heap" title="Binary heap">Binary</a></li> <li><a href="/wiki/Binomial_heap" title="Binomial heap">Binomial</a></li> <li><a href="/wiki/Brodal_queue" title="Brodal queue">Brodal</a></li> <li><a href="/wiki/D-ary_heap" title="D-ary heap"><i>d</i>-ary</a></li> <li><a href="/wiki/Fibonacci_heap" title="Fibonacci heap">Fibonacci</a></li> <li><a href="/wiki/Leftist_tree" title="Leftist tree">Leftist</a></li> <li><a href="/wiki/Pairing_heap" title="Pairing heap">Pairing</a></li> <li><a href="/wiki/Skew_binomial_heap" title="Skew binomial heap">Skew binomial</a></li> <li><a href="/wiki/Skew_heap" title="Skew heap">Skew</a></li> <li><a href="/wiki/Van_Emde_Boas_tree" title="Van Emde Boas tree">van Emde Boas</a></li> <li><a href="/wiki/Weak_heap" title="Weak heap">Weak</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Trie" title="Trie">Tries</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Ctrie" title="Ctrie">Ctrie</a></li> <li><a href="/wiki/C-trie" title="C-trie">C-trie (compressed ADT)</a></li> <li><a href="/wiki/Hash_tree_(persistent_data_structure)" title="Hash tree (persistent data structure)">Hash</a></li> <li><a href="/wiki/Radix_tree" title="Radix tree">Radix</a></li> <li><a href="/wiki/Suffix_tree" title="Suffix tree">Suffix</a></li> <li><a href="/wiki/Ternary_search_tree" title="Ternary search tree">Ternary search</a></li> <li><a href="/wiki/X-fast_trie" title="X-fast trie">X-fast</a></li> <li><a href="/wiki/Y-fast_trie" title="Y-fast trie">Y-fast</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Spatial_index" class="mw-redirect" title="Spatial index">Spatial</a> data partitioning trees</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Ball_tree" title="Ball tree">Ball</a></li> <li><a href="/wiki/BK-tree" title="BK-tree">BK</a></li> <li><a href="/wiki/BSP_tree" class="mw-redirect" title="BSP tree">BSP</a></li> <li><a href="/wiki/Cartesian_tree" title="Cartesian tree">Cartesian</a></li> <li><a href="/wiki/Hilbert_R-tree" title="Hilbert R-tree">Hilbert R</a></li> <li><a href="/wiki/K-d_tree" title="K-d tree"><i>k</i>-d</a> (<a href="/wiki/Implicit_k-d_tree" title="Implicit k-d tree">implicit <i>k</i>-d</a>)</li> <li><a href="/wiki/M-tree" title="M-tree">M</a></li> <li><a href="/wiki/Metric_tree" title="Metric tree">Metric</a></li> <li><a href="/wiki/MVP_tree" class="mw-redirect" title="MVP tree">MVP</a></li> <li><a href="/wiki/Octree" title="Octree">Octree</a></li> <li><a href="/wiki/PH-tree" title="PH-tree">PH</a></li> <li><a href="/wiki/Priority_R-tree" title="Priority R-tree">Priority R</a></li> <li><a class="mw-selflink selflink">Quad</a></li> <li><a href="/wiki/R-tree" title="R-tree">R</a></li> <li><a href="/wiki/R%2B_tree" title="R+ tree">R+</a></li> <li><a href="/wiki/R*_tree" class="mw-redirect" title="R* tree">R*</a></li> <li><a href="/wiki/Segment_tree" title="Segment tree">Segment</a></li> <li><a href="/wiki/Vantage-point_tree" title="Vantage-point tree">VP</a></li> <li><a href="/wiki/X-tree" title="X-tree">X</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other trees</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Cover_tree" title="Cover tree">Cover</a></li> <li><a href="/wiki/Exponential_tree" title="Exponential tree">Exponential</a></li> <li><a href="/wiki/Fenwick_tree" title="Fenwick tree">Fenwick</a></li> <li><a href="/wiki/Finger_tree" title="Finger tree">Finger</a></li> <li><a href="/wiki/Fractal_tree_index" title="Fractal tree index">Fractal tree index</a></li> <li><a href="/wiki/Fusion_tree" title="Fusion tree">Fusion</a></li> <li><a href="/wiki/Hash_calendar" title="Hash calendar">Hash calendar</a></li> <li><a href="/wiki/IDistance" title="IDistance">iDistance</a></li> <li><a href="/wiki/K-ary_tree" class="mw-redirect" title="K-ary tree">K-ary</a></li> <li><a href="/wiki/Left-child_right-sibling_binary_tree" title="Left-child right-sibling binary tree">Left-child right-sibling</a></li> <li><a href="/wiki/Link/cut_tree" title="Link/cut tree">Link/cut</a></li> <li><a href="/wiki/Log-structured_merge-tree" title="Log-structured merge-tree">Log-structured merge</a></li> <li><a href="/wiki/Merkle_tree" title="Merkle tree">Merkle</a></li> <li><a href="/wiki/PQ_tree" title="PQ tree">PQ</a></li> <li><a href="/wiki/Range_tree" title="Range tree">Range</a></li> <li><a href="/wiki/SPQR_tree" title="SPQR tree">SPQR</a></li> <li><a href="/wiki/Top_tree" title="Top tree">Top</a></li></ul> </div></td></tr></tbody></table></div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?useformat=desktop&type=1x1&usesul3=0" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Retrieved from "<a dir="ltr" href="https://en.wikipedia.org/w/index.php?title=Quadtree&oldid=1280122514">https://en.wikipedia.org/w/index.php?title=Quadtree&oldid=1280122514</a>"</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Help:Category" title="Help:Category">Categories</a>: <ul><li><a href="/wiki/Category:Trees_(data_structures)" title="Category:Trees (data structures)">Trees (data structures)</a></li><li><a href="/wiki/Category:Database_index_techniques" title="Category:Database index techniques">Database index techniques</a></li><li><a href="/wiki/Category:Geometric_data_structures" title="Category:Geometric data structures">Geometric data structures</a></li><li><a href="/wiki/Category:Rectangular_subdivisions" title="Category:Rectangular subdivisions">Rectangular subdivisions</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:CS1:_long_volume_value" title="Category:CS1: long volume value">CS1: long volume value</a></li><li><a href="/wiki/Category:Articles_with_short_description" title="Category:Articles with short description">Articles with short description</a></li><li><a href="/wiki/Category:Short_description_is_different_from_Wikidata" title="Category:Short description is different from Wikidata">Short description is different from Wikidata</a></li><li><a href="/wiki/Category:Wikipedia_references_cleanup_from_April_2015" title="Category:Wikipedia references cleanup from April 2015">Wikipedia references cleanup from April 2015</a></li><li><a href="/wiki/Category:All_articles_needing_references_cleanup" title="Category:All articles needing references cleanup">All articles needing references cleanup</a></li><li><a href="/wiki/Category:Articles_covered_by_WikiProject_Wikify_from_April_2015" title="Category:Articles covered by WikiProject Wikify from April 2015">Articles covered by WikiProject Wikify from April 2015</a></li><li><a href="/wiki/Category:All_articles_covered_by_WikiProject_Wikify" title="Category:All articles covered by WikiProject Wikify">All articles covered by WikiProject Wikify</a></li><li><a href="/wiki/Category:All_articles_with_unsourced_statements" title="Category:All articles with unsourced statements">All articles with unsourced statements</a></li><li><a href="/wiki/Category:Articles_with_unsourced_statements_from_June_2015" title="Category:Articles with unsourced statements from June 2015">Articles with unsourced statements from June 2015</a></li><li><a href="/wiki/Category:CS1_maint:_multiple_names:_authors_list" title="Category:CS1 maint: multiple names: authors list">CS1 maint: multiple names: authors list</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> This page was last edited on 12 March 2025, at 16:57<span class="anonymous-show"> (UTC)</span>.</li> <li id="footer-info-copyright">Text is available under the <a href="/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License" title="Wikipedia:Text of the Creative Commons Attribution-ShareAlike 4.0 International License">Creative Commons Attribution-ShareAlike 4.0 License</a>; additional terms may apply. By using this site, you agree to the <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use" class="extiw" title="foundation:Special:MyLanguage/Policy:Terms of Use">Terms of Use</a> and <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy" class="extiw" title="foundation:Special:MyLanguage/Policy:Privacy policy">Privacy Policy</a>. Wikipedia® is a registered trademark of the <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-profit organization.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Privacy policy</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:About">About Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:General_disclaimer">Disclaimers</a></li> <li id="footer-places-contact"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code of Conduct</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Developers</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/en.wikipedia.org">Statistics</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Cookie statement</a></li> <li id="footer-places-mobileview"><a href="//en.m.wikipedia.org/w/index.php?title=Quadtree&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile view</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><picture><source media="(min-width: 500px)" srcset="/static/images/footer/wikimedia-button.svg" width="84" height="29"><img src="/static/images/footer/wikimedia.svg" width="25" height="25" alt="Wikimedia Foundation" lang="en" loading="lazy"></picture></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><picture><source media="(min-width: 500px)" srcset="/w/resources/assets/poweredby_mediawiki.svg" width="88" height="31"><img src="/w/resources/assets/mediawiki_compact.svg" alt="Powered by MediaWiki" lang="en" width="25" height="25" loading="lazy"></picture></a></li> </ul> </footer> </div> </div> </div> <div class="vector-header-container vector-sticky-header-container"> <div id="vector-sticky-header" class="vector-sticky-header"> <div class="vector-sticky-header-start"> <div class="vector-sticky-header-icon-start vector-button-flush-left vector-button-flush-right" aria-hidden="true"> <button class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-sticky-header-search-toggle" tabindex="-1" data-event-name="ui.vector-sticky-search-form.icon"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </button> </div> <div role="search" class="vector-search-box-vue vector-search-box-show-thumbnail vector-search-box"> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail"> <form action="/w/index.php" id="vector-sticky-search-form" class="cdx-search-input cdx-search-input--has-end-button"> <div class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia"> <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <div class="vector-sticky-header-context-bar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-sticky-header-toc" class="vector-dropdown mw-portlet mw-portlet-sticky-header-toc vector-sticky-header-toc vector-button-flush-left" > <input type="checkbox" id="vector-sticky-header-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-sticky-header-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-sticky-header-toc-label" for="vector-sticky-header-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-sticky-header-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div class="vector-sticky-header-context-bar-primary" aria-hidden="true" ><span class="mw-page-title-main">Quadtree</span></div> </div> </div> <div class="vector-sticky-header-end" aria-hidden="true"> <div class="vector-sticky-header-icons"> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-talk-sticky-header" tabindex="-1" data-event-name="talk-sticky-header"><span class="vector-icon mw-ui-icon-speechBubbles mw-ui-icon-wikimedia-speechBubbles"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-subject-sticky-header" tabindex="-1" data-event-name="subject-sticky-header"><span class="vector-icon mw-ui-icon-article mw-ui-icon-wikimedia-article"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-history-sticky-header" tabindex="-1" data-event-name="history-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-history mw-ui-icon-wikimedia-wikimedia-history"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only mw-watchlink" id="ca-watchstar-sticky-header" tabindex="-1" data-event-name="watch-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-star mw-ui-icon-wikimedia-wikimedia-star"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-edit-sticky-header" tabindex="-1" data-event-name="wikitext-edit-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-wikiText mw-ui-icon-wikimedia-wikimedia-wikiText"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-ve-edit-sticky-header" tabindex="-1" data-event-name="ve-edit-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-edit mw-ui-icon-wikimedia-wikimedia-edit"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-viewsource-sticky-header" tabindex="-1" data-event-name="ve-edit-protected-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-editLock mw-ui-icon-wikimedia-wikimedia-editLock"></span> <span></span> </a> </div> <div class="vector-sticky-header-buttons"> <button class="cdx-button cdx-button--weight-quiet mw-interlanguage-selector" id="p-lang-btn-sticky-header" tabindex="-1" data-event-name="ui.dropdown-p-lang-btn-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-language mw-ui-icon-wikimedia-wikimedia-language"></span> <span>13 languages</span> </button> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive" id="ca-addsection-sticky-header" tabindex="-1" data-event-name="addsection-sticky-header"><span class="vector-icon mw-ui-icon-speechBubbleAdd-progressive mw-ui-icon-wikimedia-speechBubbleAdd-progressive"></span> <span>Add topic</span> </a> </div> <div class="vector-sticky-header-icon-end"> <div class="vector-user-links"> </div> </div> </div> </div> </div> <div class="mw-portlet mw-portlet-dock-bottom emptyPortlet" id="p-dock-bottom"> <ul> </ul> </div> <script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-fff85b7d-vnc8k","wgBackendResponseTime":197,"wgPageParseReport":{"limitreport":{"cputime":"0.506","walltime":"0.822","ppvisitednodes":{"value":2434,"limit":1000000},"postexpandincludesize":{"value":71361,"limit":2097152},"templateargumentsize":{"value":1613,"limit":2097152},"expansiondepth":{"value":12,"limit":100},"expensivefunctioncount":{"value":8,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":120527,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 572.982 1 -total"," 31.18% 178.658 1 Template:Reflist"," 22.01% 126.139 14 Template:Cite_journal"," 17.01% 97.441 1 Template:CS-Trees"," 15.15% 86.813 1 Template:Navbox"," 13.10% 75.074 1 Template:Short_description"," 8.30% 47.575 1 Template:Citation_style"," 8.27% 47.382 1 Template:Infobox_data_structure"," 8.19% 46.907 2 Template:Pagetype"," 7.52% 43.100 1 Template:Ambox"]},"scribunto":{"limitreport-timeusage":{"value":"0.287","limit":"10.000"},"limitreport-memusage":{"value":6787008,"limit":52428800}},"cachereport":{"origin":"mw-api-ext.codfw.next-5ffff6b79d-l6t7s","timestamp":"20250312165759","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Quadtree","url":"https:\/\/en.wikipedia.org\/wiki\/Quadtree","sameAs":"http:\/\/www.wikidata.org\/entity\/Q934791","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q934791","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2004-04-05T04:22:28Z","dateModified":"2025-03-12T16:57:58Z","image":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/8\/8b\/Point_quadtree.svg","headline":"tree data structure in which each internal node has exactly four children"}</script> </body> </html>