In Geographic Information Systems, often a region needs to be expanded to include everything within a certain distance, creating a “buffer” zone. For example, you may want to query everything that is within a mile of a shoreline or in the wider corridor of a highway. This operation is also useful in photo editing, computer vision, and robot motion planning.
Sometimes, though, maps are stored in triangular quadtrees, for example in astronomy applications. For these cases, the chessboard distance cannot be used, and the algorithm of Ang et al. is not directly applicable.
Using the principles of the original method by Ang et al., we create a new algorithm that quickly approximates region expansion in triangular quadtrees, using a triangle-friendly, hexagonal norm instead of the L∞-norm. We show that this algorithm can perform similarly to the square quadtree case, greatly accelerating the operation versus a naïve method.