Skip to content

Latest commit

 

History

History
50 lines (45 loc) · 2.54 KB

NOTES.md

File metadata and controls

50 lines (45 loc) · 2.54 KB

Efficient Region Quadtree

+--+--+--+--+--+--+--+--+--+--+       +--+--+--+--+--+--+--+--+--+--+
|  |  |  |  |  |  |  |  |  |  |       |           |                 |
+--+--+--+--+--+--+--+--+--+--+       +     1     +        2        +
|  |  |  |  |  |  |  |  |  |  |       |           |                 |
+--+--+--+--+--+--+--+--+--+--+       +--+--+--+--+--+--+--+--+--+--+
|  |  |  |  |xxxxxxxxxxx|  |  |       |           |xxxxxxxxxxx|     |
+--+--+--+--+xxxxxxxxxxx+--+--+  -->  +           +xxxxxxxxxxx+     +
|  |  |  |  |xxxxxxxxxxx|  |  |       |           |xxxx4.1xxxx| 4.2 |
+--+--+--+--+xxxxxxxxxxx+--+--+       +           +xxxxxxxxxxx+     +
|  |  |  |  |xxxxxxxxxxx|  |  |       |     3     |xxxxxxxxxxx|     |
+--+--+--+--+--+--+--+--+--+--+       +           +--+--+--+--+--+--+
|  |  |  |  |  |  |  |  |  |  |       |           |    4.3    | 4.4 |
+--+--+--+--+--+--+--+--+--+--+       +--+--+--+--+--+--+--+--+--+--+

->

+--+--+--+--+--+--+--+--+--+--+       +--+--+--+--+--+--+--+--+--+--+
|           |                 |       | 1.1 | 1.2 | 2.1 |    2.2    |
+  1  +--+--+--+--+  2        +       +--+--+--+--+--+--+--+--+--+--+
|     |\\\\\\\\\\\|           |       |     |\\\\\|\\\\\|           |
|     |\\\\\\\\\\\|           |       | 1.3 |\1.4\|\2.3\|    2.4    |
|     |\\\\\\\\\\\|           |       |     |\\\\\|\\\\\|           |
+--+--+\\\\\\\\\\\+--+--+--+--+       +--+--+--+--+--+--+--+--+--+--+
|     |\\\\\\\\\\\|/////|     |       |     |\\\\\|XXXXX|/////|     |
|     |\\\\\\\\\\\|/////|     |       | 3.1 |\3.2\|4.1.1|4.1.2|     |
|     |\\\\\\\\\\\|/////|     |       |     |\\\\\|XXXXX|/////|     |
+     +--+--+--+--+/////+ 4.2 +  -->  +--+--+--+--+--+--+--+--+ 4.2 +
|           |////4.1////|     |       |     |     |/////|/////|     |
+           +///////////+     +       +     +     +4.1.3+4.1.4+     +
|     3     |///////////|     |       | 3.3 | 3.4 |/////|/////|     |
+           +--+--+--+--+--+--+       +     +     +--+--+--+--+--+--+
|           |    4.3    | 4.4 |       |     |     |    4.3    | 4.4 |
+--+--+--+--+--+--+--+--+--+--+       +--+--+--+--+--+--+--+--+--+--+

Development notes / notes to myself:

  • Developing a Cargo library
    • Generating docs: cargo doc --no-deps
    • Previewing README.md: grip README.md localhost:8000.
  • Models for API
  • Notes on Quadtree performance
    • It's OK for insert/delete to be relatively expensive if that means query is cheap.