[pgrouting-users] Setting the tolerance argument in assign_vertex_id

[Dan Putler]

Hi Steve,

The CanMap layout has changed very little between v2006.3 and v2009.4 (which I'm using). When I shrank the layer down from all of BC to just Greater Vancouver and the Fraser Valley, I thought it might create problems with the FromNode / ToNode values, so elected to use assign_vertex_id(). At this point I think I've been too clever by half in focusing on reducing the size of the network, and need to go back to the original DMTI shapefile.

Is my assumption correct that I just need to copy FromNode into the source column and ToNode into the target column and I'm on my way with the DMTI layer? I haven't seen any documentation on working with edge layers that already have node information (much of the documentation seems to assume the use of OSM data, which isn't surprising).

Thanks for your continued hand holding.

Dan


--- On Fri, 8/27/10, Stephen Woodbridge <woodbri at swoodbridge.com> wrote:

> From: Stephen Woodbridge <woodbri at swoodbridge.com>
> Subject: Re: [pgrouting-users] Setting the tolerance argument in assign_vertex_id
> To: "Dan Putler" <putler at yahoo.com>, "pgRouting Users List" <pgrouting-users at lists.osgeo.org>
> Received: Friday, August 27, 2010, 1:56 PM
> Dan,
> 
> In general the data is not represented as 2.5D, it is all
> 2D and there 
> are relationship tables the tell you about zlevels.
> 
> Navteq uses zlevels and DMTI used to call it ren (Relative
> Elevation Nodes).
> 
> Also I noticed the DMTI rte (Roads) layer appears to have
> FromNode and 
> ToNode already assigned to the road network. These are
> logical 
> equivalents to source and target columns.
> 
> Well I have this info in my  CanMap RouteLogistic v.
> 6.3 reference manual.
> 
> -Steve
> 
> On 8/27/2010 2:45 PM, Dan Putler wrote:
> > Hi Steve,
> >
> > I'm getting the hang of the layer diagnostics. The
> data was
> > originally in a shapefile, and there is no z value in
> the attribute
> > table, so it doesn't appear to be a 2.5d file. It does
> have both
> > length and length adjusted for elevation fields, just
> no z. Your tips
> > on the diagnostics have been very helpful (translating
> what you did
> > with Mapserver into QGIS is pretty straight forward).
> Over 5% of the
> > edges have zero length, but these overwhelmingly occur
> on the loops
> > of cul-de-sacs. In addition, I'm not finding any
> mid-street dead
> > ends.
> >
> > Overall, I'm successful in routing between 85% and 90%
> of my test
> > cases using the shooting * algorithm. Some of the
> failures I'm
> > finding are very surprising, I have a hunch as to why
> some of them
> > are occurring (based on a likely two bridge, literal
> "island
> > hopping", route it would likely select), but so far
> I'm not finding a
> > problem in the road network with respect to dead-ends
> or zero length
> > segments that would cause it. The island hoping route
> does involve
> > two fairly complex interchanges, could the lack of
> detailed elevation
> > information on the interchanges be the cause of the
> problem?
> >
> > I'm going to look at a couple of things, one of them
> is to go back to
> > the original DMTI layer to make sure I didn't somehow
> screw-up the
> > data being too clever with ogr2ogr, the other is to
> see if I get a
> > solution using the Dijkstra algorithm.
> >
> > Again, thanks a lot for all your help.
> >
> > Dan
> >
> > --- On Fri, 8/27/10, Stephen Woodbridge<woodbri at swoodbridge.com>
> > wrote:
> >
> >> From: Stephen Woodbridge<woodbri at swoodbridge.com>
> Subject: Re:
> >> [pgrouting-users] Setting the tolerance argument
> in
> >> assign_vertex_id To: "Dan Putler"<putler at yahoo.com>
> Cc: "pgRouting
> >> list"<pgrouting-users at lists.osgeo.org>
> Received: Friday, August 27,
> >> 2010, 9:00 AM Dan,
> >>
> >> One more thing that you might want to consider is
> if the DMTI data
> >> has zlevels at intersections, the you might need
> to mimic
> >> assign_vertex_id() in the form of
> assign_vertex_id_3d() where you
> >> update your edge endpoints with a Z value in the
> vertices_tmp table
> >> and you set the Z value to zlevel*FACTOR where
> FACTOR greater than
> >> TOLERANCE
> >>
> >> So if you have intersection points like at an
> overpass where the
> >> under pass is A-B(0)-C and the overpass is
> J-B(1)-K
> >>
> >> B has and location (x,y) and the zlevel for A-B
> and B-C is 0 and
> >> the for edges J-B and B-K the zlevel is 1, so
> while these are at
> >> the same x,y they do not intersect. In the
> assign_vertex_id(),
> >> these will get assigned the same node, but you
> need to write
> >> assign_vertex_id_3d() so they would get different
> nodes assign
> >> based on the zlevel separation.
> >>
> >> -Steve
> >>
> >> On 8/27/2010 11:31 AM, Stephen Woodbridge wrote:
> >>> I think DMTI data is pretty high quality data.
> I have
> >> used it in the
> >>> past, granted not for routing but, I never
> noticed any
> >> quality problems.
> >>>
> >>> When I did some of the analysis on other data
> sets, I
> >> created extra
> >>> columns on the edges table an did things like
> mark the
> >> edges for all
> >>> that had the same source and target nodes and
> display
> >> them in using
> >>> mapserver and openlayers and displayed the
> >> vertices_tmp table with
> >>> deadends as red dots and other nodes as green
> dots.
> >>>
> >>> Then you can get a quick visualization of the
> data.
> >> Mostly what you want
> >>> to look for is to see if deadends fall on
> connected
> >> lines, this
> >>> indicates a problem. Look for segments with
> matching
> >> source and target
> >>> numbers (color them so they stick out on the
> map.
> >>>
> >>> If you set the tolerance wrong you will see
> lots of
> >> errors like these.
> >>> I also then run pgRouting and overlay that on
> the maps
> >> and can turn on
> >>> the reference layers for debugging weird
> routes.
> >>>
> >>> Look at this:
> >>> http://gis.imaptools.com/routing/leaddog/?zoom=10&lat=33.86222&lon=35.51589&layers=B0TTTF&start=35.504139%2033.833331&stop=35.546364%2033.883493&method=STS〈=eng
> >>>
> >>>
> >>>
> >>>
> Open the layer switcher, zoom in and select "Just the
> >> Streets" and "Dead
> >>> Ends" and you can see what I mean. "Just the
> Streets"
> >> labels the streets
> >>> with the gid of the edge table so you can go
> >> investigate a problem.
> >>>
> >>> -Steve
> >>>
> >>> On 8/27/2010 3:44 AM, Dan Putler wrote:
> >>>> Thanks a lot Steve, this looks really
> helpful. I
> >> can see that routing
> >>>> involves much of the same "art" that
> geocoding
> >> does.
> >>>>
> >>>> Based on past experience, I'm not sure
> that the
> >> road network I am
> >>>> working with is as clean as you and Daniel
> appear
> >> to assume. I'm
> >>>> going to look at the dead-end and other
> issues
> >> tomorrow. I'm also
> >>>> wondering if there is any potential
> benefit of
> >> reading the original
> >>>> shapefile into GRASS which will attempt to
> clean
> >> it, dumping it back
> >>>> into a shapefile from GRASS, and then
> importing it
> >> into PostGIS, or
> >>>> does assign_vertex_id basically do the
> same
> >> cleaning that GRASS
> >>>> does?
> >>>>
> >>>> Dan
> >>>>
> >>>> --- On Thu, 8/26/10, Stephen
> >>>> Woodbridge<woodbri at swoodbridge.com>
> wrote:
> >>>>
> >>>>> From: Stephen Woodbridge<woodbri at swoodbridge.com>
> >> Subject: Re:
> >>>>> [pgrouting-users] Setting the
> tolerance
> >> argument in
> >>>>> assign_vertex_id To: "Dan
> Putler"<putler at yahoo.com>
> >> Cc: "pgRouting
> >>>>> list"<pgrouting-users at lists.osgeo.org>
> >> Received: Thursday, August
> >>>>> 26, 2010, 8:55 PM Dan,
> >>>>>
> >>>>> I think that picking a number around
> 0.5 to 1
> >> meter should be fine
> >>>>> for that data. In general it is
> unlikely that
> >> you will have nodes
> >>>>> that are NOT connected but that close
> >> together.
> >>>>>
> >>>>> You can also do some analysis of the
> results
> >> like this, after you
> >>>>> run assign_vertex_id():
> >>>>>
> >>>>> alter table vertices_tmp add column
> cnt int;
> >> update vertices_tmp
> >>>>> set cnt = (select count(*) from
> >> "<edge_table>" where
> >>>>> vertices_tmp.id=target or
> >> vertices_tmp.id=source); select cnt as
> >>>>> connections, count(*) from
> vertices_tmp group
> >> by cnt order by cnt;
> >>>>>
> >>>>> This will analyze the connectedness of
> you
> >> network.
> >>>>>
> >>>>> connections 1 - dead ends 2 -
> segments
> >> connected but only an
> >>>>> intersection if different names 3+ -
> >> intersections
> >>>>>
> >>>>> If you run assign_vertex_id() with
> different
> >> tolerance values and
> >>>>> then run this analysis as your
> tolerance gets
> >> too big you will see
> >>>>> a shift of these numbers to the
> smaller end
> >> which is bad.
> >>>>>
> >>>>> Another important analysis you check
> is:
> >>>>>
> >>>>> select count(*) from
> "<edge_table>"
> >> where target=source;
> >>>>>
> >>>>> this count should be zero unless you
> have zero
> >> length segments in
> >>>>> your data and you can check that
> with:
> >>>>>
> >>>>> select gid, st_length(the_geom) from
> >> "<edge_table>" where
> >>>>> target=source;
> >>>>>
> >>>>> These are a good way to learn about
> your
> >> data.
> >>>>>
> >>>>> -Steve
> >>>>>
> >>>>>
> >>>>> On 8/26/2010 8:37 PM, Dan Putler
> wrote:
> >>>>>> Thanks Steve, but I do need a bit
> of a
> >> follow on I
> >>>>> think, and
> >>>>>> probably provide a bit more
> explanation.
> >>>>>>
> >>>>>> I'm using a DMTI CanMap routing
> layer for
> >> BC that
> >>>>> started out in
> >>>>>> NAD83 geographic, which I
> converted to
> >> NAD83 UTM Zone
> >>>>> 10N via
> >>>>>> ogr2ogr, I also shrank it down
> using a
> >> "with"
> >>>>> statement in ogr2ogr to
> >>>>>> cover only part of the province.
> After I
> >> sent my
> >>>>> email, I did a bit
> >>>>>> more Google searching and based on
> a
> >> question in the
> >>>>> pgRouting forum,
> >>>>>> a user using NAVTEQ layers was
> using a
> >> tolerance that
> >>>>> worked out to
> >>>>>> between 1 and 1.5 meters. Based on
> this, I
> >> set the
> >>>>> tolerance to 2
> >>>>>> meters, it sounds like I should
> set the
> >> tolerance in
> >>>>> assign_vertex_id
> >>>>>> to be much smaller (say 0.15
> meters, which
> >> is just
> >>>>> over 5 inches).
> >>>>>>
> >>>>>> In general, is it better to err on
> the
> >> side of too
> >>>>> small or too large
> >>>>>> a tolerance, or is that a "it
> depends"
> >> question?
> >>>>>>
> >>>>>> Dan
> >>>>>>
> >>>>>> --- On Thu, 8/26/10, Stephen
> >> Woodbridge<woodbri at swoodbridge.com>
> >>>>>> wrote:
> >>>>>>
> >>>>>>> From: Stephen Woodbridge<woodbri at swoodbridge.com>
> >>>>> Subject: Re:
> >>>>>>> [pgrouting-users] Setting the
> >> tolerance argument
> >>>>> in
> >>>>>>> assign_vertex_id To: "Dan
> >> Putler"<putler at yahoo.com>
> >>>>> Cc: "pgRouting
> >>>>>>> list"<pgrouting-users at lists.osgeo.org>
> >>>>> Received: Thursday, August
> >>>>>>> 26, 2010, 4:27 PM On 8/26/2010
> 2:51
> >> PM, Dan Putler
> >>>>> wrote:
> >>>>>>>> Hi,
> >>>>>>>>
> >>>>>>>> I'm curious how to
> determine the
> >> value of the
> >>>>> second
> >>>>>>> argument in the
> >>>>>>>> function
> assign_vertex_id(). Most
> >> of the
> >>>>> examples I
> >>>>>>> can find look
> >>>>>>>> like:
> >>>>>>>>
> >>>>>>>>
> assign_vertex_id('<edge
> >> table>', 0.001,
> >>>>>>> 'the_geom', 'gid')
> >>>>>>>>
> >>>>>>>> Most of the examples are
> based on
> >> edge tables
> >>>>> that
> >>>>>>> have SRIDs that
> >>>>>>>> correspond to either
> WGS84
> >> geographic or some
> >>>>> sort of
> >>>>>>> US State Plane
> >>>>>>>> feet. I'm using data that
> is using
> >> a UTM
> >>>>> coordinate
> >>>>>>> SRID, so the map
> >>>>>>>> units are in meters. My
> question
> >> is whether
> >>>>> the map
> >>>>>>> units should
> >>>>>>>> influence the choice of
> the second
> >> argument to
> >>>>> the
> >>>>>>> function (which I
> >>>>>>>> assume is a tolerance
> between
> >> edges), or
> >>>>> should I just
> >>>>>>> keep with the
> >>>>>>>> value 0.001? Implicitly,
> I'm
> >> asking if the
> >>>>> parameter
> >>>>>>> is in the map
> >>>>>>>> units of the SRID.
> >>>>>>>
> >>>>>>> Dan,
> >>>>>>>
> >>>>>>> Right units is important.
> >>>>>>>
> >>>>>>> When I use data in WGS84 that
> has at
> >> lease 6
> >>>>> decimal places then I
> >>>>>>> use 0.000001 as the tolerance.
> What
> >> this means if
> >>>>> that if the
> >>>>>>> distance between two points
> are less
> >> than or equal
> >>>>> 0.000001 units
> >>>>>>> then they should be considered
> the
> >> same point.
> >>>>> 0.000001 degrees ==
> >>>>>>> ~5 inches if I did the math
> right.
> >>>>>>>
> >>>>>>> I think there are two issues
> you need
> >> to be aware
> >>>>> of:
> >>>>>>>
> >>>>>>> 1) units 2) your data and
> what
> >> precision it was
> >>>>> built at
> >>>>>>>
> >>>>>>> HTH, -Steve
> >>>>>>>
> >>>>>>>
> >>>>>>
> >>>>>>
> >>>>>
> >>>>>
> >>>>
> >>>>
> >>>
> >>>
> _______________________________________________
> Pgrouting-users
> >>> mailing list Pgrouting-users at lists.osgeo.org
> >>> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
> >>
> >>
> >
> >
> 
>