# Linking array of sets of vector3's together

Hi, I’ve been stuck on this problem for way too long and I just can’t figure it out. I’m wondering if someone could help me out.

I’ve got a struct like this:

``````public struct Segment
{
public Vector3 start;
public Vector3 end;

public Segment(Vector3 start, Vector3 end)
{
this.start = start;
this.end = end;
}
}
``````

I’ve got an array of this struct with matching values like so (simplified):

• start (0,0,0) end (1,1,1)
• start (3,3,3) end (4,4,4)
• start (2,2,2) end (3,3,3)
• start (1,1,1) end (2,2,2)
• start (4,4,4) end (5,5,5)

I’m trying to match the start and ends of each segment so that the array will line up like so:

• start (0,0,0) end (1,1,1)
• start (1,1,1) end (2,2,2)
• start (2,2,2) end (3,3,3)
• start (3,3,3) end (4,4,4)
• start (4,4,4) end (5,5,5)

I’ve been stuck on this even though I feel like the solution would be very simple. Your help is greatly appreciated.

Well, there are a few things that need to be cleared up first. Are you sure that the “end” of one segment does exactly match the “start” of the next segment? So a == comparison between them will be true? The next thing is, do you know the first segment ahead of time or do you just want to construct a chain of unknown start and end? If you know the start segment and you have only a few segments (say around 100) you can easily use a nested for loop and finding the right start match for a given end. That way you simply walk along the chain and sort the segments into a new List.

If the starts and ends match exactly but you have a lot segments (say 1000+) you could use a dictionary based on the start position as key. That way you get rid of the nested loop and reduce the complexity. Though this approach only works with exactly matching start and end positions. If they can be off even slightly (0.00001 or less) the only way is to use a nested for loop and check against every other segment. In this case you have to define for yourself when two positions should be considered “the same”. Usually by some sort of threshold.

If the start / end of the chain is unknown and your first segment might be in the middle of the chain you have to do the search in both ways. The most efficient solution is probably to use a Stack and a Queue in this case. Using a Queue while going forward (matching the end of the current to the start of the next) and using a Stack while going backwards (matching the start of the current to the end of the pervious). At the end we can simply join both into a single List.

So the most versatile solution would be something like this:

``````public static List<Segment> OrderSegments(IEnumerable<Segment> aSegments, float aThreshold = 0f)
{
aThreshold *= aThreshold; // square the threshold
List<Segment> segs = new List<Segment>(aSegments); // create a copy of the original list
if(segs.Count < 2)
return segs;
Stack<Segment> prev = new Stack<Segment>();
Queue<Segment> next = new Queue<Segment>();
Segment curStart = segs[segs.Count-1];
Segment curEnd = curStart;
segs.RemoveAt(segs.Count-1);
next.Enqueue(curStart);
bool found = true;
while (segs.Count > 0 && found)
{
found = false;
for(int i = 0; i < segs.Count; i++)
{
var s = segs*;*
``````

if ((curEnd.end - s.start).sqrMagnitude < aThreshold)
{
found = true;
next.Enqueue(s);
segs = segs[segs.Count-1];
segs.RemoveAt(segs.Count-1);
curEnd = s;
break;
}
if ((curStart.start - s.end).sqrMagnitude < aThreshold)
{
found = true;
prev.Push(s);
segs = segs[segs.Count-1];
segs.RemoveAt(segs.Count-1);
curStart = s;
break;
}
}
}
// reuse the temp “segs” list for the result since it has already the right internal capacity
segs.Clear();
return segs;
}
Note that this assumes that all segments are actually part of the wanted chain. It starts with the last element in the list (as this can be removed cheaply). Be default the threshold is 0 which requires a perfect match between the start and end of your segments. If a segment does not match / participate in the chain it’s ignored. So the resulting list could be shorter if not all segments are used. Also keep in mind if two or more segments connect to the same “end” only the first one is used. So obviously this can not model a tree structure as it expects a chain.
To go through your example it would pick the last element as starting pivot which is moved into the “next” queue. Now it iterates through the remaining elements and searches if an element matches either the start or the end of the start/end pivot. In your case it’s the second element (index 1) where the end matches the start of our pivot. So it’s added to the prev stack and removed from the segs list. This continues until the source segs list is empty or not matching segment is found during one scan through the list.
Note: The way I delete an element from the segs list avoids unnecessary downshifts in the list when using RemoveAt with an index in between. Removing the last index in a List is an O(1) operation. By simply copying / moving the last element into the place where the element we want to remove was, we can simply remove the last element. By doing this the elements in segs might get shuffled. However since we assume the initial collection is not sorted this doesn’t matter.
Here’s a simplified run-down for your example data:
// segs next prev
0-1
3-4
2-3
1-2
4-5
// -----
0-1 4-5
3-4
2-3
1-2
// -----
0-1 4-5 3-4
1-2
2-3
// -----
0-1 4-5 2-3
1-2 3-4
// -----
0-1 4-5 1-2
2-3
3-4
// -----
4-5 0-1
1-2
2-3
3-4
// clearing segs and adding prev
0-1 4-5
1-2
2-3
3-4