Re:Planes, Spheres and Pseudospheres
by o11c on Sunday November 05, 2023 @12:38PM
(#38153396)
The interesting question for me is: for what geometries is there an efficient mapping to 1-D computer memory without too much stretching? While scaling, keep in mind that cache associativity means you're best off avoiding powers of 2.
For rectangles (or rhombuses), many languages already give you 2D arrays with a dense representation; several other mappings are possible and sometimes useful (e.g. the Hilbert Curve [1], but that needs a loop; interleaving might not need a loop in some contexts). For infinite extensions thereof it's not too hard to come up with a mapping, though practically you'll have to switch to block allocation. Wrapping in a single dimension makes a cylinder (without ends), but note that wrapping in both dimensions is topologically a torus but has significant stretching.
For triangles, you can just take the triangular number of one coordinate, then add the other, using the sum as the linear index. But in most practical cases where triangles show up, you can use 2 triangles together to make a rectangle (in many use cases, one axis will be a unit longer than the other).
For other finite fragments of a plane you're probably best off breaking it into triangles and squares, or even wasting memory. There are no good solutions for a real circle in particular.
For a sphere, pick your favorite platonic solid with triangular/square faces. The icosahedron minimizes stretching at the cost of having 20 poles (note that this involves 5 "strips" of 4 triangles each). The tetrahedron minimizes poles at the cost of severe stretching. The cube and octahedron compromise on both. Some non-platonic solids are technically possible but I've never found a reason (particularly, using the truncated icosahedron directly does not decrease stretching compared to the icosahedron).
Note that the dodecahedron does not have a reasonable solution; it's not possible to tile its faces so I'm not sure why anyone would care though.
For a torus (without stretching; topology isn't sufficient) it's possible to do similarly to the sphere. The easiest way to visualize is 8 cubes forming a hollow square; 2 faces of each cube are not exposed. Approaches using triangles (possibly via hexagons - remember a triangular prism-like can't be properly tiled by regular triangles) are probably possible but that's too much work; this post already took long enough.
The triangular pyramid is just the tetrahedron again if including the bottom; you have to use the more-complicated indexing if you have an odd number of triangles. The square pyramid is also possible, with or without the bottom. The pentagonal pyramid without the bottom is possible with the more-complicating indexing. Higher pyramids are likely to imply stretch so aren't worth considering.
For hyperbolic geometry, all implementations I'm aware of use per-node allocations, ick. It's probably possible to switch to block allocations (with more-complicated indexing for larger blocks), but that will need to be done separately based on how hyperbolic the geometry is. heptagons are common but would octagons make the mapping easier?
For rectangles (or rhombuses), many languages already give you 2D arrays with a dense representation; several other mappings are possible and sometimes useful (e.g. the Hilbert Curve [1], but that needs a loop; interleaving might not need a loop in some contexts). For infinite extensions thereof it's not too hard to come up with a mapping, though practically you'll have to switch to block allocation. Wrapping in a single dimension makes a cylinder (without ends), but note that wrapping in both dimensions is topologically a torus but has significant stretching.
For triangles, you can just take the triangular number of one coordinate, then add the other, using the sum as the linear index. But in most practical cases where triangles show up, you can use 2 triangles together to make a rectangle (in many use cases, one axis will be a unit longer than the other).
For other finite fragments of a plane you're probably best off breaking it into triangles and squares, or even wasting memory. There are no good solutions for a real circle in particular.
For a sphere, pick your favorite platonic solid with triangular/square faces. The icosahedron minimizes stretching at the cost of having 20 poles (note that this involves 5 "strips" of 4 triangles each). The tetrahedron minimizes poles at the cost of severe stretching. The cube and octahedron compromise on both. Some non-platonic solids are technically possible but I've never found a reason (particularly, using the truncated icosahedron directly does not decrease stretching compared to the icosahedron).
Note that the dodecahedron does not have a reasonable solution; it's not possible to tile its faces so I'm not sure why anyone would care though.
For a torus (without stretching; topology isn't sufficient) it's possible to do similarly to the sphere. The easiest way to visualize is 8 cubes forming a hollow square; 2 faces of each cube are not exposed. Approaches using triangles (possibly via hexagons - remember a triangular prism-like can't be properly tiled by regular triangles) are probably possible but that's too much work; this post already took long enough.
The triangular pyramid is just the tetrahedron again if including the bottom; you have to use the more-complicated indexing if you have an odd number of triangles. The square pyramid is also possible, with or without the bottom. The pentagonal pyramid without the bottom is possible with the more-complicating indexing. Higher pyramids are likely to imply stretch so aren't worth considering.
For hyperbolic geometry, all implementations I'm aware of use per-node allocations, ick. It's probably possible to switch to block allocations (with more-complicated indexing for larger blocks), but that will need to be done separately based on how hyperbolic the geometry is. heptagons are common but would octagons make the mapping easier?
[1]: https://en.wikipedia.org/wiki/Hilbert_curve