Today's node allows you to create a quadtree. A quadtree is a tree data structure in which each internal node has exactly four children. You can use this structure to locate and organize a set of points into a hierarchy of rectangular tiles and sub-tiles. Quadtrees are a secret weapon that can help you create cool looking generative art.

This may seem confusing at first, but bear with me - it's worth it!

Here is a great article about quadtrees: https://georgefrancis.dev/writing/generative-grid-layouts-with-quad...

"I like to think of Quadtrees as little containers. Once the Quadtree fills with a certain number of objects, it splits itself into four more Quadtrees. Once those Quadtrees fill up, they divide themselves again, and so on."

My quadtree node takes the following parameters:

• Boundary. A rectangular region forming the initial quadtree tile.
• Shapes or Points. A list of points (or centroids of shapes) that determine the tile hierarchy needed to contain them.
• Capacity. The maximum number of points a tile can hold before splitting into four sub-tiles.
• Levels. The maximum depth of tile hierarchy. Values can range from 1 to 7.
• Gap. An optional margin between tiles (in pixels). Only affects the drawn tiles, not the data structure.
• Output. Three possible outputs:
  • Data. A data table showing which tile each point belongs to
  • Tile IDs. A list of distinct tile IDs
  • Tiles. A list of tile rectangles ordered from top left to bottom right

The data table generated by this node has the following columns:

• pointID. An integer value index enumerating each point in the input list in its original order.
• point. The X,Y value of each point.
• tileID. A unique identifier for the tile (see explanation below) holding each point.
• tile. The rectangle forming the tile holding each point.
• tileCount. The total number of points held in that tile. The count will not exceed the capacity unless there are more points than the quadtree can hold given the maximum hierarchy depth defined by the levels parameter above.
• capacity. The maximum capacity as defined by the parameter above (the same value appears in each row).

The tileID is composed of the integers 1, 2, 3, or 4 representing the northwest, northeast, southwest, and southeast quadrants. The more digits in the ID, the deeper that tile is in the hierarchy. An ID of 2 represents the entire northeast quadrant. An ID of 231 represents the sub-sub-tile composed of the northwest quadrant of the southwest quadrant of that northeast quadrant.

This ID system guarantees that each ID is unique. But it also describes the exact size and location of each tile, and reveals all the parent-child relationships. Understanding this can be useful for some advanced use cases. For example, you could use the tileIDs to determine which tiles neighbor any given tile.

Quadtree is one of those nodes you have to play with to fully understand. I strongly encourage you to explore the attached demo.

The demo creates two displays. The one on the left, composed of yellow, green, and black circles, is similar to the example pattern described in the article I referenced above (which you should definitely read).

The quadtree23 node takes a biased scatter of 100 points and distributes them into tiles containing a maximum of 4 points. Render that node to see what the tile output looks like. The gap setting of 4 makes the circles slightly smaller than the boxes which ultimately hold them. Each tile in the original quadtree is used to form a randomly colored circle.

I then take a random subset of 40 of those circles and feed them into a second quadtree, quadtree24. The tiles of this tree are visible in the final output. As you can see, quadtree24 is simpler and less complex than quadtree23. Try playing with the settings on all the nodes in this demo to see what happens.

The display on the right shows one way to use the data and tileID outputs of the quadtree node. An unbiased scatter of 100 points is fed into two quad trees with identical settings but different outputs. Quadtree25 outputs a data table; quadtree26 outputs a distinct set of tileIDs used in that table.

Both outputs are fed into a "clumps" subnetwork which produces a star structure for each tile in the quadtree. The star is formed by connecting the centroid of the tile (in red) to each point contained in the tile (in blue). Look inside clumps to see how I do this.

NOTE: quadtree will start to bog down if fed more than about 1000 points. It is intended to create relatively simple patterns, not analyze datasets with millions of points.

Quadtrees are widely used in image processing and have countless possible applications. For more about quadtrees and their uses, see this Wikipedia article: https://en.wikipedia.org/wiki/Quadtree

This is an unusual and rather experimental node. So I will be even more grateful than usual If anyone tries it and reports back.

Enjoy!

John