2c:null 2d:["$","title",null,{"children":"[DEPRECATED] Non-overlapping Aggregated Multivariate Glyphs for Moving Objects | Fati CHEN | Observable"}] 32:T477,signature(merge, { description: md` ${html`

function MERGE(K)  
  while ${tex`\exist_{(S,T)\in K\times K}{\omega(S,T) \gt 0}`} do
    ${tex`(S, T) \leftarrow`} pair with maximal overlap ${tex`\omega(S,T)`}
    ${tex`K ← (K \setminus \{S,T\})∪\{S∪T\}`}
  return ${tex`K`}

`} I tried to respect that but some parts don't make sense : > For performance improvement of Algorithm 1, a binary Search Tree (BST) sorted on the overlap measure ${tex`\omega`} of pairs ${tex`(S,N(S))`} is maintained, where ${tex`N(S)`} is a nearest neighbour of ${tex`S`} in the sense that for no other subset ${tex`T`} ${tex`\omega(S,T)`} is larger than ${tex`\omega(T,N(S))`}. Whenever such a pair or its overlap measure changes, its position within the tree is updated. The pair with the largest overlap is now simply the right-most node in the tree. To find the nearest neighbor of a subset efficiently, the subsets are stored in a _k_-d tree [12] based on the position of their centroids. Whenever two subsets are merged, the _k_-d tree is incrementally updated. _why do I need a k-d tree if I need to check against all ${tex`T`} subsets_ ` })33:Tcb7,async function* merge(K) { const tree = new BST(BSTOptions); // const kdtree = new kd.kdTree(K, distance, ['x', 'y']); const Klinks = new Map(); const activeK = new Map(); const so = new Map(); function pretendents(S) { const P = []; activeK.forEach((T) => { const o = omega(S, T); if (o > 0 && T !== S) P.push([T, o]); }); return P; } function set(couple) { const [S, T] = couple; // console.log('set:', couple); updateSingle(S.id, T.id); updateSingle(T.id, S.id); so.set(S.id, couple); function updateSingle(Sid, Tid) { const Sside = Klinks.get(Sid); if (Sside) Sside.set(Tid, couple); else Klinks.set(Sid, new Map([[Tid, couple]])); } } function clean([S, T]) { // console.log('del:', S, T); so.delete(S.id); so.delete(T.id); cleanSingle(S.id); cleanSingle(T.id); function cleanSingle(Sid) { Klinks.get(Sid).forEach((couple, Tid) => { so.delete(Tid); tree.remove(couple); const Tside = Klinks.get(Tid); if (Tside.length === 1) Klinks.delete(Tid); else Klinks.get(Tid).delete(Sid); }); Klinks.delete(Sid); activeK.delete(Sid); } } function add(T) { const P = pretendents(T); //all subsets where omega(S, newbie) > 0 // console.log('add', T); activeK.set(T.id, T); if (P.length === 0) return; let bestPartner = null; // rewire other links P.forEach((partner) => { const [S, o] = partner; bestPartner = bestPartner && bestPartner[1] > o ? bestPartner : partner; const couple = so.get(S.id); // S is in a relationship if (!couple) { const dating = join(S, T, o); set(dating); tree.insert(dating); } if (couple && breakup(couple, T, o)) { // console.log("del:", couple); // the relationship with S -> newbie is better // remove old relation if (Klinks.has(couple[0].id)) Klinks.get(couple[0].id).delete(couple[1].id); if (Klinks.has(couple[1].id)) Klinks.get(couple[1].id).delete(couple[0].id); tree.remove(couple); // set (S -> newbie) as an new couple const dating = join(S, T, o); set(dating); tree.insert(dating); } }); let best = false; let dating = join(T, ...bestPartner); while (!best) { best = true; for (let i = 0; i < P.length; i++) { const pretendent = P[i]; if (breakup(dating, ...pretendent)) { dating = join(T, ...pretendent); best = false; break; } } } set(dating); tree.insert(dating); } let idx = 0; K.forEach(add); console.log(rollup(tree)); while (tree.max) { if (interactive) yield Promises.delay(delay, [ [...activeK.values()], rollup(tree), Klinks ]); const chosen = tree.max.value._m.values().next().value; // console.log("merge", chosen.id); const cluster = fuse(idx++, chosen); // remove all the links associated to S and T from Klinks and tree clean(chosen); // and reconstruct add(cluster); } yield [[...activeK.values()], rollup(tree), Klinks]; }34:[{"id":"ec3363a3a61879d81396ca69f5f6a2fe12881dd6c26a261fb2f7ff87852efe87ca0fe1dabf7c9d205fc6c12fbf2c055207163098d33381f9aab30e67541b0bfd","href":"https://static.observableusercontent.com/files/ec3363a3a61879d81396ca69f5f6a2fe12881dd6c26a261fb2f7ff87852efe87ca0fe1dabf7c9d205fc6c12fbf2c055207163098d33381f9aab30e67541b0bfd","name":"image.png","type":"image/png","lastModified":1614089106867.106,"size":6705},{"id":"c72312af71237b2a3cfa263d954da5d3193cf1d7e1e9dca87ca0aab1f08f855aebadfdf65cda711e86d9413c5b8f6ca7b573eb00c843f5457d6cc0cf2f7b36a4","href":"https://static.observableusercontent.com/files/c72312af71237b2a3cfa263d954da5d3193cf1d7e1e9dca87ca0aab1f08f855aebadfdf65cda711e86d9413c5b8f6ca7b573eb00c843f5457d6cc0cf2f7b36a4","name":"untitled (3).json","type":"application/json","lastModified":1620919208747.84,"size":37505}] 30:{"id":"4cd2522f782e44b3","slug":"non-overlapping-aggregated-glyphs","title":"[DEPRECATED] Non-overlapping Aggregated Multivariate Glyphs for Moving Objects","thumbnail":"c27932bb3702d74816b6c9aa7bd0fc94b9e4b022e79198fc3fd81b6998c3ec38","access_level":"public","create_time":"$D2021-02-16T15:06:49.741Z","update_time":"$D2021-06-07T16:37:18.176Z","view_time":null,"first_public_time":"$D2021-02-23T14:18:24.627Z","has_unpublished_edits":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"ffbcf8ce47e293f4","login":"stardisblue","name":"Fati CHEN","avatar_url":"https://avatars-next.observableusercontent.com/c3f14cf2d58aebca19459fc111e35113235be85745ae353f37b7731ea9a84d79","tier":"starter_2024"},"version":1313,"publish_version":1313,"role":null,"authored":false,"authors":[{"type":"individual","id":"7affeb11879b11eb","login":"stardisblue","name":"Fati CHEN","avatar_url":"https://avatars-next.observableusercontent.com/c3f14cf2d58aebca19459fc111e35113235be85745ae353f37b7731ea9a84d79","tier":null}],"members":[{"type":"individual","id":"7affeb11879b11eb","login":"stardisblue","name":"Fati CHEN","avatar_url":"https://avatars-next.observableusercontent.com/c3f14cf2d58aebca19459fc111e35113235be85745ae353f37b7731ea9a84d79","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":1,"collection":null,"type":"notebook","body":{"titling":"auto","title":"[DEPRECATED] Non-overlapping Aggregated Multivariate Glyphs for Moving Objects","cells":[{"id":0,"value":"md`# [DEPRECATED] Non-overlapping Aggregated Multivariate Glyphs for Moving Objects`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":869,"value":"html`

This is a work in progress, it will heavely change due to algorithm optimization, I publish it mainly for feedback`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":24,"value":"md`Based on _Non-overlapping Aggregated Multivariaate Glyphs for Moving Objects_ by R. Scheepens, H. v. d. Wetering and J. J. v. Wijk [10.1109/PacificVis.2014.13](https://ieeexplore.ieee.org/document/6787132)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":801,"value":"html`

\n${bind(Button('Relancer'), viewof replay)}\n${bind(Toggle({ label: \"Enable animation\" }), viewof interactive)}\n${bind(\n Range([0, 10000], { label: \"Step animation delay\", step: 1 }),\n viewof delay\n)}\n${bind(\n Range([1, 10], { label: \"Stroke width\", step: 1 }),\n viewof strokeWidth\n)}${bind(\n Range([1, 10], { label: \"Base radius\", step: 1, value: 5 }),\n viewof baseRadius\n)}\n${bind(\n Range([100, width], { label: \"Map size\", step: 10 }),\n viewof francewidth\n)}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":152,"value":"html` explanation: \\`kdtree.remove(point)\\` may fail, because the found point is not the same as the one asked for removal.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":629,"value":"boundedPoints = d3\n .groups(points, ({ localisation: { lat, lng } }) => lat + \":\" + lng)\n .map(([, values]) => ({\n localisation: values[0].localisation,\n values: values.map(v => v.value)\n }))\n .filter(\n ({ localisation: { lat, lng } }) =>\n lng > -5 && lng < 9 && lat > 41 && lat < 52\n )","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"md`## Imports`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":300,"value":"import { Range, bind, Input, Button, Toggle } from \"@observablehq/inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":131,"value":"import { points } from \"@stardisblue/siprojuris-localisations-dataset\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":63,"value":"import { signature } from \"@mootari/signature\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2,"value":"import { createMap, inputs, style } from \"@stardisblue/noag-utils\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":7,"value":"import { L } from \"@mbostock/hello-leaflet\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":12,"value":"import { _ } from \"@mbostock/hello-lodash-fp\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":95,"value":"import { Tree as BST, node } from '@stardisblue/dancing-linked-aa-tree'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":98,"value":"kd = require(\"kd-tree-javascript\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":9,"value":"d3 = require(\"d3\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W34","stdlib":"1"}} 31:"$30:body"