On your PM1

The bulk of your project 3 grade (60+% I am guessing) will revolve around building a B+ tree. The side project is to use your PM1 do to something interesting. In this case we'll use it to try to do some animation. This is the idea: I will create some world by creating a bunch of segments- I can fill it with anything I can make out of non-intersecting line segments. Think something like 10,000 lines in a 1048576 x 1048576 world. Then I'll ask for some windowed flyby view- for instance, "slide from (0,0) to (1000,1000) in 1 unit increments with a view window that is 50 x 50". Your job will then be to use the PM1 to help select to segments to draw in each frame. What's fun about this is that you have some freedom with your implementation. The simplest approach would just be, for each frame, to do a full rectangle query from the PM1. But you will find that each frame mostly overlaps the previous one, so this would involve a lot of redundant work. You might just query the newly exposed portions of the screen for each frame, and do a linear search of your old lines to decide which are no longer on the screen. You might also do some lookahead with the PM1, so that you don't actually even have to query it for each frame. The PM1 is certainly not free to access, and if you can narrow yourself to a small set of segments a linear search through those segments could easily be faster than a PM1 access. Hopefully meesh will appreciate this as the return of "We're not going to tell you the fastest way to do it, try to be creative." :) In project three we'll actually use the separate adjacency list to plot paths. This way I could, for instance, draw a large maze in the PM1, and then have the adjacency list store the correct path through the maze and ask you to follow that. There's truly no limit to what we can do! And finally, there will be two 'modes' to this PM1 application. The first will be a "to screen" application, while the second will print each frame as text output. The latter will make things easier for me in grading ;)

Web Accessibility