Why recursive data structures?
raganwald.com
Why recursive data structures?
1–10 of 129 posts
Re: Why recursive data structures?
#2The footnotes say that all the functions can be adjusted to deal with non–power-of-2 squares, but it's not obvious how this is done when working with region quadtrees.
Re: Why recursive data structures?
#3The footnotes say that all the functions can be adjusted to deal with non–power-of-2 squares, but it's not obvious how this is done when working with region quadtrees.
One way is to represent squares as a square-that-is-a-power-of-two, plus a “clipping size” that is used when the square is rastorized. If you’re using a lot of optimizations for blank regions, the extra padding has a negligible effect on performance.
Re: Why recursive data structures?
#4Reginald is definitely hinting at hylomorphisms here. I'd be curious to see if stream fusion could be achieved in JS for a hylomorphism.
Re: Why recursive data structures?
#5The footnotes say that all the functions can be adjusted to deal with non–power-of-2 squares, but it's not obvious how this is done when working with region quadtrees.
One way is to represent squares as a square-that-is-a-power-of-two, plus a “clipping size” that is used when the square is rastorized. If you’re using a lot of optimizations for blank regions, the extra padding has a negligible effect on performance.
I suppose that would work, but all the operations you do on the region quadtree have to be aware of the "clipping size" as well. For example, the rotation transformation that this article implements would also have to rotate that "clipping size" as the unwanted portion of the square is now in a different location.
Re: Why recursive data structures?
#6Earlier quoted context omitted.
One way is to represent squares as a square-that-is-a-power-of-two, plus a “clipping size” that is used when the square is rastorized. If you’re using a lot of optimizations for blank regions, the extra padding has a negligible effect on performance.
I suppose that would work, but all the operations you do on the region quadtree have to be aware of the "clipping size" as well. For example, the rotation transformation that this article implements would also have to rotate that "clipping size" as the unwanted portion of the square is now in a different location.
That depends If you can live with evenly-sized squares, you can always center the clipping square, and you’re good for rotations, flips, and so on.
If you want odd-sized squares, or other shapes, then yes, you’ll need to know how to transform the clipping path/description as well.
All in a day’s work!
Re: Why recursive data structures?
#7FYI, this article on recursive combinators from 2008:
http://www.lazutkin.com/blog/2008/06/30/using-recursion-comb...
Re: Why recursive data structures?
#8Got an opportunity to do this recently using a graph mapped on to a K^2 Tree to find out if a relationship existed or not. See https://maxdemarzi.com/2016/12/27/connected-2/
Re: Why recursive data structures?
#9Earlier quoted context omitted.
I suppose that would work, but all the operations you do on the region quadtree have to be aware of the "clipping size" as well. For example, the rotation transformation that this article implements would also have to rotate that "clipping size" as the unwanted portion of the square is now in a different location.
That depends If you can live with evenly-sized squares, you can always center the clipping square, and you’re good for rotations, flips, and so on. If you want odd-sized squares, or other shapes, then yes, you’ll need to know how to transform the clipping path/description as well. All in a day’s work!
Another approach would be to allow a cell's value to be null, meaning it should be clipped, but then you run the risk of having transforms on the region quadtrees that cause the null cells to migrate inwards into the square (such that they cannot simply be clipped off later).
Re: Why recursive data structures?
#10Earlier quoted context omitted.
I suppose that would work, but all the operations you do on the region quadtree have to be aware of the "clipping size" as well. For example, the rotation transformation that this article implements would also have to rotate that "clipping size" as the unwanted portion of the square is now in a different location.
That depends If you can live with evenly-sized squares, you can always center the clipping square, and you’re good for rotations, flips, and so on. If you want odd-sized squares, or other shapes, then yes, you’ll need to know how to transform the clipping path/description as well. All in a day’s work!
One can use recursive properties better if the structure divides equally. So if not having a strict quadtree is okay, they can divide the square into 3x3, 5x5, etc