Libraryless. Click here for Pure Java version (5832L/33K).
1 | sclass QuadTreeBitMatrix > WidthAndHeightImpl is BitMatrix {
|
2 | sclass Node {
|
3 | int compositeNodeCount() { ret 0; }
|
4 | } |
5 | sclass Prim > Node {}
|
6 | sclass On > Prim {} static new On on;
|
7 | sclass Off > Prim {} static new Off off;
|
8 | |
9 | sclass Composite > Node {
|
10 | Node a, b, c, d; |
11 | |
12 | void set(int idx, Node n) {
|
13 | if (idx == 0) a = n; |
14 | if (idx == 1) b = n; |
15 | if (idx == 2) c = n; |
16 | if (idx == 3) d = n; |
17 | } |
18 | |
19 | *(Node n) {
|
20 | a = b = c = d = n; |
21 | } |
22 | |
23 | bool simplifiable() {
|
24 | ret allEq(a, b, c, d); |
25 | } |
26 | |
27 | int compositeNodeCount() { ret 1+
|
28 | a.compositeNodeCount() + |
29 | b.compositeNodeCount() + |
30 | c.compositeNodeCount() + |
31 | d.compositeNodeCount(); |
32 | } |
33 | } |
34 | |
35 | Node root = off; |
36 | |
37 | *() {}
|
38 | *(int *width, int *height) {}
|
39 | |
40 | int half(int x) { ret roundUpToPowerOfTwo((x+1)/2); }
|
41 | int halfX(Rect r) { ret r.x+half(r.w); }
|
42 | int halfY(Rect r) { ret r.y+half(r.h); }
|
43 | |
44 | Rect rectA(Rect r) { ret rect(r.x, r.y, half(r.w), half(r.h)); }
|
45 | Rect rectB(Rect r) { ret rectFromPoints(r.x+half(r.w), r.y, r.x2(), halfY(r)); }
|
46 | Rect rectC(Rect r) { ret rectFromPoints(r.x, r.y+half(r.h), r.x+half(r.w), r.y2()); }
|
47 | Rect rectD(Rect r) { ret rectFromPoints(r.x+half(r.w), r.y+half(r.h), r.x2(), r.y2()); }
|
48 | |
49 | // have to return Bool (not bool) to satisfy BitMatrix interface |
50 | public Bool get(int x, int y) {
|
51 | Node node = root; |
52 | Rect r = rect(0, 0, width, height); |
53 | while (node cast Composite) {
|
54 | int hx = halfX(r), hy = halfY(r); |
55 | if (y < hy) |
56 | if (x < hx) {
|
57 | node = node.a; r = rectA(r); |
58 | } else {
|
59 | node = node.b; r = rectB(r); |
60 | } |
61 | else |
62 | if (x < hx) {
|
63 | node = node.c; r = rectC(r); |
64 | } else {
|
65 | node = node.d; r = rectD(r); |
66 | } |
67 | ifdef QuadTreeBitMatrix_debug |
68 | printVars(+x, +y, +hx, +hy); |
69 | endifdef |
70 | } |
71 | ret node == on; |
72 | } |
73 | |
74 | public void set(int x, int y, Bool b default true) {
|
75 | set(pointRect(x, y), b); |
76 | } |
77 | |
78 | void set(Rect r, bool b) {
|
79 | set(rootCursor(), r, b); |
80 | } |
81 | |
82 | scaffolded void set(Cursor cursor, Rect r, bool b) {
|
83 | // no intersection? exit |
84 | if (!rectsIntersect(r, cursor.r)) ret; |
85 | |
86 | // fully contained? replace with primitive |
87 | if (rectContains(r, cursor.r)) |
88 | cursor.replace(b ? on : off); |
89 | else {
|
90 | // partial intersection - turn into composite |
91 | cursor.turnIntoComposite(); |
92 | |
93 | for (Cursor c : cursor.subCursors()) |
94 | set(c, r, b); |
95 | } |
96 | |
97 | cursor.simplify(); |
98 | } |
99 | |
100 | class Cursor {
|
101 | settable Composite parent; |
102 | settable int indexInParent; |
103 | |
104 | settable Rect r; |
105 | settable Node node; |
106 | |
107 | L<Cursor> subCursors() {
|
108 | if (node cast Composite) |
109 | ret ll( |
110 | subCursor(0, node.a, rectA(r)), |
111 | subCursor(1, node.b, rectB(r)), |
112 | subCursor(2, node.c, rectC(r)), |
113 | subCursor(3, node.d, rectD(r))); |
114 | ret emptyList(); |
115 | } |
116 | |
117 | Cursor subCursor(int idx, Node n, Rect r) {
|
118 | ret new Cursor().r(r).node(n) |
119 | .parent((Composite) node).indexInParent(idx); |
120 | } |
121 | |
122 | scaffolded void turnIntoComposite {
|
123 | if (!node instanceof Composite) |
124 | replace(new Composite(node)); |
125 | } |
126 | |
127 | scaffolded void replace(Node n) {
|
128 | if (node == n) ret; |
129 | node = n; |
130 | if (parent == null) |
131 | root = n; |
132 | else |
133 | parent.set(indexInParent, n); |
134 | } |
135 | |
136 | // opposite of turnIntoComposite |
137 | scaffolded void simplify {
|
138 | if (node cast Composite && node.simplifiable()) |
139 | replace(node.a); |
140 | } |
141 | |
142 | /*toString {
|
143 | ret stdToString(this); |
144 | }*/ |
145 | } |
146 | |
147 | Cursor rootCursor() {
|
148 | ret new Cursor().r(bounds()).node(root); |
149 | } |
150 | |
151 | int compositeNodeCount() { ret root.compositeNodeCount(); }
|
152 | } |
Began life as a copy of #1026939
download show line numbers debug dex old transpilations
Travelled to 3 computer(s): bhatertpkbcr, ekrmjmnbrukm, mqqgnosmbjvj
No comments. add comment
| Snippet ID: | #1033638 |
| Snippet name: | QuadTreeBitMatrix |
| Eternal ID of this version: | #1033638/37 |
| Text MD5: | cef3379ab5e3e8859c62628b37e7e6bb |
| Transpilation MD5: | 1c41c2b2dcd97b2c92133c2f7ef5408b |
| Author: | stefan |
| Category: | javax / |
| Type: | JavaX fragment (include) |
| Public (visible to everyone): | Yes |
| Archived (hidden from active list): | No |
| Created/modified: | 2021-12-26 23:03:35 |
| Source code size: | 3917 bytes / 152 lines |
| Pitched / IR pitched: | No / No |
| Views / Downloads: | 205 / 440 |
| Version history: | 36 change(s) |
| Referenced in: | [show references] |