Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

e.g. For an icosahedron defined as follows:

Diagram: A regular icosahedron (courtesy of Microsoft Visio):

icosahedron

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

triangular recursion reference

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:

triangle side enumeration

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.

share|improve this question
    
22 revisions! Is that a record? –  Gerry Myerson Jun 13 '12 at 6:36
    
You're behind the times - we're now up to 23! Thank you for your attention to this thread, and for noticing my tendency toward perfectionism! As long as there weren't any comments or answers yet, I wanted to make sure people were working on the basis of the latest information, or on the basis of the best-informed designs I could muster without a better education in maths (my understanding has developed slightly over the last few weeks). –  Matthew Slyman Jun 13 '12 at 8:28
    
22 days without an answer! @GerryMyerson - Is that a record for a geometry question that looks like it ought to be reasonably straightforward for someone with a degree in pure mathematics? Should I conclude that there simply aren't any conventions yet for ordering the faces of a polyhedron? –  Matthew Slyman Jun 22 '12 at 10:37
    
I'm not aware of any such conventions, but that proves nothing. –  Gerry Myerson Jun 22 '12 at 12:36
    
@GerryMyerson: Do you think this post would get more attention if we simplified the title to: "Conventional ordering of faces of regular polyhedron?" Can this be done? –  Matthew Slyman Jul 28 '12 at 12:20
show 5 more comments

1 Answer 1

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"

The all-sky, skyward looking, unfolded cube is reassembled by        
arranging the faces in a sideways T with the bar on the right side:  
                                      0                                  
                          4   3   2   1                                  
                                      5           

where square face 0 is 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 http://rpg.stackexchange.com/ ?

share|improve this answer
    
This is the first time I've heard about Max Tegmark or his work (which resembles what I'm seeing elsewhere under the general heading, "Geodesic grid", after you signposted me to that). My comments on distortion applied strictly to the COBE sky cube (correctly mentioned in Tegmark's abstract as an inferior precursor to his/my work), or further to any similar scheme based on anything other than an icosahedral basis. –  Matthew Slyman Mar 25 '13 at 20:57
    
I would intuitively concur (with reference to the basic angular geometry of triangles, pentagons and hexagons) that the amount of 2D/3D projection distortion in Tegmark's scheme, the "geodesic grids" and my own "icosamap" scheme are all essentially equivalent... –  Matthew Slyman Mar 25 '13 at 21:17
    
...Naive improvements to these schemes might start with the "truncated icosahedron" (classic soccer ball shape, elegant for its 2^5=32 faces, concave semiregularity etc.); but we might demonstrate the similarity of distortion in each case by observing recursive subdivision at the basic vertices (as sub-vertex spacings approach zero separation). With some vertices of edge-order five, and some of order six; all such schemes are going to suffer from similar problems. –  Matthew Slyman Mar 25 '13 at 21:19
    
I give it as my opinion (guess) that schemes based on triacontahedra or stellated/-akis polyhedra are only going to increase problems with uniformity, while failing to address the fundamental problem of distortion (after all, distortion in some degree is essential to any 2D/3D mapping.) However anyone wishing to satisfy themselves with some formal calculations to support my suggestion might start here: slyman.org/… -- This page contains a pyramid angle calculator and relevant general analytical solution. –  Matthew Slyman Mar 25 '13 at 21:22
    
The variety in space-filling curves you listed informally confirms the consensus opinion here, that the choice of ordering is (in some degree) arbitrary (given at least, consistency and simplicity in recursion). However, on another thread, you quote Max Tegmark thus: "Unfortunately, it is a well-known group theoretical result that there are no completely regular point distributions on the sphere for N > 20." -- You're teasing me now! When I first asked this question, I entertained the vague notion that there might be some aspect of GROUP THEORY that would answer my question at least in part... –  Matthew Slyman Mar 25 '13 at 21:29
show 4 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.