2

I am trying to solve a network generation problem, and I'd be happy about inputs. First of all, my problem description:

I have a list of connections between locations with respective distances. For example:

LocationA <-> LocationB: 4500 m
LocationB <-> LocationC: 3000 m
LocationC <-> LocationA: 2000 m
...and so on...

What I do not know, but try to find out: The actual geographic position of my locations. I do know the position of a few nodes in the network, and given a large list of connections with distances, I should be able to approximatively find the positions of my unknown locations.

Note: I am not trying to actually to optimize any paths within this network (e.g. Dijkstra etc.). I simply would like to know what geographic coordinates the nodes in my system have.

My question is: What sort of "node placement algorithm" am I looking for? I'd be happy for any keywords in this regard. I am 100% sure there are some algorithms for this problem, but I do not even know what to search for.

  • Network connections consist of line segments (lines, polylines). You should be able to extract coordinates from the line segment nodes. – Matej Nov 11 '15 at 19:32
  • When you say you know the positions of a few nodes, are you certain that the distance between two known nodes would exactly match a distance in your list, or only approximate it? – Kirk Kuykendall Nov 11 '15 at 21:38
  • Thanks for commenting, guys. @Matej: Unfortunately, I do not have the lines in a shapefile or the like. I only have a csv-file which basically reads as A,B,4500 B,C,3000 C,A,2000 – Bob3k Nov 12 '15 at 13:06
  • @Kirk: The distances are only approximately right. Judging from Felix' comment below, I would need 6 instead for 3 points for triangulation, right? – Bob3k Nov 12 '15 at 13:09
  • Could this be classified as a computer vision/ pattern recognition problem? A camera captures an image, then generates points. A database of geometric objects is searched to find the the object whose nodes best match the points. – Kirk Kuykendall Nov 12 '15 at 17:08
1

As one can see from this picture

enter image description here

For every unknown point, you’ll need distances to 3 points with known coordinates. Thus I’d start with triangulation of known points. I hope the rest of the process is clear from picture.

Note: due to inaccuracies in distances to known points you’ll have to deal with 6 points. You’ll need to weed 3 of them, centre of 3 remaining will be your unknown point. There are multiple techniques to remove outliers I personally prefer convex hull peel.

Unfortunately it will work for unknown sitting inside triangle. If it is outside:

enter image description here

You'll have to find 3 points with minimum total distances to each other

  • Thanks for your comment. The triangulation is a good idea, but I am not sure that I know the exact location of a sufficient share of points to find all unknown points this way. What I rather had in mind: In my mind, one could view this task as an optimization problem. My variables to optimize are the x- and y-coordinate of my nodes. My objective function to minimize is the difference in distance between the nodes at their current position and the distance I know from my csv-file. Does anyone know an algorithm that would solve such problem? – Bob3k Nov 12 '15 at 13:19
  • It is hard enough to optimise 2 parameters. To optimise 2*number_of_nodes is impossible.What I am suggesting based on iterations, i.e. unknown point will become unknown.Are you able to upload this data somewhere? I’d like to play with it in my spare time.You can shift coordinates as far as you want to, if this is a concern – FelixIP Nov 12 '15 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.