2
$\begingroup$

I'm creating a webapplication in which I render multiple objects using Three.js. These objects are saved in a list and can be connected to each other (but don't have to be), and when they are, they are rendered next to each other.

The user can select an object in this list using the UI that I made.

An example of how the objects can be positioned is in the image below. When I select the most left object I want the whole chain to be rendered, but not the 'singular' objects that are in the same list.

enter image description here

I hope this is clear enough, if not I will gladly elaborate.

Now the problem that I'm having:

The (simplified) list can look like this:

  {
    id: 1,
    connectedObjects: [{ id: 2 }, { id: 5 }],
  },
  {
    id: 2,
    connectedObjects: [{ id: 1 }, { id: 3 }],
  },
  {
    id: 3,
    connectedObjects: [{ id: 2 }, { id: 4 }],
  },
  {
    id: 4,
    connectedObjects: [{ id: 3 }],
  },
  {
    id: 5,
    connectedObjects: [{ id: 1 }],
  },
  {
    id: 6,
    connectedObjects: [],
  },
  {
    id: 7,
    connectedObjects: [],
  },
  {
    id: 8,
    connectedObjects: [],
  },
];

Now I want to write an algorithm that checks which objects are all in the same 'group' as the selected object. So the last three (6, 7, 8) will not be rendered.

This is in JavaScript but if someone points me in the right direction with some pseudocode or a general idea that would be great!

$\endgroup$
4
  • 2
    $\begingroup$ It looks like you are trying to find the connected components in an undirected graph. Googling those terms should point you to the right direction. The keywords "BFS on graph" or "DFS on graph" could also be useful. $\endgroup$
    – Tassle
    Commented Aug 10, 2020 at 11:34
  • 1
    $\begingroup$ There is Disjoint-set datastructure, which allows you to construct the connected components and check membership efficiently. $\endgroup$
    – plop
    Commented Aug 10, 2020 at 13:53
  • 1
    $\begingroup$ You haven't defined what a 'singular' object is. $\endgroup$
    – D.W.
    Commented Aug 10, 2020 at 18:19
  • $\begingroup$ It may help to add at least one 'singular' object to the sketch, too. $\endgroup$
    – greybeard
    Commented Aug 11, 2020 at 2:29

1 Answer 1

2
$\begingroup$

Thanks for your answers!

I looked into both connected components in an undirected graph and the Disjoint set and went for the latter.

After researching this dataset I found a few packages that provided an implementation, but I used this one:

https://github.com/nawatts/disjoint

I'm a junior developer and haven't really come in contact with this kind of problems so your points in the right direction are very much appreciated.

$\endgroup$

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.