Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

I'm building an application that uses data from GPS units on board vehicles and displays it on a map. A lat/long is recorded every .5 seconds and a session can be many hours... this can add up to be a lot of data. The vehicles travel in a straight line the majority of the time but the data needs to be very accurate when a vehicle turns a corner, hence the high recording frequency. I'm storing the lat/longs as a POINT in a PostGIS/PostgreSQL database (This isn't set in stone).

I'm trying to find a way of reducing the dataset when displaying it on the map while still maintaining accuracy.

I have come up with a few options:

  1. Group the data into 2 second blocks and average the lat/longs in each group. This is really easy to do but has too much information when traveling in straight lines and not enough when turning corners.

  2. Group points together which are a certain distance (a vehicles length?) and time (4 seconds?... to ensure it won't be group if a vehicle moves over the same point half an hour later)

  3. Calculate splines of the data (I don't know very much about this option).

Perhaps PostGIS already provides this functionality? I'm simply looking for someone to point me in the right direction.

share|improve this question
    
Do you need to show the entire session for each vehicle? Or can you just return back the top 30 for each vehicle? Then you show motion/direction without the entire history of the run. –  D.E.Wright Aug 24 '11 at 23:04
    
I'm not sure what you mean by "top 30". The whole session needs to be represented, but you're right about he motion/direction... If a vehicle travels in a straight line at a constant speed for 5 minutes I could simply have a point a the beginning and end. I'm trying to find an algorithm that would allow me to do this sort of reduction. –  Mike Aug 24 '11 at 23:12
    
From the postgis website: "Our list of future projects includes full topology support, raster support, networks and routing, three dimensional surfaces, curves and splines and other features." No dice.. –  canisrufus Aug 24 '11 at 23:13
1  
Oh I see. It's a little more complicated than that...It's not a 2d map but a 3d visualizer which needs a array of lats, longs and times. Yes, unfortunately I'm not sure there is an easy solution. –  Mike Aug 24 '11 at 23:46
1  
Do you need to preserve points to determine velocity? In other words, if the vehicle is traveling on a straight highway but occasionally speeds, is this information - which might otherwise be weeded out - important? –  Kirk Kuykendall Aug 25 '11 at 17:40
show 7 more comments

2 Answers

up vote 5 down vote accepted

In PostGIS, you could use the 3DM concept. A 3DM point has four "dimension" X, Y, Z, and M where "M" stands for "measure" and can be any value you like, e.g. a timestamp in seconds.

Creating a line from 3DM points should preserve the fourth dimension for every single point. (I haven't tried this myself. I'm basing this on the excellent "PostGIS in Action" book.) Then you could use Douglas-Peucker Algorithm to reduce the number of points/vertices of the line.

share|improve this answer
1  
Yes, ST_Simplify preserves extra coordinate info, so LINESTRINGM geometries will remain intact (but ideally with redundant points removed). –  Mike T Aug 26 '11 at 0:53
    
@underdark Thanks for the answer. It seems almost perfect except won't I lose speed information? I.e. if a vehicle travels in a straight line for 2km but in that time stops and starts several times it will return just two points. –  Mike Sep 1 '11 at 4:33
    
Used a tolerance to prevent losing speed information. –  Mike Oct 13 '11 at 1:09
add comment

I think what you're trying to do is to simplify the data. PostGIS has a ST_Simplify function which takes a LineString or Polygon geometry and a tolerance and tries to remove vertices without significantly changing the geometry (see Douglas-Peucker Algorithm).

Now, the big caveat: you'll need to convert your points to lines before this will do anything meaningful. Check out ST_MakeLine. If this is out of the question, you'll need to find another solution. You could convert to a line and then back to points after simplifying, although this won't preserve attributes of points (time may be the attribute you need to preserve here).

share|improve this answer
    
Very good answer, thank you. The only problem as you pointed out as the time attribute needs to be preserved. Perhaps I need to implement the Douglas-Peucker Algorithm myself as a procedure so it can work on single points? –  Mike Aug 25 '11 at 4:31
    
@Mike a simpler solution than that might be to 1. create a point set without the third dimension, 2. simplify it, 3. add the third dimension back on to the remaining points –  canisrufus Aug 25 '11 at 12:13
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.