Hacker News Reader

Comment by braythwayt | Hacker News Reader

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.

View on HN

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).

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

For odd size squares, simply duplicate the center row and column before rotating, then deduplicate after.

Reply on news.ycombinator.com