• O(1) Vector Sorting Algorithm - Does it work or am I stupid?
    0 replies, posted
I made a little C# class for Unity a long time ago that could sort Vector2's clockwise and vice-versa with O(1) complexity (No traditional sorting involved). It worked when I was writing it and put it on GitHub, but when I tried it again and few months ago I couldn't get it to work. I made it for raycast-based mesh 2D lighting because the sorting was by and far the slowest part of the whole process. You cast ray's out to corners and sort the hit points by angle to build a proper 3d mesh. You can see the class here: SpatialSort2D The idea is that, Instead of getting the angle and doing a quick sort, you normalize the point and split the circle it makes into two sparse arrays based on an axis. Then you use the other axis as a lookup table. Sparse arrays are scaled with an epsilion value, but I think this approach can still lead to collisions, so something different is needed. Here's my question: Does my idea work and my implementation is just bad, or is there something critical that I'm missing for why this wouldn't work? Or am I over thinking something with a simple solution? Thank you very much for your time!
Sorry, you need to Log In to post a reply to this thread.