How to display an area with shortest distance to surrounding points?

Hi All,

this is my first post to the OpenStreetMap forum. I apologize if this is not the correct forum, please redirect if you think this doesn’t belong here.

I’m looking for an application/tool or some way to display an area/point with minimum distance to surrounding points.
The reason for that is, that since last month seven cats have disappeared without any trace in the area where I live. The kids are really sad.

Assuming a cat roams within a certain radius around its home, I would like to find the area all cats could reach from their home, which would probably yield the area of highest probability for a cat to disappear. This would reduce the search area (e.g. for a trap) significantly.
Ideally, the tool or application would allow to mark individual homes in OSM and display a colored area with minimum distance as a result. Another way to achieve that would be to be able to create colored circles around homes to see where they overlap.

Any help or hint is greatly appreciated.

Thanks, Joerg

This is a very difficult problem as it involves routing over areas and deducing the existence or non-existence of barriers, things that full feature routing programs have difficulty with. Moreover, very few barrier are actually mapped and many barriers would not be an effective barrier to a cat.

Where you have a simple network rather than areas, the basic algorithm is to set every node to a high value, then recursively traverse the network reducing the distances and ignoring cases where there is no resulting reduction. However, areas and boundaries add a new level of complexity, especially as you are interested in distances, so the pixel based flood fill methods are not sufficient.

I gather that very few, if any, routers tackle pedestrian areas, even when they are not butted together, and don’t have internal projections that prevent the use of the shortest path between entry and exit.

Given that we’re talking about cats here, I don’t think it’s really a routing problem is it? Cats can climb up walls, through hedges, etc.

Maybe you could use something like http://umap.openstreetmap.fr/en/ to visualise possible overlapping ranges. According to the discussion around an old Horizon program (UK) http://forums.digitalspy.co.uk/showthread.php?t=1836046 the average roaming distance isn’t that high - maybe 50m or so (though obviously there will be cats roaming further than that).

In terms of “the best place to ask this sort of question”, https://help.openstreetmap.org/ will probably get more people looking at it than here, but other than that here’s as good a place as any.

Thanks a lot for your answers!

In the meantime, I wrote a small program to get some sort of a probability matrix (x, y, p):

  • create a list with circles (where the center of each circle is the home of a lost cat)
  • the radius of every circle is (half of) the maximum of the distance between two centers plus some increment (so even the circles that are farthest have some overlap)
  • define a region surrounding the circles (matrix of x,y coordinates) with a given granularity (e.g. 1m)
  • for every point in the region, step through the list of circles. If the point is inside a circle, the probability value of that point is incremented.

This yields a 2-dimensional array of probabilities ranging from 0 (point is not inside any circle) to 7 (point is inside all circles).
Now the problem is how to link that into OSM:

  • How can I determine the coordinates of a point in OSM, and the integral representation for it (I guess there is one)?
  • Is there a way to overlay OSM with the points of my probability matrix, so that probability values are shown as colored dots (0 = none, 7=dark red or something)?
  • If yes, is there a limit in how many elements could be added to OSM? I was thinking of a region about 1000m x 1000m with a resolution of 1m, resulting in 1 million points. Well, maybe it’s not that bad, because only probability values bigger than 0 are of interest.

Thanks again, Joerg

Coordinates in OSM are real numbers (degrees of latitude and longitude).

You would not put your data into OSM, you would simply superimpose it on a rendered image of the OSM map, either using bit mapping (paint shop) type operations, or by rendering it in vector form after rendering the OSM data in vector form.

The map tiles are not OSM itself, just one possible rendering of it. The tiles always represent the same number of degrees of longitude ( ( 360 / (2 ** (zoom-level +n))), where, further research may show that n is actually zero). The vertical span of the tiles is adjusted so that they cover the same distance on the ground on both x and y axes (I’m not sure how this is handled for low zoom levels where the x width varies greatly with y, but that isn’t an issue for you).