Sorting Lua Tables: Multiple Columns

Hi there,

I'm using the midpoint algorithm for circles to generate ordered pairs for my turtle. This has been done in many other codes, but I'd like to try a new optimization method: I want to sort the ordered pairs by their polar angle.

r_i = math.sqrt(x_i² + y_i²)
theta_i = math.asin(y_i / r_i)

I think I know that table.sort requires the "key" column to be continuous integers. So, I thought maybe I could put x in one table and y in another, and write a new sort function that iterates over table.x and table.y to solve for table.theta, sort that, and then apply table.theta's "sorting code" to table.x and table.y.

But I'm pretty new to Lua. Before I go any farther, may I ask if this has been done before? Is there a more obvious solution?

Thanks!

Not sure it will be helpful in this particular case, but my code is at: http://pastebin.com/safRUyjh . This is around line 350…

Why not store the table in the format:

{[1]={x=1,y=0,theta=0},[2]={x=1,y=1,theta=45},...}

you could then use

table.sort(table, function(point1,point2) return point1.theta<point2.theta end)

to sort it, alternatively, if you didn't want to store the angle in the table, you could modify the comparison function to calculate the angles and then compare them

Brilliant - thanks!!! For future Googlers:

x1= x+x0; y1= y+y0; points[#points+1]={['x']=x1,['y']=y1,['theta']=math.atan2(x1,y1)}
x1= y+x0; y1= x+y0; points[#points+1]={['x']=x1,['y']=y1,['theta']=math.atan2(x1,y1)}
x1=-x+x0; y1= y+y0; points[#points+1]={['x']=x1,['y']=y1,['theta']=math.atan2(x1,y1)}
x1=-y+x0; y1= x+y0; points[#points+1]={['x']=x1,['y']=y1,['theta']=math.atan2(x1,y1)}
x1=-x+x0; y1=-y+y0; points[#points+1]={['x']=x1,['y']=y1,['theta']=math.atan2(x1,y1)}
x1=-y+x0; y1=-x+y0; points[#points+1]={['x']=x1,['y']=y1,['theta']=math.atan2(x1,y1)}
x1= x+x0; y1=-y+y0; points[#points+1]={['x']=x1,['y']=y1,['theta']=math.atan2(x1,y1)}
x1= y+x0; y1=-x+y0; points[#points+1]={['x']=x1,['y']=y1,['theta']=math.atan2(x1,y1)}

(...extra midpoint code...)

table.sort(points, function(p1,p2) return p1.theta<p2.theta end)

for i=1,#points do
	print('x=',points[i].x,', y=',points[i].y,', theta=',points[i].theta)	   	
end

Update: This method fails at x=0 and y=0. I was trying to avoid copying demonpants' tower code here, but I'm out of alternative ideas. To future Googlers, I would go with his method instead.

Just a a thought:
For generating the points why not just solve the circle equation? you onto need to do it in the +ve x and +ve y quadrant and then rotate it to the other quadrants. In my head it looks something like:

local function rotate(point, quadrants)
   if quadrant==1 then
	  return -point.z, point.x, point.theta+math.pi/2
   elseif quadrant==2 then
	  return -point.x, -point.z, point.theta+math.pi
   end
end

for x=0,r,0.1 do --#necessary to do steps smaller than 1 for cases when there are more than 1 block per x value
	z=math.floor((r^2-x^2)^0.5)
	xfloor=math.floor(x)
	points[#points+1]={["x"]=xfloor,["z"]=z,["theta"]=math.atan2(x,z)}
end
for i,j in pairs(points) do
	if j.x==points[i+1].x and j.z==points[i+1].z then
		table.remove(points,i+1) --#strips duplicate points from the table
	end
end
table.sort(points, function(p1,p2) return p1.theta<p2.theta end) --#sort table (though it should already be sorted by our generation method)

for= thetaoffset=1,2 do
    for i,j in pairs(points) do
       points[#points+1]={rotate(j,offset)}
    end
end

not saying this would work perfectly without some tweaking, but it could be a good starting point