[OSM-dev] Doing street names from aerial imagery

John Robert Peterson jrp.crs at gmail.com
Wed Mar 24 11:31:58 GMT 2010


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 <deltafoxtrot256 at gmail.com> 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
> dev at openstreetmap.org
> http://lists.openstreetmap.org/listinfo/dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/dev/attachments/20100324/4dc345e6/attachment.html>


More information about the dev mailing list