How to sort an array of Vector2 clockwise?

Archive
1
:information_source: Attention Topic was automatically imported from the old Question2Answer platform.
:bust_in_silhouette: Asked By Fornix

For a project I am working on I am using a CollisionPolygon2D for my ground collision detection. I can successfully grab the point positions in a path2D to set the polygons of the CollisionPolygon2D. However, this requires manual tracing for all collision areas in Godot.

So rather I am trying to automate this process. Looping through the pixels in an image mask I am checking for non-transparency, indicating collision should happen. These pixel coordinates are stored in an array.

This array can contain e.g.:
[(0, 384), (0, 640), (64, 384), (64, 640), (128, 448), (128, 640), (192, 448), (192, 640), (256, 448), (256, 640), (320, 448), (320, 640), (384, 448), (448, 512), (512, 512), (576, 512), (640, 512), (704, 512), (768, 512), (832, 512), (896, 512), (960, 512), (1024, 512), (1088, 512), (1152, 512), (1216, 512), (1216, 640)]

As it is built out of a for x and nested for y loop, the array is sorted by x-coordinates first, y-coordinates secondary.

This however does not work as vector array for a CollisionPolygon2D. Resorting the array into a clockwise orientation should do the tick. However, this is where I appear to be hitting a wall right now.

So I was wondering whether anybody here has a possible solution for me on how to sort an array of Vector2 data clockwise?

2
:bust_in_silhouette: Reply From: Charlie

Not tested:

array_of_vector2s.sort_custom(self, "sort_clockwise")

func sort_clockwise(a, b):
	return a.angle() < b.angle()

self here tells sort_custom() where to find sort_clockwise(), so you can change it to put the sort function wherever you want. You’ll have to check @GDScript to see if angle() is exactly what you want, but I think it is.

I played around with this myself as well, although this doesn’t quite deliver the expected result.

Before sorting clockwise
[(0, 384), (0, 640), (64, 384), (64, 640), (128, 448), (128, 640), (192, 448), (192, 640), (256, 448), (256, 640), (320, 448), (320, 640), (384, 448), (448, 512), (512, 512), (576, 512), (640, 512), (704, 512), (768, 512), (832, 512), (896, 512), (960, 512), (1024, 512), (1088, 512), (1152, 512), (1216, 512), (1216, 640)]

After sorting clockwise
[(1216, 512), (1152, 512), (1088, 512), (1024, 512), (1216, 640), (960, 512), (896, 512), (832, 512), (768, 512), (704, 512), (640, 512), (576, 512), (512, 512), (448, 512), (384, 448), (320, 448), (256, 448), (320, 640), (192, 448), (256, 640), (192, 640), (128, 448), (128, 640), (64, 384), (64, 640), (0, 640), (0, 384)]

Although it does sort by angle correctly, it’s not truly clockwise yet because it does not factor in the distance to the various points correctly. Going through the different points listed, you can note as to how the angle will increase on these first points, but it is actually moving down on the x-axis whilst remaining on the same y-axis. And in the end it’s making zig-zag jumps.

In some way I think the distance_squared_to() function needs to be factored in, referring to the origin as Vector2(0,0). But I have yet to figure out the correct code to mix these two.

I have tried the following:

var origin = Vector2(0,0)

if a.distance_squared_to(origin) < b.distance_squared_to(origin):
	if a.angle() < b.angle():
		print("a: ", a, "    b: ", b)
		return true
	else:
		return false
else:
	pass #...

Herein taking the notion that if a is closer to the origin than b, I only want to sort it this way if the angle of a is actually less than b.

a: (1216, 512)    b: (1216, 640)
a: (1152, 512)    b: (1216, 640)
a: (1088, 512)    b: (1216, 640)
a: (1024, 512)    b: (1216, 640)
a: (320, 448)     b: (320, 640)
a: (256, 448)     b: (256, 640)
a: (256, 448)     b: (320, 640)
a: (192, 448)     b: (192, 640)
a: (192, 448)     b: (256, 640)
a: (128, 448)     b: (128, 640)
a: (64, 384)      b: (64, 640)

The coordinates matching these conditions are the ones above.

And having “finished” the sort (I would assume it leaves part of it just unsorted, because there is no further conditional), this gives:

After sorting clockwise
[(1216, 512), (1152, 512), (1088, 512), (1024, 512), (1216, 640), (960, 512), (896, 512), (832, 512), (768, 512), (704, 512), (640, 512), (576, 512), (512, 512), (448, 512), (384, 448), (320, 448), (256, 448), (320, 640), (192, 448), (256, 640), (192, 640), (128, 448), (128, 640), (64, 384), (64, 640), (0, 640), (0, 384)]

And here we face the same problem again. We can see this occur in the individual coordinates as well, take for example the first few:

a: (1216, 512)    b: (1216, 640)
a: (1152, 512)    b: (1216, 640)
a: (1088, 512)    b: (1216, 640)
a: (1024, 512)    b: (1216, 640)

Yes, a is smaller than all of the provided b’s. But the last a is closer to the origin than the first a and as such is supposed to be sorted first.

And this is where I keep hitting a wall for now. And in which I am actually wondering whether this approach is actually viable, I am just overlooking something right now. So if you or anyone else has any further suggestions, please let me know.

Fornix | 2019-01-03 10:52

Oops! Output looks like counter-clockwise rather than clockwise. Just flip < to > for that.

I’m still not sure what you mean by “clockwise” if not angle from some center. Perhaps the problem here is that the center from which we are calculating angle is (0, 0)?

Do you want it to sort by angle around the point (50, 50)? If so, then…

var center

func my_function():
     center = Vector2(50, 50) # set this here!
     my_array.sort_custom(self, "sort_clockwise")
  
func sort_clockwise(a, b):
      # This MUST always return true or false, not null!!!!
      return (a - center).angle() < (b - center).angle()

Set center to whatever you need before calling the sort.

If by “clockwise” you mean something other than angle around some specified center (as numbers in an old fashioned clock) then you need to define exactly what you want (for yourself, not me) and do that in the sort function.

Be careful in the sort function to ALWAYS return true or false! Your code snippet above returns null on the “else: pass” condition. This breaks the sort. Return true if you want a before b, or false if you want b before a, where a and b are any two elements in your array (for ties, you still need to return true or false!).

Charlie | 2019-01-03 18:52

Thanks for the reply. The output looks counter clockwise at the start, but it is not counter clockwise, it continues in a bit of a ‘random’ zigzag pattern towards the end. As for the pass, not returning true or false, that was just a quick and dirty escape, not sure on as to what do fill in for now, primarily aimed at seeing which a and b values it handled.

As to what I mean with clockwise, the 2d points the code gives me are the border points of a transparency mask. Think a photoshop layer mask, but rather than black/white I use a single color on a transparent layer. Each Vector2 matches with a pixel of color bordering transparency.

For the CollisionPolygon2D I need to trace all those Vector2’s in the correct order, clockwise around the field of color on the image basically.

Maybe the fact that I am using the top left corner of the image as reference for origin is a problem. I will have a look at computing a center first and computing the angle relative to that. Thanks for the suggestion!

Fornix | 2019-01-03 21:00