Thursday, 3 December 2009

The Shoestring Explained




One of my students got too little sleep last night because he kept trying to figure out why the shoelace algorithm worked. One of those really bright kids who transferred in and just hasn't had an education up to his potential. He has never been introduced to vectors, so after a very cursory overview of the idea of vectors and cross products, I showed him the following as a way of "explanation". He had seen determinants in Alg II but never used to find area.



If we take the the set of vertices and add one more point at the origin, then we can draw vectors from the origin to each pair of consecutive vertices. In the first image we have drawn the vetors [1,1] and then [5,2], and we show the triangle area formed between the two vectors. The Determinant of the two vectors will give us twice this area. If we imagine the area being swept out by the first vector rotating until it reaches the second, a rotation of a positive direction will give us a positive value for the determinant, and a negative rotation will give us a negative value. Since we started at (1,1) our first area is negative, and equal to or -3/2.


As we proceed in order from vertex to vertex, the vector triangles will add and subtract areas as it sweeps around the polygon until it gets back to the starting point. The Vectors from [5,2] ot [4,4] add back the area just subtracted in the first pair of vectors, and also the area inside the polygon formed by triangle BCD (this is just by chance because vectors AB and AD have a common slope)



The next pair of vectors add the rest of the polygon, but also some excess in the amount of triangle ABE. This excess is removed when we sweep back to the original point A and so we have the final area of the polygon.

If we had traversed our way around the vertices in the reverse order, the determinants would have all had their signs reversed and we would have a total which was the negative of the actual area. Hope that is pretty clear, there was a lot more armwaving when I was doing this at the board.
Post a Comment