[pgrouting-users] Setting the tolerance argument in assign_vertex_id

[Stephen Woodbridge]

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
>>
>>
>
>