GJK Explained

A friend of mine has been writing an article that explains the GJK (GIlbert-Johnson-Keerthi) algorithm for collision testing.  His goal is to write something that comes at it from a geometric approach in the hopes to make it more understandable as he finds that many of the other explanations are far too convoluted to follow.  If you are interested in collision detection and how to test it easily you should check it out.  He would love to get some feedback on whether what he wrote is easy to understand and how things could be clarified.

You can find it here:  http://phill.vec3.net/gjk

Creating Data Structure Animations with Processing.js

Ever since I saw the first demonstration of Processing.js I have wanted to do something with it.  I teach a data structures and algorithms course and one of the annoying things I have found is that many of the animations for showing how these structures work were written in Java and put on a web page as an applet.  Many of these animations are also just broken.   Thus as a response I thought it would be a good idea to put together a set of algorithms animations that didn’t need any plugins.

I started putting together a small bubble sort animation about a year ago.  I liked the way the way the final animation looked but I didn’t like the way the code looked and felt.  It was really hacky and not very good.  Definitely not extendible for other algorithms.  About a week ago I decided to restart that effort.  I thought about what would actually be necessary to do general algorithms and data structure animations.  I rewrote the code (you can get it here: https://github.com/cathyatseneca/DSAnim ).  Currently the code animations are pure Processing sketches (I didn’t stick any bits of JS in my sketch this time ).  However that might change later when I try to add in controls.  You can check it out live here:

https://cs.senecac.on.ca/~catherine.leung/sketches/index.html

When I was putting these animations together, one of the things that I had trouble with was translating the algorithms into animations. Processing works by repeatedly calling a draw() function in which you tell it what to draw in the next frame.  In other words there is a sort of built in loop.  While it is possible to call a function for some algorithm (a sort for example) within the draw loop, you can’t really animate it just by calling it as it will be called each frame and what you want is to animate steps within the function.

I admit that I’m very new to Processing.  Thus, this may not be the best way to do this (if anyone has suggestions please let me know!)  The design I settled on in the end was to create a general array animation. The array has a single draw function that the main draw loop will call.  Depending on the state of the array, the array’s draw() function will animate one frame of what is going on (one frame of a swap for example).

The array has states which determines what to draw.   Currently the array has these functionalities:

• moves (move number from one element to another)
• swaps (swaps two values in array)
• stable (nothing is happening)
• move to temp (move number to a temporary location out of array)
• move from temp (move number from temporary location to array)

The object also has indicators and a splitter bar that you can add to your animation. You can also change the colour of the text in the array.

So far I have completed the bubble and insertion sorts.  I think I will need to add more functionality to properly show merge sort.  I have not yet really thought too much about a quick sort.  After the sorts I will probably start looking to add trees and lists.  I am hoping to also add animations for other data structures as well.  The code is far from perfect but it looks neat and for now that will have to do .

First Blog of Year and a Story of a Scam

Hi All,

The new school years begins so I figured I should write a blog post for planet CDOT.  Now… the only question is what to write about?  I had been working on trying to create a series of processing.js animations to illustrate how some algorithms works.  But then while trying to figure out the best way to animate a merge sort, I got a call.

It was one of those long distance call rings which meant that it was either my parents or telemarketers…I hate being telemarketed to.  I know that the telemarketers are just paid to do a job so I’m polite to them but I really don’t like getting calls from people I don’t know.  Thus the conversations usually go: “Thank you for calling, can you please take me off your calling list.”.  Usually they do this or at least say they will and hang up.

Anyhow, this person calls and since I didn’t recognize their voice I start on the “please take me off your list” line.  They then proceed to tell me that they are calling because they are detecting that my computer is downloading a lot of viruses.  And since I couldn’t believe my ears to the silliness of that statement I said “what?” over the phone.  He then says something about detecting many viruses being downloaded onto my windows computer.  (I have been using Macs for about 3 years now and I’m only ever on windows bootcamp partition when I absolutely have to be). So I insist that I highly doubt that my computer has a problem.  He then insists that they have an “internet research company” that was detecting a large number of virus downloads to my computer.  This exchange happens a few more times (I think he missed the part where I said I blew up my windows machine 3 years ago)

Although I was irritated about getting telemarketed/scammed at I thought it was really really funny at the same time. I really wanted to see where this was going.  So I asked “So how are you able to associate my computer’s IP with my phone number”.  And then he continuous on about whether or not I knew what a virus was and how my windows computer was infected.  I then told him to hold because he was too funny and I had to record him for my students.  A few seconds later he hung up.  I guess that he didn’t want me using it to teach my students about viruses on windows.  You would think he would love to have his research shared .

Now, having finished this conversation I wanted to know what was going on so I did a search on scams, viruses and telemarketing.  Apparently there are some social engineering scams where these telemarketers would try to gain access to a person’s computer and then use it to steal credit card info.  For myself, I knew this was a hoax from the start but I can’t help to think what would happen if this was someone like my parents who aren’t really comfortable with computers.  Would they fall for it?  How do we spread the word to our friends and family about these sorts of scams so that they are aware of them and won’t fall victim.  I think I will start by writing this blog.