Sort array clockwise order

Monkey Forums/Monkey Programming/Sort array clockwise order

Hezkore

(Posted 2014) [#1]

I have this tiny function for creating polygons, but I need it specified in a clockwise order.
Math really isn't my strong point (or numbers in general), so I'd really appreciate some help sorting it clockwise.
Basically the top left corner needs to come first, then the top right corner, bottom right and if there is a bottom left, it'll come last.
There will never be more than 4 corner or less than 3 corners.
This is used with the standard DrawPoly() function and it's stored like this [x,y,x2,y2,x3,y3,optionalx4,optionaly4]

Function createPolygon:cPolygon(verts:Float[])
	Local nP:cPolygon = New cPolygon
	nP.verts.Resize(verts.Length - 1)
	
	For Local i:Int = 0 To verts.Length - 1
		nP.verts[i] = verts[i]
	Next
	
	Return nP
End

Gerry Quinn

(Posted 2014) [#2]

Where are the vertices coming from? If you are creating this data, the easiest thing might be to create it sorted.

For four vertices, there isn't actually any answer to your question, because four arbitrary vertices could represent several different polygons.

Hezkore

(Posted 2014) [#3]

I can't input the data, only alter it. But things are pretty stright forward though, it's always one triangle or one quad in the array.

I found this - http://gamedev.stackexchange.com/questions/13229/sorting-array-of-points-in-clockwise-order
But I have no idea how to do it in Monkey.

Floyd

(Posted 2014) [#4]

Assuming the vertices can form a convex polygon then I think the idea is this:

1. Find a "center" point by computing the average of the vertices, i.e. add up the x's and divide by how many there are to get cx.
Do the same with the y's to get cy. Now you have a point (cx,cy) in the interior.

2. For each vertex calculate a direction vector from the center to the vertex as ( dx, dy ) = ( vx - cx, vy - cy ).
Then apply ATan2 to the numbers dx,dy. This gives an angle for each vertex.

3. Now sort the vertices, comparing them by angle values. I don't know what order the angles should be, increasing or decreasing. This will depend on the details of how things are set up: which way does the y-axis point, which way are dx,dy supplied to ATan2. Just try one order. If that doesn't work then you need the other one.

consty

(Posted 2014) [#5]

Can you do a reverse for loop instead?

Strict

Function Main:Int()
	' Representation of the data
	Local vert:List<Int> = New List<Int>
	vert.AddLast(4)
	vert.AddLast(3)
	vert.AddLast(2)
	vert.AddLast(1)
	
	'-----------------------------------------------------
	
	' The easiest and fastest way to do this
	' http://www.monkey-x.com/docs/html/Modules_monkey.list_List.html#Backwards
	' file:///C:/MonkeyX77a/docs/html/Modules_monkey.list_List.html#Backwards
	Print("Print vertex list backwards")
	For Local i:Int = Eachin vert.Backwards()
		Print(i)
	Next
	
	'-----------------------------------------------------
	
	' Another more classic way
	Local vertArray:Int[] = vert.ToArray()

	' remember that the actual data are zero based
	Print("Print vertex array backwards")
	For Local i:Int = vertArray.Length-1 To 0 Step -1
		Print(vertArray[i])
	Next
	
	'-----------------------------------------------------

	Return 0
End

Hezkore

(Posted 2014) [#6]

@consty Not all of them are in counterclockwise other I'm afraid. Some are the correct order, and occasionally the order is flipped.

muddy_shoes

(Posted 2014) [#7]

I find it hard to imagine a situation where you are getting tri and quad verts that are completely unordered. I suspect that your real question is how to determine the winding order so you can reverse the vertices if the input isn't in the direction you desire. As you've only got tris and quads to deal with in this case you just need to use the cross product of the first two edges. If you search you'll find hundreds of references on how to determine winding order in this way, e.g.: http://allenchou.net/2013/07/cross-product-of-2d-vectors/

Hezkore

(Posted 2014) [#8]

Well, for anyone with similar issues... this is what we came up with in the end

Function sortVecs:Float[](in:Float[])
	Local points:Int = in.Length() / 2
	Local center:Float[2]
	Local angles:Float[points]
	Local out:Float[points*2]
	
	For Local i:Int = 0 to points - 1
		center[0] += in[i*2+0]
		center[1] += in[i*2+1]
	Next
	
	center[0] /= points
	center[1] /= points
	
	For Local i:Int = 0 to points - 1
		angles[i] = -ATan2r(in[i*2+0]-center[0], in[i*2+1]-center[1]);
	Next
	
	For Local i:Int = 0 to points - 1
		
		Local lowest:Int = 0
		Local lowest_value:Float = angles[0]
		
		For Local j:Int = 1 to points - 1
			If (angles[j]<lowest_value)
				lowest = j
				lowest_value = angles[j]
			End
		Next
		
		out[i*2+0] = in[lowest*2+0]
		out[i*2+1] = in[lowest*2+1]
		
		angles[lowest] = PI
	Next
	
	Return out
End