Technical/Design/Implementation Discussions (CHM/Travel Mapping)

[Jim]

So pay attention in your data structures class.

We never learned about quadtrees in my data structures class. Maybe next year I might.

To be honest, I rarely get to cover quadtrees when I teach data structures or even algorithms.  But this very handy example might motivate me to slip them in this fall.

[rickmastfan67]

I'm happy to report a lot more data processing progress, though none that produces any new visual results.  All colocated waypoints are now detected, which will allow me to detect concurrencies efficiently, which is, I think, the next thing on the list.  It's also what's needed to support the links to intersecting and continuing routes that are not in the draft highway browser yet.  I believe Tim used to have a tolerance to consider very nearby points colocated, but I am requiring exact coordinate matches.  If this requirement remains, it means some work to fix up some of the data, but much of that can be done automatically.  We'd just need a manual check to make sure no points are merged which were kept separate intentionally.

Jim, I think we still need to have the offset of .000001 for the linking to other routes.  It was needed to keep false multiplexes from being detected.  I know that FL-84 & I-75/I-595 are completely separate for a good distance, but need the offset since they almost always intersect the same highways since FL-84 is the service road(s).
http://cmap.m-plex.com/hb/hwymap.php?sys=usafl&rg=all&gr=p&r=fl.fl084

[yakra]

I believe Tim used to have a tolerance to consider very nearby points colocated, but I am requiring exact coordinate matches.  If this requirement remains, it means some work to fix up some of the data, but much of that can be done automatically.  We'd just need a manual check to make sure no points are merged which were kept separate intentionally.

I think Tim's method is the way to go. An exact match was required for a concurrency, while very nearby points meant a simple junction. It comes down to the intentionally-separate points.
Consider TX US183 TX21 (30.027758°, -97.687909°) & TX TX130 461 (30.027758°, -97.687908°). These need to be separate to avoid flagging a concurrency here, as US183 runs along TX130's frontage roads.
But if an exact coordinate match is required, then the point on TX21 will not be detected as a junction with both routes.

[Bickendan]

AP-7 and B-30 in Barcelona, ON 401's express and local lanes (if we were to track the two as opposed to one route).

[Jim]

I don't mean those points where we intentionally separate points to avoid a false concurrency should be aligned.  I'm talking about those places where a road crosses a state border or where two normal highways intersect in some standard way - the points should be exactly the same.  Maybe I'm missing something more subtle here.

[english si]

Jim - make Near Miss Points an error or something.

There needs to be some leeway for intersecting to deal with local-express setups and similar. Concurrencies are (obviously) exact matches.

Tim's old system worked, other than it didn't tell us where NMPs were.

[Bickendan]

How many local-express delineations do we have to deal with in this? While it'd be nice to account for them all, I think the only 'valid' one for our purposes is AP-7/B-30 in Barcelona because of the different route numbers (AP-7 express, B-30 local).

[english si]

RA1-A14 in Italy. There's lots more that possibly might be added.

Many, many, smaller versions exist, for 2 or 3 junctions.

[yakra]

I-91 / CT15
US183 / TX130
A couplefew more TX examples where a state highway is on the frontage roads of a toll road
Maybe I-88/355, I dunno man I didn't do it

I don't mean those points where we intentionally separate points to avoid a false concurrency should be aligned.  I'm talking about those places where a road crosses a state border or where two normal highways intersect in some standard way - the points should be exactly the same.  Maybe I'm missing something more subtle here.

I think you may be. In my example upthread, TX21 and TX130 are normal highways intersecting in a standard way.
TX TX130 461: (30.027758°, -97.687908°)
TX TX21 US183/130: (30.027758°, -97.687909°)

[Duke87]

US 219 and I-90
I-790/NY 49 and I-90
NY 27 and BeltPkwy

[ntallyn]

Maybe I-88/355, I dunno man I didn't do it

Those are on two separate roadbeds. And there's no interchanges during that parallel section, anyway.

[Jim]

I think you may be. In my example upthread, TX21 and TX130 are normal highways intersecting in a standard way.
TX TX130 461: (30.027758°, -97.687908°)
TX TX21 US183/130: (30.027758°, -97.687909°)

So for this one, and others like it, we're trying to avoid introducing a false concurrency between TX 130 and US 183, correct?  Would it be bad to introduce a slightly-moved hidden waypoint between the interchanges?   I assume in many cases, the route on the outer roadway has additional intersections anyway.

Mainly, what I want to suggest is that if there's no good reason to have to have points off by a small amount, we should have them in the exact same point.  Cases are everywhere, but one that I see is OH 518/OH 644.  No reason that I can tell for those to be in different places.

The data used is a bit out of date, but you can see the "near miss" points detected when I turned CHM data into graph form a while back at http://courses.teresco.org/chm/graphs.html in the .nmp links in the rightmost column.

[english si]

Mainly, what I want to suggest is that if there's no good reason to have to have points off by a small amount, we should have them in the exact same point.

The only reasons to make intersecting points exactly identical are:
1) anal retentiveness
2) making sure there's a concurrency
3) making it easier to make files by starting with points that intersect that route

The first is literally "no good reason", though the second is (but only applies to specific bits). The third is a time saver (negated by the hassle of keeping points identical - if you move one point to be more accurate because it was slightly off, then you have to do the same in every other route that meets there).

NMP is not a true error (unless a concurrency that should be isn't registered) that causes issues with end users and statistics and so on. But sure, it's a falling short from perfection and ought to be flagged as a potential error.

And certainly, while you have a script for it, I don't want files merged to the average location of the point. All the GB ones come from when, either through peer review or update, I've got a more pinpointed location, and simply not done it on other routes. Averaging out would take a 0m wrong point and a 10m wrong point and make 2x 5m wrong points. If I sort out those NMPs, it will be manually and with the priority of the snipe hunt that it is.

[Jim]

The only reasons to make intersecting points exactly identical are

My own reason is that I use the data for academic projects by converting to a graph structure.  It's how I justify at least some of the time I put into the project.  I have to merge those points to be able to get a lot of the algorithms (like Dijkstra's shortest paths) to produce expected results, but then I sometimes end up merging points that were left separate intentionally.  Re-creating/updating graphs as highway data evolves becomes simpler and more accurate if I'm confident that any points that were not exactly the same are that way on purpose.  So, bottom line, I have a reason, but not one that anyone else will care about.

[yakra]

yakra already wrote a parser that can take all that and put it into a map.  The next logical step would be to decide how the database would look and modify the parser (and map? or do that later?) to put the contents in the database.

Hope we can get that code into the repository to use or at least refer to.

It's over here: http://205.209.84.174/roads/chm/canvas/

This is good.  If there are no objections from the authors, I'd like to get that into our repository as reference code.

Firstly, a slightly more up-to-date revision of the code:
http://205.209.84.174/roads/chm/canvas/canvas.cpp

No objections, though a few BEWARE!s.

This was only ever really intended to run on my (Linux) system, with my data. Which it does.
Others have had problems. The CSV reading routines don't account for UNIX vs DOS style line feeds. So, if you feed it a file with DOS line feeds, or try to compile and run it in Windows, shit will explode. Sorry about that.

Also, it's not designed to handle a viewport that straddles the 180th meridian. Which may never end up being an issue in practice, but... nota bene.

It reads all the routes from "routes.csv". (Allowing multiple CSVs to be specified on the commandline has been on my to-do list, but a low priority. It works as it is, without too much additional hassle.)
The .list file must be named "list.list".

So, it's a bit rough around the edges. But gets the job done. Really, I view the important part as, not this C++ program (everything will have to be rewritten for the web, in a different language, anyway), but the Javascript that it spits out. Again, far from perfect, but a working proof of concept.

I envision implementing multiplex detection eventually, because:
1.) even if everything is marked as unclinched, plotting, say,  US202 on top of ME100 on top of ME17 on top of ME11 makes the line noticeably darker/bolder. Yecch.
2.) drawing stuff in the right color. Example: Only ME15 is marked as clinched, and as a result doesn't get the dark blue Interstate color.
This would require that things be done quite differently from how they are now. That's a bigger discussion for another time.

Another interesting/worthwhile side discussion is how to cull line segments that fall outside the viewport, in order to keep down both the size of the JavaScript code, and CPU time needed to crunch it.
My program doesn't do any sort of culling. Tim's centermap.php does. Can you spot the difference?

Lastly, a link to what I consider the canonical example of the program's output.

[yakra]

Texas, complete with state highways, loops and spurs
http://205.209.84.174/roads/chm/canvas/stuff/tx-final.htm
A bit more boring however in that nothing is marked as clinched.

[Jim]

[Firstly, a slightly more up-to-date revision of the code:
http://205.209.84.174/roads/chm/canvas/canvas.cpp

No objections, though a few BEWARE!s.

It's definitely got a ton of useful stuff there, even though I doubt we'll be able to use any C++.  I am confident we can get PHP to output the same kind of Javascript, but getting its data from the database I'm building, and its bounds from a web page (I hope) someone will develop that will pick regions, cities, etc.

[oscar]

I've grabbed a bunch of the .list files from some of those who contacted me to be a part of testing.  My program generates log files along the lines of those on the old CHM site, but with what I hope is some additional useful information.  For example, I report a note when an old route name is in the .list and I'm instead using the new canonical name.

My spot check of the logs have led to several improvements (better handling of empty lines, lines with extraneous whitespace, etc).  I am posting all of the logs from a recent run at

http://www.teresco.org/~terescoj/travelmapping/logs/

If you see anything unexpected there or have any other questions or suggestions, let me know.

Many South Dakota state routes seem not to have made it to the new database, unless that was taken care of after the log was generated.

Most of the other errors in my log are expected, from new routes or route extensions after CHM's data freeze, or in anticipation of the new NM and UT state route sets. Some are puzzling at first glance, but I'll dig deeper once I'm back home, and make any necessary fixes before I submit a new list file.

[Jim]

Many South Dakota state routes seem not to have made it to the new database, unless that was taken care of after the log was generated.

Turns out usasd was omitted unintentionally.  It's in now, and next update will take care of it.

Thanks.

[Highway63]

I have some changes that were to be done in SD, the notes sitting sitting on my desktop. I didn't do them yet.

[sammi]

Jim, would you mind if I got access to your database? I'm developing a web frontend and was hoping to use the data on your site.

[Jim]

Jim, would you mind if I got access to your database? I'm developing a web frontend and was hoping to use the data on your site.

Of course.  At this point, since I'm occasionally breaking things, it's probably best to have your own private copy.  Several ways we could go with this.  I'll send a private message so we can discuss specifics.

[sammi]

I've been working yesterday and today to rewrite Jim's data processing code. In particular, I want to know what we're doing with the .wpt file format. I've written some parsing code for a possible new format already, but I'm not quite sure where that format stands.

I also noticed a discrepancy between Jim's log output and mine. A rather large one, too. So I'm actually not sure if my code is doing the right things...

    Log file created at: 2015-06-18 22:24:11.973266
    Waypoint label(s) not found in line: ON ON10 ValRd RR12
    Processed 44 good lines marking 1021 segments traveled.

vs (after changing ValRd to ValBlvd)

    Processed 45 good lines marking 868 segments traveled.

[SSOWorld]

Couple things to think about:
1) is the update intended to be one entire database dump?  If that's the case, you'll be spending a while doing something else while your ssh finishes its job.
2) Those using python - are your versions similar or the same?  I use an older version of linux due to supporting older software and am forced to use one earlier than the one Jim uses.  It made a big deal b/c the flush function for strings does not exist in mine.

[Jim]

Couple things to think about:
1) is the update intended to be one entire database dump?  If that's the case, you'll be spending a while doing something else while your ssh finishes its job.
2) Those using python - are your versions similar or the same?  I use an older version of linux due to supporting older software and am forced to use one earlier than the one Jim uses.  It made a big deal b/c the flush function for strings does not exist in mine.

The differences between Python 2.x and Python 3.x are significant.  I'm using Python 3, and it's not a good idea to try to back port it, most likely.  However, Python 3 has been around a long time now, and I'd be surprised if any Linux still worth running doesn't have it.  Typically, it's installed to run as "python3" from the command line.