Finding/Categorizing Paths from A to B

[sub3]

Hi,

I hope someone can share some ideas for an approach.

I have a bunch of data for driving from point a to b and b to a (home & work).
It is GPS data, so it is lat/lon & speed.  I am trying to see what
the data says about me, i.e. optimized time, least time waiting,
total milage, etc.

What I don't have is any indication of what paths I took, so I
have no idea how to average several trips / path.  From my own
thoughts, there has to be many distinct paths; but finding them seems
to be a very hard problem (no silver bullet), so I know I'll be
doing a lot of hard work.

But, here is current thoughts for an approach:

-Find an area for each type of path that the other paths don't
go near (perhaps an intersection, town, road, etc).  This would allow me to
mark/name that type of path, then move on to the rest.  As I am mixing path
segments, this doesn't seem to work well.

-Given the first path x, find each point in y, to the line in x. Find the
total distance away per points.  Determine some cutoff point to determine
if x is really y.  If not y becomes its own path (which will then be
compared to the other path).


Has anyone done something like this that they can share their approach, or
can think of an easier/better way?

Thanks all.

[webb.sprague]

Thoughts below

> I have a bunch of data for driving from point a to b and b to a (home &
> work).
> It is GPS data, so it is lat/lon & speed.

Could you specify the format of one piece of data exactly in text?  Is
it point, line, or polygon?  Samples?

> What I don't have is any indication of what paths I took, so I
> have no idea how to average several trips / path.  From my own

You can aggregate points into lines, which then would give you a path,
using a group by on a time criteria, for example.

I would try to think in terms of the canonical geographical vector
model:  is it a point (zero dimension -- like a town in a small scale
map) , a line (single dimension -- a road in the map), or a polygon
(like a state boundary).

How exactly are you collecting the data -- it might make it easier for
all of us.
_______________________________________________
postgis-users mailing list
postgis-users@...
http://postgis.refractions.net/mailman/listinfo/postgis-users

[sub3]

Thanks for you quick reply.

>Thoughts below
>
>> I have a bunch of data for driving from point a to b and b to a (home &
>> work).
>> It is GPS data, so it is lat/lon & speed.
>
>Could you specify the format of one piece of data exactly in text?  Is
>it point, line, or polygon?  Samples?

I have a table (called rawdata) with columns of :
Path#,Point#(int),Latitiude(double),Longitude(double),Speed(double),Timestamp,Point (basically lat/lon in a single point object)

I have a second table called paths:
Path#(int),Line (line object)

So, I really want to find a way to look at the paths table and determine that paths 1,2,3 I took 1st street. Path 4,5 I took 5th street. Path 6 started going on 1st street then switch over to 5 street.

So if I looked at it graphically on a map, I could easily determine which paths where which.


>
>> What I don't have is any indication of what paths I took, so I
>> have no idea how to average several trips / path.  From my own
>
>You can aggregate points into lines, which then would give you a path,
>using a group by on a time criteria, for example.
>
>I would try to think in terms of the canonical geographical vector
>model:  is it a point (zero dimension -- like a town in a small scale
>map) , a line (single dimension -- a road in the map), or a polygon
>(like a state boundary).

It would definitely be one line for the full trip. So if I took each point in the line, and found the
closest point between it and a different line; it would be the same line as long as none of them differed by too much?  Is that really the best approach?


>How exactly are you collecting the data -- it might make it easier for
>all of us.
I have a gps feeding into a laptop and capturing the data every minute.


Thanks for you help.

[webb.sprague]

>
> I have a table (called rawdata) with columns of :
> Path#,Point#(int),Latitiude(double),Longitude(double),Speed(double),Timestamp,Point
> (basically lat/lon in a single point object)
>
> I have a second table called paths:
> Path#(int),Line (line object)
>
> So, I really want to find a way to look at the paths table and determine
> that paths 1,2,3 I took 1st street. Path 4,5 I took 5th street. Path 6
> started going on 1st street then switch over to 5 street.
>
> So if I looked at it graphically on a map, I could easily determine which
> paths where which.

Overlaying on a map should be easy: QGIS, etc.  Do you have a table of
streets, if you need to see which street you went down (you need one)?

>>
>>> What I don't have is any indication of what paths I took, so I
>>> have no idea how to average several trips / path.

You have lines that are your aggregated points that are the paths you
took, you have times on each point, plus you have an attribute
(path#) that allows you to group points into paths.  If speed is what
you need to average (It is hard to understand what means "how to
average several trips/ path" -- average WHAT over WHAT?), then you can
find the speed for each path by taking the (time at begin - time at
start) / distance for each path.

YOu might be able to GROUP BY path# on rawdata, then use
MAX(timestamp) - MIN(timestamp) to get time elapsed.  I would update
the "paths" table with this.  Then LENGTH(path) (check docs for
correct func).  Then update paths set speed = length/ time. Voila --
sort by speed, assuming that the begin and end in paths is always the
same.  This doesn't give you which street at all, but that would be
the next query.

I am afraid you haven't specified your problem very clearly so it is a
little hard to help more.

Also it is easier to deal with code and output without your filtering.
 For the tables, could you run "\d mytable"  and cut and paste the
output?  Maybe also a select blah limit 10 from the tables, using
astext to get the geometries?  Don't worry about email length.  Google
likes to mine it for text anyway....
_______________________________________________
postgis-users mailing list
postgis-users@...
http://postgis.refractions.net/mailman/listinfo/postgis-users

[sub3]

>> So, I really want to find a way to look at the paths table and determine
>> that paths 1,2,3 I took 1st street. Path 4,5 I took 5th street. Path 6
>> started going on 1st street then switch over to 5 street.
>>
>> So if I looked at it graphically on a map, I could easily determine which
>> paths where which.
>
>Overlaying on a map should be easy: QGIS, etc.  Do you have a table of
>streets, if you need to see which street you went down (you need one)?

That is exactly what I want to do... but first I want to find a way to boil down all trips to 12 or so distinct paths; without having to overlay every trip.  But since I only have points, not streets; i have no way to say path #1 is different from path #2.

So take the example path over a grid A->E by 1->5 where A1 is start, E5 is the end.
I would have paths:
1 | Line(A1,B1,C1,D1,E1,E2,E3,E4,E5)
2 | Line(A1,A2,A3,A4,A5,B5,C5,D5,E5)
3 | Line(A1,A2,A3,B3,C3,D3,E3,E4,E5)
4 | Line(A1,B1,C1,D1,E1,E2,E3,E4,E5)
5 | Line(A1,B1,C1,D1,E1,E1,E1,E2,E3,E4,E5)

I would like to find out that 1 is the same path as 4 and 5, but I can't do a direct 1==4. Since A1 is a
latitude/longitude from a GPS, it wouldn't be the exact A1 each time.  If I traverse through A1, I might get lat/lon: 39.54/75.07 one day, while 39.53/75.08 the next day.  It would be the same road, just 200ft further down it, based on when the gps record is taken.

After I find the distinct paths,I can easily find avg time/speed based on rows 1,4,5; since they are really the same.

Thanks.

[webb.sprague]

> That is exactly what I want to do... but first I want to find a way to boil
> down all trips to 12 or so distinct paths; without having to overlay every
> trip.  But since I only have points, not streets; i have no way to say path
> #1 is different from path #2.

Write a function that returns an intersection id based on a point;
this function would have to find the closest intersection to the
input.  You need a table with intersection point geoms and
intersection ids.  The function could  be a big case statement to
start.

You might also be able to finesse this with "snap to grid" or by
rounding (look in the docs -- I would read the section on geometric
functions and see if any strike you as useful)

Then use array_accum  and group by on the path# to create lists of
intersection sequences.  Compare these however you feel like.

If you use another projection (UTM etc) the units will be in meters
and easier to interpret.

There is still a lot of work, but does that make sense?
_______________________________________________
postgis-users mailing list
postgis-users@...
http://postgis.refractions.net/mailman/listinfo/postgis-users

[webb.sprague]

Rethinking:

On Sun, May 18, 2008 at 12:10 PM, Webb Sprague <webb.sprague@...> wrote:
>> That is exactly what I want to do... but first I want to find a way to boil
>> down all trips to 12 or so distinct paths; without having to overlay every
>> trip.  But since I only have points, not streets; i have no way to say path
>> #1 is different from path #2.

1.  Find or make a table that describes the street system as polygons
for each block and intersection, with unique ids  (create through
buffering lines/ points or by converting a shapefile or creating
geometric data from float input). Be careful to get the topology right
(full coverage, non overlapping etc)

2.  Match each of your points to the street/ intersection polygon it
is "within()", store the ID.  This is how you go from floating
geometries to a schematic representation.

3. Using group by and sort, collect the street/ intersection ID's into
an ordered array array_accum for each path

4.  For each array, collapse the repeated street/ intersection IDs
into single IDs (make  S1, S1, S1, I2, I2, S3, S3, I4, I4, I4 into S1,
I2, S3, I4, with a fancy function or some regex trickery after
converting into a string).

5.  Give the new schematic / collapsed array to each path row (UPDATE).

6.  Find the average times, return the paths with the lowest.  You may
have to average times based on grouping with the street sequence to
get meaningful results.  Also different times/ events may yield
different average trip times.

If you start a wiki page with data, code, results, and questions
somewhere, I would happily collaborate (I think this is a fun problem)
_______________________________________________
postgis-users mailing list
postgis-users@...
http://postgis.refractions.net/mailman/listinfo/postgis-users

[Paragon Corporation-2]

 


On Sun, May 18, 2008 at 12:10 PM, Webb Sprague <webb.sprague@...>
wrote:
>> That is exactly what I want to do... but first I want to find a way
>> to boil down all trips to 12 or so distinct paths; without having to
>> overlay every trip.  But since I only have points, not streets; i
>> have no way to say path
>> #1 is different from path #2.

This is all very interesting stuff.  

>> 1.  Find or make a table that describes the street system as polygons for
each block and intersection, with unique ids  (create through buffering
lines/ points >> or by converting a shapefile or creating geometric data
from float input). Be careful to get the topology right (full coverage, non
overlapping etc)

If you are in the U.S.  You could download the Tiger Street index for your
area to give you paths for streets

http://www2.census.gov/geo/tiger/TIGER2007FE/


2. Then Use Paul's nifty hack  (plus my corrections to his logic :) to snap
your GPS points to a line segment  (that will sort of normalize all your
points so to speak)

http://blog.cleverelephant.ca/2008/04/snapping-points-in-postgis.html


3.  Now form new line segments from the snapped points - this will guarantee
all your line strings align with the street topology.

4. Now to figure out what paths are the same -  do a  (well this part I
haven't given much thought to) and if I thought about it a bit more, I'm
sure I can come up with something simpler than this

WHERE st_intersects(a,b) AND Length(ST_Difference(a,b)) < sometolerance

Hope that helps,
Regina


_______________________________________________
postgis-users mailing list
postgis-users@...
http://postgis.refractions.net/mailman/listinfo/postgis-users

[Greg Troxel]

  I have a bunch of data for driving from point a to b and b to a (home &
  work).
  It is GPS data, so it is lat/lon & speed.  I am trying to see what
  the data says about me, i.e. optimized time, least time waiting,
  total milage, etc.

I have the same sort of data, but haven't gotten to looking at it.

My thoughts are to have a table of branch/merge points, perhaps obtained
manually from looking at overlaid paths, but basically I know which
intersections I turn at.  You could do this from street data too, but it
might be easier to have a more restricted set.

Then, I'd convert my long paths into segments of shorter ones between
branch points.  I could then look at sub-path travel times, and analyze
the various choices.

_______________________________________________
postgis-users mailing list
postgis-users@...
http://postgis.refractions.net/mailman/listinfo/postgis-users