Thinking about my time commitments I think it's so bad that if a CD showed up as a bribe I wouldn't even have time to work on parsing the format. Sigh.

For the convenient use of the gps application I'd be glad to have complete map data CD's on the hard disc to recalculate routes automatically in case of traffic jams and the like - in Germany we already receive traffic information electronically - and to define routes without internet access.

So the question would be which CD's to use. They should be available for different countries and need to be up to date (updated periodically!). That's what I don't see for any free map data as updating is hell a lot of work to do and needs to be financed. In any case we will have to pay for useable map data! So only commercial products remain suitable - but they should at least follow open specifications.

GDF is in fact not a proprietary format but an open specifiaction used not only by Teleatlas (see http://www.ertico.com/links/gdf/gdf.htm). Teleatlas is just a commercial provider of map data according to the open GDF specification - and in my view the best provider in the world today. The GDF format is used by almost all of the commercial navigation systems and is already installed in thousands and millions of cars. So map data updates for the long future are guaranteed and the map data format is not likely to change (as already installed systems need updates in the actual format).

So I see no real alternative for GDF is we want to have useable map data.

Juergen

(BTW: I'm not paid by Teleatlas)

Name a single open source application that already uses GDF. Any one, I don't care. I'm actually curious to see how it works, and like the last 20 messages said, I don't have time to write a parser for it myself.

(BTW: I'm not paid by Teleatlas)
I believe you.

It just looks like a lot of "cart before horse" from here, and I don't mean you particularly, either, so please don't consider this a personal attack; I don't mean it that way.

O.K., I understand your point.

So our task is to find either open soure parts for parsing GDF files or a translator form GDF to GIS-T or.

Anybody out there with an idea?

BTW: Some interesting information on map file formats and the like: http://www.nas.edu/trb/publications/nchrp/nchrp_rpt_460.pdf (see also attachement)

Actually, if you can get any sufficient format that OGR (http://gdal.velocet.ca/) already speaks, getting it into any other format is simple.

However it looks like OGR will only *create* shapefile, "Mapinfo" file ("tab" files) and some database-backed formats.

Interestingly it appears teleatlas already distributes some data in mapinfo tab form.

Also, there's a free MapInfo tab and .MIF/.MID library here:
http://pages.infinit.net/danmo/e00/index-mitab.html

This link contains information about TeleAtlas Multinet.
http://www.teleatlas.com/frames.jsp?page=gis_main.htm

Here's a quote from that url:
"MultiNet is available in GDF-AS (GDF-ASCII-Sequential), GDF-AR (GDF-ASCII-Relational) and ShapeFile Format."

So we have TeleAtlas Data in the shapefile format. The Multinet CDs are released twice a year.

Here's at least a commercial program that reads/writes _many_ formats, including GDF and Shapefile (See link... an overview of the formats)
http://www.safe.com/products/fme/formats/index.php

But it's quite expensive. The GDF reader plugin alone is about 4000 USD

Or this one http://www.manifold.net/products/mfd50pro/mfd50pro_home.html
Includes GDF import
much cheaper... 245 USD

Information from the Teleatlas MultiNet broschure:

Tele Atlas MultiNet™ shapefile format offers the complete, high-end Tele Atlas
database contents structured according to a ready-to-use layered data model
and in a standard GIS format. As such, the Tele Atlas flagship product MultiNet
is available in a run-time data exchange format that is easy to implement into
any GIS-based application.
MultiNet shapefile offers the greatest coverage area, completeness, accuracy,
and most recent data, compliant to the highest demands of turn-by-turn
navigation applications and offers optimum geocoding match rates. Shapefile
is designed for direct use with standard GIS software and tools and is
optimized for fast and superior cartographic display, accurate geocoding and
rapid optimal route calculation.
MultiNet is available in shapefile format for Western Europe and the United
States.
Shapefile format was created at ESRI®, Environmental Systems Research
Institute, Inc. (http://www.esri.com).

(see attached)

I'm pretty much ignoring all of these discussions about various applications and map formats.

Many of the links that are repeated over and over are raster/bitmap based 'map scrollers', which boils down to a georeferenced image that is moved along depending on your location. i.e. it won't tell you how many miles to the next turn and what the name of the street is. They typically depend on having a lot of colors and higher resolution to avoid screen clutter, it is probably possible to get something like that to work, and possibly a lot simpler even than the current gpsapp, but I don't find it interesting.

Then I really love those, look at this link, maybe gpsapp could use some of their code. But when I go there there is a trivial 'block diagram', and an overly bloated user interface specification that shows that someone doesn't know that all GPS receivers can/will use the WGS84 datum, and that simple SysV ipc system calls do not become 'clearer' by wrapping them like DoReceiveQueuedMessage(foo, bar) { ipc_rcv(foo, bar); }. However there is no code.

And finally, any open specification format (GDF/Shapefile) does _intentionally_ only document the interchange part of the dataset. The important part for routing and mapping applications are the spatial indexes. There is surprisingly little information in this area documented, and most of it is guarded closely by patents.

I've mostly been looking at using a geo-hash in a simple flat database, or a 2 dimensional quadtree index. Converting from whatever to whatever is trivial compared to having to efficiently find routes across a continent when you have every single road in your dataset. It takes my desktop a considerable time and a lot of memory to find the 'optimal' route between 2 points in a single city. Of course I don't know much about routing, but I'm sure that some heuristics can give an almost optimal route in hardly any time at all. I still do have to 'reinvent' those heuristics.

So really I don't care about gdf, shapefile, teleatlas, or whatever else there is, they are 'exchange formats', and not readily useful for actual use. Sorry for blowing up there for a second, but it is really ridiculous, I see the same links pop up in different threads and nothing useful or even realistic is added. The difficulty is not reading the data off the disk in whatever format it is stored. It is how to read only the data that we're really interested in and what to do with once we have it in memory.

Sorry for getting on you nerves. 0:-)
To speak for myself, I'm not a programmer, but I try to do what's in my power to help you to get real-time navigation working with gpsapp. If I can support you by sending money, I will do so (but keep in mind, I'm still a high school student ;-)
At least I post what I think might be usefull. Sorry again.

I thought the problem is to interface the data and the pathfinding algorithm is relatively trivial. I don't understand that a TeleAtlas CD suffices for a car navigation system and we can't use the information on that CD. Also I don't understand why a car navigation system can do the route finding in a few seconds and we can't? Do they use better CPU as the StrongArm?

I thought the problem is to interface the data and the pathfinding algorithm is relatively trivial. I don't understand that a TeleAtlas CD suffices for a car navigation system and we can't use the information on that CD. Also I don't understand why a car navigation system can do the route finding in a few seconds and we can't? Do they use better CPU as the StrongArm?

Finding a path is relatively trivial, I got that working in about an hour. But doing it quickly is more difficult. For instance we could optimize the path finding algorithm by only considering roads that are going towards our final target (or at least bring us closer to it). However this way we won't see that if we drive in the wrong direction for 2 blocks that there is a much faster highway to get us there. If we keep track of every possiblity we've evaluated it is trivial to find shortcuts that we happen to have seen before or avoid going down the same street that leads to a dead-end when backtracking. But we don't have memory to remember all possible paths we looked at previously.

Same way with accessing the dataset. Of course we can read through the whole file and draw whatever street happens to fall within the boundaries of the display (or area that we are looking at during routing). That would mean reading several MB (or even GB) for each screen redraw.

For instance, I've been playing with the Tiger/Line dataset for Pennsylvania. There are 9160094 line segments (not all of these are actually streets). So having an index to quickly find the 50-100 segments around my current location is very important, otherwise I have to check every line to see if it happens to intersect with the currently displayed area. All the magic to do this efficiently is in the spatial indexes, which is why those are such a closely guarded secret.

They also might be using a CPU that is more efficient at floating point calculations and doesn't run a software mp3 decoder and visualizations at the same time, but the strongarm should be good enough.

Why are spatial indexes a guarded secret? I thought it is a common technique to speed up database queries in general?
/me hoping not to get on your nerves to much....

Finding a path is relatively trivial, I got that working in about an hour. But doing it quickly is more difficult.

I've been looking for research papers on the subject, but thus far hadn't found anything of interest.

Honestly, I don't really care to see pathfinding implemented right on the car player. Although it would be neat to see implemented, I wouldn't tend to use it very much.

I'd rather use someone else's carefully engineered (and commercial-quality) mega-reliable pathfinding engine, and download *that* path to the player.

In fact, I think the MapsOnUs solution is the best possible "basic architecture" for my needs. It does exactly what I want it to do... If only MapsOnUs didn't suck so bad...

I like the idea of intercepting the Garmin download and converting it into GPSapp file-format. That sounds like it would be about the same (architecturally) as the MapsOnUs solution, but with better mapping data and better pathfinding.

For instance, I've been playing with the Tiger/Line dataset for Pennsylvania. There are 9160094 line segments (not all of these are actually streets). So having an index to quickly find the 50-100 segments around my current location is very important, otherwise I have to check every line to see if it happens to intersect with the currently displayed area.

That sounds like a typical programming competition task... the kind where I read the winners notes hoping to learn something, but they're all over my head

In reply to:

---

Honestly, I don't really care to see pathfinding implemented right on the car player

---

I have to agree with you, I used gpsapp on a trip to NC from VA on wednesday, I think it's an awesome solution, probably the best possible way to do it with the limited display capabilities. The trip was only 315 miles yet maps on us tells me its 625? Yeah MapsOnUs is terrible I wish big brother would implement raw data with streets and trips... I used streets and trips on a laptop during the summer on a road trip from CA to VA and the street info and gps implentation was dead on...

Granted I'd love my empeg to have a 5inch touchscreen lcd display with an onscreen keyboard for typing info easily, but I don't see that happenin any time soon

Honestly, I don't really care to see pathfinding implemented right on the car player

have to agree with you

Don't implement it, and don't use it, then.

Don't get me wrong it'd be cool, I just want data that doesn't suck... I'd be 200% happy with the app, it's cool like it is now, but not 100% dependable.

Don't know if I fully understood all issues right.

My imagination would be that:
- you set the desitination manually
- get the actual position from GPS
- calculate the best route from here to destination (which is a rather and probably the most complicated task)
- transmit this route to gpsapp (prob. as shapefile)
- best case but not essential: gpsapp draws the map around the actual position (but arm could be overloaded)
- follow the route with gpsapp
- if you leave the route gpsapp gives the user a notification
- calculate a new route with the actual GPS position as start point (manually or automatically triggered)
- restart gpsapp with the new route

So the critical tasks would be to read map disc data, calculate routes and generate a input file for gpsapp.

This is in fact not as comfortable as a commercial navigation system but at least suitable for frequent drivers.

Juergen

That brings up an interesting idea.

I was thinking about the problem of determining which roads might be drawn on screen without having to going through all of them every frame. I came to the conclusion that it's over my head

But what if a desktop PC computed the route and when it sent it to GPSapp, it also sent along a list of all the roads within a given radius along the current trip's path. It could even build an index as to which ones branch off the current path.

That might make it easy enough for GPSapp to show surrounding roads when drawing the current path.

hey jaharkes, here's another link
concerning the route calculation algorithm:
http://sourceforge.net/projects/routeplanner