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.

Improve this question
5
  • Network connections consist of line segments (lines, polylines). You should be able to extract coordinates from the line segment nodes.
    – Matej
    Commented Nov 11, 2015 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
    Commented Nov 11, 2015 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
    Commented Nov 12, 2015 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
    Commented Nov 12, 2015 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
    Commented Nov 12, 2015 at 17:08

1 Answer 1

Reset to default
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

Improve this answer
2
  • 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
    Commented Nov 12, 2015 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
    Commented Nov 12, 2015 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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