Sort list of Vectors2 into a line

Question

Hi,

I have a list of edges defined as such:

var finaledgeList  = [[Vector2(-12, -12), Vector2(-14, -12)], [Vector2(-12, -10), Vector2(-12, -12)], [Vector2(-14, -12), Vector2(-14, -10)], [Vector2(-14, -10), Vector2(-16, -10)], [Vector2(-16, -8), Vector2(-14, -8)], [Vector2(-16, -10), Vector2(-16, -8)], [Vector2(-10, -10), Vector2(-12, -10)], [Vector2(-10, -8), Vector2(-10, -10)], [Vector2(-12, -8), Vector2(-10, -8)], [Vector2(-12, -6), Vector2(-12, -8)], [Vector2(-14, -6), Vector2(-12, -6)], [Vector2(-14, -8), Vector2(-14, -6)]]

Each edge is define as an array of 2 Vector2. Normally where one edge finishes another starts. But some of them can be inverted.

I would like to sort all point such that it forms a continuous line.

I have tried by using loops and checking each element as such:

var flattenededgeList = [finaledgeList[0][0], finaledgeList.pop_front()[1]]

while finaledgeList.size() > 0:
    for edge in finaledgeList:
        if edge[0] == flattenededgeList[-1]:
            flattenededgeList.append(edge[1])
            finaledgeList.erase(edge)
        elif edge[1] == flattenededgeList[-1]:
            flattenededgeList.append(edge[0])
            finaledgeList.erase(edge)
        elif edge[1] == flattenededgeList[0]:
            flattenededgeList.push_front(edge[0])
            finaledgeList.erase(edge)
        elif edge[0] == flattenededgeList[0]:
            flattenededgeList.push_front(edge[1])
            finaledgeList.erase(edge)

When a point is found that can match the end of the current line then that edge is added and removed from : finaledgeList.

But this doesn't seem to work well on larger list of arrays and is probably quite slow. I was wondering if anybody new of a better solution ?

Thanks a lot,

Answer 1

When you say it doesn't work on larger list of arrays, how large are you talking about? Hundreds of edges? Millions of edges? Billions of edges ? Or Is it that it just doesn't work as intended?

Sadly if you are talking about larger data sets, this is not an easy solution. If it is millions +, I can say from experience that running large data through GD script or through the functionality of the engine can have issues with performance and or be game breaking. I came across this when passing Strings of game load data that were sizes of 10,000,000+.

For a large amount of the built in classes with the engine when you start doing anything in the millions of sizes whether it be adding values onto string or whatever. The engine will be very slow and you should think about either creating a Engine module and or GDNative Module(separate DLL) to handle this problem.

Functions that need high performance or large amounts of data involved should use this module and do the calculations and pass those results afterwards back into the engine.

I will link the GDNative information for you, hopefully this will help or lead you in the right direction.

GDNative Link Stable 3.3

Comments

Hi, thanks for your answer:

No nothing like that high number :)

Maybe a hundred at max. I was simply wondering if there was a more efficient way to do the loop I am trying to do, as it seems to me that looping over a list and removing an element at once seems quite non efficient.

I will look into GDNative thanks for the recommendation.

---

If it is that small, a hundred should be fine. If you need the performance GDNative is the way to implement a simple class to handle this logic for you and be as fast as possible.

But I would see if it actually makes a difference on what ever devices you want to deliver on before doing any optimizations.

My general rule of thumb is make everything work first and then if there is a performance issue when the game is nearly finished, then optimize it.

If you optimize everything from the get go, you might just be wasting time trying to get a few extra CPU cycles when it is not needed.