From: Warren Brown <WBrown@...>
Date: 2004-10-14T02:39:38+09:00
Subject: Re: [QUIZ][SOLUTION] Geodesic Dome Faces (#3)

Wow,

    This quiz took a lot longer than an hour or two.  I had to pare down
my solution a lot due to time constraints (I was at the Texas State Fair
on Friday, and then I was sick most of the weekend).  It seems that the
real point of the puzzle - the routine to subdivide the triangles - was
a small portion of the "figure out where the Vector class is", "read all
of the triangles from the primitives", "call the subdivide routine for
each triangle", "normalize the resulting triangles" setup that had to go
around it.  Perhaps future puzzles can try to limit the scope to the
important bits and provide any setup code that is needed.  Just my
opinion...

    Anyway, I took the approach of calculating the triangles from "top"
to "bottom" and "right" to "left" (directions chosen arbitrarily and
only for descriptive purposes) by calculating the vertices and then
creating the triangles from the vertices.  One nice feature of this
approach is that it works for any triangle, not just equilateral ones.

    To be a little more explicit, given a triangle ABC:

        A
       / \
      /   \
     /     \
    /       \
   /         \
  /           \
 /             \
B---------------C

    I find the vertices on the sides AB and AC by simply subdividing the
line segments:


        A
       / \
      X   X
     /     \
    X       X
   /         \
  X           X
 /             \
B---------------C


    Then I start with the first two "horizontal" lines - the first
passing through A, and the second passing through the next "lower" pair
of vertices:


--------A--------
       / \
------X---X------
     /     \
    X       X
   /         \
  X           X
 /             \
B---------------C

    I know all of the vertices on both of these lines, so I create the
one and only triangle.  Next I move down to the next line and subdivide
that line in half:

        A
       / \
------X---X------
     /     \
----X---X---X----
   /         \
  X           X
 /             \
B---------------C

    This gives me all of the vertices for the next three triangles, so I
create them.  Next I move down another line and subdivide that line into
thirds:

        A
       / \
      X---X
     / \ / \
----X---X---X----
   /         \
--X---X---X---X--
 /             \
B---------------C

    This gives me all of the vertices for the next five triangles, so I
create them.  I continue moving down one line and subdividing all the
way through the last line (i.e. the one running through BC):

        A
       / \
      X---X
     / \ / \
    X---X---X
   / \ / \ / \
--X---X---X---X--
 /             \
B---X---X---X---C

    I create the triangles for each "row" by handling the first triangle
specially, then for each "middle" vertex (i.e. not the first or last) on
the bottom line, I create the triangle "above" it, then the triangle
"above and to the right" of it.  I create the triangles in the same
"clockwiseness" as the original triangle, so as long as the original
triangles are all ordered correctly, the resulting ones will be too.
Note that the supplied primitives did NOT order the points in all of the
triangles the same.  I wanted to write a routine to reorder the given
triangles to make them all clockwise, but I didn't have time.

    The routine currently uses a simple algorithm to subdivide each line
segment.  I wanted to change this routine to subdivide the *arc* defined
by the two endpoints, but I ran out of time.  This would have made the
normalized triangles equal in size instead of being slightly larger
towards the middle.

    I also wanted to move everything into spherical coordinates (think
three dimensional polar coordinates), but I didn't have time to do that
either.  I think this would have simplified things in some ways (no
normalization required), but made things more complicated near the poles
and near 0/360 degrees.

    I didn't have time to write a proper interface to the whole thing
either :o(

    Anyway here it is:


require 'matrix'


# A wrapper for the supplied primitives.
module Primitives
  SQRT2 = Math.sqrt(2)
  SQRT3 = Math.sqrt(3)
  TETRA_Q = SQRT2 / 3
  TETRA_R = 1.0 / 3
  TETRA_S = SQRT2 / SQRT3
  TETRA_T = 2 * SQRT2 / 3
  GOLDEN_MEAN = (Math.sqrt(5)+1)/2
  PRIMITIVES = {
    :tetrahedron => {
      :points => {
        'a' => Vector[ -TETRA_S, -TETRA_Q, -TETRA_R ],
        'b' => Vector[  TETRA_S, -TETRA_Q, -TETRA_R ],
        'c' => Vector[        0,  TETRA_T, -TETRA_R ],
        'd' => Vector[        0,        0,        1 ]
      },
      :faces => %w| acb abd adc dbc |
    },
    :octahedron => {
      :points => {
        'a' => Vector[  0,  0,  1 ],
        'b' => Vector[  1,  0,  0 ],
        'c' => Vector[  0, -1,  0 ],
        'd' => Vector[ -1,  0,  0 ],
        'e' => Vector[  0,  1,  0 ],
        'f' => Vector[  0,  0, -1 ]
      },
      :faces => %w| cba dca eda bea def ebf bcf cdf |
    },
    :icosahedron => {
      :points => {
        'a' => Vector[  1,  GOLDEN_MEAN, 0 ],
        'b' => Vector[  1, -GOLDEN_MEAN, 0 ],
        'c' => Vector[ -1, -GOLDEN_MEAN, 0 ],
        'd' => Vector[ -1,  GOLDEN_MEAN, 0 ],
        'e' => Vector[  GOLDEN_MEAN, 0,  1 ],
        'f' => Vector[ -GOLDEN_MEAN, 0,  1 ],
        'g' => Vector[ -GOLDEN_MEAN, 0, -1 ],
        'h' => Vector[  GOLDEN_MEAN, 0, -1 ],
        'i' => Vector[ 0,  1,  GOLDEN_MEAN ],
        'j' => Vector[ 0,  1, -GOLDEN_MEAN ],
        'k' => Vector[ 0, -1, -GOLDEN_MEAN ],
        'l' => Vector[ 0, -1,  GOLDEN_MEAN ]
      },
      :faces => %w| iea iad idf ifl ile
                    eha ajd dgf fcl lbe
                    ebh ahj djg fgc lcb
                    khb kjh kgj kcg kbc |
    }
  }
  # Get all triangles from a primitive.
  def Primitives.triangles(solid)
    hash = PRIMITIVES[solid]
    if hash.nil?
      puts "Unknown solid '#{solid}'"
      exit(-1)
    end
    points = {}
    hash[:points].each do |name,point|
      points[name] = point.map { |coord| coord.to_f }
    end
    triangles = []
    hash[:faces].each do |str|
      triangles << [
        points[str[0,1]],
        points[str[1,1]],
        points[str[2,1]],
      ]
    end
    triangles
  end
end


# Subdivide a line into (frequency + 1) segments,
# distributing rounding errors across the line.
# This routine is for demonstration purposes.
# Although simple, it does not distribute
# rounding errors very evenly.
def subdivide_line(line,frequency)
  result = [ line[0] ]
  (frequency + 1).to_i.downto(2) do |step|
    result << result[-1] + ((line[1] - result[-1]) * (1.0 / step.to_f))
  end
  result << line[1]
end


# Subdivide a triangle into (frequency + 1) ** 2
# congruent sub-triangles.
def subdivide_triangle(triangle,frequency)
  steps = frequency.to_i + 1
  # Pick two sides.
  side_a = [triangle[0],triangle[1]]
  side_b = [triangle[0],triangle[2]]
  # Calculate the points along those two lines.
  vertices_a = subdivide_line(side_a,frequency)
  vertices_b = subdivide_line(side_b,frequency)
  # Start with triangle closest to the AB intersection.
  result = []
  vertices_current = nil
  vertices_next = [side_a[0]]
  # For each step, create the next line closer to (and parallel to)
side_c.
  (1..steps).each do |step|
    line_next = [vertices_a[step],vertices_b[step]]
    # Get all of the vertices along that line.
    vertices_current = vertices_next
    vertices_next = subdivide_line(line_next,step - 1)
    # Add the first triangle.
    result << [vertices_current[0],vertices_next[0],vertices_next[1]]
    # Add the rest in pairs.
    (1...step).each do |line_step|
      result << [
        vertices_current[line_step - 1],
        vertices_next[line_step],
        vertices_current[line_step],
      ]
      result << [
        vertices_current[line_step],
        vertices_next[line_step],
        vertices_next[line_step + 1],
      ]
    end
  end
  result
end


# Normalize all points in the given triangles.
def normalize_triangles(triangles,norm)
  triangles.map do |triangle|
    triangle.map do |vertex|
      vertex * (norm.to_f / vertex.r)
    end
  end
end


# Sample usage.
triangles = Primitives.triangles(:icosahedron).map do |triangle|
  normalize_triangles(subdivide_triangle(triangle,3),1)
end.flatten
p *triangles


    - Warren Brown