[{"_1":2,"_171":-5,"_172":-5},"loaderData",{"_3":4,"_92":93},"root",{"_5":6,"_35":36,"_65":66},"ctx",{"_7":8,"_23":-5,"_24":25,"_26":27,"_28":20,"_29":20,"_30":20,"_31":32,"_33":20,"_34":20},"auth",{"_9":-5,"_10":-5,"_11":-5,"_12":-5,"_13":-5,"_14":-5,"_15":-5,"_16":-5,"_17":-5,"_18":-5,"_19":20,"_21":22},"sessionClaims","sessionId","sessionStatus","userId","actor","orgId","orgRole","orgSlug","orgPermissions","factorVerificationAge","isAuthenticated",false,"tokenType","session_token","user","preferencesKeybindings","default","preferencesTheme","light","preferencesFixers","preferencesCopilot","preferencesSelectionAi","notificationCount",0,"flagDenols","isTeamOrgMember","ENV",{"_37":38,"_39":40,"_41":42,"_43":44,"_45":46,"_47":48,"_49":50,"_51":52,"_53":54,"_55":56,"_57":58,"_59":60,"_61":62,"_63":64},"REACT_APP_SENTRY_DSN","https://586020d86f05489db63a554690acf1e9@o1398359.ingest.sentry.io/6724499","VAL_RUNTIME_NAME","prod","RENDER_GIT_COMMIT","dc548fcd12b3326c19c6514669630405c66f7ccb","RENDER_GIT_BRANCH","main","CLERK_PUBLISHABLE_KEY","pk_live_Y2xlcmsudmFsLnRvd24k","POSTHOG_API_TOKEN","phc_nmoyuAkStEZuUp69rYlg1DZgrIt19Gx0Y4Hwf8tGgJP","POSTHOG_API_HOST","https://wart.val.town","WEB_API_TEMPLATE","https://{val}.web.val.run","APP_URL","https://www.val.town","MODULE_URL","https://esm.town","VANITY_WEB_API_TEMPLATE","https://{label}.val.run/","DENOLS_URL","https://lsp.val.town","NODE_ENV","production","API_URL","https://api.val.town","clerkState",{"_67":68},"__internal_clerk_state",{"_69":70,"_71":46,"_72":73,"_74":73,"_75":20,"_76":73,"_77":73,"_78":73,"_79":73,"_80":81,"_90":20,"_91":20},"__clerk_ssr_state",{"_21":22,"_9":-5,"_10":-5,"_11":-5,"_12":-5,"_13":-5,"_14":-5,"_15":-5,"_16":-5,"_17":-5,"_18":-5,"_19":20},"__publishableKey","__proxyUrl","","__domain","__isSatellite","__signInUrl","__signUpUrl","__afterSignInUrl","__afterSignUpUrl","__clerk_debug",{"_82":20,"_19":20,"_83":73,"_84":85,"_86":73,"_87":46,"_88":20,"_89":73},"isSignedIn","proxyUrl","reason","session-token-and-uat-missing","message","publishableKey","isSatellite","domain","__telemetryDisabled","__telemetryDebug","routes/embed.x.$handle.$name.$",{"_94":95,"_96":97,"_98":99,"_100":101,"_148":149,"_168":169,"_170":-5},"handle","agariolove","name","legendmod","path","quadtree.ts","project",{"_102":103,"_96":97,"_104":105,"_106":-5,"_107":20,"_108":109,"_110":-5,"_111":-5,"_12":112,"_113":-5,"_114":20,"_115":-5,"_116":-5,"_117":32,"_14":118,"_119":120,"_121":120,"_122":123,"_124":123,"_125":123,"_126":120,"_127":120,"_23":128,"_131":132,"_134":135,"_147":20},"id","ca57d36a-efbd-11f0-b9de-42dde27851f2","createdAt",["D",1768225887106],"deletedAt","legacyEnvVars","privacy","public","description","imageUrl","019bb279-9ea8-77bf-8a8c-390256196f3e","pinnedFileId","pinPreview","pinMigrated","screenshotVersion","likeCount","019bb279-9ea8-77bf-8a8c-3f3f51d5ed48","userPerm","r","valPerm","blobPerm","rw","emailPerm","sqlitePerm","projectPerm","telemetryPerm",{"_94":95,"_129":130},"profileImageUrl","https://img.clerk.com/eyJ0eXBlIjoicHJveHkiLCJzcmMiOiJodHRwczovL2ltYWdlcy5jbGVyay5kZXYvb2F1dGhfZ2l0aHViL2ltZ18zODl5MHhjbGFyU2RpQkxjODRuMW1DQTJIeGwifQ","org",{"_94":95,"_133":130,"_12":112},"avatar","branch",{"_136":137,"_96":44,"_102":138,"_139":103,"_140":-5,"_141":-5,"_142":-5,"_143":-5,"_144":-5,"_145":97,"_146":95},"version",60,"ca58162c-efbd-11f0-b9de-42dde27851f2","projectId","forkedBranchId","forkedBranchVersion","forkedProjectPrivacy","forkedProjectId","forkedProjectOrgId","projectName","userHandle","isOwned","file",{"_102":150,"_96":99,"_151":152,"_153":-5,"_154":138,"_155":156,"_157":158,"_104":159,"_136":160,"_161":162,"_163":164,"_165":20,"_166":-5,"_98":167},"ae6d3480-efde-11f0-813c-42dde27851f2","fileId","2973f9f6-efc7-11f0-b95e-42dde27851f2","parentId","branchId","branchVersion",55,"latest",true,["D",1768240013657],2,"fileType","script","content","/**\n * Point QuadTree Implementation\n * Optimized for spatial indexing of points\n */\n\n// Basic interface for any object with coordinates\ninterface Point {\n x: number;\n y: number;\n}\n\n// Interface for the bounding box used in searches\ninterface AABB {\n x: number;\n y: number;\n w: number;\n h: number;\n}\n\n// Global constant for tree depth growth factor\nconst GROWTH = 1.1;\n\nclass Node {\n public x: number;\n public y: number;\n public w: number;\n public h: number;\n public points: Point[] | null; // Null if not a leaf node\n public children: Node[] | null; // Null if a leaf node\n\n constructor(x: number, y: number, w: number, h: number) {\n this.x = x;\n this.y = y;\n this.w = w;\n this.h = h;\n this.points = [];\n this.children = null;\n }\n\n // Check if this node spatially contains a specific point\n containsPoint(point: Point): boolean {\n return (\n point.x >= this.x &&\n point.x <= this.x + this.w &&\n point.y >= this.y &&\n point.y <= this.y + this.h\n );\n }\n\n // Check if this node overlaps with a search area (AABB)\n overlaps(aabb: AABB): boolean {\n return (\n aabb.x < this.x + this.w &&\n aabb.x + aabb.w > this.x &&\n aabb.y < this.y + this.h &&\n aabb.y + aabb.h > this.y\n );\n }\n\n insert(point: Point, maxPoints: number): void {\n // If we have children, push down to them\n if (this.children != null) {\n const col = point.x > this.x + this.w / 2 ? 1 : 0;\n const row = point.y > this.y + this.h / 2 ? 1 : 0;\n this.children[col + row * 2].insert(point, maxPoints * GROWTH);\n } else {\n // We are a leaf, add to local points\n this.points!.push(point);\n\n // Split if we exceed capacity and aren't too small\n if (this.points!.length > maxPoints && this.w > 1) {\n this.split(maxPoints);\n }\n }\n }\n\n some(aabb: AABB, test: (point: Point) => boolean): boolean {\n if (this.children != null) {\n // Recursive search through children\n for (let i = 0; i < this.children.length; ++i) {\n const child = this.children[i];\n if (child.overlaps(aabb) && child.some(aabb, test)) {\n return true;\n }\n }\n } else {\n // Leaf search\n // The original code used `Node.prototype.containsPoint.call(aabb, point)`\n // effectively checking if the point is inside the AABB. We write that explicitly here.\n for (let i = 0; i < this.points!.length; ++i) {\n const point = this.points![i];\n // Check if point is inside the search box (aabb)\n const inSearchBox = point.x >= aabb.x &&\n point.x <= aabb.x + aabb.w &&\n point.y >= aabb.y &&\n point.y <= aabb.y + aabb.h;\n\n if (inSearchBox && test(point)) {\n return true;\n }\n }\n }\n return false;\n }\n\n split(maxPoints: number): void {\n this.children = [];\n const halfW = this.w / 2;\n const halfH = this.h / 2;\n\n // Create 4 children\n for (let y = 0; y < 2; ++y) {\n for (let x = 0; x < 2; ++x) {\n const px = this.x + x * halfW;\n const py = this.y + y * halfH;\n this.children.push(new Node(px, py, halfW, halfH));\n }\n }\n\n // Redistribute existing points to new children\n const oldPoints = this.points!;\n this.points = null; // Mark as non-leaf (points array gone)\n\n const midX = this.x + halfW;\n const midY = this.y + halfH;\n\n for (let i = 0; i < oldPoints.length; ++i) {\n const point = oldPoints[i];\n const col = point.x > midX ? 1 : 0;\n const row = point.y > midY ? 1 : 0;\n this.children[col + row * 2].insert(point, maxPoints * GROWTH);\n }\n }\n\n clear(): void {\n if (this.children != null) {\n for (let i = 0; i < 4; ++i) {\n this.children[i].clear();\n }\n this.children.length = 0;\n this.children = null;\n }\n if (this.points) {\n this.points.length = 0;\n this.points = null;\n }\n }\n}\n\nexport class PointQuadTree {\n public root: Node;\n public maxPoints: number;\n\n constructor(x: number, y: number, w: number, h: number, maxPoints: number) {\n this.root = new Node(x, y, w, h);\n this.maxPoints = maxPoints;\n }\n\n clear(): void {\n // Original implementation effectively destroyed the tree structure.\n // To allow reuse, we reset the root to a fresh empty node with same dimensions.\n const { x, y, w, h } = this.root;\n this.root.clear();\n this.root = new Node(x, y, w, h);\n }\n\n insert(point: Point): void {\n if (!this.root.containsPoint(point)) return;\n this.root.insert(point, this.maxPoints);\n }\n\n some(aabb: AABB, test: (point: Point) => boolean): boolean {\n return this.root.some(aabb, test);\n }\n}","deleted","label",[99],"permalink","https://www.val.town/x/agariolove/legendmod/code/quadtree.ts","extension","actionData","errors"]