Recursive javascript function to find the shortest distance between 2 points thats greater than 1

Viewed 46

I have a set of points and an object that describes how each point is linked to one another.

Here is a simplified example:

const points = ["a","b","c","d","e","f"];

const links = {
    a : [ "b", "f" ],
    b : [ "c", "f" ],
    c : [ "d", "e" ],
    d : [ "a", "e" ],
    e : [ "c", "d", "f" ],
    f : [ "a", "b", "e" ],
};

In this example 'a','b','c','d' describe the corners of a rectangle and 'e','f' are points inside of the rectangle that link to 2 corners each.

b ------------ c
|\            /|
| \          / |
|  f ------ e  |
| /          \ |
|/            \|
a ------------ d

I am trying to work out a recursive function that returns all possible outcomes where the distance (steps) between the points is greater than 1 to form polygons.

Desired output:

output = [
    [ "a", "f", "b" ],
    [ "b", "f", "e", "c" ],
    [ "c", "e", "d" ],
    [ "d", "e", "f", "a" ],
]

There would obviously be duplicate results if the points order were reversed so ideally, in ascending order a->d, heading around the perimeter, forming polygons as you go. ie;

start: a, end: b, result: [ a, f, b ]

start: b, end: c, result: [ b, f, e, c ]

start: c, end: d, result: [ c, e, d ]

start: d, end: a, result: [ d, e, f, a ]

More specifically I would like a function that would return the desired result given a start and end point, eg:

function shortestPath(data, start, end) {
    // ... magic ...
    return result;


result = shortestPath(links, 'b', 'c')
// [ "b", "f", "e", "c" ]

Apologies if any of this is unclear - first time posting on SO.

Thank you in advance!

0 Answers
Related