Hacker News Reader

Comment by eridius | Hacker News Reader

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

View on HN

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!

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.

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

Yes, that made me lose a lot of confidence in the article. This shouldn't have been a footnote. It should have been stated in the beginning that the author was only considering powers of two, and the footnote should have been a reference to ways to deal with other sizes - my very first question, before I got to the footnotes, was "How would I deal with a 3x3 square?"

Reply on news.ycombinator.com