Let's say I have an array of points, each of them defined by their distance to surrounding points, rather than by coordinates on a map. For instance, NY's location would be defined by its distance to Pennsylvania and Maryland, etc. And Washington is defined by its distance to Oregon and Idaho, etc.

Assuming each point is defined by a limited number of connections, how would I find the distance between two points that don't share connections, such as NY and WA?

The scenario is a map of node points in 3D space, and rather than defining their coordinates in terms of XYZ on a graph, I'm defining their distances between each other in terms of XYZ. So if Point A is in some location in space with a number of surrounding neighbors, and Point Z is in some other location in space with a number of other surrounding neighbors, I want to be able to find the distance between A and Z.

I've already considered a flood method, similar to how simpler pathfinding works, flooding a temporary connection map and finding the shortest path drawn and using that path to figure out a straight line distance. This method seems very costly, however.

  • $\begingroup$ If the point dont have connections, you dont have any form to get their distance?? How supposedly you wil trace a straight line between them, if there is not a map??. Not clear at all. $\endgroup$ – Brethlosze Jun 8 '17 at 2:09
  • $\begingroup$ Is dynamic programming relevant (stackoverflow.com/questions/1065433/what-is-dynamic-programming) ? $\endgroup$ – Jean Marie Jun 8 '17 at 2:13
  • $\begingroup$ @hyprfrco No "straight lines" ; consider this issue as a graph theory problem. $\endgroup$ – Jean Marie Jun 8 '17 at 2:14
  • $\begingroup$ "using that path to figure out a straight line distance" $\endgroup$ – Brethlosze Jun 8 '17 at 2:17
  • $\begingroup$ @hyprfrco you are right, I didn't notice. The OP must "downgrade" his expectations. He/she will get at best larger distances than straight line distances. $\endgroup$ – Jean Marie Jun 8 '17 at 2:22

Using graph theory you'll get the shortest distance between the two nodes pretty easily assuming the are indirectly connected (this is a classic and you'll find a zillion algorithms and their implementations online).

If you want the euclidian distance then after finding a path (you're not forced to have the shortest path, although it might lead to quicker computation) then you'll have to solve a system of equations. Note that for this to work you need to have 2 (or 3 in 3 dimensions) known distance for each and every single node of your path (this might lead you to add nodes outside the path, this is ok as long as those extra nodes also respect the previous rule)

  • $\begingroup$ The way I have it in my head, is each point would have defined neighbors. I'm working out how these neighbors could change where points might move, but using these neighbor lists I could define paths, essentially, between two unconnected points. It kinda seems like that's what you're getting at, something like this. $\endgroup$ – Daniel Jun 8 '17 at 3:08
  • $\begingroup$ Others suggest graph theory as well, and as I'm reading about it (new topic, to me) this is the direction I want to go. Thanks! $\endgroup$ – Daniel Jun 8 '17 at 3:29
  • $\begingroup$ No problem, graphs are a really powerful tool to solve a lot of problem but they are changing the way you think about things like distance. $\endgroup$ – Furrane Jun 9 '17 at 9:05

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.