Re: [Routing] Roundabouts - why is a separate segment required?

[Marcus Wolschon]

Am 14.02.2018 um 18:21 schrieb Dave F:
> On 14/02/2018 16:46, Marcus Wolschon wrote:
>>
>> We often have roundabouts with dedicated lanes leading only to the
>> (heavily trafficed) exit
>> just off to the right. These are not part of the logical roundabout
>> and the particular traffic rules regarding
>> roundabouts do not apply. Yet they share nodes with the roundabout as
>> you can freely switch lanes in that circle segment.
>
> I think I understand what you're saying but for clarity could you
> provide an example.

The wiki page talks about them as "one way lateral shortcuts" just above
the seldom case of roads crossing the middle of the
roundabout. (I often see that as special ways for oversized transports
near industrial areas.)

The lane on the very right is such one.
https://upload.wikimedia.org/wikipedia/commons/thumb/a/a3/Blackwood_roundabout.jpg/1482px-Blackwood_roundabout.jpg

>
>> Only if you calculate the angle in an euclidian XY-plane for each one
>> and then sort them in clockwise
>> or counterclockwise fassion.
>
> The geometry is irrelevant. Entrances/exits can be determined because
> they don't contain a junction=roundabout tag.


It is not irrelevant as you need to tell the user "enter the roundabout
and use the THIRD exit".
How do you plan to determine how many exists to pass?


>
>> Assuming you can find out what side of the road people drive on in
>> this part of your route.
>
> Any person writing a routing/navigation shouldn't be doing it if they
> can't determine that. And anyway it's irrelevant to my point - it's
> the same in either direction.

It's not the same. Using the second exit from the right or the fourth
from the left is different.
Also this is one of the very few places where the direction of driving
actually matters for routing and only in your node-based aproach.
Simple because the tag oneway=yes is explicitely implied in the
segment-based aproach as stated on the Wiki page.

>
>> Something that can be avoided altogether with oneway segments making
>> up the roundabout.
>
> All ways with junction=roundabout are one way.

Yes and your proposal is a single node instead of a circle of segments.
How can a node be a oneway and thus determine a direction for counting
the exits?


>
>>
>>>
>>> DaveF.
>>>
>>>>
>>>> Phil (trigpoint)
>>>>
>>>> On 14 February 2018 15:38:01 GMT+00:00, Dave F
>>>>  wrote:
>>>>
>>>> To be doubly clear, this is an example of a road entering a roundabout 
>>>> & 
>>>> sharing a node with it:
>>>>
>>>> https://www.openstreetmap.org/node/19091900
>>>>
>>
>> A nice example of 2 shared nodes making up 1 exit.
>>
>>
>>>> Dave F.
>>>>
>>>> On 14/02/2018 15:21, Dave F wrote:
>>>>
>>>> On 14/02/2018 15:02, Marcus Wolschon wrote:
>>>>
>>>> What you describe is a mini-roundabout. 
>>>>
>>>> No it wasn't. It was perfectly clear as I posted the
>>>> 'junction=roundabout ' page. Much of the following is
>>>> incoherent to me. The rest is irrelevant to my point.
>>>>
>>
>> Irrelevant to your point but not to mine.
>>
>> The purpose of this map is much more then just routing for motorized
>> vehicles.
>> Representing the real road as accurate as possible is a major point here.
>> Or do you proclaim that e.g. accurate graphical rendering of a map is
>> not important for anyone?
>> That pedestian crossings on the legs of a roundabout are not
>> important for anyone?
>> That the roundabout-segment a postbox is at is not important for anyone?
>>
>> Also for vehicle routing, calculating the metrics as preicsely as
>> possible is a major
>> quality factor in good routing. So if using a roundabout is much
>> slower itself and
>> slows you down in front of (decellerating) and behind the roundabout
>> (accelerating)
>> compared to a simple right-turn, then this is an imporant thing to
>> model correctly.
>>
>> If a construction site or traffic jam blocks one exit, your model
>> would block the entire roundabout
>> instead of just that exist. Causing the driver to be routed way
>> around that intersection while for
>> his/her particular route it poses not much of an issue.
>>
>>
>>
>>>> DaveF
>>>>
>>>> That has a different geometry as the

Re: [Routing] Roundabouts - why is a separate segment required?

[Marcus Wolschon]

Am 14.02.2018 um 16:55 schrieb Dave F:
>
>
> On 14/02/2018 15:46, Philip Barnes wrote:
>> If an entering way shares a node with an exiting way there is no need
>> to pass through a roundabout way
>
> If that shared node is also part of junction=roundabout, then it does
> "need to pass through".


We often have roundabouts with dedicated lanes leading only to the
(heavily trafficed) exit
just off to the right. These are not part of the logical roundabout and
the particular traffic rules regarding
roundabouts do not apply. Yet they share nodes with the roundabout as
you can freely switch lanes in that circle segment.


>
>
>
>> It also messes up the exit count in navigation instructions.
>
> How? It has the same number of exits/entrances, no matter if they
> share nodes. They're all still countable.

Only if you calculate the angle in an euclidian XY-plane for each one
and then sort them in clockwise
or counterclockwise fassion.
Assuming you can find out what side of the road people drive on in this
part of your route.
Something that can be avoided altogether with oneway segments making up
the roundabout.

>
> DaveF.
>
>>
>> Phil (trigpoint)
>>
>> On 14 February 2018 15:38:01 GMT+00:00, Dave F
>>  wrote:
>>
>> To be doubly clear, this is an example of a road entering a roundabout & 
>> sharing a node with it:
>>
>> https://www.openstreetmap.org/node/19091900
>>

A nice example of 2 shared nodes making up 1 exit.


>>
>> Dave F.
>>
>> On 14/02/2018 15:21, Dave F wrote:
>>
>> On 14/02/2018 15:02, Marcus Wolschon wrote:
>>
>> What you describe is a mini-roundabout. 
>>
>> No it wasn't. It was perfectly clear as I posted the
>> 'junction=roundabout ' page. Much of the following is
>> incoherent to me. The rest is irrelevant to my point.
>>

Irrelevant to your point but not to mine.

The purpose of this map is much more then just routing for motorized
vehicles.
Representing the real road as accurate as possible is a major point here.
Or do you proclaim that e.g. accurate graphical rendering of a map is
not important for anyone?
That pedestian crossings on the legs of a roundabout are not important
for anyone?
That the roundabout-segment a postbox is at is not important for anyone?

Also for vehicle routing, calculating the metrics as preicsely as
possible is a major
quality factor in good routing. So if using a roundabout is much slower
itself and
slows you down in front of (decellerating) and behind the roundabout
(accelerating)
compared to a simple right-turn, then this is an imporant thing to model
correctly.

If a construction site or traffic jam blocks one exit, your model would
block the entire roundabout
instead of just that exist. Causing the driver to be routed way around
that intersection while for
his/her particular route it poses not much of an issue.



>> DaveF
>>
>> That has a different geometry as the center of that one
>> is traversable.
>> https://wiki.openstreetmap.org/wiki/Tag:highway%3Dmini_roundabout
>> a) I don't see a node as anything you "are on" at any
>> time. Only segments. At most nodes are considered for
>> calculating the metric of making certain turns between
>> segments. b) Routing algorithms that don't know or deal
>> with roundabouts would still work perfectly well with a
>> circle of segments and give proper instructions. c) In
>> reality this is a circle of road-segments. So segments
>> represent reality more closely. So for the purpose of the
>> map as a representation of real world geometry, this is
>> simply a much better approximation. This is not only for
>> routing but also for map-rendering to scale the size of
>> the roundabout correctly. (There are vast differences in
>> possible sizes.) d) These segments have a significantly
>> different metric then an intersection (much slower
>> traffic in the roundabout then the surrounding roads).
>> They have an angle to the entering and exiting road that
>> can be used in a metric because you need to slow down to
>> make such hard turns, limiting your average speed in the
>> segments before and after the roundabout (lookahead).
>> There may be traffic jams or construction sites blocking
>> part of a roundabout but still allowing certain turns to
>> 

Re: [Routing] Roundabouts - why is a separate segment required?

[Marcus Wolschon]

What you describe is a mini-roundabout.
That has a different geometry as the center of that one is traversable.
https://wiki.openstreetmap.org/wiki/Tag:highway%3Dmini_roundabout

a)
I don't see a node as anything you "are on" at any time. Only segments.
At most nodes are considered for calculating the metric of making 
certain turns

between segments.
b)
Routing algorithms that don't know or deal with roundabouts would still 
work

perfectly well with a circle of segments and give proper instructions.
c)
In reality this is a circle of road-segments. So segments represent 
reality more closely.
So for the purpose of the map as a representation of real world 
geometry, this is simply
a much better approximation. This is not only for routing but also for 
map-rendering
to scale the size of the roundabout correctly. (There are vast 
differences in possible sizes.)

d)
These segments have a significantly different metric then an 
intersection (much slower traffic

in the roundabout then the surrounding roads).
They have an angle to the entering and exiting road that can be used in 
a metric because you
need to slow down to make such hard turns, limiting your average speed 
in the segments before and

after the roundabout (lookahead).
There may be traffic jams or construction sites blocking part of a 
roundabout but still
allowing certain turns to be made. This can not be described with a 
simple node.



On 2018-02-14 15:40, Dave F wrote:

Hi
Could anyone give me an explanation for this line from
https://wiki.openstreetmap.org/wiki/Tag:junction=roundabout

"Each road has to be connected with the roundabout in a separate
node—that is, between these nodes a segment of the roundabout is
required."

I see no requirement for a separate segment:

* When a entering road shares a node with a roundabout then the
router knows it's entered that roundabout by reading the tags on the
circular way.
* Whilst on that node, the router checks to see if there are any
suitable exits. If there are, then it leaves the roundabout.
* If not, it continues going around until it finds an appropriate
exit.

 Cheers
DaveF
___
Routing mailing list
Routing@openstreetmap.org
https://lists.openstreetmap.org/listinfo/routing


___
Routing mailing list
Routing@openstreetmap.org
https://lists.openstreetmap.org/listinfo/routing

Re: [Routing] house numbers

[Marcus Wolschon]

So what's the issue?
That's way more accurate and I suspect you are able to determine what 
side of a line a coordinate is on and to do a linear

interpolation between two such coordinates.


Am 24.06.14 16:29, schrieb Shaun McDonald:
I think he means that most houses are now put in individually (often 
on the buildings) rather than using the interpolation method of 
storing house numbers in the OSM data. The nearest street which has 
the same name as the addr:street is the line that you would be looking 
for.


Shaun

On 24 Jun 2014, at 15:20, Marcus Wolschon <mailto:mar...@wolschon.biz>> wrote:




Why would interpolation no longer be supported?
Supported by whom?


Am 24.06.14 15:53, schrieb Siegfried Jetzke:

Dear members,

I'm new to this list and don't know wether my question already has 
been discussed several times or not. If yes, please send me some 
link to the place where I can find it.


I do have an academic and commercial background and I'm working on 
route planing. In former projects I used commercial data, e.g. those 
from teleatlas.
For a new project that started some time ago, I want to see wether 
we can use OSM.
My question is the following: I get an address, like 38159 Vechelde, 
Brinkstr. 4b. I consider each street as a list of road elements and 
each road element as a pair of two edges, one left and one right edge.


To use this address within my application I do need to know the edge 
to which this address belongs. It would be "nice" to know 
approximately the distance of this address from one of the nodes, 
defining the edge. I'm not interested in the coordinates of the address.


I found that "interpolation" gives exactly the information I need 
but that this will not longer be supported.


Can anyone give me some hint how to find the edge belonging to one 
address?


Thanks in advance

Siegfried
--

*Prof. Dr. Siegfried Jetzke*

*good/S/ync* GmbH
Konzepte und Lösungen für eine effiziente Logistik
Brinkstraße 4b
38159 Vechelde

Telefon :   +49 5300 9019211
Fax :   +49 5300 9019209
e-mail :s.jet...@goodsync.de
URL :   www.goodsync.de




___
Routing mailing list
Routing@openstreetmap.org
https://lists.openstreetmap.org/listinfo/routing


___
Routing mailing list
Routing@openstreetmap.org <mailto:Routing@openstreetmap.org>
https://lists.openstreetmap.org/listinfo/routing




___
Routing mailing list
Routing@openstreetmap.org
https://lists.openstreetmap.org/listinfo/routing


___
Routing mailing list
Routing@openstreetmap.org
https://lists.openstreetmap.org/listinfo/routing

Re: [Routing] house numbers

[Marcus Wolschon]

Why would interpolation no longer be supported?
Supported by whom?


Am 24.06.14 15:53, schrieb Siegfried Jetzke:

Dear members,

I'm new to this list and don't know wether my question already has 
been discussed several times or not. If yes, please send me some link 
to the place where I can find it.


I do have an academic and commercial background and I'm working on 
route planing. In former projects I used commercial data, e.g. those 
from teleatlas.
For a new project that started some time ago, I want to see wether we 
can use OSM.
My question is the following: I get an address, like 38159 Vechelde, 
Brinkstr. 4b. I consider each street as a list of road elements and 
each road element as a pair of two edges, one left and one right edge.


To use this address within my application I do need to know the edge 
to which this address belongs. It would be "nice" to know 
approximately the distance of this address from one of the nodes, 
defining the edge. I'm not interested in the coordinates of the address.


I found that "interpolation" gives exactly the information I need but 
that this will not longer be supported.


Can anyone give me some hint how to find the edge belonging to one 
address?


Thanks in advance

Siegfried
--

*Prof. Dr. Siegfried Jetzke*

*good/S/ync* GmbH
Konzepte und Lösungen für eine effiziente Logistik
Brinkstraße 4b
38159 Vechelde

Telefon :   +49 5300 9019211
Fax :   +49 5300 9019209
e-mail :s.jet...@goodsync.de
URL :   www.goodsync.de




___
Routing mailing list
Routing@openstreetmap.org
https://lists.openstreetmap.org/listinfo/routing


___
Routing mailing list
Routing@openstreetmap.org
https://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Routing for autonomous agents

[Marcus Wolschon]

Am 03.09.12 20:38, schrieb Vin Baines:


Do you have any suggestion for where to extend? I'm assuming the 
underlying data is already there in the list of nodes which make up 
the route? Something like extending the csv/gpx output with 
routingStep.getWay().getWayNodes() for each way?
Exactly but ignore the nodes before "start" and after "end" and check 
what direction you need to iterate through.



___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Routing for autonomous agents

[Marcus Wolschon]

Am 03.09.12 18:58, schrieb Tobias Knerr:

Hello Vin,

original projects like yours are something I always find interesting,
especially when they involve 3D models. So I hope we can solve your
routing problem.

On 02.09.2012 20:49, Vin Baines wrote:

I've looked at the travelling salesman code, which almost does what I
want - I can pass it a set of lat-longs and get the route, but its
returned as OSM nodes, or a gpx file. If I load gpx data and use that as
coordinates for the driver to move to, then any curves in t he road get
ignored. But, in the GUI the route follows the road exactly. Ideally,
I'd export this data in say 5m intervals, and the driver agent would use
that as a series of moveTo(X,Y) actions.

I'm not sure whether I understand the issue, but as I'm not familiar
with the output of Travelling Salesman, I may be missing something. Some
clarifications would be helpful.

You say you can get the result as a gpx file, but it doesn't include
curves. Does this mean that the gpx only contains track points at
junctions and nothing in between? Is that also the problem with the
nodes - that you don't get *all* nodes along the route, but just a few
of them?



The result of routing on the command line (for use in scripts) are
pairs of wayID, start-nodeID, end-nodeID with lat+lon included to make
scripting easier.
More complex schemas are trivial to code in Java as TS is only a graphical
frontend to the osmRouting library wich uses the libOSM library and it's
plugin-framework.
All 3 are intended for prototyping algorithms and data storage structures
by having only to code whatever part of an end-user routing application
you are working in and getting all other aspects for free.





Tobias

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing



___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Average speeds, Fastest Paths in Contraction Hierarchies

[Marcus Wolschon]

Curt Nowak  schrieb:

Hi everyone,

 

I'm developing a routing application using Contraction Hierarchies. Trying to 
implement fastest path queries I'm currently facing two problems:

1: What average speed should I assume for different highway types (, and 
vehicles, and countries) ?

2: Has anyone already solved this for Contraction Hierarchies and if so, how do 
you extract travel times for a shortcut edge that may span over multiple 
highway types and even countries?

 

So far, I could not find a lot in the web - not even for question 1. Any 
pointer (or link) would be greatly appreciated.

 

Curt


Avg.speed: outside cities legal speed of the current country +10, inside -20km/h
Penalties for sharp curve/traffic light/rush hour,
Bonus for multiple lanes.
...have fun coding this ;)

-- 
Diese Nachricht wurde von meinem Android-Mobiltelefon mit K-9 Mail gesendet.___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Additional calculation within routing algorithm.

[Marcus Wolschon]

Am 19.04.2011 11:12, schrieb Andrew Poodle:

 Hi,

I'm new on the list, and new to OSM mapping, and I can't find a 
definitive answer for my queries in the documentation so I thought I'd 
post in here.


I have a number of potential , specific use-cases where I want to 
calculate the geometry of the roads used in a route but I can't 
identify if that information is easily accessible with the OSM data.


Does the OSM map data contain information such that the geometry of 
road/routes could be calculated both in 2D (radius) and, to a lesser 
extent 3D, and could it be incorporated into routing calculations?


Of cause it does.
It's a graph made out of nodes (with latitude and longitude)
and ways as an ordered list of such nodes.

You can apply all geometry-calculations you like.

If you are interested in writing specific metrics or routing-algorithms
without caring about the rest of the infrastructure
I suggest to look at Traveling Salesman. You can write
a new metric or algorithm as a plugin and it will be selectable
in the config-dialog.
http://travelingsales.sourceforge.net/

(I'm the maintainer but haven't done anything on it in a while.
 It does however work well for maps up to the size of a major city.)

Marcus



tia

Andrew




___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] shooting star

[Marcus Wolschon]

This may be interesting for you:

http://sourceforge.net/apps/mediawiki/travelingsales/index.php?title=Plugin/TurnRestrictedMultiTargetDijkstraRouter



On Fri, Dec 10, 2010 at 15:38, Marcus Wolschon  wrote:
> -BEGIN PGP SIGNED MESSAGE-
> Hash: SHA256
>
> I am using it too in traveling salesman.
>
>
>
> "Daniel Kastl"  schrieb:
>
>>Hi Javad,
>>
>>You're right. You haven't asked for pgRouting but for the theory.
>>Though the person, who wrote Shooting * implementation for pgRouting
>>(Anton
>>Patrushev) is usually sitting on the desk next to me. And while I'm not
>>sure
>>he is still subscribed to this list, he is for sure reading the one I
>>told
>>you. That's why I recommended you to ask there.
>>
>>What other said already: Shooting Star routes from edge to edge instead
>>of
>>point to point as Dijkstra and A-Star do.
>>There are some research papers about such an algorithm, but the name
>>was the
>>idea of Anton. I'm not aware of any other place it is used than in
>>pgRouting. If I'm wrong here, let me know where else.
>>
>>Daniel
>>
>>
>>2010/12/10 javad sadidi 
>>
>>> no
>>> I asked about the theory of the shooting star algorithm with an
>>example.
>>> principles of shooting star algorithm.
>>>
>>> On Fri, Dec 10, 2010 at 1:53 PM, Daniel Kastl
>>wrote:
>>>
>>>> Hi,
>>>>
>>>> You might want to ask on the pgRouting list:
>>>> http://www.pgrouting.org/support.html
>>>>
>>>> Daniel
>>>>
>>>>
>>>> 2010/12/10 javad sadidi 
>>>>
>>>>> hi
>>>>> I am looking for about the shooting star algorithm . I am just a
>>beginner
>>>>> and need to know how it works. I mean basics and principles of
>>shooting
>>>>> star. please help me-
>>>>>
>>>>> ___
>>>>> Routing mailing list
>>>>> Routing@openstreetmap.org
>>>>> http://lists.openstreetmap.org/listinfo/routing
>>>>>
>>>>>
>>>>
>>>>
>>>> --
>>>> Georepublic UG & Georepublic Japan
>>>> eMail: daniel.ka...@georepublic.de
>>>> Web: http://georepublic.de
>>>>
>>>> ___
>>>> Routing mailing list
>>>> Routing@openstreetmap.org
>>>> http://lists.openstreetmap.org/listinfo/routing
>>>>
>>>>
>>>
>>> ___
>>> Routing mailing list
>>> Routing@openstreetmap.org
>>> http://lists.openstreetmap.org/listinfo/routing
>>>
>>>
>>
>>
>>--
>>Georepublic UG & Georepublic Japan
>>eMail: daniel.ka...@georepublic.de
>>Web: http://georepublic.de
>>___
>>Routing mailing list
>>Routing@openstreetmap.org
>>http://lists.openstreetmap.org/listinfo/routing
> -BEGIN PGP SIGNATURE-
> Version: APG v1.0.7
>
> iI0EAREIAE0FAk0CO1VGHE1hcmN1cyBXb2xzY2hvbiAoZW1haWwtYWRyZXNzIGZv
> ciBidXNpbmVzcy11c2UpIDxNYXJjdXNAV29sc2Nob24uYml6PgAKCRA1p5EQQT42
> dqkqAKDpGUPUL8Y8sDm+Lm8myB4NB38RWQCgxzQmDcdBujFp4tJIcIBphP26Oqk=
> =XvP+
> -END PGP SIGNATURE-
>
>
> ___
> Routing mailing list
> Routing@openstreetmap.org
> http://lists.openstreetmap.org/listinfo/routing
>

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] shooting star

[Marcus Wolschon]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA256

I am using it too in traveling salesman.



"Daniel Kastl"  schrieb:

>Hi Javad,
>
>You're right. You haven't asked for pgRouting but for the theory.
>Though the person, who wrote Shooting * implementation for pgRouting
>(Anton
>Patrushev) is usually sitting on the desk next to me. And while I'm not
>sure
>he is still subscribed to this list, he is for sure reading the one I
>told
>you. That's why I recommended you to ask there.
>
>What other said already: Shooting Star routes from edge to edge instead
>of
>point to point as Dijkstra and A-Star do.
>There are some research papers about such an algorithm, but the name
>was the
>idea of Anton. I'm not aware of any other place it is used than in
>pgRouting. If I'm wrong here, let me know where else.
>
>Daniel
>
>
>2010/12/10 javad sadidi 
>
>> no
>> I asked about the theory of the shooting star algorithm with an
>example.
>> principles of shooting star algorithm.
>>
>> On Fri, Dec 10, 2010 at 1:53 PM, Daniel Kastl
>wrote:
>>
>>> Hi,
>>>
>>> You might want to ask on the pgRouting list:
>>> http://www.pgrouting.org/support.html
>>>
>>> Daniel
>>>
>>>
>>> 2010/12/10 javad sadidi 
>>>
 hi
 I am looking for about the shooting star algorithm . I am just a
>beginner
 and need to know how it works. I mean basics and principles of
>shooting
 star. please help me-

 ___
 Routing mailing list
 Routing@openstreetmap.org
 http://lists.openstreetmap.org/listinfo/routing


>>>
>>>
>>> --
>>> Georepublic UG & Georepublic Japan
>>> eMail: daniel.ka...@georepublic.de
>>> Web: http://georepublic.de
>>>
>>> ___
>>> Routing mailing list
>>> Routing@openstreetmap.org
>>> http://lists.openstreetmap.org/listinfo/routing
>>>
>>>
>>
>> ___
>> Routing mailing list
>> Routing@openstreetmap.org
>> http://lists.openstreetmap.org/listinfo/routing
>>
>>
>
>
>--
>Georepublic UG & Georepublic Japan
>eMail: daniel.ka...@georepublic.de
>Web: http://georepublic.de
>___
>Routing mailing list
>Routing@openstreetmap.org
>http://lists.openstreetmap.org/listinfo/routing
-BEGIN PGP SIGNATURE-
Version: APG v1.0.7

iI0EAREIAE0FAk0CO1VGHE1hcmN1cyBXb2xzY2hvbiAoZW1haWwtYWRyZXNzIGZv
ciBidXNpbmVzcy11c2UpIDxNYXJjdXNAV29sc2Nob24uYml6PgAKCRA1p5EQQT42
dqkqAKDpGUPUL8Y8sDm+Lm8myB4NB38RWQCgxzQmDcdBujFp4tJIcIBphP26Oqk=
=XvP+
-END PGP SIGNATURE-


___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Traveling Salesman: Barrier restriction for toll highways

[Marcus Wolschon]

Oleg Demchenko wrote:

Hi All and Markus.
 
Running route method for a different Start/End locations I've found that 
method can't connect locations using 22 Kms bridge way which connects 2 
biggest Denmark Islands */Sjælland /and/ Fyn ./*
*//* 
Reason is, method consider this node 
 
http://www.wikimapia.org/#lat=55.3493823&lon=11.1087763&z=18&l=0&m=b 

 
as not allowed, because bridge is tool highway and  barrier="toll_booth" 
is exists for node.
 
Yes, toll booth is some kind of barrier, but any car could pass through 
it. :-)



Well, feel free to allow barrier="toll_booth" while retaining the
default-behavior for unknown "barrier=*" to be disallowed.



Questions are:
-How method is working for a lot of tool highways within EU? It is 
ignoring them?


tool highways?

-Which other kind of barriers could happen in OSM data file for toll 
highways?


Unknown.
Highways are free of charge where I live.



___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] PluginLifecycleException during TurnRestrictedMultiTargetDijkstraRouter.route method execution

[Marcus Wolschon]

JPF uses it's own class-loaders.
There are known issues with Servlets
that you can look up at the JPF-forum
at Sourceforge.

Marcus

Oleg Demchenko wrote:

Hi Markus and all.
 
I'm running this method from java web app under TomCat.
Sources of libosm, osmnavigation and ts are downloaded from SVN, 
modified and recompiled with my application.
I've did a series of corrections to make method more "stable" with a 
different country speed restrictions, illegal way width, height, length, 
maximal speed tags permanently

occurred within OSM database used.
 
It works pretty fine with a short distance, but server CPU/RAM is not 
good enough to find path  for 150 Kms and more. It takes several minutes.

For my last soap call I get the following exception under TomCat:
/SEVERE: org/java/plugin/PluginLifecycleException
java.lang.NoClassDefFoundError: org/java/plugin/PluginLifecycleException
 at 
org.openstreetmap.travelingsalesman.routing.selectors.Motorcar.isAllowed(Unknown 
Source)
 at 
org.openstreetmap.travelingsalesman.routing.routers.TurnRestrictedAStar.getNextNodes(Unknown 
Source)
 at 
org.openstreetmap.travelingsalesman.routing.routers.TurnRestrictedAStar.route(Unknown 
Source)
 at 
org.openstreetmap.travelingsalesman.routing.routers.TurnRestrictedAStar.route(Unknown 
Source)/

...
/ at java.lang.Thread.run(Unknown Source)/
/Caused by: java.lang.ClassNotFoundException: 
org.java.plugin.PluginLifecycleException
 at 
org.apache.catalina.loader.WebappClassLoader.loadClass(WebappClassLoader.java:1645)
 at 
org.apache.catalina.loader.WebappClassLoader.loadClass(WebappClassLoader.java:1491)/
 
It happened after 180 seconds of request execution. In previous Markus 
answers I've found reason could be jpf*.jar is missed in CP. But, 
jpf.jar with PluginLifeCycle classes is in my Libosm project.
 
How to make MotorCar plugin object LifeCycle time longer? For example 5 
minutes?

Didn't find any parameters within jpf.jar resources.

--
All the best
   Oleg Demchenko




___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing



___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] IRouteMetric selection for TurnRestrictedMultiTargetDijkstraRouter route method

[Marcus Wolschon]

On Tue, Sep 7, 2010 at 11:36, Oleg Demchenko  wrote:
> Hi Marcus.
> First of all thank you for you prompt response. Debugging my data I've
> review your metric/navigation code and found it very smart,
> precise and heuristic.
>
> Regarding Traffic messages: my understanding that using iDataset specified
> for a metric object you are creating several tables there and downloading
> (probably using other plugin/process) to those tables traffic data from an
> external source.

No, IDataSet is the map.
TrafficData is temporary data and used live in the metric and not
stored in the map.
The TMC-implementation for traffic data stores messages in it's own
H2-database until
they expire.


> Error happened during execution of
> private TrafficMessageStore myTrafficMessages =
> TrafficMessageStore.getInstance();
> I think reason was I forgot initialize metric object iDataset with  setMap
> method. Type of error was : cannot find datasource.

If the h2.jar in your classpath? The databse is created if it does not exist.


> OK, I commented myTrafficMessages initialization and set
> Collection allMessages = null during initialization. So, not
> traffic blocks anymore :-)

Works too. ;)

> Also I've met some challenges to find way maxspeed within getEstimatedSpeed
> method.
> 1) Method can't determine a country (there is no country specified in
> attributes for the most ways/nodes in a file) and fails with exception
> trying to find max speed for a country (DEFAULTCOUNTRY) and way type. OK,
> I've corrected a code a little bit, because I "know" a country.

> 2) There is a challenge within TrafficRuleManage class, when metric trying
> to check inCity attribute. Exceptions happens within  public static
> IAddressDBPlaceFinder getCities(final IDataSet aMap). Can you tell me more
> how it is working?. It is supposed call to external service/application or
> class should find it using *.OSM (iDataSet) data itself? How can I set city
> borders for my (country) area/data? I really would like to keep this logic,
> because car speed within cities is slower.

It is supposed to use the supplied map to find out if you are without
a city-polygon
or within a radius around a city-node.
It may reuse the address-database build during map-import if I
remember correctly.

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] IRouteMetric selection for TurnRestrictedMultiTargetDijkstraRouter route method

[Marcus Wolschon]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

Am 06.09.2010 15:05, schrieb Oleg Demchenko:
> Hi Marcus and All.
>
> I'm successfully running route estimation method with a default
> ShortestRoteMetric, but results are not acceptable for my task.
> method selects short, but very small roads first, instead of
> motorways and other fast driving roads.
>
> From a description I see that most suitable for my task is
> StaticFastestRouteMetric - metric counting the travel-time of the
> way using fixed averaged for known highway-types
>
> But when I'm trying to initialize StaticFastestRouteMetric object
> , I'm get an exception from TrafficMessageStore.java module, when
> program trying connect to external Traffic Message source
>
> private TrafficMessageStore() { *this.myDatabaseURL =
> Settings.getInstance().get("tmc.storepath", getDefaultURL());*
> this.myConnection = getConnection(); }

What exception do you get?



>
> I don't need any TrafficMessage for my purpose. Metric which
> prefer "fastest" roads building a path, will be suitable for my
> situation.
>
> Questions: 1) how to remove traffic logic from this metric?

Take the source, copy this metric to a new file, remove it, rename it
and there you have a new Metric.

> Any setup or command line parameter?
Obvisiously you can store the empty tmc-message -store in another
directory using the
*tmc.storepath -setting
(in ~/libosm/preferences.xml or using the --set or --override
paramerters described
in --help or at
http://sourceforge.net/apps/mediawiki/travelingsales/index.php?title=Traveling_Salesman
)
*
There is no way to use a command-line parameter to remove code from a
class.

> 2) In which source is defined average car speed depending on a way
> type?
>

The code of the metric should tell that:
http://travelingsales.svn.sourceforge.net/viewvc/travelingsales/trunk/osmnavigation/src/org/openstreetmap/travelingsalesman/routing/metrics/StaticFastestRouteMetric.java?revision=1499&view=markup
they are fixed for the cost-calculation in the sourcecode at this time.

At some later time these:
http://travelingsales.svn.sourceforge.net/viewvc/travelingsales/trunk/osmnavigation/src/org/openstreetmap/travelingsalesman/navigation/traffic/
may be used. Currently they are only used for getEstimatedSpeed() .

Marcus

> p.s. I'm using last versions of libosm,  osmnavigation and
> TravelingSalesMan project downloaded from SVN.
>
> Thanks in advance.
>
> -- All the best Oleg Demchenko
>
>
> ___ Routing mailing
> list Routing@openstreetmap.org
> http://lists.openstreetmap.org/listinfo/routing

-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAkyFQ+EACgkQf1hPnk3Z0cSm2QCcDO56uBMZEhNw2dsTKqfYjhEL
G3EAoMaiXIiYcDD25CE4H5J966Ba0VzM
=6uXM
-END PGP SIGNATURE-

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] How to load OsmBinDataSet dataset to memory and reuse it during next sessions

[Marcus Wolschon]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA256

See the sourceforge page.
They explain the SVN URIs.

Marcus


"Oleg Demchenko"  schrieb:

>Dear Marcus.
>Thank you for your response.
>
>I've created H2 database and loading data from there. Performance is much
>better.
>
>Marcus I'm using currently binary traveling salesman.jar with version
>1.0.3-RC1
>How to download  latest sources and build a project on my side?
>I see via http
>http://travelingsales.svn.sourceforge.net/viewvc/travelingsales/trunk/traveling_salesman/,
>
>but can't upload using my SVN repobrowser for windows.
>
>I would like to debug method TurnRestrictedMultiTargetDijkstraRouter route
>method on my database.
>
>
>
>
>2010/8/27 Marcus Wolschon 
>
>> -BEGIN PGP SIGNED MESSAGE-
>> Hash: SHA1
>>
>> Am 27.08.2010 19:50, schrieb Oleg Demchenko:
>>
>> > Dear all.
>> >
>> > I've imported country OSM file to OSM Binary format and more or
>> > less successfully finding a route using travelingsalesman class
>> > and osmbin as dataset. Performance is much faster than with XML
>> > (OSM file), but there are still some points for improvement.
>>
>> OsmBin is outdated and replaced by H2DataSet.
>>
>> > Well, each time when program call method like .getNearestNode(),
>> > I'm getting exception (warning)
>> >
>> > /org.openstreetmap.osm.data.osmbin.FixedRecordFile  INFO:
>> > Memory-maping the file failed in
>> > org.openstreetmap.osm.data.osmbin.IDIndex File - using
>> > conventional io instead/
>> >
>>
>> That is okay and means that your file is larger then the Address-Range
>> you supply on
>> the Java-Command-Line for Memory-Mapped IO. So the file cannot be
>> mapped into memory
>> and is accessed using conventional IO.
>> That is about 10x slower for such random access then memory mapped IO.
>> Thus the strong warnings.
>>
>> The recommed command-line for Sun Java is:
>> *java -XX:MaxDirectMemorySize=512M -jar traveling_salesman.jar*
>>
>> (Documented in travelingsales.sourceforge.net under
>> "using Traveling Salesman"
>> -BEGIN PGP SIGNATURE-
>> Version: GnuPG v1.4.9 (GNU/Linux)
>> Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/
>>
>> iEYEARECAAYFAkx4DpoACgkQf1hPnk3Z0cSIXACeKDNQ91ZedZ9Uhm87/zVkNiHN
>> QhwAn2FE/fJnLeaYgsvv+5DnWX/oEEHG
>> =19wU
>> -END PGP SIGNATURE-
>>
>>
>> ___
>> Routing mailing list
>> Routing@openstreetmap.org
>> http://lists.openstreetmap.org/listinfo/routing
>>
>>
>
>
>--
>All the best
>   Oleg Demchenko
>___
>Routing mailing list
>Routing@openstreetmap.org
>http://lists.openstreetmap.org/listinfo/routing
-BEGIN PGP SIGNATURE-
Version: APG v1.0.7

iI0EAREIAE0FAkx+PHZGHE1hcmN1cyBXb2xzY2hvbiAoZW1haWwtYWRyZXNzIGZv
ciBidXNpbmVzcy11c2UpIDxNYXJjdXNAV29sc2Nob24uYml6PgAKCRA1p5EQQT42
dvLCAKDpjJmSDUzqZEMoNVtf6giezhk0MgCeJL6ZdnCEdPQrLr0dEFk6bROrkpc=
=XaGT
-END PGP SIGNATURE-


___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] How to load OsmBinDataSet dataset to memory and reuse it during next sessions

[Marcus Wolschon]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

Am 27.08.2010 19:50, schrieb Oleg Demchenko:
> Dear all.
>
> I've imported country OSM file to OSM Binary format and more or
> less successfully finding a route using travelingsalesman class
> and osmbin as dataset. Performance is much faster than with XML
> (OSM file), but there are still some points for improvement.

OsmBin is outdated and replaced by H2DataSet.

> Well, each time when program call method like .getNearestNode(),
> I'm getting exception (warning)
>
> /org.openstreetmap.osm.data.osmbin.FixedRecordFile  INFO:
> Memory-maping the file failed in
> org.openstreetmap.osm.data.osmbin.IDIndex File - using
> conventional io instead/
>

That is okay and means that your file is larger then the Address-Range
you supply on
the Java-Command-Line for Memory-Mapped IO. So the file cannot be
mapped into memory
and is accessed using conventional IO.
That is about 10x slower for such random access then memory mapped IO.
Thus the strong warnings.

The recommed command-line for Sun Java is:
*java -XX:MaxDirectMemorySize=512M -jar traveling_salesman.jar*

(Documented in travelingsales.sourceforge.net under
"using Traveling Salesman"
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAkx4DpoACgkQf1hPnk3Z0cSIXACeKDNQ91ZedZ9Uhm87/zVkNiHN
QhwAn2FE/fJnLeaYgsvv+5DnWX/oEEHG
=19wU
-END PGP SIGNATURE-

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Derive data: number of lanes and capacity

[Marcus Wolschon]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

Am 10.08.2010 02:06, schrieb Tom Müller:
> Am 10.08.2010 00:04, schrieb Stephen Woodbridge:
>> So I would agree the collecting more is better AND that
>> collecting it in a standardized form is best so we know what we
>> have in the future when we want to use it.
>>
>> -Steve
>
> But the lanes-tag is standardized, isn't it? It's just not set
> very often, is it?

Yes
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAkxgz9QACgkQf1hPnk3Z0cR2zQCgoyijAO/Ep4rhvQ4AihOR3iau
hD4AoMZFcPapJwc2+QWNPf3+63zmPDCo
=zg1U
-END PGP SIGNATURE-


___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Travelling Salesman: issue with using H2 Database

[Marcus Wolschon]

Have you used the same version of both?
version is a part of the schema since quite a while.

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Derive data: number of lanes and capacity

[Marcus Wolschon]

Tom Müller wrote:

There is an explicit tag
lanes=
http://wiki.openstreetmap.org/wiki/Key:lanes


yes. I know. But it's set pretty rarely. For Berlin it's set for approx. 
6% of all highways ... So I was just wondering if there are any defaults 
which are deriveable by the highway-type or so?!


I would assume that all highway=* to be lanes=1
(residential, secondary, service,...)
except motorways with lanes=2

Maybe highway=primary be 2 lanes too.

Marcus

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Derive data: number of lanes and capacity

[Marcus Wolschon]

Tom Müller wrote:

 Hi there,

I'm pretty new to this mail-list, so please excuse if I'm missing some 
knowledge about rules or stuff, if there are any :)


I'm searching for a way to get the number of lanes and the capacity of a 
street. As far as I found out there are no defaults for this kind of 
data, are there? actually I'll be able to approx the capacity from the 
number of lanes, so what I'm focussing on is to get the number of lanes 
first.


There is an explicit tag
lanes=
http://wiki.openstreetmap.org/wiki/Key:lanes


Marcus

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Bad routing: U turns for highway links?

[Marcus Wolschon]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

Am 18.07.2010 04:52, schrieb Alan Millar:
>>
http://maps.cloudmade.com/?lat=45.418666&lng=-122.321563&zoom=16&directions=45.41881686582581,-122.32349395751953,45.4324308667588,-122.36778259277344&travel=car&styleId=1
>
>>
>>
A good example of a place where dual carriageways should be used.
>>> Notice the double-double yellow lines separating the two
>>> directions of traffic.
>
>> Definately. The road should never have been modeled as only 1 way
>> in the first place. The router was absolutely right. The road was
>> wrong.
>
> No, I don't agree; this is not an obvious dual carriageway.
>
> You CAN turn both left and right leaving the highway; the middle
> lane is a left-turn lane in both directions, crossing the opposite
> side.  You just can't turn left entering the highway.

Why isn´s it?
I see a dual-carriageway with oneway-links on both sides
and 2 oneway-links in the middle. As all these ways are
oneway in reality just connect or don't connect
the middle lane to the carriage-way they are crossing
if and only if making U-turns using the middle lane
is forbidden.

Marcus



>
> An that is just this one crossing.  The very next intersection at
>
> http://nroets.dev.openstreetmap.org/demo/index.html?lat=45.40876&lon=-122.30162&zoom=17
>
>
>
is just a simple meeting of two roads, as are most of the rest of the
> crossings as the road heads east.

Ok, so turn-restrictions it is.

> That doesn't make any more sense to me than adding "no left turn"
> in a place where the link approaches at a small angle of a few
> degrees and you are supposed to merge left onto the highway.  That
> may make sense for routing restrictions, but it is going to really
> confuse a human map reader.
>
> Am I really asking something unreasonable of a router that when an
> _link way meets an  way at a very low angle, the router
> should know to go forward and not almost reverse?

Yes because
a) such intersections with very sharp angles exist in many cities
and are valid. (I already said that I know real live examples.)
b) It is not the place of the routing-algorithm to change the
topology of the well defined graph it is routing on.
c) Routers don't care for angles or even for any kind of physical
location most of the time.  Metrics do but most metrics would
   act incorrect if they where to associate extreme cost with sharp
   angles. (A shortest route is no longer shortest if it cares about
angles,
   fastest- and fuel-efficient and motorbike-friendly- already have their
   own set of rules for angles,...)
d) You would need to add your heuristic not to one but to ALL our
   routing-engines and all their routing-algorithms, document them, test
   them, tune them, make them well-behaved.  As opposed to fixing the map.

Whould it not be easier to write a trivial tool to search for such
sharp angles
and offer them to users for checking if a turn-restriction would be
apropriate? Maybe even prepare a changeset, so the offered
turn-restriction
can be added with one click?
That´s even less work then changing one and only one router considering
the testing and documentation involved as the router still needs to work
correctly on all other roads.

Marcus
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAkxCoj0ACgkQf1hPnk3Z0cQgAQCeKshSgy0jfkSkbK6IZ8V0wgHS
MfgAoL1bRkOH6ab3byiABBaAp0u2CTpZ
=lN1l
-END PGP SIGNATURE-


___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Bad routing: U turns for highway links?

[Marcus Wolschon]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

Am 17.07.2010 21:19, schrieb Apollinaris Schoell:
>
> On 17 Jul 2010, at 11:36 , Marcus Wolschon wrote:
>
>> -BEGIN PGP SIGNED MESSAGE- Hash: SHA1
>>
>> Am 17.07.2010 19:20, schrieb Apollinaris Schoell:
>>>
>>> In this example it seems just too easy for a good router to do
>>> the right thing without hard facts.
>>
>>
>> How? Please post the algorithm you are thinking about.
>>
>
> typical intersection like this one requires 2 turns
>
> 70-110 degree from main road to ramp and 5-20 degree from ramp to
> trunk
>
> the cloudmade route choose 80degree + 160 degree turn when it was
> possible with nearly exact same length to do  110 degree + 5 degree
>  I think something like a exponential cost increase for the angle
> of a turn will result in 90% of the unclear situations

- From what I saw the links where oneway-streets.
Else it would already have chosen the correct one because
it´s simply the shortest path.


>
>
>
> I haven't done any of this or looked into the code. Mark explained
> a bit in some postings in the mkgmap dev list. just to be clear.
> this is not for the routing itself just for the announcements.
> Don't announce if the angle is small and roads continue with
> similar tags. the routing itself is done by the Garmin device

What do you mean with "announcement"?



>
> you are so lucky! in US there is lot of imported data of
> questionable quality. But even with plain tiger data routing is
> possible. there is a program for that. but I have never tested how
> good it is. so it is possible to fix things on the router side

We have lots of mappers but WAY too few developers.
Why not invest what little time we have into steadily improving the
editors,
so people can simply fix broken and incomplete data.

Why invent complex heuristics that will take month to debug and tune
when it´s not really complex to create a filter to find this kind of bug
and present the user with a suggested fix and the choice to tag that this
is actually correct.

Marcus
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAkxCBJAACgkQf1hPnk3Z0cTLOwCeJLH+ytyp+ksx9Pz5bvoOCLgP
5TcAoN4WPjo23i8J1zuzjO5yFsrLdXZd
=exDR
-END PGP SIGNATURE-


___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Bad routing: U turns for highway links?

[Marcus Wolschon]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

Am 17.07.2010 19:20, schrieb Apollinaris Schoell:
>
> In this example it seems just too easy for a good router to do the
> right thing without hard facts.


How?
Please post the algorithm you are thinking about.

> This can be done by the router or some intelligent preprocessing
> if compute time is critical as an example mkgmap does these type of
> preprocessing to reduce the number of unnecessary announcements and
> creates the routing graph accordingly.

Details?

>
> We might reach the state where all rouads are mapped with lanes,
> yellow lines, all turn restrictions …

Actually, over here we have cities where all streets are there and
people start mapping
single trees and individual lamp-posts.


> but in the meantime it shouldn't stop us from using fuzzy data in
> an intelligent routing algorithm. Ans whenever I has tested
> Cloudmade routing it was not so great.

Please make suggestions on how you plan of doing this.

Marcus
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAkxB+EUACgkQf1hPnk3Z0cQ0jACghRQjIwXA8nJfvpRHy4wYAKuT
4AgAoIyHQnB8+E1fUbF0BHEoUKEJ1vsO
=QomC
-END PGP SIGNATURE-


___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Bad routing: U turns for highway links?

[Marcus Wolschon]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

Am 17.07.2010 01:12, schrieb Anthony:
> On Fri, Jul 16, 2010 at 5:21 PM, Alan Millar  > wrote:
>
> My most recent example is here:
>
> http://maps.cloudmade.com/?lat=45.418666&lng=-122.321563&zoom=16&directions=45.41881686582581,-122.32349395751953,45.4324308667588,-122.36778259277344&travel=car&styleId=1
>
>
>
>
A good example of a place where dual carriageways should be used.
> Notice the double-double yellow lines separating the two
> directions of traffic.
>

Definately.
The road should never have been modeled as only 1 way in the first place.
The router was absolutely right. The road was wrong.

I know places myself where you have 2 separated, oneway primary_links from
a secondary to a primary and it is not only legal but required
to do exactly this turn to turn left.

Marcus
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAkxBWdAACgkQf1hPnk3Z0cRO8gCfSFxIPFjKFlm0JdwmUzBia+TC
PbMAoMPf8KbAMALNCwsZjaPVuhJoHop1
=JNKB
-END PGP SIGNATURE-

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] General Routing question and specific OSRM question

[Marcus Wolschon]

On Thu, Jul 15, 2010 at 7:51 AM, Marc Coevoet  wrote:
> Ted Rosenbaum schreef:
>>
>> Hi,
>> I am very new at routing (this is not my field, and I am just looking to
>> use this in my own research).  I have a general and a specific question.
>> First the general:
>
>
> Could this list of algo hlp you??
>
> http://tech.groups.yahoo.com/group/Opentom/links


Some of them like OLRS and LSR are routing-algorithms for routing
network-packets.
They are not for finding a route for a car on a network of streets.

Marcus

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Fellow mappers, , , I have the pleasure to announce the initial release of a high-perfomance, routing backend

[Marcus Wolschon]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

Am 11.07.2010 13:26, schrieb Dennis Luxen:
>>
>> You would you avoid random IO?
>
> Let me make that more clear. The problem is the number, no the
> locations of the I/Os. A good arrangement of the data gives also
> good cache-effects.

Ok.
I was interpreting it as "ordering the datastructure
to faciliate long linear reads over multiple 8k-blocks"
instead of the probably intended "ordering it to do
reads mostly in 8k-pages already accessed buth with
these pages randomly distributed".


Let´s stop here until we have actual data-structures
to optimize, shall we?
I´m quite amazed by the numbers Christian just posted.

Do you happen to know the limitations this algorithm
has on metrics and the assumptions it makes?
How expensive is a partial map-update actually?
Does it require a full rebuild of some indice or are
incremental updates feasable?


>> On a flash-chip random IO is as cheap as linear IO and not much
>> slower then RAM access. (both chips being on the same memory-bus
>> and no caching or speculative reading in an ARM CPU)
>
>
> Accessing flash linearily gives good cache effects and flash is
> certainly not as fast as RAM.

I guess you mean from the cached pages because I haven´t read about
any speculative read-ahead on any ARM here.
Of cause the flash is not as fast as the ram but it´s not the dramatic
numbers we know from HDDs.

Marcus
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAkw5sGUACgkQf1hPnk3Z0cSWIwCffu9uGtVQgIJ3+K8HQIK+58Fx
YvQAnifygqBHoSuuXS1dyKvrvrzJQLPt
=NJ2k
-END PGP SIGNATURE-


___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Fellow mappers, , , I have the pleasure to announce the initial release of a high-perfomance, routing backend

[Marcus Wolschon]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

Am 11.07.2010 13:03, schrieb Dennis Luxen:
>
> Yes, you are right. On a mobile device you want to avoid random
> accesses to the data structure, because RAM is scarce and I/O is
> pretty expensive. The good news is that it is perfectly possible to
> rearrange the data structures in a way that only a handful of I/Os
> are necessary to compute a route.

You would you avoid random IO?
On a flash-chip random IO is as cheap as
linear IO and not much slower then RAM
access. (both chips being on the same
memory-bus and no caching or speculative
reading in an ARM CPU)

Marcus
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAkw5qLcACgkQf1hPnk3Z0cQMWACaAvNeURi60K8awpXx4ukV2Dq/
rf4An2/p7xQECg+0KvkU8UfquJPWa9H2
=h1bR
-END PGP SIGNATURE-


___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Fellow mappers, , , I have the pleasure to announce the initial release of a high-perfomance, routing backend

[Marcus Wolschon]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

Am 11.07.2010 11:12, schrieb Danny Backx:
> On Sat, 2010-07-10 at 09:06 +0200, Dennis Luxen wrote:
>>> Thanks for publishing it. The algorithm is standart
>>> contraction hierarchies, isn't it ?
>>
>> It is a variant that utilizes all available cores during
>> preprocessing.
>
> Probably a stupid question. How feasible is it to run this
> algorithm on a mobile device ?

- From what I reat, not at all.
The old memory vs. request-computing-time vs. precomputation-time
tradeoff.

Marcus
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAkw5jEsACgkQf1hPnk3Z0cTe2wCg1WdibafGlsU5St1CX80J1eUr
m1EAoKrmiNk5C6qRgazw1qkcAzQcxyPR
=HuSS
-END PGP SIGNATURE-


___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Fellow mappers, , , I have the pleasure to announce the initial release of a high-perfomance, routing backend that is able to handle thousand(s) of requests per, minute. So, without fur

[Marcus Wolschon]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1




Am 09.07.2010 22:00, schrieb Tristram Gräbener:
>  Clearly kml is a bad
> format for a web application. Probably JSON or Protocol Buffer would
> help here.
>


I guess GeoJSON would be perfect because
you are likely to use routing with OpenLayers and
map-tiles.
It´s also very simle.

Marcus
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAkw3hwEACgkQf1hPnk3Z0cR4ZQCgunAcsE9xsFQlZY42vw3hn2CO
tfEAn2ku7iPxBKC/x/5OLqgEYBDTmZCe
=vo2y
-END PGP SIGNATURE-


___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Find shortest path using OSM format file for a country.

[Marcus Wolschon]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

Am 29.06.2010 21:24, schrieb Oleg Demchenko:
>
> I have more specific question about
> TurnRestrictedMultiTargetDijkstraRouter class. My understating it
> is more advanced router from
> org.openstreetmap.travelingsalesman.routing.routers Problem is for
> some Target/Single nodes selected with .GetNearestNode method
> distanced each other 15-20 Kms route method get a "dead" loop. Even
> after 20 minutes it continue calculates something ( I see it from
> console). From other side if I change Start or Target coordinates a
> little bit, route method could be completed successfully after
> 10-15 secs.

If you find a test-case that can be reproduced with a map of managable
size.
Please open a ticket in the bug-reporting.
Finding the cause of such issues is important.
(Even though I cannot promise to have a look myself as I
 an moving to a new job at the moment.)

> Taking into account find ANY car route between to points is on top
> priority for my application comparing with other options (find a
> best way using one turn-restrictions (etc) I have the following
> questions
>
> 1) Does TurnRestrictedMultiTargetDijkstraRouter is suitable for my
> case ( I believe Yes:-))
>

Yes, it is.
You may be faster and more reliable with one of the simpler algorithms
but the resulting routes may be illegal due to turn-restrictions.

> 2) Shall I pass to route method collection of Target nodes instead
> of single node? How to find this collection?
> getNearestNode()returns a single node.
>

You could pass it e.g. all nodes in a given radius but it is okay to
route to any random node in this set.

> 3) It is possible to ask route method after N seconds of
> processing: well, give me actual best path you've found for this
> moment. I see addProgressListener for this class.
>

Not with the ProgressListener (that is only for progress-bars) and not
with this routing-algorithm.
This algorithm aborts as soon as it reaches the start-node from the
set of target-nodes. So if you abort,
you will only get a minimum-cost path that comes near the start-node
but you will not have a route from
the start-node to any of the target-nodes.

> 4) Any links on source examples to find how last
> TurnRestrictedMultiTargetDijkstraRouter is working? Link
> http://travelingales.sourceforge.net/ts.jnlp from
> http://sourceforge.net/apps/phpbb/travelingsales/viewtopic.php?f=3&t=46&p=138
> page is broken.
>
>
>
> From my side I'm ready to prepare a document like "How to find
> optimal car/vehicle/pedestrian  path with
> TurnRestrictedMultiTargetDijkstraRouter?" with a concept and
> source code example when explore it with myself.
>

If you want to understand how it is working, you may read the
DijkstraRouter, then MultiTargetDijkstraRouter and then
TurnRestrictedMultiTargetDijkstraRouter.
The idea behind the MultiTargetDijkstraRouter is to route from target
to start and to let the target be a set of nodes connecting to a
virtual target-nodes with links of metric 0.
The turn-restricted variation improves on that by routing not on edges
of the graph but on pairs of edges. This we we can disallow to make
certain turns on intersections.

It´s not very complicated, quite managable in code-size and the
comments try to explain what is done pretty well.


Marcus
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAkwqVU0ACgkQf1hPnk3Z0cRCjwCfeuZQ+rEzw161LdR0DfUIEdM2
Ix4AnRM9zIoSC+K+Xuqawhwk7/nIPltK
=VoTy
-END PGP SIGNATURE-

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Find shortest path using OSM format file for a country.

[Marcus Wolschon]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

Am 28.06.2010 22:55, schrieb Oleg Demchenko:
> I've met some difficulties to "load" data into H2DataSet from
> Traveling Salesman io class. Well, preliminary I've imported it
> from XML OSM file using OSMOSIS with OSMLIB plugin and
> --write-osmbin-0.6 option to local directory, There are the
> following files within dir C:\temp\osm_export:
...
> : Unable to establish a database connection to
> 'jdbc:h2:C:\temp\osm_export'.
>
> Caused by:
>
> _org.h2.jdbc.JdbcSQLException_: Unsupported database file version
> or invalid file header in file "C:\temp\osm_export.h2.db"
> [90048-126]

Why are you trying to read a map in Osmbin-format in H2-format?
These are 2 different database-formats.

> Unfortunatelly H2DataSet is not documented well (link from WIKI to
> JAVA documentation is broken). Code examples are missed as well.
>
>

There is not much to document on it. It implementes the
same public methods from the IDataSet-interface like all
the other map-databases and no other methods.


Marcus
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAkwpX5kACgkQf1hPnk3Z0cQWgACgtxTfr6+5NMV8rJn6lmxqn7u6
W+QAoLLNimbFFFLjPZh4aLSW357BJPiT
=Z9YO
-END PGP SIGNATURE-

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Find shortest path using OSM format file for a country.

[Marcus Wolschon]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

Am 21.06.2010 13:28, schrieb Curt Nowak:
> Hi Oleg,
>
> in order to get a well connected graph (i.e. a graph in which
> every node is reachable from every other node in that graph) I use
> the follwowing procedure:
>
> ...
>
> If your map contains m disjunct well connected graphs, you will
> end up with m clusters. Then I simply delete all but the largest
> cluster. In my findings (map of Germany) this main cluster
> contains ~99% of the nodes if I remember correctly, so I don't
> really mind deleting the rest.
>
> Curt


I think your idea falls apart when there are oneway-streets.
Something we have lots of. It may however not be of practical relevance.

Marcus
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAkwfT10ACgkQf1hPnk3Z0cTmMgCgkqo3GlawVi+7oST+pyFprXsG
ibwAn2E6upkTOjyx28aF2r2cCddsgyz4
=2GcD
-END PGP SIGNATURE-

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Find shortest path using OSM format file for a country.

[Marcus Wolschon]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

Am 20.06.2010 21:21, schrieb Oleg Demchenko:
> For bigger distance and bigger number of lines it do not connect
> them all properly while building a graph and
> DijsktraShortestPathFinder can't find a path.


Be careful with Dijkstra and turn-restrictions.


>
> Afterwards GEOTools and OSM developers advised me to use OSM
> format files, because they already contains nodes, ways, relations,
> etc. I've load   country highway DB to PostgreSQL using OSMOSIS API
> v1.6
>
> Could you advice, please,  me how to build well connected graph
> and/or find a route on reliable basis? One of the options I've
> found is Traveling Salesman with Route class. It is possible to
> load OSM file from  disk. But how to build a graph afterwards and
> how mySelector below should be implemented?
>
> /FileLoader fl = new FileLoader(new
> File("C:\\Install\\denmark.osm.highway")); MemoryDataSet map =
> fl.parseOsm(); /

Import your MemoryDataSet into some database-backed DataSet
(H2 or implement something yourself for PostGIS) unless you have LOTS
of memory.
The current version of H2 sadly has a known but in the geospatial
indexing that
shows up for negative lat+lons. The fix is in SVN but not tested yet.

> / LatLon startCoord = new LatLon(12.180064, 55.470843); Node
> startNode = NodeHelper.findNearestNode(osmData, startCoord);
>
> LatLon targetCoord = new LatLon(12.198208, 55.516831); Node
> targetNode = NodeHelper.findNearestNode(osmData, targetCoord);
>
> TurnRestrictedMultiTargetDijkstraRouter router = new
> TurnRestrictedMultiTargetDijkstraRouter(); Route theRoute =
> router.route(map, targetNode, startNode, mySelector);/ ...
>

You can use the SimpleCarSelector. It selects all roads that a usual car
can drive on.
(I don´t think you want walking people or bicycles or something
special. ;) )


Marcus
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAkwebX8ACgkQf1hPnk3Z0cTpWgCeOqBk2x4yWF88LMjc5vVd0iXP
qtAAn2rpR1l7wE/B7DpSmxFKQ/P70a2k
=TyEN
-END PGP SIGNATURE-

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Fast Routing Engine - State of Play

[Marcus Wolschon]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1
 
Am 01.04.2010 17:09, schrieb Dennis Luxen:
>> Is it possible to return tripels of NodeID+WayID+NodeID instead
>> if lat+lon from this engine or are it´s internal datastructures
>> too far from the original map?
>
> That's certainly possible, but memory consumption might rise. The
> NodeIDs are already present. The WayIDs are currently thrown away
> at preprocessing. Keeping them in memory as well takes up some
> space. I think it will be bearable.
>
> On the other hand, the ID of the way can be easily queried from
> the original data, since source and target node of each segment is
> already known. I put this feature on the todo list.
>


Thanks. :)
If that was possible then I could very easily add it as another
IRouteFinder -plugin
to Traveling Salesman and the existing other plugins would take care
of driving-instructions, ...

Marcus
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.9 (MingW32)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/
 
iEYEARECAAYFAku0uFoACgkQf1hPnk3Z0cSImwCggGBGRxHJlaTx2/B8Pzpzzjvv
6r8AoKycuvvgjkkLUDjeF+SDMdno94PW
=JI1Z
-END PGP SIGNATURE-


___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Fast Routing Engine - State of Play

[Marcus Wolschon]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1
 

Is it possible to return tripels of NodeID+WayID+NodeID instead if
lat+lon from this engine
or are it´s internal datastructures too far from the original map?

Marcus
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.9 (MingW32)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/
 
iEYEARECAAYFAku0tJIACgkQf1hPnk3Z0cTCjQCgnFPm6ODSufgrbbpbV2FW5+Is
IN0Anjlp6ctW9gqIAOPoG3tUHbBUlxp3
=aQed
-END PGP SIGNATURE-


___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] routing on shapefile

[Marcus Wolschon]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1
 
Am 31.03.2010 01:52, schrieb Pawe? Byszewski:
>
>
> Do you know which format routing is support for?I cann't find eny
> explicite explanation, I found only that there is no capability of
> routing on IMG (garmin) format?
>
> Does anybody know any openSource project which implements routing
> on any format of map?



http://wiki.openstreetmap.org/wiki/Routing#Routing_software

Most routers have one of more of their oen database formats.


Marcus
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.9 (MingW32)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/
 
iEYEARECAAYFAkuylzQACgkQf1hPnk3Z0cTeFQCgwtgH0DKte1JDAGk38SsmpngR
cnQAoIJrYxNzqkDgJCmEtk2J38h0brHs
=2b54
-END PGP SIGNATURE-

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Help: how route through a collection of nodes?

[Marcus Wolschon]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

Camillo Anania schrieb:
> I want to: show that calculated path in some way, on OpenStreetMap
> or Google Maps. Actually I don't know how to indicate when a street
> is traversed different times, so I think that just highlight a path
> on a static map it's not enough. So I was thinking to attach to a
> static map with an highlithed path some driving information so I
> can fully show the path I calculated.
>
> Can I use Traveling Salesman to show that cyclical path? If yes,
> it's a good idea to use a static map with highlighted path and
> driving information?

Sure. Give your path to one of the renderers as the route and let it
render a sensible bounding-box around your path into a Graphics2D-object.
Doing that with one of the 2 renderers that download tiles as a
background could be done in maybe a dozen lines
of code and have no dependencies to anything but some very basic
interfaces.

It´s a trivial task and there is lots of code to do that. Nearly every
mobile phone application contains that
(as they usually don´t render themself.)

Marcus
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAkus1bUACgkQf1hPnk3Z0cTs9gCgue8c+x7z0ZnvBHOzjkU8htKH
bPUAnjRFvfMQ8kU3D9SwMVPFBFxHSzOw
=5N0D
-END PGP SIGNATURE-


___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Help: how route through a collection of nodes?

[Marcus Wolschon]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

Am 26.03.2010 13:58, schrieb Camillo Anania:

> Right, I already have a route from my algorithm and right I mean
> NAVIGATE through these nodes giving instructions to a driver and/or
> showing a map, depend what is easier to do.

It´s usually not an "either or" but an "and" and there are lots of
other things to take care of on the road too.
* Finding, configuring and parsing the output of GPS-device (at least
NMEA).
* handling bad and unreliable gps-reception
* detecting where the driver is
* detecting if the driver is still on the road
* finding a good name for a random piece of road to use in directions
* detecting and  handling turnarounds and complex motorway-link
properly in your instructions
* ...

> Do you know where I can find some examples of code or anything that
> can help me doing that?


Handling general navigation, route-recalculation, ...
http://travelingsales.svn.sourceforge.net/viewvc/travelingsales/trunk/osmnavigation/src/org/openstreetmap/travelingsalesman/navigation/NavigationManager.java?revision=1314&view=markup

Multiple methods of painting a moving map:
http://travelingsales.svn.sourceforge.net/viewvc/travelingsales/trunk/osmnavigation/src/org/openstreetmap/travelingsalesman/painting/

Driving instructions:
http://travelingsales.svn.sourceforge.net/viewvc/travelingsales/trunk/osmnavigation/src/org/openstreetmap/travelingsalesman/routing/describers/
http://travelingsales.svn.sourceforge.net/viewvc/travelingsales/trunk/osmnavigation/src/org/openstreetmap/travelingsalesman/routing/speech/

Parsing and managing TMC messages (traffic delays):
http://travelingsales.svn.sourceforge.net/viewvc/travelingsales/trunk/osmnavigation/src/org/openstreetmap/travelingsalesman/trafficblocks/


(Traveling Salesman is based entirely on plugins. It is MADE to allow
you to plug in one piece and get all
 the others for free.)

Marcus
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.9 (MingW32)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAkussxkACgkQf1hPnk3Z0cRktACfUzi5Dz2ag6zeQ6CfhpMPn86w
v3AAoMVbqNgmKjQIbN3P/Rk6rkAJlC0E
=aEx/
-END PGP SIGNATURE-

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Help: how route through a collection of nodes?

[Marcus Wolschon]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1
 
Am 26.03.2010 11:34, schrieb Camillo Anania:
> Hi guys, I have an ordered collection of points with the associated
> latitude and longitude that represents a path. I obtain those list
> of nodes from a routing algorithm I wrote. Now I have the necessity
> to route through those nodes (those nodes are nodes of an osm map
> where I applied the routing algorithm). I'm a newbie of
> OpenStreetMap but I like the idea very much.
>
> Can you please give me a direction on how I can route through
> those nodes? There are some applications that I can use
> immediately? Any suggestion is appreciated.
>
> Thank you.
>
> Camillo



What do you mean with "route through these nodes"?
You already have a route from your routing algorithm.
Or do you mean NAVIGATE through these nodes, giving
instructions to a driver, showing a map, ...?

You could implement the IRouter-interface in Traveling Salesman
and get all the navigation (map, instructions, re-routing if the driver
misses a turn, estimated travel time, voice, ...) immediately.

Marcus
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.9 (MingW32)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/
 
iEYEARECAAYFAkusj1MACgkQf1hPnk3Z0cRCpwCfagmVJIo+w46h23nZwslXMURb
SzAAoMGJsPzJ/0DXUNsJFFsZx1eIH816
=BpFD
-END PGP SIGNATURE-


___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] routing on shapefile

[Marcus Wolschon]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

Marc Coevoet schrieb:
> Pawe? Byszewski wrote:
>> Hello, I try to create my first GIS application. I managed to
>> display map and I have some problem. I use shapefile downloaded
>> from Geofabrik. Is it appriopriate format to create car
>> navigation application? Do you have any documentation, tutorial
>> or do you know what should I tape in google to find anything
>> about routing on ShapeFIle? I write in Qt(c++) and I don't want
>> use any library if it isn't open source.
>>
>> Reagards Pawel
>
>
> Hello,
>
> Take a look at this open source prj:
>
> http://navit.sf.net  (you can join the effort?)
>
Navit does shapefiles???

> For eg Routing Algorithms, I set up some links here:
> http://tech.groups.yahoo.com/group/Opentom/link
If you can write an implemenation of the IDataSet -interface
of Traveling Salesman that readsy your shape-files, then you get
UI, routing-algorithms, metrics, config-framework, driving-
instructions, translations,... for free. ;)

http://travelingsales.sourceforge.net


Marcus
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAkuq+nwACgkQf1hPnk3Z0cSr3gCgyH9pvcBnAIIwy5zha3PdJPvb
PkEAoMVuaKtz2pjFGDBPXRds481Eied4
=JShv
-END PGP SIGNATURE-


___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] [OSM-dev] Request for help: libosmscout

[Marcus Wolschon]

Did you document your file-format somewhere?

Marcus

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Getting data about average drive times on road segments

[Marcus Wolschon]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

Dr Tim Cooper schrieb:
> 
>
> I need to get data about the average time to drive down individual
> road segments, preferably with data about how it varies at
> different times in the day because in a busy city it can vary
> considerably.
>
>
>
> It looks to me like OpenStreetMap does not have this information.
> It certainly doesn’t appear to be in the .osm files.  I was hoping
> we could get it out of the .gpx files,
>
Do not use the gpx-files for this.
a) many files are anonymized with random times
b) people who map drive VERY different from people trying to get from
A to B


Marcus
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAkt/JkwACgkQf1hPnk3Z0cTtBwCg3NZayS/21QtCMy6qqOP95sOK
SyAAoMEsGqclaa/1p4G09jIGU3T7juLP
=f9Wr
-END PGP SIGNATURE-


___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Yet another parser

[Marcus Wolschon]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

Dennis Luxen schrieb:
>> They use something very different for routing.
> Then what is their algorithm?

I reat a paper on it. Quite interesting.
Basically precomputing lots of routes
with a lot of simplifying.

>> An aproach based on map-reduce that works very well for their
>> scale but does not scale down to anything below 1 datacenter. ;)
>
> I wouldn't bet on Google not knowing the latest research.
Why do you think so?
They have to scale UP to hundrets of
datacenters. Their code never has to scale
DOWN to run on a mobile phone or a single
pc for that  matter.

>>> I have the idea routing algos sometimes take too much roads of
>>> no importance, and arrive where the traffic shouldn't come.
>> what routers with what routing-algorithms, target-metric and
>> parameters did you use?
>>
>> the shortest route for example will almost always use roads of
>> low importance as anything else will just not be the shortest
>> route.
>
> Some would argue that the roads with highest importance tend to lie
> on many shortest paths, i.e. the important highway was built for a
>  reason. Or how do you define importance?

That many people drive from A to B does not mean
that you want to take their road when driving from C to D .
Also roads are build for political reasons, different
distribution of money between comunities, geographical
difficulties, historic reasons...
nothing of this has anything to do with you route at this
day and optimized for what kind of route you want this time.

Marcus

>
> --Dennis
>
> ___ Routing mailing
> list Routing@openstreetmap.org
> http://lists.openstreetmap.org/listinfo/routing

-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAkrwfmoACgkQf1hPnk3Z0cRhYACgu2U0RcJbzoLNsGuBIVVAEA/N
+L8An0tau3u1hPnY+gpPaM7qPWOOpFkQ
=SfNL
-END PGP SIGNATURE-


___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Yet another parser

[Marcus Wolschon]

On Tue, 03 Nov 2009 12:00:03 +0100, Marc Coevoet 
wrote:
> Dennis Luxen schreef:
>>> I've always asked myself why we wouldn't try some quadtree algoritm  
>>> for
>>> parsing/routing/filing our data...
>>> 
>>
>> Well, Quad-Trees don't help you much when it comes to routing. It's a  
>> data structure that helps answering queries that ask for a nearest  
>> neighbor to some coordinate. 
> 
> They use quadtrees at google (for display), I do not know if it is for 
> routing, but.. (if they use quadtrees at google, it is a reason not to 
> study quadtrees here ;-)  "I am a shareholder "...

They use something very different for routing.
An aproach based on map-reduce that works very well
for their scale but does not scale down to anything below
1 datacenter. ;)

> I have the idea routing algos sometimes take too much roads of no 
> importance, and arrive where the traffic shouldn't come.

what routers with what routing-algorithms, target-metric
and parameters did you use?

the shortest route for example will almost always
use roads of low importance as anything else will just
not be the shortest route.

> if you organise a hierarchy of roads, say highways, then "route 
> nationale", then "departementale", you can always prefer to take 
> highways instead of nationales, etc, for a LONG journey.  And I guess 
> there is a relation between "hierarchy" and "dichotomy" somewhere.  
> Where do they meet ??

I have no idea what a "route nationale" and "departementale" are but
we already have a hirachy expressed via the "highway"-tag.


Marcus

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Yet another parser

[Marcus Wolschon]

On Tue, 3 Nov 2009 08:20:54 +0100, Dennis Luxen  wrote:
>> I've always asked myself why we wouldn't try some quadtree algoritm  
>> for
>> parsing/routing/filing our data...
> 
> Well, Quad-Trees don't help you much when it comes to routing. It's a  
> data structure that helps answering queries that ask for a nearest  
> neighbor to some coordinate. For routing it is the easiest to use a  
> simple adjancy list representation for the graph.

Actually it does.
Because before you can do the actual routing you have to find
the nearest Street the driver can actually be on and you have
to find all the target-locations.
For navigation as opposed to route-finding you also need
to continously render a moving map and for that you need
to answer range-queries VERY fast.
This part is actually more demanding on the datastructures
used then simply getting all ways a node is connected to,
the next+prev node along a way and some tags on the ways/nodes
you are evaluating in your routing-application. Also because
the rendering is a realtime-case while route-calculation  happens
usually only once.


> And when it comes to  
> a serious routing scenario, where you have millions of edges and nodes  
> then you need to do specialized preprocessing. Dijkstras classical  
> algorithm and related heuristics don't scale that well on large data  
> sets. There are several exact speedup-techniques for that problem.

Can you please point out a few and maybe even add links to them on
the "Routine" wiki-page? This may be interesting for a lot
of readers.

> Again, a Quadtree is an index structure that answers neighborhood  
> queries fast like "Whats the nearest neighbor to coordinate xy?" or  
> "What is all information we have for a certain region or tile?".

As I pointed out. Very usefull. It need not be the only index.

> Routing on the other hand implies some connection between the nodes  
> that is easier (meaning: more efficiently) to exploit than a spatial  
> index. On the other hand, I have to acknowledge that there is  
> scientific work, that speeds up Dijkstras algorithm by employing tree- 
> like data structures but only among other algorithmic techniques.

(Another index by ID and a backward-reference from node to way
and from node/way/relation to relation are a very, very good thing
for the route-calculation.)

Marcus

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Questions concerning Routing

[Marcus Wolschon]

On 2009-08-04, ibrahim_bouchr...@hotmail.com
 wrote:
> The osmosis library seems to contain some classes to connect with the
> postgresql database.

Yes but only for bulk-reading and bulk-writing.
Not for searching for and accessing individual elements.

> The javadoc i used is located here:
> http://travelingsales.sourceforge.net/javadoc/libosm/

That one is completely outdated.
I need to repair the script that uploaded the javadoc
some time.

> I could also just use JDBC to connect and send out queries, but I noticed
> that the libosm library contains some methods that are transparent to the
> user to work with Nodes. (in other words the queries do not need to be
> writtenn which is a great timesaver for the routing part)
> So i think it would be better to use the libosm's pgsql classes instead of
> just jdbc.

LibOSM contain no current IDataSet -implementation for Postgres.
Your are however free to write one. E.g. based on the H2DataSet.

> Could you provide me with better documentation of how these classes work (if
> better documentation is available) or a clear example of how the connection
> is made using this library?

Look at H2DataSet and MysqlDataSet to see how to connect
to a database. Node, Way, Relation, Entity,... are just data-objects.
IDataSet is where it gets interesting.
There is lots of doumentation on it in the wiki:
http://travelingsales.sourceforge.net/
Looking at the "Plugins"-page and then "IDataSet" can get you started.

PS:
There are no unaproved posts in the forum.
I´m checking it (nearly) every day.

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Questions concerning Routing

[Marcus Wolschon]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

IbrahimB22 schrieb:
> Hi,
>
> I'm just getting started on writing some routing algorithm, but I'm
>  a bit lost. I used osmosis to load a osm file of one city into a
> postgresql database with postgis. I downloaded the jarfiles: libosm
>  2.5.1, osmnavigation 2.5.1 and traveling salesman 1.0.2. I have no
>  clue though where to start, isn't there some site with some full
> examples on how the connection with the local postgresql database
> is made and which classes are most important to start? Someone
> pointing me i the right direction would be great!
Traveling Salesman does not support PostgreSQL-databases
yet. It supports a number of other ways of storing a local
map but not that one (yet).

You only need Traveling Salesman and you just double-click
on that jar or call "java -jar traveling_salesman.jar" and
a wizzard will guide you through the first steps.

The forum to ask questions about traveling salesman ist at:
http://apps.sourceforge.net/phpbb/travelingsales/

If you find any bugs or missing features, you can open a
ticket at
http://travelingsales.sourceforge.net/bugs/bug_report_page.php

You can find the documentation of Traveling Salesman at
http://apps.sourceforge.net/mediawiki/travelingsales/

Regards,
Marcus
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAkp1x8YACgkQf1hPnk3Z0cTKfACeJ8+HwGrE96spUSxKrYZoZxeA
L3wAoKBJpcaE8RHuQPjpa+ScOfE3hGyA
=ufky
-END PGP SIGNATURE-


___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] gosmore skips first motorway entry

[Marcus Wolschon]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

ヴィカス ヤダワ (vikas yadav) schrieb:
> Thanks for the suggestion.
>
> I fixed the entry and exits of the motorway and made all as
> motorway_link. I also changed the service lane from motorway_link
> to secondary so that gosmore counts it slower.
If it is a service-lane, then it is not a secondary road.

>
> Please suggest or point me to an existing motorway road so I can
> learn from that setup.

Entry and Exit are motorway_link and may be oneway=true or oneway=false .
Rest-stops are highway=service and may be oneway=true .
The actual lanes are of cause highway=motorway .
The actual lanes are grouped as ordered relations of
type=road;ref=


Bonus points:
These relations may be part of a well known relation
of type=road_network;name=...

More bonus points:
If there happens to be a public TMC-service in your
country the proper tmc-location-codes may also be added
to the road-relation(for roads) or the intersections(points)
or ways(segments) to identify the location of traffic jams
electronically announced in your radio.

Marcus
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAkpkmzEACgkQf1hPnk3Z0cToEgCgi9CLTd7ItVxjWEzdg+GTWM11
gZkAni7uN2GQOuXtgB1nxDJNMcoG/BGN
=quiH
-END PGP SIGNATURE-


___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Having problems with osm data structure

[Marcus Wolschon]

On Wed, 8 Jul 2009 06:09:21 -0700 (PDT), IbrahimB22
 wrote:
> I'm trying to use osmosis instead of osm2pgsql now. It seems like it will
> be
> of great help later on when I'll try to update my database using change
> sets, plus that libOSM seems interesting too.
> I downloaded osmosis-latest (0.30) from
> http://gweb.bretth.com/osmosis-latest.zip and unzipped it to my work
> directory.
> When I try to run the osmosis.bat it says:
> 
> Exception in thread "main" java.lang.NoClassDefFoundError: and
> Caused by: java.lang.ClassNotFoundException: and
> at java.net.URLClassLoader$1.run(Unknown Source)
> at java.security.AccessController.doPrivileged(Native Method)
> at java.net.URLClassLoader.findClass(Unknown Source)
> at java.lang.ClassLoader.loadClass(Unknown Source)
> at sun.misc.Launcher$AppClassLoader.loadClass(Unknown Source)
> at java.lang.ClassLoader.loadClass(Unknown Source)
> at java.lang.ClassLoader.loadClassInternal(Unknown Source)
> Could not find the main class: and.  Program will exit.
> 
> What am I doing wrong here?

You should ask Brett Henderson about this.
I set him on CC.

Marcus

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Having problems with osm data structure

[Marcus Wolschon]

On Wed, 08 Jul 2009 12:43:50 +0200, Frederik Ramm 
wrote:
> There's a tool called 
> osm2pgrouting somewhere which you should try if you want to do pgrouting 
> (unsure how current the tool is though), or build your own structure 
> based on an "osmosis" data import.

You may also look at Traveling Salesman/LibOSM. It is written for
developers and allows multiple ways of storing a local map, rendering it,
routing, finding an address/place, giving driving-instructions, getting
the current location,... .
It may be a good starting-point or reference to you as I made sure it's
very consistently formatted, commented and documented code.

> note that you can remove those nodes from the graph that have only two 
> neighbours.

Not "can remove", but "may simplify". They are still important for
the calculation of the metrics. ;)

>> All in all, I have to say, is that I'm really confused by this.
> 
> Writing a thesis ought require a bit of dealing with confusing 
> situations otherwise everybody would do it ;-)

Well, if you have any questions. Just ask. :) We don't bite (usually).


Marcus

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] How to make the driver direction is always the north direction

[Marcus Wolschon]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

jiatao83 schrieb:
>
> Hi, all, I am looking for some free APIs or library to mashup a
> mobile navigation application, and I will use the OSM tile as the
> base map. I am just using the free libaray j2memap, But it did not
> provide such a API that could rotate the map so that the driver
> direction is always the north direction! By the way, I have found
> that the VGPS software provide the similar function, But it is not
> free. I have also tried to rotate the map tile, but this method not
> only distorts the map image,but also upside down the road name
> information when you rotate the map image by 180 degree. Could
> anyone help me? Or if there is other solution to make the driver
> direction always the north direction? sad I have been stucked by
> this problem for several weeks. So any Suggestion is welcomed.
> Please help me! Thanks!smile Regards.
>

If the direction of driving is norththe you are driving north.
Pretty useless application ;)



Marcus
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAkoyfrMACgkQf1hPnk3Z0cQXdgCeI0RdLvgW5zvS0U4Rs4b8cfa7
Y2MAnA5KepfgHEUzTcJ6O0Ktz7UVL3Bi
=pby6
-END PGP SIGNATURE-


___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Google Route Alternatives

[Marcus Wolschon]

Frederik Ramm schrieb:
> Hi,
> 
> just played with Google routing from one side of London to the 
> other, and found it tends to display the fastest (often M25) route 
> first, but then offer a number of "alternatives", seemingly named after 
> the road that makes up the largest portion. So in addition to the 
> initial M25 route, you immediately get "M4 (xyz minutes)" and others. I 
> wonder how it is done, algorithmically. It must be more than just the 
> shortest and the fastest route. Does it perhaps store which routes 
> people print after playing aroung with via points, and use that, or 
> something?

>From what I could find they seem to
employ a database of fastest sub-routes
to break down routing to their usual
mapreduce-algorithm.
Can`t find the paper right now.
You could do such a thing yourself
using e.g. apache hadoop but it only
makes sense if LOTS of routes are
to be calculated.

Marcus

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

[Routing] Traveling Salesman - v1.0.0

[Marcus Wolschon]

Traveling Salesman - v1.0.0
==

Traveling Salesman is a navigation application for use on nettops and
laptops for
the OpenStreetMap. It's focus is on clean, well documented code and modularity
via plugins.

Download it:
https://sourceforge.net/project/platformdownload.php?group_id=203597
Start it via Java Webstart:
http://travelingsales.sourceforge.net/ts-stable.jnlp
Changelog:
http://travelingsales.sourceforge.net/bugs/changelog_page.php

V1.0.0 is the first stable version that is feature-complete and bug-free enough
to be called 1.0.
It is not "finished" as such a project never is. There are enhancements already
present in the trunk-version that will become1.1 that are not yet part of 1.0
(TMC-support, more translations, new database-backends, ...).
There are also still issues to be looked at. Importing maps is very
slow but fully
working. But you have to do the cut and call it 1.0 at some point and
for us this
cut was at 1.0.0-RC1.

To try it out, you can use the 2 webstart-versions:
 http://travelingsales.sourceforge.net/ts-stable.jnlp  and
 http://travelingsales.sourceforge.net/ts.jnlp
a wizzard will guide you through the impor of your first
map and configuration of the GPS-device.


Marcus

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

[Routing] state of preparing the TMC-import

[Marcus Wolschon]

I have made quite some progress in preparing the import
of the German TMC Location-Codes that was allowed to us
by the BASt. Now I would like to present what we may get into
the map in a few month.

http://wiki.openstreetmap.org/wiki/TMC/TMC_Import_Germany


We are talking about:
28.520 points
  1.699 segments
  2.889 roads
16.966 intersections
 6.135 administrative areas
932 other areas

spanning all of the german road-network.
Some of these roads, areas and points may not yet exist
in OSM.

There are no tools to do this import yet.
There will need to be due to the excessive topology-checing
required and that this import of Germany may just be the
first of some dozen other complete countries that use TMC
and thus the same exchange-format for their LocationCodeLists.
(No "today germany, tomorrow he world"-jokes please. Actually
 Italy was the first to publish their LCL publicly without highly
 restrictive licensing.)

There is one tool linked in the wiki that can convert the segments
and points (not yet ways, areas and intersections) into an osm-map
for visualisation and manual checking of yet to write import-tools.

== understanding TMC==

I managed to write a small TMC-parser and look at quite a
selection of messages. A proof of concept to use the tagging-
schema below in an actual working navigator with TMC-support
if slowly taking shape. (As the result of the import is to be computer
readable, I believe it should be proven that it can be read and
used in the intended way before starting to add elements the map
that may prove inadequate.)

I managed to get a good understanding of how locations
are referenced in the TMC-system and the given tagging-schema
with its location-codes, forward- and backward-references looks
adequate to the task. The challange may still be that the topology
of the very simplistic tmc-road-network has to be mapped to
our much more detailed osm-network and thus to a more refined
topology. (e.g. dual-carriageways and motorway-juctions are
just a simple line or point in tmc but a tmc-message mentioning
an affected direction may only affect one half of our dual-cardiageway.)

== tagging schema ===

I prepared a tagging-schema that I would very much like feedback on
as it does not yet look very "pretty". (Please use the Talk-Page)
Due to the fact that there are multiple countries with their own
Location-List and that some countries have more then one operator
and that a Tag can only have one value there was a decision to make.
For TMC:Roads the best way to tag them was relations as they are only
ordered lists of TMC:Segments.
But for TMC:Points=OSM:Nodes and TMC:Segments=OSM:Ways
there where 2 options:
1: use a relation with only one member and simple tags like
 tmc:country
 tmc:table
 tmc:locationcode
or
2:tag the element itself but use more complex keys to allow
   the same element to be referenced from multiple locationcodes.
I opted for the second as it is easier to understand, work with
and faster to obtain the referenced objects. (Points and Segments
are usually referenced by TMC-messages. Roads and Areas
more seldomly.)
I tried to avoid characters like "(" or "[" and stayed with ":" and "_"
instread, to avoid special-characters that need encoding.

Marcus

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

[Routing] Traveling Salesman v0.9.8 released

[Marcus Wolschon]

Today I am proud to announce Traveling Salesman v0.9.8 .
In a few weeks, when API 0.6 goes online we want to push
v1.0.0 and to do that, we need your help!
We need people who try it out, make bug-reports, suggest
improvements, complain... we need YOU.
Just click on the webstart-link below, try to use it and
then go back to the forum linked below and tell us what
you think. We want to make this as stable and reliable as
possible to make a usefull navigator for you to use.

Traveling Salesman - 0.9.8
==

Download it:
https://sourceforge.net/project/platformdownload.php?group_id=203597
Start it via Java Webstart: http://travelingsales.sourceforge.net/ts.jnlp
Changelog:
http://travelingsales.sourceforge.net/bugs/changelog_page.php
Announcement:
http://apps.sourceforge.net/phpbb/travelingsales/viewtopic.php?f=3&t=49


After introducing house-numbers with v0.9.7, a great deal of new improvements
are now getting published with v0.9.8.
The most important are probably:
* support for turn-restrictions and metrics for making turns with a
completely new routing-engine -plugin
TurnRestrictedMultiTargetDijkstraRouter.
* support for determining what country a road is in and if it is inside a city
* that is used to provide support for country-spefic traffic
regulations like different maximum speeds and driving on the left side
* we show the ETA and remaining kilometers in the routeInstructionPanel
* Plugins now support having settings of their own and the
Settings-dialog was cleaned up big time
* We support many more speech-synthesesis -plugins with SpeechD and
invoking external programs.
* The low zoom-maps are now much faster and show more roads then
before by applying improved road-combining-algorithms




= Changes 

- 052: [Renderers] ODRPaintVisitor: simplified view missing
significant parts of roads (Marcuswolschon) - erledigt.
- 055: [Renderers] ODRPaintVisitor: map is really sluggish with a
database full of detail (Marcuswolschon) - erledigt.
- 076: [Route-Finding] Route is recalculated too often
(Marcuswolschon) - geschlossen.
- 075: [Driving Directions] NullPointerException in
SimpleRouteDescriber if there is no myNextStep (Marcuswolschon) -
geschlossen.
- 072: [Databases] tags-keys changing (Marcuswolschon) - geschlossen.
- 060: [User-Interface] Selectable predefined zoom for
destinations or route (Marcuswolschon) - geschlossen.
- 071: [User-Interface] Icon for roundabouts missing
(Marcuswolschon) - geschlossen.
- 074: [Route-Finding] TurnRestrictedMultiTargetDijkstraRouter
(Marcuswolschon) - geschlossen.
- 073: [Address-Search] AdressDB strips cyrillic characters
(Marcuswolschon) - geschlossen.
- 070: [User-Interface] show ETA and remaining distance to
destination in UI (Marcuswolschon) - geschlossen.
- 043: [User-Interface] add context menu to map with two items
(combbs) - geschlossen.
- 069: [Driving Directions] allow an external program to be used
for voice-output (Marcuswolschon) - geschlossen.
- 068: [Settings and Plugin-Management] support Config-Settings
with a list to choose from (Marcuswolschon) - geschlossen.
- 067: [Driving Directions] support voice-output using Speechd
(Marcuswolschon) - geschlossen.
- 066: [Settings and Plugin-Management] Settings cannot handle
null values (Marcuswolschon) - geschlossen.
- 065: [Settings and Plugin-Management] Improve plugin-system to
let plugins have settings of their own (Marcuswolschon) - geschlossen.
- 054: [Renderers] ODRPaintVisitor: highway=path without
additional tags falsely rendered like a normal road (combbs) -
geschlossen.
- 059: [Driving Directions] 0.9.8-beta: still wrong instructions
(Marcuswolschon) - geschlossen.
- 061: [User-Interface] improved finnish translatrion
(Marcuswolschon) - geschlossen.
- 058: [User-Interface] search field has "steetname"
(Marcuswolschon) - geschlossen.
- 056: [Driving Directions] A "turn right" is needed but screen
shows "follow road" (Marcuswolschon) - geschlossen.
- 057: [User-Interface] add instructions to log-panel
(Marcuswolschon) - geschlossen.

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] default-sizes for city/town/village/...

[Marcus Wolschon]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

Eddy Petrișor schrieb:
> 2009/3/27 Eddy Petrișor :
>> 2009/3/27  :
>>> * Is there a way to use is_in or other hints to make this more
>>> accurate?
>> how about extending the bounding box to
>>
>> Xdelta = max (DEFAULT_*_SIZE, max(abs (Cx - Pix) | for every i
>> node)) Ydelta = max (DEFAULT_*_SIZE, max(abs (Cy - Piy) | for
>> every i node))
>>
>> Where: - (Cx, Cy) is the origin of the place and - (Pnx, Pny) is
>> the position of n-th node that contains place's name in the is_in
>>  value*.
>
> Note that you should consider every node of each way that has
> contains place's name in is_in. Considering only the ends of the
> way is not correct since for a curved way the nodes in the middle
> might be more outwards than the ends.

Indeed I could do that while building the  Address-Database.
It would never shrink the place if an updated node with a
changed location comes in  but that should nave little effect.

In don`t think it will change much as is_in is practically
unused.
It would also slow down map-imports even more
as for every node and way with an is_in or is_in:city
I need to do a name-normalisatio and "where name like"
- -lookup in the HSQLDB.
Loading all nodes of an incomming way should not slow
down things as they get loaded anyway to set their
back-references to the ways that use them and nodes
are stored in a memory-sensitive cache when being loaded.

But still a good idea. It may help in seldom cases

Marcus
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAknNCZMACgkQf1hPnk3Z0cT2pwCgxJrF4nZMWPY11xau14tlBYNu
a1sAn2Ec44QosuQ95v61PezKsiQsnH/O
=BrWZ
-END PGP SIGNATURE-


___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Need info about route planners

[Marcus Wolschon]

On Wed, 25 Mar 2009 10:08:19 +, Xayide p  wrote:
> Hello!
> 
> Thanks for your answers!! It's been of great worth!
> 
> I have a doubt about pgRouting and Traveling Salesman: if they can be
used
> for planning routes in public transport, which data format do they use? i
> mean, i know there are some standars as GTFS and European Trident. Do any
> of those planners use standard data format or custom data format, or any
of
> them?

TS:
none yet. You would have to write your own IRouter that can use the
existing
routers on the road to route to the nearest train,... -stations and to the
target,
then calculate waiting-time and time in transport in the train/... to the
station nearest to the destination and then routing for pedestrians
(a different ISelector then the SimpleCarSelector) for the way from that
station to the destination.

Looks like maybe a week or half a week of work.

Marcus

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Searching for ShootingStar -algorithm

[Marcus Wolschon]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

Wolfgang Wasserburger schrieb:
>> It sounds interesting and if I only have some time I will check it.
>> By the way, do you have any papers? :)
>>
> 
> In Wikipedia you find a good starting point for all the standard algorithms
> 
> Regards from Vienna
> 
> Wolfgang

Dear Wolfgang,

Wikipedia has no article on the shootingStar -algorithm,
http://de.wikipedia.org/wiki/Shooting_Star

this is one of the first things I checked when I started
searching for it last year. In fact, I only find the most
standard algorithms there and none that supports restrictions
or cost on turns between 2 edges.

Marcus
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFJyUNef1hPnk3Z0cQRAjoaAJ9kaT2eMrX0HLZ7WS/85XNHNoa1yACgmtsZ
fHIzsMQVxrLW8hIgJYY0018=
=C6WF
-END PGP SIGNATURE-

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Searching for ShootingStar -algorithm

[Marcus Wolschon]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

Wolfgang Wasserburger schrieb:
> Try pgRouting, it also incorporates shooting* within PostGIS/PostgreSQL
> 
> Greetings from Vienna, Austria
> 
> Wolfgang

Well, you seem to have missed the initial post
where I already told that I knew it was implemented
in pgRouting.
However PostGIS is no option for me. I am implementing
it as a routing-plugin for Traveling Salesman, thus my data-store is
the 4 sets of Osmbin -files (base-layer and 3 simplified
levels of detail) and implementation is 100% pure Java.

I could not require an unskilled Windows- or Linix- user
to install PostgeSQL and PostGIS on his Nettop or Car-PC
prior to using my navigation-program.
Nor would pgRouting allow for my routing-metrics
and most of the osm-specific data I am dealing with.

Marcus
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFJyUJDf1hPnk3Z0cQRAq2cAJoD0/1xA1vuFl5uwgd8VpH1VQRUYACbBuCn
T4BcIs+QSibVoTQIGlUscGM=
=+ZYW
-END PGP SIGNATURE-

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Searching for ShootingStar -algorithm

[Marcus Wolschon]

On Tue, 24 Mar 2009 18:14:58 +0900, Anton Patrushev 
wrote:
> Hi Marcus,
> 
> It sounds interesting and if I only have some time I will check it.
> By the way, do you have any papers? :)

Hi Anton,

no. I haven't read many papers since I left university and started working.
;)
I just followed the aproach outlined by Nic Roets and made up my own mind
of how it needed to work.

Marcus

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Searching for ShootingStar -algorithm

[Marcus Wolschon]

On Tue, 24 Mar 2009 10:19:35 +0900, Anton Patrushev 
wrote:
> Hi Marcus,
> 
> I believe that if I don't have a description than nobody has it. And
> unfortunately I don't have any :(
> I can give you some hints and ideas, but I never had time to make any
> kind of scientific papers.
> 
> Shooting* is edge-based, so it goes from edge to edge while A* and
> Dijkstra go vrom vertex to vertex. Thus you need a data structure
...
> So, that's an idea behind the Shooting*.
> 
> I am ready to help you with your implementation, so please contact me
> if you need any help.

Thanks Anton,

I just manages an implementation of edge-based routing here:
http://apps.sourceforge.net/mediawiki/travelingsales/index.php?title=Plugin/TurnRestrictedMultiTargetDijkstraRouter

It seems to work fine however much testing remains before I can release
it as the new default routing-engine.

Marcus

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] turn-restrictions working in Traveling Salesman

[Marcus Wolschon]

On Fri, 20 Mar 2009 17:27:30 +0200, Nic Roets  wrote:
>> Can you give some more details about how you did it?
> 
> Give numbers to all your segments (gosmore uses "double half segments"
but
> the idea is the same)
> 
> Then you have an array of Dijstra nodes :
> struct DijkstraNode {
>   int segnumber;
>   boot forwards; /* Are we traveling forwards or backwards ? */
>   float distance;
>   boot unprocessed;
>   /* For A* you may have an additional variable for the heuristic */
> }
> 
> Each (segnumber, forwards) pair may only occur once.
> So for each Dijkstra iteration you look in the array for the dijkstraNode
d
> with the lowest distance with unproceesed equal to TRUE.
> * If forwards is true, you find the OSM node n to which the segment is
> pointing to. Otherwise n is the OSM node that the segment is coming from.
> * Now you look at all the segments s connected to n. (Gosmore will
current
> not consider s=d.segnumber, so u-turns back into the same way are not
> allowed) Can I travel from d.segnumber to s ? If yes, add
> (segnumber=s,unprocessed=TRUE) to the dijstraNode array. If it's already
in
> the array and the new distance is shorter, update it.

Thanks a lot for the suggestion Nic!
I was able to implement it and it seems to work fine.
Other then your implementation I does allow u-turns
(unless a no_u_turn -relation exists).

As I already have a RoutingStep -class that is used to abstract
between routing-engines and diving-instruction-plugins I could do
away with the "bool forwards;" and segment-numbering. A RoutingStep
contains a start-node, way and end-node.
I do not mark them as "unprocessed" as I keep one sorted set of
RoutingSteps to be processed and one map of the best step for each
processed one.

Announcement:
  http://apps.sourceforge.net/phpbb/travelingsales/viewtopic.php?f=3&t=46
I'll update the Java Webstart -version of Traveling Salesman tonight
in case anyone wants to play around with it.

Marcus

>> "a user who simply looks for a navigation or routing- application to
USE"
> 
> Note that a user does not need to know what algorithm the program uses.

I agree that many would not care and just skip that point.
The ones who care would like to know and the others dont care.
As most of them are free software I as a developer do care as
it shows me where I can look for reference as I just did with your
turn-restrictions.

> AFAIK the house number data in OSM is still quite limited. So saying
'Yes'
> is very misleading to a newbie.

I don't think think so. It is an important feature to distinct between
the capabilities of the different programs. That's what the table it about.

> Will you update your table when new versions of gosmore is released ? I
> doubt it. So your table will just continue to mislead newbies.

If I notice such a change in
http://wiki.openstreetmap.org/wiki/Gosmore
yes, I will update it acordingly.

> I can't see how a smart guy like you can think it's acceptable to just
make
> up facts.

What factual errors remain in the table?

Marcus

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] comparison of navigation-apps

[Marcus Wolschon]

Eddy Petrișor schrieb:
>> I don't suspect we get enough information to get more then just
>> the major applications into the table at all. Anyway we will have many
> 
> The way the table is arranged now, it even discourages possible new
> applications to be added.
> 
>> more features then applications. This the table would grow terribly wide.
> 
> I think this layout is better:
> http://wiki.openstreetmap.org/wiki/Software

That table has very short headings.
What can we do about the explanations for each heading we have?
I guess the grouping of headers can be done using 2 header-rows and
colspans.
We`ll see how it looks when you`re done, ok? :)

Marcus

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Traveling Salesman - version 0.9.5 released

[Marcus Wolschon]

Sorry.

For all those who got a ClassNotFoundError due to
"org.java.plugin.PluginClassLoader",
I just uploaded a bugfixed version.
I forgot to include the new jpf.jar in the distributed executable jar.
My mistake.


Marcus



On Wed, Mar 4, 2009 at 9:45 AM,   wrote:
>
> Version 0.9.5 of the Traveling Salesman navigation-system for
> OpenStreetMap has just been released.
>
> * With an improved plugin-system we now have an optional speechPack to add
> voice-output.
>  (Note that higher quality voices and phonems for other languages can be
> installed later.)
> * Thanks to your help in the OSM-Wiki
> (http://wiki.openstreetmap.org/wiki/Sample_driving_instructions)
>  we now not only have much improved driving-directions but also the first
>  translated driving-instructions.
> * There are some major speed-improvements in the reference-implementation
> of the OsmBin
>  file-format and the LODDataSet (automatic Generation of simplified low
> zoom-levels).
> * You can now file feature-requests, bug-reports and complains via the
> help-menu.
> * Testing without a GPS-device has become much easier with the new gpx-file
> -controlpanel
>  reachable from the debug-menu. (fast forward and slow down in gpx-files)
>
> As we want to REACH VERSION 1.0 BY THE 23.3.2009 with the introduction of
> the
> OpenStreetMap API 0.6 we need YOUR HELP. We NEED BUG-REPORTS, feedback,
> ideas
> but also patches, plugins and feature-request.
> Tell us what needs improvement!
> Tell us what we did wrong!
> Tell us what needs better documentation!
>
> http://apps.sourceforge.net/phpbb/travelingsales/viewtopic.php?f=3&t=29
> http://sourceforge.net/project/showfiles.php?group_id=203597
>

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] parsing roundabouts

[Marcus Wolschon]

On Mon, 2 Mar 2009 09:50:12 +0100, Guenther Meyer 
wrote:
> Am Montag 02 März 2009 schrieb marcus.wolsc...@googlemail.com:
>> Hello everyone.
>>
>> I'm thinking about how to add support for
>> proper driving-instructions for roundabouts
>> to Traveling Salesman.
>> "In 200m enter the roundabout! Then take the second exit!"
>>
>> There are 2 issues:
>>
>> 1 How to determine if the roundabout is drawn clock-wise
>>   or counter-clock-wise.
> 
> is this relevant?

Yes, it is.
Not for routing but for the driving-instructions.
You need to know the ordering to determine if you count the exits
in ascending or descending waynode-order to get the "second" in
"Then take the second exit!".
..unless I'm missing someting.

> if the routing is implemented properly, the route shouldn't walk into the

> wrong direction (roundabouts are oneway).
> when the route has been calculated, you just count the number of exits
from
> 
> entering until leaving, then you have the number of the needed exit.

mmh... can I actually assume all roundabouts to be drawn in the correct
direction?
This would indeed make my thinking obsolete and this trivial to implement.

Marcus

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] collecting translations of driving-instructions

[Marcus Wolschon]

Eddy Petrișor schrieb:
> Why don't we use templates?
> Templates are translatable and missing strings are immediately
> visible, while outdated strings appear in English if the id-s are
> changed when the original changes.

Hello Eddy,

how would you like to apply the mediawiki-template mechanism?
I see not way to do what you describe.

Marcus

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] collecting translations of driving-instructions

[Marcus Wolschon]

On Fri, 27 Feb 2009 14:01:22 +0100, "Pierre-André Jacquod"
 wrote:
> Hi,
> I just tried to extend it to french, but on wiki that is not so easy.
> And I have no way to have a look if some text has been added to the
> reference language.. which is english I guess?

Yes, english is the most common language so it makes sense to have it as a
reference.
The easiest way is to have the reference-page and the page you are
translating in
2 browser-tabs. It worked fine for me when I added the german translations.

> Usually we are using PO file in order to store this kind of translation.
> There are editors that helps to support this kind of work (like KBabel,
> even if I have never used it up to now).
> But this is a great idea

I am well aware of that but the wiki is the one place where everyone
finds this and can easily edit it without separate editors.
It should be possible to generate .po -files from the wiki via
a script. I hope to find the time for an IRouteDescriber -plugin
for Traveling Salesman next week reads these wiki-pages uppon startup
and an ant-task to generate .properties and/or .po -files from them 
to make it easy to test and use.

Marcus

>> http://wiki.openstreetmap.org/wiki/Sample_driving_instructions


___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] collecting translations of driving-instructions

[Marcus Wolschon]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

Eddy Petrișor schrieb:
> Marcus Wolschon a scris:
>> Hello,
>>
>> I started the page:
>> http://wiki.openstreetmap.org/wiki/Sample_driving_instructions
>>
>> to collect translations of driving-instructions for all our
>> routing and navigation -programs to use. It is clear that not
>> every project has developers speaking every language, so we may
>> as well collect a pool of translations.
>>
>> I tried to give the pages an easy to parse structure, so that a
>> simple script can extract the translations and build the
>> .properties, .po or whatever files the individual program uses.
>
> It is very nice what you're trying to do, but I must warn you that
> some languages, such as Serbian, have different forms for the
> plural depending on the number of counted items. Same is for
> Russian, iirc.


Thaks for pointing that out.
Even as I "learned" russian in scool
15 years ago I don't remember anything
about it any longer.

I started a discussion about it on the talk-page.

Marcus
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAkmle+MACgkQf1hPnk3Z0cTUJgCgwa4cg3ObCLlm++nn5Jjvbm04
eQYAnRtfwzFs15ujYVKNLhxs/9+uuj3K
=TAkP
-END PGP SIGNATURE-


___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

[Routing] collecting translations of driving-instructions

[Marcus Wolschon]

Hello,

I started the page:
http://wiki.openstreetmap.org/wiki/Sample_driving_instructions

to collect translations of driving-instructions for all our
routing and navigation -programs to use.
It is clear that not every project has developers speaking
every language, so we may as well collect a pool of translations.

I tried to give the pages an easy to parse structure,
so that a simple script can extract the translations and
build the .properties, .po or whatever files the individual
program uses.

Marcus

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] OpenLayers, KML: how to display route?

[Marcus Wolschon]

On Sun, 22 Feb 2009 13:53:10 +0100, Lambertus  wrote:
> Marcus Wolschon wrote:
>> Lambertus schrieb:
>>> A webbrowser does not allow you to do cross site AJAX calls. You will 
>>> need to setup a local proxy on your webserver who relais the 
>>> yournavigation.org queries.
>> 
>> I found a way around this limitation a while ago.
>> It works file to dynamically include a javascript from
>> that remote site and have it set variables as a replacement
>> for the ajax-calls.
>> 
> Ok, I could provide such a javascript file if that makes it easier for 
> other sites to use the YOURS API, but I don't clearly see what should be 
> in there: a variable containing the base URL? And would that be enough, 
> because I cannot pre-set every possible lat/lon in advance?

No, that I used was a php-script that took URL-parameters and
gave an output like:


  answer = "xyz";
  handleAnswer(answer);


Where handleAnswer(param) is a method defined on the website
(similar to the ajax-handler).

It worked well across domain-boundaries in FF2, FF3,
Safari, IE5, IE6, IE7 and Chrome.

Marcus

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] OpenLayers, KML: how to display route?

[Marcus Wolschon]

Lambertus schrieb:
> A webbrowser does not allow you to do cross site AJAX calls. You will 
> need to setup a local proxy on your webserver who relais the 
> yournavigation.org queries.

I found a way around this limitation a while ago.
It works file to dynamically include a javascript from
that remote site and have it set variables as a replacement
for the ajax-calls.

Marcus

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] collecting read-world average-speeds

[Marcus Wolschon]

On Fri, 20 Feb 2009 14:26:23 +0100, "Wolfgang Wasserburger"
 wrote:
>> Forum-thread:
>> https://apps.sourceforge.net/phpbb/travelingsales/viewtopic.ph
>> p?f=7&t=17
>> 
> ... Um mir da nur mal kurz anzuschauen: mu? ich mich da wirklich irgendwo
> anmelden? Wenn ja wo, wie?

Sorry, I just copied that from the address-bar.
For non-sourceforge-users it's
http://apps.sourceforge.net/phpbb/travelingsales/viewtopic.php?f=7&t=17
(without SSL = no login required)


Marcus

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

[Routing] collecting read-world average-speeds

[Marcus Wolschon]

Hello,

I started a small experiment to collect real-world
speeds in order to get better ETA-calculations.

What do you think about the classification I used?
I tried to collect as little personal data as possible,
thus you never send driving-times or anything that
can identify a single vehicle.

If the general idea is aproved I want to make it
a web-service and write
1) an optional  plugin for Traveling Salesman to
   automatically collect and upload such data
2) a metric that uses this in calculating the fastest
   route.

The Test itself:
speedcollector.comyr.com

Forum-thread:
https://apps.sourceforge.net/phpbb/travelingsales/viewtopic.php?f=7&t=17


Marcus

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

[Routing] preprocessing for turn-restrictions usins an osmosis-plugin

[Marcus Wolschon]

Hello,

I am planning to add a new plugin-task to osmosis
that turns nodes with turn-restrictions into
an equivalent graph of oneway-roads.
This may enable routing-engines that cannot deal with
restrictions or cost on graph-nodes to deal with
turn-restrictions.

I just think it may be usefull to others as well. ;)

Brett:
 how do you think I may do this using ormosis
 architecture?
Can a task read from an entity-stream and write
to a DataSet that is also needs to read from and
remove entities from?
(Stream all nodes and ways to the DataSet,
 then process the incomming relations and change
 ways already written to the DataSet. This includes
 ways that may have been in there before osmosis started.)

Marcus

http://wiki.openstreetmap.org/wiki/Osmosis/DetailedUsage#--induce-ways-for-turnrestrcitions_.28-iwtt.29
http://sourceforge.net/tracker2/?func=detail&aid=2612536&group_id=203597&atid=986234



___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] tracks, ways, avg. speed -& gt; new attribs for our ways

[Marcus Wolschon]

On Wed, 11 Feb 2009 15:19:08 +0100 (MET), "Gary G:"  wrote:
> is there a wiki page for that topic already?

Not yet.
Feel free to create one.


Marcus 

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] tracks, ways, avg. speed -> new attribs for our ways

[Marcus Wolschon]

On Wed, 11 Feb 2009 13:39:19 + (GMT), GS 
wrote:
> hi,
> 
> i just stumbled upon this article here
>
http://www.gpsbusinessnews.com/TomTom-s-crowdsourcing-5-millionth-map-correction_a1234.html
> 
> it says (beside other things) tomtom collects track data of their users
and
> calculates avg. speeds per street/way.
> 
> - did anyone think about that using our tracks and map data?

Yes, we have some lengthy discussion on this topic in the archive.
The end of it was that our track-data is not usable for this purpose
but that a customized service to collect average speeds of different
general car-types with drivers that are not currently mapping side-roads
would be a good thing.
Also many ways of anonymizing and corrupting gpx-tracks have been
discussed.

> - is it feasible?
> - will/can derived data be used?

It can be used, the license is clear. However the quality of the data is
not good enough.

We SHOULD get something like the map_features -page but for tags on
gpx-tracks. This way we can query our tracks by vehicle-type and similar
categories.

Marcus

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] "avoid-obstacles" algorithm

[Marcus Wolschon]

On Thu, 29 Jan 2009 12:53:27 +0100, Ivan Garcia 
wrote:
> Hi everybody
> 
> we would like to implement for disabled persons that will help them to
find
> the route by avoiding obstacles or undesired areas in the map.
> 
> An example of this is http://seamster.cs.umd.edu:8090/map/index.html ,
> where
> you can add dinamically obstacles that you will not like to pass by.
> 
> That means that we are looking for some open source software(or library)
> that allows us to do that. Another approach could be giving a high WEIGHT
> to
> some paths so that way the route algorithm will avoid passing by there.

With Traveling Salesman
(https://sourceforge.net/projects/travelingsales/)
you can do this by creating a specialized Selector
(http://travelingsales.svn.sourceforge.net/viewvc/travelingsales/libosm/src/org/openstreetmap/osm/data/Selector.java?view=markup)
that denies stairs and similar and passing this
to the routing-engine of choice.
(https://apps.sourceforge.net/mediawiki/travelingsales/index.php?title=TS/Examples)

Marcus

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Traveling Salesman 0.8 with the OsmBin file-format version 0.9 and libOSM+OsmNavigation 2.3.9 released.

[Marcus Wolschon]

2008/12/23, Marcus Wolschon :
> Hello everyone.
> After a year of silence I found the SVN-Head to
> be stable enough to relase
> * version 0.8 of the Traveling Salesman -navigator and
> * Verson 2.3.9 of the LibOSM and OsmNavigation -libraries
> https://apps.sourceforge.net/mediawiki/travelingsales/index.php?title=Main_Page
> (Note: The Java-Webstart -link will be updated to the new
> version in a few days. I need to access my key-storage
> on another computer first to create a signed jar.)

Sorry, I posted the wrong link. It's
http://apps.sourceforge.net/mediawiki/travelingsales/index.php?title=Main_Page
The https-link asks for a sourceforge-account to edit wiki-pages.

Marcus

>
> They are now using 0.9, the first non-draft -version of
> my OsmBin file-format
> http://wiki.openstreetmap.org/wiki/OSMbin(file_format)
> as their new default-format.
> I intend to finalize this file-format as a version 1.0 when API0.6
> is public with a added version-numbers and small improvements.
> Please give comments, so we can make this a better format
> for indexed, mutable on-disk -storage with random access.
>
> I also changed the default-renderer from the SimplePaintVisitor
> to the much nicer OdrPainsVisitor after adding support for
> different text-styles depending on zoom-level and way-type.
>
> Please feel invited to comment on my file-format
> and to file any bugs you encounter to
> https://sourceforge.net/tracker2/?group_id=203597&atid=986231
>
> Thank you.
> Marcus Wolschon
>

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

[Routing] Traveling Salesman 0.8 with the OsmBin file-format version 0.9 and libOSM+OsmNavigation 2.3.9 released.

[Marcus Wolschon]

Hello everyone.
After a year of silence I found the SVN-Head to
be stable enough to relase
* version 0.8 of the Traveling Salesman -navigator and
* Verson 2.3.9 of the LibOSM and OsmNavigation -libraries
https://apps.sourceforge.net/mediawiki/travelingsales/index.php?title=Main_Page
(Note: The Java-Webstart -link will be updated to the new
version in a few days. I need to access my key-storage
on another computer first to create a signed jar.)

They are now using 0.9, the first non-draft -version of
my OsmBin file-format
http://wiki.openstreetmap.org/wiki/OSMbin(file_format)
as their new default-format.
I intend to finalize this file-format as a version 1.0 when API0.6
is public with a added version-numbers and small improvements.
Please give comments, so we can make this a better format
for indexed, mutable on-disk -storage with random access.

I also changed the default-renderer from the SimplePaintVisitor
to the much nicer OdrPainsVisitor after adding support for
different text-styles depending on zoom-level and way-type.

Please feel invited to comment on my file-format
and to file any bugs you encounter to
https://sourceforge.net/tracker2/?group_id=203597&atid=986231

Thank you.
Marcus Wolschon

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Tiger Data and Routing

[Marcus Wolschon]

John07 schrieb:
>> I have added a button "edit" that starts JOSM with the currently
>> visible part of the map into my Navigator "Traveling Salesman"
>> a long time ago.
>> A button "Mark Error in Map" sounds good. What could such a button
>> do?
>> Create a note with a "FIXME=yes" and "node=..." and have the user enter
>> a comment?
>>   
> I think the best way would be to intigrate openstreetbugs like the 
> openstreetbugs-plugin in josm does.

The current extension-point for the renderer-plugins
does not allow for such a thing and I don't want to
confuse any users that do NOT want to map under any
circumstances.
so...not an option.

Suran

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Crowdsourced costing - offer of writing a c lient+metric for it

[Marcus Wolschon]

On Thu, 04 Dec 2008 10:37:49 +0100, Frederik Ramm <[EMAIL PROTECTED]>
wrote:
> But the one thing we have and they don't is, we have an expert among us 
> for almost every single road! We have someone who lives round the corner 
> and who can tell us first-hand whether the road is likely to be blocked 
> or difficult at certain times, which path he would use, and so on. This 
> is the key thing that sets us apart from the big players, and we must 
> make use of this capacity. Automatic derivation of traffic situation 
> data is not an OSM USP, everyone can (and will) do it.

Helle Frederic,

I see automatic meassurements as one thing we simply can do.
As for tapping into the pool of mapperss, I do't see HOW
we can do that without opening every door to vandalist.
Since the local people are also the ones who want their
street to be nice and quiet and less traffic to cross in front
of thei're kids schools,...

You are right, that this is one thing we have and the professionals
don't. But just because eventually others will collect data too
does not mean that we shouldn't start doing it.
We can set the standards for traffic-meassurement and car2car because
we can be the first that actually get such a thing deployed on the
road. Thus we can make sure that the protocolls we employ are simple
to understand and can be implemented (both client and server) by everyone
without joining an industry-consortium and paying a fortune for the
previledge of looking at their cryptic standard.

Marcus

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Tiger Data and Routing

[Marcus Wolschon]

On Wed, 3 Dec 2008 17:20:55 -0600, "David Lynch" <[EMAIL PROTECTED]> wrote:
> Actually, this wouldn't be a bad place for the crowdsourcing mentioned
> elsewhere on this list in the last couple days. Giving users the
> ability to mark errors in the data and have it corrected -- without
> requiring them to edit the underlying OSM data themselves -- wouldn't
> be bad, and some of it could even be done automatically (though this
> may not always be wise.)

Hello.

I have added a button "edit" that starts JOSM with the currently
visible part of the map into my Navigator "Traveling Salesman"
a long time ago.
A button "Mark Error in Map" sounds good. What could such a button
do?
Create a note with a "FIXME=yes" and "node=..." and have the user enter
a comment?

Marcus

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Crowdsourced costing - offer of writing a client+metric for it

[Marcus Wolschon]

Sascha Silbe schrieb:
>> I`d more like to leave local storage of the answers up to the
>> application.
> If you're only ever concerned with single queries, that's fine. I
> imagined downloading data excerpts for a whole area that could be shared
> by different applications (so they don't need internet access during
> route calculation).
> The querying user has to trust the server not to store its query
> patterns, BTW, so another case of "user has to trust the server".

That sounds interesting. I did not yet think about that.
What do you propose?

MArcus

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Crowdsourced costing - offer of writing aclient+metric for it

[Marcus Wolschon]

On Wed, 3 Dec 2008 14:11:23 +0100, "Wolfgang W. Wasserburger"
<[EMAIL PROTECTED]> wrote:
> The best description for date and time is a timestamp. Further
anonymizing
> should be done at query time.

What do you mean with "at query time"?

It makes no sense to save the original meassurements with a timestamp
as you cannot query a timestamp for "similar times". So they need to
be grouped semantically (like I tried). The original timestamp is never
needed.

Marcus 

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Crowdsourced costing - offer of writing a client+metric for it

[Marcus Wolschon]

On Wed, 3 Dec 2008 12:42:31 +0100, Sascha Silbe
<[EMAIL PROTECTED]> wrote:
> On Wed, Dec 03, 2008 at 12:11:46PM +0100, Marcus Wolschon wrote:
> 
>> I tried to not make it to make my firt draft not too
>> fine-grained due to privacy and not-enough-data -concerns.
> 
>> We can have a * day =
>>
(weekday,weekend,holiday,beforeHoliday,afterHoliday,schoolVacation,beforeSchoolVacation,afterSchoolVacation)
>> ** weekday (mo,...sa,so)
> That's better, though you still miss some cases (e.g. the christmas 
> shopping period). In addition, the user is required to enter more data, 
> making it more likely (s)he just doesn't bother enough to submit the 
> data.
> How about just making the (full) date field optional? Send it by 
> default, but give the user the choice of anonymizing the data.

I don`t think the xmas-perio matters that much apart
from the days right before and after the holidays.
(xmas, night before xmas and new-year)
I see privacy as a main-issue here, thus I don`t want
the user to have to trust the server at all. If it does
not need the exact timestamp, it will not get it in the
first place. 

>> The server need never hand out data of a single upload.
>> To be meaningfull it even needs to be averaged for many
>> users.
> To be useful to a single end-user, it needs to be aggregated some way, 
> yes. But there are many ways to aggregate the data, so tool developers 
> would want excerpts of the raw data as well.

To provide the aggregated data is exactly the service provided.
I`m not sure about this requirement to come up at all but we may
add additional query-types for them later as they come up.
No need to over-engeneer things.


>> I suggested soap because it is supported by many
>> systems, it is type-safe and trivial to check and
>> there is good tooling.
> Type-safety is certainly good to have. Though I'd rather like a format 
> that can be used for offline storage and exchange as well...

I`d more like to leave local storage of the answers up to the application.

Marcus


___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Crowdsourced costing - offer of writing a client+metric for it

[Marcus Wolschon]

On Wed, 3 Dec 2008 11:44:15 +0100, Sascha Silbe
<[EMAIL PROTECTED]> wrote:
> On Wed, Dec 03, 2008 at 07:50:26AM +0100, Marcus Wolschon wrote:
> 
>> * day = (weekday,weekend,holiday)
>> * time = (night,morning,afternoon)
>> ** sub-time = (early,mid,late)
> Unfortunately, that's too coarse. You'll miss things like "Shops are 
> closed on Wednesday, so much less traffic then". Or the yearly recurring 
> traffic increase due to christmas insanity...


I tried to not make it to make my firt draft not too
fine-grained due to privacy and not-enough-data -concerns.
We can have a 
* day =
(weekday,weekend,holiday,beforeHoliday,afterHoliday,schoolVacation,beforeSchoolVacation,afterSchoolVacation)
** weekday (mo,...sa,so)

is that more to your liking?

>> * we do not receive user-identifications at all
>> * the IP and upload-time are stored to revert manually detected 
>> vandalism
> Those two are mutually exclusive. Though german ISPs tend to assign 
> dynamic IP addresses so they can sell static ones for more money, it's 
> not the case everywhere. Even then, given usual IP address lifetimes 
> (24h), the tuple (IP address,time) is enough to identify a user if 
> correlated with other sources (e.g. emails).

Yes, that can be a problem. Does anyone on this list have suggestions
on how to prevent or revert vandalism?
We do have the option of ignoring that part for a prototype for the
time being and care about it later.


> Summary:
> - there are some cases where anonymity is not possible at all
> - => need to warn users about that
> - in the general case, the server must anonymize the data (either by not 
> storing user-identifiable data or by not handing it out)
> - => the users have to trust the server

The server need never hand out data of a single upload.
To be meaningfull it even needs to be averaged for many
users.


> PS: The rest of your proposal looked OK to me (apart from using bloat 
> like SOAP, but that's a matter of taste anyway). I'd say go on and set 
> up such a server. Let's gather some experience from using it and 
> analyzing the data it collected. Before we do that, it's hard to know 
> what data is useful; kind of like crystal gazing. I dare say we'll need 
> a second version anyway, even if we try to imagine every possible usage 
> scenario now.

Okay.
I suggested soap because it is supported by many
systems, it is type-safe and trivial to check and
there is good tooling.
For a test it should be okay. Something binary or
at least smaller can still be specified later for
a final version.

Marcus


___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Crowdsourced costing - collecting traffic-events

[Marcus Wolschon]

On Wed, 3 Dec 2008 10:15:55 +0200, "Jaak Laineste" <[EMAIL PROTECTED]>
wrote:
> Hi,
> 
>  Wouldn't it be too complicated to have proper coverage? Some of the
data,
> like average speed, is also very hard easy to estimate without really
good
> experiences or specialist analysis. And average speed is most important
> data
> for fastest way calculation, it would be too easy to get garbage-in
> garbage-out situation.

This is indeed a risk.
However for the "proper coverage"-argument I can offer the gravefull
degration by having vehicle-types and times grouped and ignoring single
parameters untill a proper number of meassurements exist for an answer.
It will at all times be the best answer that can be given but seldomly
(it ever) be for the exact case that was asked for.
It can not hurt to collect these.

I think about gathering the average speed from navigation-software and
mapping-software running on a device in the driving vehicle and averaged
over a complete way until the vehicle leaves the way.
Maybe we should indeed filter out meassurements over distances that are
too short to be meaningfull. Do you agree?

>  I would suggest to have live traffic event data, collectable mostly
using
> mobile devices from the road. The events could be:
> a) road temporarily blocked. No routing over here.
> b) road speed disturbance (e.g. traffic jam). Calculate extra time for
> routing.
> c) other traffic-related events: e.g. mobile speed trap. Notify user,
> perhaps does not affect routing.

This sounds like an excellent separate service using the same meassurement.
Such data can be centrally collected and merged with data about
road-construction
-sites and published traffic-diversions/jams. Programs that can make use
of it can then either request the current state from a central server (if
they have internet at the moment) or even exchange such data among each
other in the (very seldom) case that 2 such vehicles pass within
wifi-distance.

While one could host both services on one location I don`t think
we should join them as they are usefull for different situations
(metrics can be used on a website without actually driving) and
require somewhat different data to be collected.

> With mobile data collection it should be very easy, possible to be
entered
> while driving (click "mark traffic event to current location", select
type
> from short list, OK), so any extra data (like estimated duration of
event)
> should be optional. Maybe for block duration is essential: it could be 3
> month roadworks, or just 30 minutes due to an accident.
> 
>  Technically, the "mark" event is then attached to certain road segment,
> which is found automatically from user's current GPS location.

This sounds like an excellent idea.
Do you offer to implement a prototype of it or specify a protocoll
or user-interface for it? I would really like to see such a thing happen.

Marcus

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Crowdsourced costing - offer of writing a client+metric for it

[Marcus Wolschon]

On Wed, 3 Dec 2008 00:27:46 -0800 (PST), j2megps <[EMAIL PROTECTED]> wrote:
> Hi Marcus,
> 
> I refer to your previous post:
> <<<
> I suggest a service that collects the following data:
> 
> collection:
> * vehicly-category (car,bike,foot,ship,other)
> * vehicle-type (String, freely chosen with some presets)
> ** vehicly-subtype (flow, normal, fast)
> ** used metric (String, freely chosen, presets: fastest, shortest,
> efficient, scenic, mapping)
> * average speed in km/h
> * way-ID, startNode, endNode
> * day = (weekday,weekend,holiday)
> * time = (night,morning,afternoon)
> ** sub-time = (early,mid,late)
> 
> example: car-fast, 123-456 on way 789 with 78km/h at early morning 

> 
> When I read your post, I just wonder how you store those information
above
> into current data model (node/way/relation)?

Hello,

I did not propose to store it in the current datamodel that is
used for the map at all. However this is a good question.
I suggested a separate database and that implies a separate
datamodel for this one service only.

I am not sure what the best design for such a datamodel would
look like. I guess some averages need to be cached and the
values for the highway-tag of submitted wayIDs be fetched from
the osm-database on collection and stored.
You could then have 2 indice by highway-type and by wayID.
Selecting all meassurements for a wayID should not take too long
but if it does a combined index on wayID and the property that
shows to be the best to separate meassurements that are required
to give an answer and the ones that are not (e.g. by "vehicly-category")
can speed things up.

Such things are the experience you can gather by writing a prototype
and then trying to actually use it.

Marcus

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Crowdsourced costing - Routing-Nodes

[Marcus Wolschon]

On Tue, 2 Dec 2008 23:51:37 -0800 (PST), j2megps <[EMAIL PROTECTED]> wrote:
> After reading this crowdsourced costing email, I assume that OSM
community
> is
> now start to work on collect routing information?
> 
> But before we start to collect routing information, do we have any new
data
> model to store routing node information? or we just use existing OSM data
> model (node/way/relation) and add more tags to the way element?
> 
> If you are planning to add new data model (node/way/relation/routing
node)
> to store routing node information, can we reconsider my idea about adding
> routing node element into OSM database that I posted long time ago?
> http://wiki.openstreetmap.org/wiki/Routing_with_osm_data

Hello there,

the last state of the discussion on that was that
we on the list could not agree on the nessecity of routing-nodes
at all and on what vehicle-types to consider for this.
As far as I remember it was still left to the application
to have or have not a simplified graph of routing-nodes
selected to it`s own vehicles needs from the OSM-data.

Thus we only have way-ids and node-ids to refer to our map
in such a service and no routing-node-relation-id.

(I still am not convinced that having such a thing is
 a good idea for everyone but you. But you are free to
 add whatever relation you like to the map and use it
 yourself.
 The voting on the page you mentioned has not a single
 PRO-vote but a lot of CONs. Thus I see it as "declined".)

Let`s use another topic or even better the talk-page
on your wiki-page to discuss this. It seems to have no
immediate relevance to crownsourced metrics.

Regards,
Marcus

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Crowdsourced costing - offer of writing a client+metric for it

[Marcus Wolschon]

Hello,

I suggest a service that collects the following data:

collection:
* vehicly-category (car,bike,foot,ship,other)
* vehicle-type (String, freely chosen with some presets)
** vehicly-subtype (flow, normal, fast)
** used metric (String, freely chosen, presets: fastest, shortest,
efficient, scenic, mapping)
* average speed in km/h
* way-ID, startNode, endNode
* day = (weekday,weekend,holiday)
* time = (night,morning,afternoon)
** sub-time = (early,mid,late)

example: car-fast, 123-456 on way 789 with 78km/h at early morning

privacy: 
* the user-application is supposed to care about not sending
  information about a user-chosen radius around the start and end of a
route
* we do not receive exact times or dates because there is no need to care
  about them anyway
* we do not receive user-identifications at all
* the IP and upload-time are stored to revert manually detected vandalism

retrieval:
* the service can be asked with the same query-parameters that collection
has
* if a significant number of exact matches exist, they are returned
* if not it uses data for other streets of this highway-value, other
vehicly-types,...
  and multiplies the difference 
  e.g. (average for noon everywhere)/(average of all times everywhere) as
an offset
  to give better estimates where it has no exact data.

This can be hosted as a web-service with SOAP and a WSDL to be usable for
pretty much all programming-languages and platforms. The data would not be
stored in the OSM-database at all but in a separate database.

A prototype can be written e.g. in google-app-engine to gather
real-world-experience
with this kind of service.
I am offering to implement a well documented client and a metric for such a
service as a plugin into my own navigation-software Traveling Salesman as a
testbed and reference-implementation.

I am currently busy debugging my osmbin indexed, mutable, binary
file-format for
osm-data. So I do not know if I can find the time to write such a service
myself
in the next weeks but I sure would like to. 

Marcus


On Tue, 2 Dec 2008 23:37:12 +0200, "Nic Roets" <[EMAIL PROTECTED]> wrote:
> Of the 3 ideas I'm most inclined to agree with Frederik. From the
> discussions on talk regarding smoothness and the slowdown in user edits,
> it's clear that the community is willing to fine tune all supported
routing
> tags, provided it's easy and (nearly) interactive:
> * 1 numeric parameter per way for each vehicle type.
> * Allow hundreds of vehicle types. Anything from a courier delivering
> documents to a tourist on a mountain bike taking the scenic route. Anyone
> who disagrees with your (subjective) tagging, should just add their own
> vehicle type.

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Default speed limits / built-up areas (was: Re: generalized routing format - pre-computation)

[Marcus Wolschon]

On Tue, 21 Oct 2008 14:18:17 +0200, "Nic Roets" <[EMAIL PROTECTED]> wrote:
> On Tue, Oct 21, 2008 at 1:43 PM, Marcus Wolschon
> <[EMAIL PROTECTED]>wrote:
> 
>> You don't set maxspeed-values for default-values.
>> There have been lengthy discussions about that and
>> this is what was agreed on.
> 
> 
> The only thing that OSM agrees on is that "discussion", "agreed on" and
> "approved by voting" does not really matter.
> 
> What matters is what's in the planet and what the software (currently in
> use) implements.

Well, whatever.
If you write your software in a way, that it
does not differentiate between in-city and outside-city
then your assumed speeds and thus ETA-times and often
enough even the routes will be wrong.

Marcus

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] Default speed limits / built-up areas (was: Re: generalized routing format - pre-computation)

[Marcus Wolschon]

On Tue, 21 Oct 2008 13:28:38 +0200, "Nic Roets" <[EMAIL PROTECTED]> wrote:
> On Tue, Oct 21, 2008 at 11:52 AM, Sascha Silbe <
> [EMAIL PROTECTED]> wrote:
> 
>> On Mon, Oct 20, 2008 at 10:31:35PM +0200, Nic Roets wrote:
>>
>>  During rebuild, gosmore only mmaps the wayType data which is roughly
>>  1GB.
>>> During one stage, it iterates through the node data and update the
>>> wayTypes
>>> they point to so that bounding boxes can be computed.
>>>
>> OK, so you don't index by location currently (since that would need
>> bounding boxes)? How does your geocoder work? I.e. how does it find a
>> given
>> street inside a given town?
>>
> 
> You type the name of the town, click to center, then type the name of the
> street. The nearest occurrence will be the first result, so clicking on
it
> will take you there.
> 
> Implementation : Each wayType has a center point and zero or more "tag
> values", for example the name. There's an alphabetical index of the names
> as
> well as a complicated algorithm for handling the case where two tag
values
> are equal by finding the nearest occurrence.
> 
> 
>>
>> Each time you enter a town (or village or whatever), there's a yellow
>> sign
>> (StVO sign number 310 [1]). Exactly at the location of these signs the
>> defaults change from 100km/h to 50km/h (for cars). This is regulated by
>> law
>> (Straßenverkehrsordnung (StVO) § 3 (3) [2])
>> The area delimited by these signs is called "Geschlossene Ortschaft"
[3],
>> roughly translated it would be "closed (=delimited) place (village)".
>>
> 
> Then the way should be split where these signs occur and the max_speed
tags
> set explicitly.

You don't set maxspeed-values for default-values.
There have been lengthy discussions about that and
this is what was agreed on.
You have default-values documented in the wiki in
a machine-readable format for each country. It 
depends on the type of vehicle, the value of the
highway-tag and the fact that you are inside or
outside a closed city.

Marcus

> The US makes up more than half of our "planet". If you consider that the
US
> population more than doubled during the 20th century, you realize that
the
> majority of US town planning took place after the invention of the
> motorcar.

The US is an outdated piece of imported data that very, very slowly
gets corrected by way too few people.
If you want growth done by mappers, look at asia or europe.
It is not representative for how things need to be done to correctly
reflect
all situations everywhere in the world.

> This means you often get stretches of highway / motorway inside cities
with
> large shoulders, embankments and railings so that it's safe to drive
there
> at high speed.

Well, these seem to be single roads that get their own maxspeed-tag anyway.
Do you have no general speed-limit on all roads inside the town this is in?
If a single driveway has no maxspeed-tag, am I allowed to drive there as
fast
as I can?

Marcus

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] generalized routing format - pre-computation

[Marcus Wolschon]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

Nic Roets schrieb:
> During rebuild, gosmore only mmaps the wayType data which is
> roughly 1GB. During one stage, it iterates through the node data
> and update the wayTypes they point to so that bounding boxes can be
> computed.
>
> Nothing stops you from adding code to that stage that will test if
> each node falls inside a polygon (e.g. place) and then modify that
> way.
>
> I don't believe that writing software for adjusting speeds for
> built-up places is worth all the effort. Reasons : * Place
> boundaries can't be surveyed by OSM members. Can only be guessed
> from aerial photos or imported from other sources.
On every road (that's the points where it matters) there is a sign
when you enter or leave a town.
> * Applies to few countries.
There are countries without different general speed-limits inside and
outside towns?
> * This extra info will seldom make a substantial difference in the
> route proposed by the routing system, because all the roads will
> typically go through the built up place.
Very often I see rings of roads around a town, to divert traffic.
Such a road being a primary-road  is longer then the primary-road through
the town but it is faster since you are allowed to drive at 2x the speed
and get 3-4x the actual speed since there are no traffic-lights at all.

I guess this makes for a very high difference in a significant number
of cases.

Also think not only of the routing itself but the projected ETA. If
will be horribly wrong
without differentiating between roads in cities and outside.

Marcus
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAkj87owACgkQf1hPnk3Z0cT83gCg3HKXeml+DZ/w7yWBKWVSSAaC
QosAniOyPhzCw42GSeyuJxxchIYw9xIx
=DaE6
-END PGP SIGNATURE-


___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] generalized routing format - comments on degree 2

[Marcus Wolschon]

On Mon, 20 Oct 2008 06:18:46 -0700, "Tristram Gräbener"
<[EMAIL PROTECTED]> wrote:
> Well, thus the conclusion of this thread is that there is no way to make
> some kind of universal routing database ?

Maybe not a database but there is a good chance for a universal
binary format. If it is capable of storing all we know, it will
still be capable of storing what a single developer needs after
throwing out everything else.
I think that we could use an indexed format to store things
like forests and unreduced ways (even if "only" for painting
the result) but allow for custom data to be stored alongside.

Think of allowing to store a custom attribut with each node
that contains a next node reachable by car, the pre-computed
length of the way to that node and the id of the way to use
(to compute other metrics).
This gives you your G(N, A)-graph with full indexing but still
stores everything you need for the metrices and everything an
application written by someone else needs to visualise your
route or generate driving-instructions from it.
These applications will ignore your custom attributes but
still no data needs to be dublicated on disk and the data
for your routing and other people's map-paiting, driving-instructions
or roadwork/traffic-jam -updates have the exactly same version
of the local database you have because it's the same file.


Marcus

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] generalized routing format - comments on degree 2

[Marcus Wolschon]

On Mon, 20 Oct 2008 05:28:02 -0700, "Tristram Gräbener"
<[EMAIL PROTECTED]> wrote:
> Hello,
> 
> After some thoughts, I think that what I would need, is only the
> current xml files, where there is a constraint that each way may be
> only made of nodes of degree 2 (except  at start and end). Of course I
> guess that there is no way to change the API ;)
> 
> Wouldn't be it easy to make that as the exchange format, e.g. by
> adding a Link property made of nodes ? Of course this would break the
> normal form as it would be redundant to ways.

I think the issue is a bit more complicated then this.
* Not all ways are roads. You can have nodes that are of a
  degree > 2 only because they are also used by a passing
  river or similar.
* Before reducing roads to links between intersections you need
  to compute your metrics. You loose all information about the
  length and path of the road.
* This really means _your_ metrics. Others may want to add a penalty
  for curvy mountian-roads in addition to their length+highway-class
  or they may compute for a truck instead of a sports-car.

Thus you can do some routing on a graph reduced as proposed
by you but you will not be able to compute the shortest, nor
the fastest route as you will have lost that information in
the export.

> A universal binary format with some API would be nice for people that
> want to play with graph algorithms (like students) but I personnaly
> have no use for that (yet).

Well, you don't have to.
I have no need for many other features, so
I let them be and don't care about them.
> 

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] generalized routing format - pre-computation

[Marcus Wolschon]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

Sascha Silbe schrieb:
>> Do you have a better algorithm to "complete" the incomplete data we
>> get
>> from the mappers on city-limits?
> Unfortunately not. Actually, I don't think better heuristics are
> worth it (they would probably get very expensive). Let's rather try to
> a) reach a consensus on how to tag the relevant borders (at least in
> germany, these are far from being coincident with the corresponding
> administrative borders) - how would a native speaker could this
> border [2], BTW?
Currently they don't as there is too much discussion on the difference
between the actual placement of the signs,
the  landuse-area, the administrative border and the area that has the
speed-limit associated with a city.
All of these are not the same polygon.


Marcus
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAkj3Wr0ACgkQf1hPnk3Z0cR2KACgjp32DIl71Mo/iLwlngh2uV07
23YAn03+R8qTtD7bANfqzbUHCdxAs+Pq
=mL9Z
-END PGP SIGNATURE-


___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] generalized routing format - pre-computation

[Marcus Wolschon]

On Thu, 16 Oct 2008 13:16:58 +0200, Sascha Silbe
<[EMAIL PROTECTED]> wrote:
> On Thu, Oct 16, 2008 at 12:39:53PM +0200, Marcus Wolschon wrote:
> 
>> Where do you think the most pre-computing occurs?
> For my last prototype (the current one isn't finished yet), the most 
> expensive precomputation was determining whether each way is inside or 
> outside a built-up area ("Geschlossene Ortschaft" for germans). It even 
> prevented me from using a europe dump: it didn't finish within 10 days; 
> the german one only takes a few hours. There's some room for improvement 
> (as I do it in PostGIS, I have to validate each polygon because a single 
> broken one causes the whole transaction to abort), but I still expect it 
> to be very expensive.
> Building an address hierarchy including house numbers would be quite 
> useful, too (and similarly expensive).

Yes, indeed.

How do you go about defining the polygon ofa build-up area?
I am searching if such a polygon was mapped and if not estimate
a radius from the type of town. This of cause if far from being good.
Do you have a better algorithm to "complete" the incomplete data we get
from the mappers on city-limits?

Do you have the polygons indexed by their bounding-boxes to
limit the number of polygons you have to test?
The test itself is trivial. Just counting the number of intersections
of a ray from your location with the polygon and checking if it is
even=outside or odd=inside.

Marcus

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] generalized routing format

[Marcus Wolschon]

On Thu, 16 Oct 2008 12:12:13 +0100, "Robert (Jamie) Munro"
<[EMAIL PROTECTED]> wrote:

> Personally, I don't think OSM should be trying to do this in the
> abstract. I think that as people develop routing applications, they
> should develop their own formats and converters from OSM XML format,
> optimised to how their particular applications work. As routing
> applications evolve, they could copy ideas and formats from each other.
> I don't think we should try to invent a format that is targeted at a
> particular market.

A binary-format that is indexed and directly usable can open the
door to many new tools. It is not trivial to write and not everyone
is capable of defining one. You make it sound like a trivial step
but it takes quite a bit more then a single developer can come up
with whereas writing a parser for it is very easy.
Also most formats used by existing
software are not documented, highly specific or require that one
database that this software is using.
Noone is forced to use the format we are discussing and it will
certainly not be perfect for every developer.

> It may be worth repackaging OSM XML and changesets as a binary format
> that is more compact, but routing applications would still need to index
> it before they could use it.

I don't agree here.
The existing xml-format is already great for general interchange.
Having it zipped there is no need for a new format just to make
it smaller (It will probably not get any smaller then today).

> Certianly I don't think that OSM centrally should be splitting the data
> into "routing layers".

I strongly agree. A binary-format should not loose any information
that may be usefull to an application.


Marcus

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing

Re: [Routing] generalized routing format - pre-computation

[Marcus Wolschon]

On Thu, 16 Oct 2008 12:17:31 +0200, Frederik Ramm <[EMAIL PROTECTED]>
wrote:
> Hi,
> 
>> Finding a simple, easy to understand format that can already be used
>> for routing but does not loose information yet. This can easily be
>> used as an intermediate format but tools have the ability to already
>> use it directly.
>>
>> * indexed
>> * marking or separately indexing
>> ** ways that are drivable (highway, cycleway,.. but not river, forest,
>> power-lines,..)
>> ** nodes that are of order >2 if you only consider drivable roads
>> ** marking or somehow prefering a fixed set of attributes that are  
>> most
>> important for routing
>>(e.g. "highway", "maxspeed", "name", "access")
> 
> Yes, something like that was what I had in mind. I didn't want to  
> simply set something up without input from the routing community  
> though - wanted to avoid doing someting that nobody can use in the  
> end;-)

Of cause.

Where do you think the most pre-computing occurs?
I think the indexing node->ways and the separation
of ways and nodes into the ones that are relevant for
traffic and the ones that are "scenery" as well as
normalizing street-names and adresses would be the
biggest step.

Maybe we can also do some more normalizing like
merging country-borders and cities/suburbs/.. represented
only by a single node into polygons (we could give them negativ
IDs or otherwise mark them as non-original-data).
Also things like converting maxspeed-values in mph into kph
and creating a net of oneway-roads to replacejunctions with
turn-restrictions can be pre-computed.

I guess a database-schema is no good as an intermediate format
as you cannot put that into a zip-file everyone can read.
(You would force everyone to have that one dbms installed.)

What do you think of the aproach I outlined in:
http://wiki.openstreetmap.org/index.php/User:MarcusWolschon%5Cosmbin_draft#nodes.obm

Marcus

___
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing