e.g. For an icosahedron defined as follows:
Diagram: A regular icosahedron (courtesy of Microsoft Visio):
We define position and orientation w.r.t. this body's frame of reference as follows:
- Point O at the origin: (0, 0, 0)
- Point P within the half-line: (x=0, y>0, z=0)
- Point P1 within the half-line: (x=0, y<0, z=0)
- Point A within the quarter-plane: (x>0, y<0, z=0)
Question 1: Formal methods/conventions?
Is there (a) a formal way to index/order the faces of a regular polyhedron? In other words, are some methods of ordering the faces/vertices etc., more correct, logical or conventional than certain other methods? If not, then do certain face encodings/orderings facilitate more efficient vector manipulation? How then should the faces be ordered, or, in what order should we generate their normal direction vectors?
OR, is it (b) a matter of arbitrary discretion according to the requirements of the specific application one is designing for; or otherwise arbitrary due to fundamental constraints on the shape of the data structures & algorithms required to manipulate these data most efficiently?
Question 2: Ordering for recursive precision
Suppose we break each surface triangle down recursively into four sub-triangles so that:
- Any face may be folded if its edge-adjacent neighbours are also folded along common edges and their constituent sub-triangles stretched (each sub-triangle remaining flat but no longer remaining coplanar with each other); so as to more perfectly approximate the curved surface being modelled
- Each successive ≈4× improvement in area precision requires exactly two additional bits of information to store the resulting surface-positional “reference code” or “index number”
Is there (a) a formal mathematical way to order or encode these constituent sub-triangles?
Or is this (b) open to the engineer's discretion, to define a convention that he prefers?
Do some encodings of the constituent triangles permit more efficient data manipulation, or is this choice arbitrary? Can this be proven either way? If the choice is theoretically arbitrary, then does a relevant mathematical convention already exist?
Typical application: geographical data visualisation
We will use this for data geocoding, indexing, querying & visualisation; using polyhedral projections from near-spherical shapes (the surface of the Earth) with the best all-round properties of:
- computational efficiency (for encoding/ retrieval/ visualisation)
- low spatial distortion, high area uniformity by code space
- information density
- conceptual simplicity
Our general purposes are illustrated by this document:
http://www.progonos.com/furuti/MapProj/Normal/ProjPoly/projPoly.html#PolyhedralMaps
Suggested conventions for mapping geographical data
We will orient our icosahedral mapping so that:
- Point O (the origin) corresponds to the centre of mass of the body being modelled
- Point P corresponds to the geographical North Pole at +90° latitude
- Point P1 corresponds to geographical South Pole at −90° latitude
- Point A lies within the half-plane containing the prime meridian i.e. zero longitude in the standard modern polar (latitude, longitude) coordinates. The icosahedral diagram here:
http://www.win.tue.nl/~vanwijk/myriahedral/
— from Jack van Wijk's work on “myriahedral projections” appears to validate the near-optimality of this convention for planet Earth in the current geological era.
For modelling or display purposes, the model polyhedron should be scaled such that its volume is equivalent to the modelled geoid. Where the geoid is irregular and the modelling polyhedron is of high resolution, approximations to this rule might be considered acceptable.
Reference design for encoding surfaces/ positions
Unless advised of a better way, we plan to order the faces first according to their apex orientation with triangle base perpendicular to (P→P1), whether up/down with respect to vector (P→P1); and second (for each orientation) in a spiral/helix, working first anticlockwise around (P→P1), and then clockwise around (P1→P) for the opposite apex orientation. This would number the 20 main triangles from 0 to 4, 8 to 12, 16 to 20 and 24 to 28 as follows:
+ 0 1 2 3 4
0 P A1 B1; P B1 C1; P C1 D1; P D1 E1; P E1 A1;
8 A1 A B ; B1 B C ; C1 C D ; D1 D E ; E1 E A ;
16 P1 B A ; P1 C B ; P1 D C ; P1 E D ; P1 A E ;
24 B B1 A1; C C1 B1; D D1 C1; E E1 D1; A A1 E1;
— This coding system has discontinuities to simplify logical functions for calculating surface polygon orientation, which is necessary for translating position data between systems of coordinates (orientation might be considered on the basis of individual triangles, or cumulatively on the basis of recursive N-ary sum style positional calculations). Note that the rows in this table correspond to horizontally oriented slices of the icosahedron, whereas the columns in this table correspond to diagonally (near-vertically) oriented half-slices.
We plan to encode each sub-triangle recursively as per:
File format; recursion-conforming data compression
We plan to support data compression and adaptive rendering by storing at each detail level only the differences from the average values corresponding to the hierarchical parent surface. In accordance with this objective, location codes will be stored and communicated in a big-endian format. If modelling a perfect unit sphere, the “unit sphere” should be of unit radius. The volume of the unit spheroid/geoid etc. should generally approach 4π/3 cubic units as closely as possible (altitudes should be defined in proportion with such a unit geoid, and a scale factor should be specified for the entire geoid).
Community benefits (public domain, IP considerations)
To promote industrial standardisation; I now release these plans freely here, and will further consider releasing my work freely when complete as a set of open-source software libraries. For the record, I (Matthew Slyman) started working independently on this project some time around the year 1993, and first proposed this idea to Iestyn Bleasdale-Shepherd late in 1996 (he implemented the first proof-of-concept as an IBM PC program written in C over the Christmas holidays of 1996–1997). We subsequently shelved the original application we were discussing; and as the originator of this idea and the sole developer of this specification, I (Matthew Slyman) hereby relinquish any claim to the intellectual property rights for this data structure or any compatible code implementations that might be created by third parties. In order to better serve the mathematical community, I would like to give priority at the design/implementation stage to any relevant formal mathematical requirements or conventions. Anyone commenting on this thread thereby places their comments likewise in the public domain, for general community benefit. In the absence of further instruction, we will number the faces according to our practical requirements or whims (see above). We would be grateful for any formal improvements that can be offered by anyone better educated in mathematics.
I propose to give this standardised set of conventions a name: “Icosamap”. Please register any objections to this name, including links to any evidence of priority within the relevant field of science.
Best Answer
I am also interested in knowing if there are any good reasons to pick one ordering of polygons over some other ordering.
I'll post what little I know, but I'm really hoping someone else will post something much better.
I have heard of 3 "standards" for ordering these polygons, but as far as I can tell they were arbitrarily picked: Your icosahedron-based method, the quadrilateralized spherical cube, and Tegmark's icosahedron-based method for pixelizing the celestial sphere.
All three are examples of geodesic grids.
Ordering polygons on a polyhedron
icosahedron-based method for pixelizing the celestial sphere
"What is the best way to pixelize a sphere?" by Max Tegmark
gives a format that appears extremely similar to your proposal:
Tegmark starts with an icosahedron, just as you do, and recursively subdivides it, just as you do. So I find it hard to believe that his method is "computationally and geometrically far more complex than what [you] are proposing" or that it has significantly "greater distortion in either area or geometry".
Given some specified resolution (the same as your depth of recursion) and some point on a sphere, Tegmark's system assigns that point to a "pixel number" (the number indicating what major icosahedral face it is on, and which particular minor sub-triangle on that face that point is in).
quadrilateralized spherical cube
Wikipedia: "quadrilateralized spherical cube"
where square face
0is centered on the North pole, square face 5 is centered on the South pole, the vernal equinox -- at latitude=0, longitude=0-- lies at the center of square face 1. Ecliptic longitude increases from face 1 to face 4.other polyhedra
Tegmark mentions that "it is clearly desirable to use as small faces as possible".
Subdividing each face of a (30-faced) rhombic triacontahedron into two nearly-equilateral isosceles triangles gives the (60-faced) pentakis dodecahedron, as you mentioned, which one might expect to give less error than starting with a (20-faced) icosahedron.
Further subdividing each of those faces into two irregular triangles gives the (120-faced) disdyakis triacontahedron (dual to the truncated icosidodecahedron).
I've been told that the strictly convex polyhedron with the maximum number of identical faces (exactly equal-shaped and exactly equal-area) is that disdyakis triacontahedron.
However, apparently none of these shapes gives any improvement over your icosahedron proposal. Tegmark's code immediately breaks up each equilateral triangle of the 20-sided icosahedron into 6 identical irregular triangles. The resulting 20*6 = 120 identical triangles are the same triangles as the faces of the disdyakis triacontahedron, right?
Ordering polygons on a recursively subdivided polygon
The quadrilateralized spherical cube recursively subdivides each square -- each division of 4 by area adding 2 more bits of localization information -- using a Morton code (Z-order curve).
The Maidenhead Locator System uses a system similar to the Morton code. You might also want to look at the military grid reference system.
Other ways of ordering such subdivided square (i.e., drawing a path that hits the center of each square exactly once) include the Sierpiński curve, the Hilbert curve, the Peano curve, the Moore curve, etc.
There exist other space-filling curves based on recursively subdividing a triangle -- each division of 4 by area adding 2 more bits of localization area. (Do any of them have popular names?)
There are 2 popular ways of subdividing squares and triangles: ( a, b )
"Class I"/"alternate" method: each of the original triangles (or squares) is replaced with n^2 triangles (or squares) that exactly fit inside the original triangle (or square). (n=1 gives the original base shape, n=2 gives a shape with 4 times as many faces). The small triangles have edges (very close to) parallel to the original big triangles.
"Class II"/"triacon" method, employed on almost every major geodesic dome project in the 1950s ( a p. 30 ), each of the original triangles is replaced with 3*n^2 triangles. The small triangles have edges (very close to) right angles to the original big triangles. (Unreliable sources tell me the triacon method can be applied to the cube or rhombic solids, each of the original squares or rhombuses is replaced with 2*n^2 rhombuses). (n=1 converts the icosahedron to the pentakis dodecahedron I mentioned earlier; n=8 converts the icosahedron to an approximation of the Epcot "Spaceship Earth"; n=1 converts the cube into the rhombic dodecahedron, etc.).
EDIT:
The most common application of numbering the sides of a platonic solid is while making dice. One particular way of putting numbers of the sides of an icosahedron is shown on DiceCollector's page, but I don't know if that is particularly "standard". Have you considered asking "What is the proper way to number the sides of a 1d20 die?" or "What is the proper way to number the sides of a 1d120 die?", or both, on the https://rpg.stackexchange.com/ ?