Anna Becker
Software Engineer

Graham’s Scan

Last Friday I attempted my implementation of Graham’s Scan. My C++ is a bit rusty since I haven’t used it since the fall. Last term was all C, but we were doing with it was different enough to make me a bit rusty. The project isn’t due until this Monday so the plan was to get the following coded:

1. Write the point class for holding the coords and the doing the math needed – mostly cross product and distance.

2. Input the points coords from the given files – we were given 6 different sets. To make it easier on the grader, I made a switch statement so all they have to do is type the # of the file and it passes the file name to the input function. I’m nice like that.

3. Write and test the function that finds Point 0 – the point with the smallest Y coord. And if there is a tie, to choose the one with the smallest X.

4. Write and test a merge sort that sorts the remaining points by polar axis to P0 by calculating the cross product (the vector of P0Pi x the vector of P0Pj). If positive Pi goes first and if negative Pj goes first.

Midnight. This is where I hit a brick wall. Or more specifically this part of my notes: if two points have the same polar angle, throw out the one with the shortest distance to P0. Fuck. I was using an array of point objects. Doing it in the merge sort might have worked by just ignoring it and not copying, but not if it was the last element and then you have issues with the size. I might have gotten it to work correctly, but it seemed more trouble than it was worth.

So which container to use instead? A vector would be the easiest to implement, but will it work? A linked list would be a lot more complicated, but would work better. I opened a new project and started over using a linked list.

1am: eff this. I need to sleep on it. I have an assignment due this week that I haven’t even looked at yet. Not to mention personal obligations. There really are only so many times a person can not show up to social events before people stop asking.

8am: I should just try a vector. Just to see what happens. By 1pm I had a fully working version including the merge sort! Which left enough time to go to the market, stuff some strawberries and go to the cinco de mayo party.

Would a link list be better? Yeah. But I think it would have been overkill for the assignment. There are only 18 set of points in the largest file, so the copying of merge sort isn’t a big deal. It also doesn’t matter if I rearrange the points since the only thing I’m doing with them is this. Using a vector is the most efficient way to go in this case.

All I have left to do this weekend is the graham’s scan function. Should be fine.

Leave a Reply

Your email address will not be published. Required fields are marked *