Fundamentally this is a simple application of some of the shortest path algorithms that are studied at university computer science and mathematics departments adnausium.
There are however a bunch of complications that make it a little less simple, and is likely best worked out in each individual instance. (You already know this, but for completness:) The way it's generally done at mapping parties is to cut the area up intuitively into a bunch of areas, naturally divided up by natural boundaries (such as main roads, rivers etc) let volunteers allocate themselves areas by ersonal preference. (cutting the cake) However due to the huge number of variables involved, I'd be surprised if there was any way a computer could do it faster or better: Someone says "I like driving, so I'll take the furthest away bit"; Someone say "I have a bike, so i can do that little area with lots of foot paths"; someone says "I like trees, and I know there are lots of trees in that area" (OK, that's a slight exaggeration); When you arrive on the ground you can find that there are names only at one end of a grid of streets, and your carefully pre planned route breaks. There are so many different kinds of areas (grid patterns; modern curvey estates, terraced areas, industrial parks, one way systems) that routing algorithms would have to be tweaked for each area; You could however call every intersection a node, and come up with an algorithm to visit each node once. This is almost the Travelling_salesman_problem<http://en.wikipedia.org/wiki/Travelling_salesman_problem>though extra complexity is added when you find that some streets only need one end visited. While there are severe problems with finding a perfect solution to the TSP, there are plenty of shortcuts that can be taken in this case. Now reading between the lines of your problem, there are a few questions -- are you willing to assume that if you drive past one end of a street, it's captured, or does both ends need to be captured? Or is some live update system going to be implemented so that volunteers can enter information about when they get a street name, and the route can be recalculated? Are you willing to accept that if a road changes name part way though, and that missing this is a reasonable error? Is it reasonable to assume that all volunteers are especially the same (they all have a car, and have no specific preferences)? Is it reasonable to assume that everyone starts and finishes at a predetermined "base"? Is it reasonable ot assume that if someone finds a 1 way system, or other restriction, that the route will go wrong, and this is ok? How large an area are we dealing with here? most algorithms for this type of thing get proportionately slower the more data is put in, and as such, will have a point at which they simply fall over or get so slow that it would be quicker to use a pencil and some brain cells. In short: I'd recommend just using intuition, but if that's not an option, give a load more details, and we can work something out. On to a related subject, are there any tools that have been developed to assist with cake cutting tasks? I have personally been tairing my hair out for the last few days trying ot get josm to display cake segments for yahooing tiger data. Thanks, JR On 24 March 2010 10:52, John Smith <[email protected]> wrote: > This is a routing problem, hopefully someone has already solved it. > > If there is a suburb of streets mapped from aerial imagery and you > have several volunteers how do you work out the most efficient path > for all the voluneteers to take to grab street names with minimal > overlap etc. > > _______________________________________________ > dev mailing list > [email protected] > http://lists.openstreetmap.org/listinfo/dev >
_______________________________________________ dev mailing list [email protected] http://lists.openstreetmap.org/listinfo/dev
