CompSciWeek10

Suggested Reading

• Linear Transformations and Their Representing Matrices by David Webb

Class 1

A motivating problem for vector mathematics.

The following problem appears in structure building for molecular modeling. The 20 common amino acids are joined into polypeptides by attaching the C-terminus of one amino acid to the N-terminus of the next. Each joint has a specific orientation in 3D space (determined by the amide plane).

Here, we tackle a smaller instance of this problem. You are building a series of 2D figures by joining together the edges of smaller 2D figures. At each joining point, an orientation is specified in terms of local x and y directions. When joining A and B, for example, the ending orientation of A must match the starting orientation of B. We choose to rotate and translate B to make this happen.

This phrasing is partially motivated by a fun little language for composing 2D figures [1]. Its solution involves important concepts for determining relative positions and orientations using vectors, and should be generally useful for any problem involving geometric relationships.

The following code outlines a class structure for holding each object. Two basic functions to implement are figure visualization (vis, below) and the joining process. Before the next class, try and implement the joining operation yourself!

<source lang="python">

1. Holds shape class

from numpy import * import pylab as plt

1. not used, since it's just a single array
2. class Pt:
3. position + orientation (6 numbers)
4. v = array([[A00, A01, t0],
5. [A10, A11, t1]])
6. A00, A10 is local x-direction
7. A01, A11 is local y-direction

class Shape: # lines : [ t1, t2 ] (list of lines in object), t1 : 2D vec # REDO -- lines : one giant array # pts x 2 (st/end) x 2 # # rt : Pt (right sticky point) def __init__(self, lines, rt): self.lines = lines self.rt = rt def __add__(a, b): # return r = a + b print "TODO: implement addition" # 1. determine rotation matrix that attaches # b at origin onto a.rt

# 2. transform all of b's lines and # add them to a.lines -> r

# 3. fix r's right endpoint # by combining a's end with b's end return r

1. vis : Shape -> pylab state
2. do visualization using pylab
3. Note: This is not a method inside Shape since pylab is not really related
4. to the properties of the Shape class.

def vis(s): # loop through lines and call plt.plot() on each one. for line in s.lines: st_x, st_y = line[0] en_x, en_y = line[1] plt.plot([st_x, en_x], [st_y, en_y], 'k-', lw=2)

       # extra lines to represent endpoint of the shape

st_x, st_y = s.rt[:,2] en_x, en_y = s.rt[:,2] + s.rt[:,0]*0.2 plt.plot([st_x, en_x], [st_y, en_y], 'r-', lw=2) # local x-dir st_x, st_y = s.rt[:,2] en_x, en_y = s.rt[:,2] + s.rt[:,1]*0.2 plt.plot([st_x, en_x], [st_y, en_y], 'b-', lw=2) # local y-dir

xh = array([[0,0], [1,0]]) # line from 0,0 to 1,0

yh = array([[0,0], [0,1]]) # line from 0,0 to 0,1

triangle = Shape(array([xh*2, [[0,0], [1,1]], [[2,0], [1,1]]]), array([[ sqrt(0.5),-sqrt(0.5), 1], [ sqrt(0.5), sqrt(0.5), 1]])) square = Shape([xh, xh+array([0,1]), yh, yh+array([1,0])], array([[1,0, 1], [0,1, 1]]))

1. a = triangle + square #

plt.plot([-1,2], [-1,2], 'w') # make the plot large enough to see

vis(triangle) plt.show() </source>

Class 2

• Linear transformations
• Homogeneous coordinates
• Composing linear transformations
• Inverse operations, implicit solutions, and complexities

Homework - Due Wed., Nov 5

1. I have a linear transformation that maps vectors in <math>R^m</math> to vectors in <math>R^n</math>. It is represented by a matrix (an <math>n \times m</math> array). I want to specify it in terms of how it acts on a set of starting vectors (in <math>R^m</math>). How many starting vectors do I need to transform for a complete specification? Is there an easy way to choose them?
2. Say that I wanted to have several "sticking points" for each object. What modifications would have to be made to the Shape class? What does this mean for the __add__ operation?
3. I have two objects in 3D, each with a 3x3 orientation matrix, A for object A and B for object B. What is the rotation matrix for rotating elements attached to A (specified in A's coordinate frame) to match elements attached to B (specified in B's coordinate frame)?
4. Coordinate frames always should have the property that each vector is normalized (<math>v_i \cdot v_i = 1</math>) and orthogonal to all the others (<math>v_i\cdot v_j = 0</math>). Matrix multiplication transforms objects in the coordinate frame to objects in the global frame. What does matrix multiplication do if the "coordinate frame" has a vector that is not normalized? What if it has 2 vectors that are not orthogonal?
5. The following function takes points in 2D space and fits them to a line of the form y = a*x + b. Use it to write a function that takes points in 2D space and returns an orientation matrix describing the best fit direction as "x hat" and the other direction as "y hat".

<source lang="python"> from numpy import * import numpy.linalg as la

def fit(xy): # xy is an N x 2 array of points

 V = xy.copy() # 1st col is x (linear term), a
 V[:,1] = 1.0 # 2nd col is 1.0 (constant term), b
 Vy = dot(xy[:,1], V) # sum x_i y_i and sum y_i
 Dx = dot(transpose(V), V) # Vandermonde matrix
 a, b = la.solve(Dx, Vy) # solve Dx * [a,b] = Vy
 return a, b

x = arange(12) # test the function! y = x*12 - 2.0 + random.random() - 0.5 print fit(transpose([x,y])) </source>