Re: [talk-au] How to map out streets the most efficently
On 16/06/2009, at 1:08 AM, Delta Foxtrot wrote: Now does anyone have suggestions on how to basically drive the entire town the most efficiently with the minimal amount of overlap, or how does one plan such a feat. There's a nice mathematical algorithm for figuring out that. All you need for it is a complete map of the area ;) -- James ___ Talk-au mailing list Talk-au@openstreetmap.org http://lists.openstreetmap.org/listinfo/talk-au
Re: [talk-au] How to map out streets the most efficently
On 16/06/2009, at 1:52 PM, Liz wrote: On Tue, 16 Jun 2009, Delta Foxtrot wrote: Most likely I'll be returning via a different direction, I don't particularlly like going out west, there is whole lots of nothing inbetween a few somethings. OSM makes you look for somethings out there between the nothings. Sometimes it does that a bit too much. Since I started mapping, every time I drive somewhere that's a reasonable distance away I keep thinking to myself Mark, bridge over XYZ creek., Mark, four-way junction with ABC road. I should probably buy an audio recorder, and think aloud instead. -- James ___ Talk-au mailing list Talk-au@openstreetmap.org http://lists.openstreetmap.org/listinfo/talk-au
Re: [talk-au] How to map out streets the most efficently
--- On Wed, 17/6/09, Liz ed...@billiau.net wrote: It's a problem given to all computer science students to solve: the travelling salesman. The more points to cover, the more processing power it uses which makes the way the human brain can solve those problems really cool. The difference between people and computers, computers brute force, although they can at times improve search times by getting more efficent search algorithms. However on the other hand humans tend to cheat, in some respect, while we can't usually crunch numbers in the same brute force manner as computers, we tend to pattern match really well, it helped during evolution if we could efficiently match friends or foes, dangers or harmless things quickly. This is why we usually don't remember names as well as faces, it's just the way our brains have evolved to help us survive in the past. ___ Talk-au mailing list Talk-au@openstreetmap.org http://lists.openstreetmap.org/listinfo/talk-au
Re: [talk-au] How to map out streets the most efficently
On Wed, 2009-06-17 at 19:27 +1000, Liz wrote: On Wed, 17 Jun 2009, James Livingston wrote: There's a nice mathematical algorithm for figuring out that. It's a problem given to all computer science students to solve: the travelling salesman. The more points to cover, the more processing power it uses which makes the way the human brain can solve those problems really cool. (sorry, I didn't get my comp sci degree for nothing :)) Actually, this is the Chinese Postman Problem, which is closer to the problem of finding a Eulerian path, which is actually very possible - even without knowing the map before hand (with a few assumptions). The travelling salesman problem tries to find a short path between lots of places, but it doesn't make any attempt to cover every street, so it will miss out on lots of roads. Exciting computer science ahead. Read on if bored (you've been warned): A Eulerian path is a path that goes down every road exactly once, which is exactly what you want. Unfortunately, it is only possible to do when there are 0 or 2 intersections with an odd number of roads leading into them (a dead end counts as an intersection too). And, if there is a pair of intersections with an odd number of roads, then we need to start on one of them (and we'll finish at the other). And yes, you also need to have full knowledge of the map when you are planning, there also can't be one-way streets or turning restrictions. If you ignore the restriction from the previous paragraph for now then: 1) Keep driving until you hit an intersection. 2) Go down a road you haven't been down. If there are multiple roads which you haven't driven down, then pick any of the roads to follow, unless choosing one would split the set of undriven roads in two. Now to fix the dead end and T intersection problem, before you start: 1) Find an intersection with an odd number of roads going to it. 2) Find the shortest path from it to any other intersection with an odd number of roads going to it. 3) Add a fake road along that path, so you are then allowed to travel down it more than one time. For example, if you have a T intersection leading to a dead end, then the dead end road would get a fake road placed over the top of it. (but like most maths, this would probably end up making things worse if you actually tried it - as it is much quicker to go straight than to be constantly making right hand turns everywhere, and this algorithm doesn't care) (oh, and someone suggested that if the roads were all in a grid, you could do smart things to take into account the redundancy, and just zig-zag through, knowing you can extrapolate later... I don't know of any algorithms that will find the best path in these cases - you would need to add a fair bit of extra magic to existing graph theory to solve it) Andy ___ Talk-au mailing list Talk-au@openstreetmap.org http://lists.openstreetmap.org/listinfo/talk-au ___ Talk-au mailing list Talk-au@openstreetmap.org http://lists.openstreetmap.org/listinfo/talk-au
Re: [talk-au] How to map out streets the most efficently
--- On Wed, 17/6/09, Andy Owen andy-...@ultra-premium.com wrote: (oh, and someone suggested that if the roads were all in a grid, you could do smart things to take into account the redundancy, and just zig-zag through, knowing you can extrapolate later... I don't know of any algorithms that will find the best path in these cases - you would need to add a fair bit of extra magic to existing graph theory to solve it) I was thinking about this earlier, what's the most important feature about roads, the answer is the end points, which for the most part are dead ends or T-intersections. The next important piece of information is the points where streets or roads intersect. Finally any extra information about the path of the street between intersections. If you have the first 2, the third piece of information can be extrapolated, especially if the streets are mostly straight. So it's not as important to traverse every street if you can get the end points and intersections of streets, the rest can be refined. ___ Talk-au mailing list Talk-au@openstreetmap.org http://lists.openstreetmap.org/listinfo/talk-au
Re: [talk-au] How to map out streets the most efficently
On Tue, 16 Jun 2009, Delta Foxtrot wrote: what did you say about geocachers?? Been some accidents while people were concentrating more on their GPS than on the road, trying to find the link with photos but nothing is coming up in google. I knew what you meant even osm wiki has examples of mappers coming to grief -- BOFH excuse #434: Please state the nature of the technical emergency ___ Talk-au mailing list Talk-au@openstreetmap.org http://lists.openstreetmap.org/listinfo/talk-au
Re: [talk-au] How to map out streets the most efficently
--- On Tue, 16/6/09, Elizabeth Dodd ed...@billiau.net wrote: I knew what you meant even osm wiki has examples of mappers coming to grief You meant this? http://wiki.openstreetmap.org/wiki/Mapping_accidents :) ___ Talk-au mailing list Talk-au@openstreetmap.org http://lists.openstreetmap.org/listinfo/talk-au
Re: [talk-au] How to map out streets the most efficently
On Tue, 16 Jun 2009, Delta Foxtrot wrote: Now does anyone have suggestions on how to basically drive the entire town the most efficiently with the minimal amount of overlap, or how does one plan such a feat. It depends if they are set out in rectangular bocks or wiggles rectangular blocks - circle the block, then do a zig zag through it We photograph the street signs which means we go round slowly Again we means often we have a team of two Wiggly streets hopeless for speed as you have to do the lot. ___ Talk-au mailing list Talk-au@openstreetmap.org http://lists.openstreetmap.org/listinfo/talk-au
Re: [talk-au] How to map out streets the most efficently
On Tue, 16 Jun 2009, Delta Foxtrot wrote: Thoughts, hints and tips will be appreciated. Personally I'd concentrate on doing one or two on the journey up and one or two on the journey back. One large and one small? ___ Talk-au mailing list Talk-au@openstreetmap.org http://lists.openstreetmap.org/listinfo/talk-au
Re: [talk-au] How to map out streets the most efficently
On Tue, 16 Jun 2009 07:22:42 +1000 Liz ed...@billiau.net wrote: On Tue, 16 Jun 2009, Delta Foxtrot wrote: Thoughts, hints and tips will be appreciated. Personally I'd concentrate on doing one or two on the journey up and one or two on the journey back. One large and one small? I'd agree. It's not a race so focus on doing the job fully to the level you are happy with on a smaller scale and come back later to finish it. If you try to rush and shortcut you'll only have to go back later to finish the things you find out you've missed the first time. The number of POI's and small side alleys I've found off obscure back streets of rural towns you really need to check every street if you want to consider everything mapped. -- =b ___ Talk-au mailing list Talk-au@openstreetmap.org http://lists.openstreetmap.org/listinfo/talk-au
Re: [talk-au] How to map out streets the most efficently
--- On Mon, 15/6/09, Liz ed...@billiau.net wrote: It depends if they are set out in rectangular bocks or wiggles Most of the streets in the towns given seem to be fairly straight, thankfully. We photograph the street signs which means we go round slowly I've been playing around lately on the best way to store street name info and voice recording notes seems to win hands down because it is easier/quicker, especially when doing it by yourself. You don't have to stop or fumble with devices, you just talk to yourself a lot. :) Again we means often we have a team of two I don't have that luxury. ___ Talk-au mailing list Talk-au@openstreetmap.org http://lists.openstreetmap.org/listinfo/talk-au
Re: [talk-au] How to map out streets the most efficently
On Tue, 16 Jun 2009, Delta Foxtrot wrote: I've been playing around lately on the best way to store street name info and voice recording notes seems to win hands down because it is easier/quicker, especially when doing it by yourself. You don't have to stop or fumble with devices, you just talk to yourself a lot. :) I got a cheap mp3 player that offered recording but i couldn't get it to work, so i quit that line of investigation. could be worthwhile, certainly easier than writing on paper on the steering wheel at speed ___ Talk-au mailing list Talk-au@openstreetmap.org http://lists.openstreetmap.org/listinfo/talk-au
Re: [talk-au] How to map out streets the most efficently
--- On Mon, 15/6/09, Liz ed...@billiau.net wrote: OSM makes you look for somethings out there between the nothings. You have to, at times, squint and turn round, maybe pluck a chook to find it! :) I know that country, and the Hay Plains still win for nothingness. A few prickly pear, a couple of roos and a dozzen road trains don't count as something... If you don't come back by a different direction, we'll miss other data Exactly! :) ___ Talk-au mailing list Talk-au@openstreetmap.org http://lists.openstreetmap.org/listinfo/talk-au
Re: [talk-au] How to map out streets the most efficently
--- On Mon, 15/6/09, Liz ed...@billiau.net wrote: I got a cheap mp3 player that offered recording but i couldn't get it to work, so i quit that line of investigation. could be worthwhile, certainly easier than writing on paper on the steering wheel at speed Have you seen the photos of Geocachers not paying full attention to the conditions round them and having accidents? :) ___ Talk-au mailing list Talk-au@openstreetmap.org http://lists.openstreetmap.org/listinfo/talk-au
