2e:null 2f:["$","title",null,{"children":"Finding text occlusion with quadtrees and r-trees | Benjamin Schmidt | Observable"}] 34:T557,md`# Finding text occlusion with quadtrees and r-trees Occlusion hides things that are blocked by another element. @fil's original notebook uses a brute-force approach to compare nodes. \`d3-quadtree\` allows you to make this process more efficient when searching across thousands of points. I started developing this method for [this web site visualizing a word2vec layout of street signs](http://creatingdata.benschmidt.org/streets), and wanted to refine it as I think about [deep scatterplots](https://observablehq.com/@bmschmidt/zoom-strategies-for-huge-scatterplots-with-three-js). Although the optimization for a few thousand points is trivial, it may matter with tens of thousands on canvas; and when [deep scatterplot zooming](https://observablehq.com/@bmschmidt/zoom-strategies-for-huge-scatterplots-with-three-js) is an issue, there are cases when this quadtree can be used to precalculate occlusion at different levels and retain labels as zooming continues without rerunning the entire set of occlusion code. This notebook contains some code preparatory for a d3.formatOcclusion method that you can call on data that has a '.bbox' element. Here I generate those from the canvas text, which gives a tighter box than the svg text method. The visualization below shows how this method works compared to other collision detection algorithms for labels. `35:T586,total = { drawn return md`## Algorithms The selector above lets you choose one of three methods. The current method, **"${which_visit}"** requires ${d3.format(",")(d3.sum(drawn.map(d => d.visited.length)))} comparisons to get occlusion for the ${d3.format(",")(N)} text elements in the svg on screen. Mousing over a point shows the bounding-box comparisons that were made to determine if that word was occluded. For brute force, it shows the true bounding boxes of individual words; for the quadtree methods, it shows both the quad extents that had to be checked and the *possible* bounding boxes, larger than the true ones, that the visit function uses based on the largest rectangles seen to this point. When a collision is found, that box is partially filled in. * Brute force checks all currently-laid out points; * \`visit\` is a method based on d3.quadtree's basic 'visit' function; * The third, optimized method selected by default is an expanded version of d3.quadtree.visit that allows the callback to break the visit loop entirely, and includes some optimizations to the search order from d3.quadtree.find. * The fourth, at @fil's suggestion, uses RBush, a library that implements r-tree indices that should work well for rectangular intersect queries. I've subclassed it so that you can visualize the quads compared in any given query--the results are strikingly different from quadtrees! ` }36:T5aa,md`## Performance The particular case here--1,900 points--is probably a little small to be useful. But purely looking at number of comparisons, my quad-tree method appears to perform perhaps slightly better than RBush: those two are followed by normal quadtree visit, with brute force (obviously) bringing up the rear. I think that in relatively sparse overlap cases RBush seems to work better, but in highly dense situation with relatively small labels, the adjusted quadtree formula may require only half as many searches. Of course, 'number of bounding box comparisons' is not the ideal metric; purely for performance, we'd rather just look at timing issues. But for understanding optimization possibilities in conjunction with this visualization, I find it useful. Another option I don't do, that would work in flat 2d visualizations like this, is simply to keep another canvas around and draw the rectangles onto it, and then check pixel values before drawing a new rectangle. I think this would probably be fast! You could even cut out the canvas and write directly to a type Uint8 buffer in javascript treated as two dimensions on insertion. I think this would be fast. But that approach is much less generalizable than the ones here, so I'm not implementing it, especially because for the cases where it's useful (a visualization frame with few enough pixels to fit on a computer screen) it doesn't really matter what you do, honestly. `37:T484,md` ## Explanation A quadtree searches for points, but labels are rectangles. The big challenge with this method is that labels may extend well away from their center points; or, that a placed label might be large enough to engulf an existing label. The solution is to not use points and quadtree.find, but instead to detect collisions, we traverse quads using quadtree.visit. Using their bounds, you can see if any points inside them could conceivably overlap with the bounding box of the object; that means you have to add the maximum width and height of known elements to quadtree size, since a label might spill out of its containing quad. The visualization below shows, on mouseover, the traversal order for each point. Although this requires many fewer word comparisons, it also requires a large number of quadtree comparisons as well. So I show both quad bounding boxes (blue squares) and text element bounding boxes (red rectangles--you can generally tell the word they're anchored to). In general, this seems to take perhaps 1/10 the number of comparisons as the naive method; and there should be some other advantages in the case of a zoom. `38:T75d,text_els = { let current_word = undefined; d3.select("#canvas2").on("mousemove", function() { const [x, y] = d3.mouse(this) const d = search_tree.find(x, y) if (d === current_word) { return } current_word = d; let foo = 0 const context = d3.select("#canvas2").node().getContext("2d") context.clearRect(0, 0, width, height) context.textAlign = "center" context.textBaseline = 'middle' context.globalAlpha = 1 context.font = `${d.size}px Times New Roman`; context.fillStyle = 'red' context.fillText(d.text, d._cx, d._cy) d.highlit = true; const bbox = d._bbox context.beginPath() context.strokeStyle='hotpink' context.globalAlpha = .5 context.lineWidth = 5 context.fillStyle = 'none' context.strokeRect(bbox[0] - 6, bbox[2] - 6, bbox[1] - bbox[0] +6 , bbox[3] - bbox[2] + 6) context.stroke() context.closePath() // Visualize the current element. animation[0].stop() let i = -1; function drawRects() { if (i >= d.visited.length) { animation[0].stop() return } const n = d.visited[i++] if (!n) {return} context.beginPath() context.globalAlpha = .66 context.strokeStyle = n.variety == "word" ? "orange": 'black' context.lineWidth = n.variety == "word" ? 4 : 2 context.fillStyle = (n.variety == "word" && n.overlaps) ? "red" : "none" context.rect(n.x0, n.y0, n.x1 - n.x0, n.y1 - n.y0) context.stroke() context.globalAlpha = (n.variety == "word" && n.overlaps) ? .3: 0 context.fill() context.globalAlpha = 1 context.closePath() } animation[0] = d3.interval(drawRects, 100) }) return svg }39:T4ca,formatOcclusion = function(data, sort_key) { var iter_order = order(data, sort_key) var labels; if (which_visit == "brute") { labels = [] iter_order.forEach((index, i) => { const datum = data[index] datum.visited = [] datum._occluded = labels.some((label, i) => { const [x0, x1, y0, y1] = label._bbox const overlaps = hasOverlaps(label._bbox, datum._bbox) datum.visited.push({x0, y0, x1, y1, variety : "word", overlaps}) return overlaps }) if (!datum._occluded) {labels.push(datum)} }) } else if (which_visit == "RBush") { const tree = new MyRBush(R_BUSH_PARAM); iter_order.forEach((index, i) => { const datum = data[index] datum.visited = [] datum._occluded = false if (tree.collides(datum)) { datum._occluded = true } else { tree.insert(datum) } }) data[0].tree = tree } else { labels = d3.quadtree() .x(d => (d._bbox[0] + d._bbox[1])/2) .y(d => (d._bbox[2] + d._bbox[3])/2); labels.extent([-80, -35], [width+80, height+35]) iter_order.forEach((index, i) => { insert_and_check(data[index], labels) data[index].order = i }) } }3a:T9a9,function insert_and_check(datum, quadtree) { const corners = datum._bbox // Visit every quadtree section that overlaps the bounding box: if it finds an overlap with a particular node, abandon ship. quadtree._max_width = quadtree._max_width || 0 quadtree._max_height = quadtree._max_height || 0 datum._occluded = false if (DEBUG) { datum.visited = [] } quadtree[which_visit]( (node, x0, y0, x1, y1) => { // Break in the event that it's the old quadtree visit algorithm. if (datum._occluded) {return true} if (DEBUG) { datum.visited.push({x0, y0, x1: x1, y1: y1, variety : "quad", overlaps: false}) } if (node.length) { // true if it's a node, not a leaf. // Check if we need to check children in this quadtree section. Returning true means halt search. const box_intersects_quad = hasOverlaps( corners, [x0 - quadtree._max_width/2, x1 + quadtree._max_width/2, y0 - quadtree._max_height/2, y1 + quadtree._max_height/2], ); if (!box_intersects_quad) { return true } else { datum.visited[datum.visited.length - 1].overlaps = true return undefined } } else { if (DEBUG) { const [x0, x1, y0, y1] = node.data._bbox const [x, y] = [(x0 + x1)/2, (y0 + y1)/2] datum.visited.push({x0, y0, x1, y1, variety: "word", word: node.data.text, overlaps: false}) // datum.visited.push({x0:x - quadtree._max_width/2, y0:y - quadtree._max_height/2, x1:x + quadtree._max_width/2, y1:y + quadtree._max_height/2, variety: "word", word: node.data.text, overlaps: false}) } if (hasOverlaps(corners, node.data._bbox)) { if (DEBUG) { datum.visited[datum.visited.length - 1].overlaps = true } datum._occluded = true return "break"; } } }, [quadtree.x()(datum), quadtree.y()(datum)]); // TODO: in zoom settings, sometimes you may want to add the point even if it isn't displayed to 'hold' the spot for later. if (!datum._occluded) { quadtree.add(datum) if (quadtree._max_width < corners[1] - corners[0]) { quadtree._max_width = (corners[1] - corners[0]) } if (quadtree._max_height < (corners[3] - corners[2])) { quadtree._max_height = corners[3] - corners[2] } } }3b:T7c0,visit2 = function(callback, target) { // a modified version of quadtree.visit // target is a set of [x,y] coordinates that determines which quads are visited first. // The callback returns one of three values. // If it's false, the search continues. // If it's truthy, quadrants below the current depth are ignored. // If it's "break", the quadtree visit sequence is immediately halted. (This is important // for, e.g., collision detection.) var quads = [], q, node = this._root, child, x0, y0, x1, y1, i, i_, x, y, response; if (target) { [x, y] = target } if (node) quads.push(new Quad(node, this._x0, this._y0, this._x1, this._y1)); while (q = quads.pop()) { response = callback(node = q.node, x0 = q.x0, y0 = q.y0, x1 = q.x1, y1 = q.y1) if (response == "break") {break} if (!response && node.length) { var xm = (x0 + x1) / 2, ym = (y0 + y1) / 2; // wheres keeps track of which node is in which position... see below. A kludge. const wheres = [] if (child = node[3]) quads.push(new Quad(child, xm, ym, x1, y1)) && wheres.unshift(3); if (child = node[2]) quads.push(new Quad(child, x0, ym, xm, y1)) && wheres.unshift(2); if (child = node[1]) quads.push(new Quad(child, xm, y0, x1, ym)) && wheres.unshift(1); if (child = node[0]) quads.push(new Quad(child, x0, y0, xm, ym)) && wheres.unshift(0); // quadtree.find uses the code below to figure out which quadrant to look in where i is // the index, directly; but that breaks when using the optimization from quadtree.visit // where unpopulated nodes are not visited. This could be optimized further. if (target && (i = (y >= ym) << 1 | (x >= xm))) { i_ = wheres.indexOf(i) if (i_ > 0) { q = quads[quads.length - 1]; quads[quads.length - 1] = quads[quads.length - 1 - i_]; quads[quads.length - 1 - i_] = q; } } } } return this; }3c:T690,set_bboxes = function() { // This is expensive, but can be done once. If zooming, we can simply store the aspect ratio, too... that's a later task. // In canvas or webGL, the way this is done will be quite different. // Even on different canvas providers, the bounding box may not be exactly the same because the better bbox standard isn't universally supported. context.textAlign = 'center' context.textBaseline = 'middle' data.forEach(function(d) { // if (d._bbox) {return} context.font = `${d.size}px Times New Roman` const ms = context.measureText(d.text) /* From SVG const bbox = this.getBBox(); // Set the corners, b/c that's what a quadtree needs. d._bbox = [bbox.x, bbox.x + bbox.width, bbox.y, bbox.y + bbox.height] */ // The better way to get a bbox. d._bbox = [d.tx - ms.actualBoundingBoxLeft, d.tx + ms.actualBoundingBoxRight, d.ty - ms.actualBoundingBoxAscent, d.ty + ms.actualBoundingBoxDescent ] if (isNaN(d._bbox[0])) { // Not all browsers support the full standard. d._bbox =[ d.tx - ms.width/2, d.tx + ms.width/2, d.ty - d.size*2/3, // Guess at the pixel ratio for the top and bottom based on the font size. d.ty + d.size*2/3 ] } // RBush has its own format. d.minX = d._bbox[0] d.maxX = d._bbox[1] d.maxY = d._bbox[3] d.minY = d._bbox[2] // [d.minX, d.maxX, d.minY, d.maxY] = d._bbox d._cx = d.tx // bbox.x + bbox.width/2 d._cy = d.ty // bbox.y + bbox.height/2 }) }3d:T48b,class MyRBush extends RBush { collides(new_node) { let node = this.data; new_node.visited = [] let cb = node // Allow search from datapoints const new_box = new_node._occluded ? this.toBBox(node) : new_node new_node.visited.push({ x0:cb.minX, x1: cb.maxX, y0: cb.minY, y1: cb.maxY, variety: node.leaf ? "word": "quad"}) if (!intersects(new_box, cb)) return false; const nodesToSearch = []; while (node) { for (let i = 0; i < node.children.length; i++) { const child = node.children[i]; const childBBox = node.leaf ? this.toBBox(child) : child; cb = childBBox new_node.visited.push({x0:cb.minX, x1: cb.maxX, y0: cb.minY, y1: cb.maxY, variety: node.leaf ? "word": "quad"}) if (intersects(new_box, childBBox)) { if (node.leaf || contains(new_box, childBBox)) return true; nodesToSearch.push(child); } } node = nodesToSearch.pop(); } } } 3e:T44c4,rwg_words = [ // Borrowed from xkcd password generator which borrowed it from wherever "ability","able","aboard","about","above","accept","accident","according", "account","accurate","acres","across","act","action","active","activity", "actual","actually","add","addition","additional","adjective","adult","adventure", "advice","affect","afraid","after","afternoon","again","against","age", "ago","agree","ahead","aid","air","airplane","alike","alive", "all","allow","almost","alone","along","aloud","alphabet","already", "also","although","am","among","amount","ancient","angle","angry", "animal","announced","another","answer","ants","any","anybody","anyone", "anything","anyway","anywhere","apart","apartment","appearance","apple","applied", "appropriate","are","area","arm","army","around","arrange","arrangement", "arrive","arrow","art","article","as","aside","ask","asleep", "at","ate","atmosphere","atom","atomic","attached","attack","attempt", "attention","audience","author","automobile","available","average","avoid","aware", "away","baby","back","bad","badly","bag","balance","ball", "balloon","band","bank","bar","bare","bark","barn","base", "baseball","basic","basis","basket","bat","battle","be","bean", "bear","beat","beautiful","beauty","became","because","become","becoming", "bee","been","before","began","beginning","begun","behavior","behind", "being","believed","bell","belong","below","belt","bend","beneath", "bent","beside","best","bet","better","between","beyond","bicycle", "bigger","biggest","bill","birds","birth","birthday","bit","bite", "black","blank","blanket","blew","blind","block","blood","blow", "blue","board","boat","body","bone","book","border","born", "both","bottle","bottom","bound","bow","bowl","box","boy", "brain","branch","brass","brave","bread","break","breakfast","breath", "breathe","breathing","breeze","brick","bridge","brief","bright","bring", "broad","broke","broken","brother","brought","brown","brush","buffalo", "build","building","built","buried","burn","burst","bus","bush", "business","busy","but","butter","buy","by","cabin","cage", "cake","call","calm","came","camera","camp","can","canal", "cannot","cap","capital","captain","captured","car","carbon","card", "care","careful","carefully","carried","carry","case","cast","castle", "cat","catch","cattle","caught","cause","cave","cell","cent", "center","central","century","certain","certainly","chain","chair","chamber", "chance","change","changing","chapter","character","characteristic","charge","chart", "check","cheese","chemical","chest","chicken","chief","child","children", "choice","choose","chose","chosen","church","circle","circus","citizen", "city","class","classroom","claws","clay","clean","clear","clearly", "climate","climb","clock","close","closely","closer","cloth","clothes", "clothing","cloud","club","coach","coal","coast","coat","coffee", "cold","collect","college","colony","color","column","combination","combine", "come","comfortable","coming","command","common","community","company","compare", "compass","complete","completely","complex","composed","composition","compound","concerned", "condition","congress","connected","consider","consist","consonant","constantly","construction", "contain","continent","continued","contrast","control","conversation","cook","cookies", "cool","copper","copy","corn","corner","correct","correctly","cost", "cotton","could","count","country","couple","courage","course","court", "cover","cow","cowboy","crack","cream","create","creature","crew", "crop","cross","crowd","cry","cup","curious","current","curve", "customs","cut","cutting","daily","damage","dance","danger","dangerous", "dark","darkness","date","daughter","dawn","day","dead","deal", "dear","death","decide","declared","deep","deeply","deer","definition", "degree","depend","depth","describe","desert","design","desk","detail", "determine","develop","development","diagram","diameter","did","die","differ", "difference","different","difficult","difficulty","dig","dinner","direct","direction", "directly","dirt","dirty","disappear","discover","discovery","discuss","discussion", "disease","dish","distance","distant","divide","division","do","doctor", "does","dog","doing","doll","dollar","done","donkey","door", "dot","double","doubt","down","dozen","draw","drawn","dream", "dress","drew","dried","drink","drive","driven","driver","driving", "drop","dropped","drove","dry","duck","due","dug","dull", "during","dust","duty","each","eager","ear","earlier","early", "earn","earth","easier","easily","east","easy","eat","eaten", "edge","education","effect","effort","egg","eight","either","electric", "electricity","element","elephant","eleven","else","empty","end","enemy", "energy","engine","engineer","enjoy","enough","enter","entire","entirely", "environment","equal","equally","equator","equipment","escape","especially","essential", "establish","even","evening","event","eventually","ever","every","everybody", "everyone","everything","everywhere","evidence","exact","exactly","examine","example", "excellent","except","exchange","excited","excitement","exciting","exclaimed","exercise", "exist","expect","experience","experiment","explain","explanation","explore","express", "expression","extra","eye","face","facing","fact","factor","factory", "failed","fair","fairly","fall","fallen","familiar","family","famous", "far","farm","farmer","farther","fast","fastened","faster","fat", "father","favorite","fear","feathers","feature","fed","feed","feel", "feet","fell","fellow","felt","fence","few","fewer","field", "fierce","fifteen","fifth","fifty","fight","fighting","figure","fill", "film","final","finally","find","fine","finest","finger","finish", "fire","fireplace","firm","first","fish","five","fix","flag", "flame","flat","flew","flies","flight","floating","floor","flow", "flower","fly","fog","folks","follow","food","foot","football", "for","force","foreign","forest","forget","forgot","forgotten","form", "former","fort","forth","forty","forward","fought","found","four", "fourth","fox","frame","free","freedom","frequently","fresh","friend", "friendly","frighten","frog","from","front","frozen","fruit","fuel", "full","fully","fun","function","funny","fur","furniture","further", "future","gain","game","garage","garden","gas","gasoline","gate", "gather","gave","general","generally","gentle","gently","get","getting", "giant","gift","girl","give","given","giving","glad","glass", "globe","go","goes","gold","golden","gone","good","goose", "got","government","grabbed","grade","gradually","grain","grandfather","grandmother", "graph","grass","gravity","gray","great","greater","greatest","greatly", "green","grew","ground","group","grow","grown","growth","guard", "guess","guide","gulf","gun","habit","had","hair","half", "halfway","hall","hand","handle","handsome","hang","happen","happened", "happily","happy","harbor","hard","harder","hardly","has","hat", "have","having","hay","he","headed","heading","health","heard", "hearing","heart","heat","heavy","height","held","hello","help", "helpful","her","herd","here","herself","hidden","hide","high", "higher","highest","highway","hill","him","himself","his","history", "hit","hold","hole","hollow","home","honor","hope","horn", "horse","hospital","hot","hour","house","how","however","huge", "human","hundred","hung","hungry","hunt","hunter","hurried","hurry", "hurt","husband","ice","idea","identity","if","ill","image", "imagine","immediately","importance","important","impossible","improve","in","inch", "include","including","income","increase","indeed","independent","indicate","individual", "industrial","industry","influence","information","inside","instance","instant","instead", "instrument","interest","interior","into","introduced","invented","involved","iron", "is","island","it","its","itself","jack","jar","jet", "job","join","joined","journey","joy","judge","jump","jungle", "just","keep","kept","key","kids","kill","kind","kitchen", "knew","knife","know","knowledge","known","label","labor","lack", "lady","laid","lake","lamp","land","language","large","larger", "largest","last","late","later","laugh","law","lay","layers", "lead","leader","leaf","learn","least","leather","leave","leaving", "led","left","leg","length","lesson","let","letter","level", "library","lie","life","lift","light","like","likely","limited", "line","lion","lips","liquid","list","listen","little","live", "living","load","local","locate","location","log","lonely","long", "longer","look","loose","lose","loss","lost","lot","loud", "love","lovely","low","lower","luck","lucky","lunch","lungs", "lying","machine","machinery","mad","made","magic","magnet","mail", "main","mainly","major","make","making","man","managed","manner", "manufacturing","many","map","mark","market","married","mass","massage", "master","material","mathematics","matter","may","maybe","me","meal", "mean","means","meant","measure","meat","medicine","meet","melted", "member","memory","men","mental","merely","met","metal","method", "mice","middle","might","mighty","mile","military","milk","mill", "mind","mine","minerals","minute","mirror","missing","mission","mistake", "mix","mixture","model","modern","molecular","moment","money","monkey", "month","mood","moon","more","morning","most","mostly","mother", "motion","motor","mountain","mouse","mouth","move","movement","movie", "moving","mud","muscle","music","musical","must","my","myself", "mysterious","nails","name","nation","national","native","natural","naturally", "nature","near","nearby","nearer","nearest","nearly","necessary","neck", "needed","needle","needs","negative","neighbor","neighborhood","nervous","nest", "never","new","news","newspaper","next","nice","night","nine", "no","nobody","nodded","noise","none","noon","nor","north", "nose","not","note","noted","nothing","notice","noun","now", "number","numeral","nuts","object","observe","obtain","occasionally","occur", "ocean","of","off","offer","office","officer","official","oil", "old","older","oldest","on","once","one","only","onto", "open","operation","opinion","opportunity","opposite","or","orange","orbit", "order","ordinary","organization","organized","origin","original","other","ought", "our","ourselves","out","outer","outline","outside","over","own", "owner","oxygen","pack","package","page","paid","pain","paint", "pair","palace","pale","pan","paper","paragraph","parallel","parent", "park","part","particles","particular","particularly","partly","parts","party", "pass","passage","past","path","pattern","pay","peace","pen", "pencil","people","per","percent","perfect","perfectly","perhaps","period", "person","personal","pet","phrase","physical","piano","pick","picture", "pictured","pie","piece","pig","pile","pilot","pine","pink", "pipe","pitch","place","plain","plan","plane","planet","planned", "planning","plant","plastic","plate","plates","play","pleasant","please", "pleasure","plenty","plural","plus","pocket","poem","poet","poetry", "point","pole","police","policeman","political","pond","pony","pool", "poor","popular","population","porch","port","position","positive","possible", "possibly","post","pot","potatoes","pound","pour","powder","power", "powerful","practical","practice","prepare","present","president","press","pressure", "pretty","prevent","previous","price","pride","primitive","principal","principle", "printed","private","prize","probably","problem","process","produce","product", "production","program","progress","promised","proper","properly","property","protection", "proud","prove","provide","public","pull","pupil","pure","purple", "purpose","push","put","putting","quarter","queen","question","quick", "quickly","quiet","quietly","quite","rabbit","race","radio","railroad", "rain","raise","ran","ranch","range","rapidly","rate","rather", "raw","rays","reach","read","reader","ready","real","realize", "rear","reason","recall","receive","recent","recently","recognize","record", "red","refer","refused","region","regular","related","relationship","religious", "remain","remarkable","remember","remove","repeat","replace","replied","report", "represent","require","research","respect","rest","result","return","review", "rhyme","rhythm","rice","rich","ride","riding","right","ring", "rise","rising","river","road","roar","rock","rocket","rocky", "rod","roll","roof","room","root","rope","rose","rough", "round","route","row","rubbed","rubber","rule","ruler","run", "running","rush","sad","saddle","safe","safety","said","sail", "sale","salmon","salt","same","sand","sang","sat","satellites", "satisfied","save","saved","saw","say","scale","scared","scene", "school","science","scientific","scientist","score","screen","sea","search", "season","seat","second","secret","section","see","seed","seeing", "seems","seen","seldom","select","selection","sell","send","sense", "sent","sentence","separate","series","serious","serve","service","sets", "setting","settle","settlers","seven","several","shade","shadow","shake", "shaking","shall","shallow","shape","share","sharp","she","sheep", "sheet","shelf","shells","shelter","shine","shinning","ship","shirt", "shoe","shoot","shop","shore","short","shorter","shot","should", "shoulder","shout","show","shown","shut","sick","sides","sight", "sign","signal","silence","silent","silk","silly","silver","similar", "simple","simplest","simply","since","sing","single","sink","sister", "sit","sitting","situation","six","size","skill","skin","sky", "slabs","slave","sleep","slept","slide","slight","slightly","slip", "slipped","slope","slow","slowly","small","smaller","smallest","smell", "smile","smoke","smooth","snake","snow","so","soap","social", "society","soft","softly","soil","solar","sold","soldier","solid", "solution","solve","some","somebody","somehow","someone","something","sometime", "somewhere","son","song","soon","sort","sound","source","south", "southern","space","speak","special","species","specific","speech","speed", "spell","spend","spent","spider","spin","spirit","spite","split", "spoken","sport","spread","spring","square","stage","stairs","stand", "standard","star","stared","start","state","statement","station","stay", "steady","steam","steel","steep","stems","step","stepped","stick", "stiff","still","stock","stomach","stone","stood","stop","stopped", "store","storm","story","stove","straight","strange","stranger","straw", "stream","street","strength","stretch","strike","string","strip","strong", "stronger","struck","structure","struggle","stuck","student","studied","studying", "subject","substance","success","successful","such","sudden","suddenly","sugar", "suggest","suit","sum","summer","sun","sunlight","supper","supply", "support","suppose","sure","surface","surprise","surrounded","swam","sweet", "swept","swim","swimming","swing","swung","syllable","symbol","system", "table","tail","take","taken","tales","talk","tall","tank", "tape","task","taste","taught","tax","tea","teach","teacher", "team","tears","teeth","telephone","television","tell","temperature","ten", "tent","term","terrible","test","than","thank","that","thee", "them","themselves","then","theory","there","therefore","these","they", "thick","thin","thing","think","third","thirty","this","those", "thou","though","thought","thousand","thread","three","threw","throat", "through","throughout","throw","thrown","thumb","thus","thy","tide", "tie","tight","tightly","till","time","tin","tiny","tip", "tired","title","to","tobacco","today","together","told","tomorrow", "tone","tongue","tonight","too","took","tool","top","topic", "torn","total","touch","toward","tower","town","toy","trace", "track","trade","traffic","trail","train","transportation","trap","travel", "treated","tree","triangle","tribe","trick","tried","trip","troops", "tropical","trouble","truck","trunk","truth","try","tube","tune", "turn","twelve","twenty","twice","two","type","typical","uncle", "under","underline","understanding","unhappy","union","unit","universe","unknown", "unless","until","unusual","up","upon","upper","upward","us", "use","useful","using","usual","usually","valley","valuable","value", "vapor","variety","various","vast","vegetable","verb","vertical","very", "vessels","victory","view","village","visit","visitor","voice","volume", "vote","vowel","voyage","wagon","wait","walk","wall","want", "war","warm","warn","was","wash","waste","watch","water", "wave","way","we","weak","wealth","wear","weather","week", "weigh","weight","welcome","well","went","were","west","western", "wet","whale","what","whatever","wheat","wheel","when","whenever", "where","wherever","whether","which","while","whispered","whistle","white", "who","whole","whom","whose","why","wide","widely","wife", "wild","will","willing","win","wind","window","wing","winter", "wire","wise","wish","with","within","without","wolf","women", "won","wonder","wonderful","wood","wooden","wool","word","wore", "work","worker","world","worried","worry","worse","worth","would", "wrapped","write","writer","writing","written","wrong","wrote","yard", "year","yellow","yes","yesterday","yet","you","young","younger", "your","yourself","youth","zero","zebra","zipper","zoo","zulu" ]3f:[] 32:{"id":"76b2912dd9879cbc","slug":"finding-text-occlusion-with-quadtrees","title":"Finding text occlusion with quadtrees and r-trees","thumbnail":"4433e1d7b106da74fe82b2a395290297a130991ca97131badc0f2e2129341c81","access_level":"public","create_time":"$D2020-01-13T15:48:29.888Z","update_time":"$D2022-02-15T14:52:13.951Z","view_time":null,"first_public_time":"$D2020-01-15T19:49:45.573Z","has_unpublished_edits":null,"fork":{"id":"56a170de7e71a28e","slug":"occlusion","title":"Occlusion","owner":{"id":"863951e3ebe4c0ae","login":"d3","name":"D3"}},"stars":35,"starred":false,"owner":{"type":"team","id":"18bbeceb36c8f564","login":"bmschmidt","name":"Benjamin Schmidt","avatar_url":"https://avatars-next.observableusercontent.com/addc2adb5ec95cc72a64820e4a08488bad5d48d95a895eef85a45b136ed66792","tier":"starter_2024"},"version":1357,"publish_version":1357,"role":null,"authored":false,"authors":[{"type":"individual","id":"33354ca265b21f01","login":"bmschmidt","name":"Benjamin Schmidt","avatar_url":"https://avatars-next.observableusercontent.com/addc2adb5ec95cc72a64820e4a08488bad5d48d95a895eef85a45b136ed66792","tier":null}],"members":[{"type":"individual","id":"33354ca265b21f01","login":"bmschmidt","name":"Benjamin Schmidt","avatar_url":"https://avatars-next.observableusercontent.com/addc2adb5ec95cc72a64820e4a08488bad5d48d95a895eef85a45b136ed66792","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":13,"collection":{"id":"129de12642a17c31","slug":"deep-scatterplots","title":"Deep Scatterplots","owner":{"id":"18bbeceb36c8f564","login":"bmschmidt","name":"Benjamin Schmidt"}},"type":"notebook","body":{"title":"Finding text occlusion with quadtrees and r-trees","cells":[{"id":0,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":711,"value":"visualization = html`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":877,"value":"viewof which_visit = radio({options: [{label: \"Brute force\", value: \"brute\"}, {label: \"quadtree 'visit'\", value:\"visit\"}, {label: \"d3.quadtree 'visit' with traversal order optimization\", value:\"visit2\"}, {\"label\": \"RBush library detection\", value: \"RBush\"}], value: \"visit2\", title: \"Comparison algorithm\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":944,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1110,"value":"$36","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1316,"value":"md`## Change number of items\n\nThe slider below changes the number of items up to 10,000. Be careful that you don't clobber your device!`","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1299,"value":"viewof N = html``\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":964,"value":"$37","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":5,"value":"svg = {\n const svg = d3.select(\"#svg\")\n return svg\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1121,"value":"canvas = d3.select(\"canvas\").node()","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1126,"value":"context = canvas.getContext('2d')","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1128,"value":"drawn = {\n set_bboxes()\n occlusion(data)\n render_canvas()\n return data\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1205,"value":"function render_canvas() {\n context.clearRect(0, 0, width, height)\n context.textAlign = \"center\";\n context.textBaseline = 'middle' \n data.forEach( d=> {\n context.font = `${d.size}px Times New Roman`; \n context.globalAlpha = d._occluded ? 0.15 : 1\n context.fillStyle = 'black'\n context.fillText(d.text, d._cx, d._cy)\n })\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":222,"value":"function hasOverlaps(corners, compCorners) {\n // mutable n_checks += 1\n // Do the ys first, because they're more likely to be false in landscape-oriented elements and this function is usually false.\n // For portrait-oriented, would be better to reverse this. But I don't know if it matters.\n return (corners[2] < compCorners[3] &&\n corners[3] > compCorners[2] &&\n corners[0] < compCorners[1] &&\n corners[1] > compCorners[0]);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":571,"value":"data = {\n const words = []\n for (let i = 0; i < N; i++) {\n words.push(rwg_words[Math.floor(Math.random()*rwg_words.length)])\n }\n d3.shuffle(words)\n return words.map(d => {\n return {\n text: d, priority: Math.random(), \"tx\": Math.random() * width, \"ty\": Math.random()* height,\n size: Math.sqrt((Math.random() + .5) * 332)}\n}).slice(0, N)\n \n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":775,"value":"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":261,"value":"function order(data, sort_key = d => d) {\n return Array.from(Array(data.length).keys())\n .sort((a, b) => sort_key(data[a]) < sort_key(data[b]) ? -1 : (sort_key(data[b]) < sort_key(data[a])) | 0)\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1200,"value":"search_tree = {\n \n // A quadtree used for lookups on the canvas--different than the label occlusion one, though it doesn't have to be.\n const tree = d3.quadtree().x(d => d._cx).y(d => d._cy)\n tree.addAll(drawn)\n return tree\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1237,"value":"function bbox_to_coords(bbox) {\n return [bbox[0], bbox[2], bbox[1] - bbox[0], bbox[3] - bbox[2]]\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1328,"value":"md`A slot to store in-progress animations. There's probably a better way to do this with 'mutable' than hiding it in an array, but this works...` \n","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1240,"value":"animation = [d3.interval(function () {}, 1000)]","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1017,"value":"md`## Canvas rendering code`","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":197,"value":"$38","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":622,"value":"drawn_old = {\n drawn\n text_els\n return occlusion(data)\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":58,"value":"html``","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":166,"value":"$39","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":208,"value":"$3a","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":957,"value":"md`## Visit algorithm\n\nHere I rewrite the quadtree 'visit' algorithm to allow traversal order to not just be upper-right to lower-right, and to allow the callback to escape further exploration of the function if it returns 'break'.\n\n`","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":879,"value":"$3b","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":778,"value":"Quad = function(node, x0, y0, x1, y1) {\n // From d3-quadtree: need this rewrite visit.\n this.node = node;\n this.x0 = x0;\n this.y0 = y0;\n this.x1 = x1;\n this.y1 = y1;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":720,"value":"DEBUG = true","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":22,"value":"height = 500","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":168,"value":"$3c","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1098,"value":"R_BUSH_PARAM = 2 // A low number maximizes RBush's performance on the metric here at the cost of insertion performance, which is the fair thing to do here. Although the higher numbers aren't much worse, really. ","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":26,"value":"function occlusion(data) {\n formatOcclusion(data, d => -d.priority)\n return data\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"d3 = require(\"d3@5\").then(d3 => {\n // patch with the new visit function\n d3.quadtree.prototype.visit2 = visit2\n return d3\n })\n","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":936,"value":"import {radio} from \"@jashkenas/inputs\"\n","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1035,"value":"$3d","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1055,"value":"function box_to_corners(box) {\n const oput = []\n for (const x of box.slice(0, 2)) {\n for (const y of box.slice(2, 4)) {\n oput.push([x,y])\n }\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1052,"value":"function contains(a, b) {\n return a.minX <= b.minX &&\n a.minY <= b.minY &&\n b.maxX <= a.maxX &&\n b.maxY <= a.maxY;\n}\n","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1048,"value":"function intersects(a, b) {\n // from RBush\n return b.minX <= a.maxX &&\n b.minY <= a.maxY &&\n b.maxX >= a.minX &&\n b.maxY >= a.minY;\n}\n","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1033,"value":"RBush = require('rbush')","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":9,"value":"$3e","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W3f","stdlib":"1","titling":"auto"}} 33:"$32:body"