I probably shouldn’t give too many details, but I’ve been in talks with a certain freeware developer over developing a flight planning application for a web connected hand-held device. (Anybody who knows anything about me can probably guess the developer and the device.)
My part would be a server app that would respond to requests for data from the device and send new data or updates. Nothing too different than what I’ve been doing before, but one of the things we’ve been talking about is managing “areas”. His concept was that if the user entered an id that wasn’t on the device already, my server would send the device a whole “area”, and the device would keep track of what areas it had in memory already, when they were last updated, and would occasionally request updates of the areas it knew. He thought that each area could be a whole country. The first thing that struck me about that is that if the point you asked for was in the US, you could be asking for thousands of waypoints (70,584 in the current database). That could take a long, long time on an Edge network. Then we discussed maybe breaking it down by state or province in the US and Canada.
But the thing is, I used to be a GIS (Geographic Information Systems) programmer. I know there are better ways. At first I started looking around for the HHCode algorithm since I worked with Herman Varma and the Oracle guys implementing the original Oracle “Spatial Data Option”, until that scumbag Jim Rawlings screwed me out of three months pay. But I can’t find the source code anywhere.
So my next idea was a modified quad tree. Basically, when populating the database, I made a “rectangle” that incorporates the whole world and start adding points. When I hit a threshold, I subdivide that “rectangle” into 4 equal sub-rectangles, and move the points into whichever rectangle they belong to. This means that where points are sparse, the rectangles are large, and where they are dense, the rectangles are small. That way I’ve got some consistency in the size of the file to be sent to the device, and I’m not wasting people’s time sending the 19 waypoints in Wake Island, say, as an individual file.
I’ve been experimenting today with PostGIS, which is an extension to Postgresql which adds some very efficient geographic query tools. The program I wrote to take the data from my old MySQL database and put it into the PostGIS database while building these quad cells runs pretty fast. Surprisingly fast, even. PostGIS is pretty capable. Too bad the manual for it sucks rocks.
One thing that I keep forgetting is how much faster computers are now than when I was doing GIS for a living. I keep expecting things to take hours when they end up taking minutes, because the last time I did this sort of thing I was using a 40MHz SPARC and now I’m using a dual core 1.86GHz Intel Core2 Duo, and I’ve got more RAM at my disposal now than I had hard drive space back then.
Anyway, mostly I’m writing this because I’m really enjoying working with GIS-type stuff again. I wish I could do it full time again.
The quad tree sounds like a hack I came up with lo these many years ago, when Mandelbrot sets were still cool.
The PC I had to code with was slow enough that it would take a day or more to generate a set to cover the screen, so I made a couple of assumptions. I had read that the MS was connected, so my program calculated the pixels around the outside border, then quartered the area. Each quarter was checked if all pixels around the border were identical. If yes, blockfill and move on to the next quarter. If not, move on to the next quadrant, recurse. This algorithm could generate a MS in a couple of hours, by spending al its time on the fiddly bits, and not wasting time on the big flat areas.
I’m still sorta proud of that code.
Reminds me of a hack I made waaay back when
* mandelbrot sets were newly cool
* computers were slow
* Pen Plotters existed!
I sorted xy-vectors ( and pen color actually ) for large plotter files as part of the plot spool s/w. These could be generated really stupidly, with long pen movements between vectors.
After sorting, it was kind of fun to watch it draw in Sierpinski sorted order.
Sarah
Hey long time since I heard from the guy who use to sing Barrett’s Privateers over HHCode discussions and beer. Contact me through BIO in Dartmouth NS and I’ll see what I can do to give you a hand.
herman varma