[pgrouting-users] Setting the tolerance argument in assign_vertex_id

Fri Aug 27 22:42:16 EDT 2010

Hi Steve,

That's right.
If you have very large ID's, which is often the case when you take an
already existing source/target ID, it can slow down the query.
So it's a good idea to renumber your source/target nodes as you said.

Thank you for all the examples! I think we should link this thread with the
tips & tricks wiki page.

Daniel

>
> I think pgrouting would prefer to have the nodes mostly sequential because
> of the way it allocates memory. But I'm not sure on that, anyway here are
> two ways you could try doing it:
>
> 1. Try using it directly:
>
> update <edge_table> set source=fromnode, target=tonode;
>
> 2. Try renumbering the nodes in an extra table:
>
> create table node_renum ( id serial, oldnode integer, primary key id);
> insert into node_renum (oldnode) (
>  select distinct nid from (
>    select source as nid from <edge_table> union
>    select target as nid from <edge_table>
>  ) as foo
> );
>
> create index oldnode_idx on node_renum using btree (oldnode);
> analyze node_renum;
>
> update <edge_table> as a set a.source=b.id from node_renum as b where
> a.fromnode=b.oldnode;
>
> update <edge_table> as a set a.target=b.id from node_renum as b where
> a.tonode=b.oldnode;
>
>
>
>  Thanks for your continued hand holding.
>>
>
> No problem.
>
> Sounds like a fun project.
>
> -Steve
>
>
>  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
>>>>>>
>>>>>
>>>>>
>>>>>
>>>>
>>>>
>>>
>>>
>>
>>
> _______________________________________________
> Pgrouting-users mailing list
> Pgrouting-users at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-users/attachments/20100828/52f0a7ee/attachment-0001.html