Let;s talk about scenegraphs

Yes, that is possible. The question is whether that approach is fast enough to be of use in real-time. It would require linear sorting of perhaps 10x the number of objects within the rectangle. What it basically amounts to is a binary search on one axis followed by a linear search on the other.

Here's a test I made using a scene graph with a fixed-size array. It sorts 100,000 points onscreen and only draws those within a rectangle. As you can see, the scenegraph mode is many times faster than the linear method, but it requires tuning of the sector size and how many objects there are. There's definitely an optimal balance:
http://www.leadwerks.com/post/SceneGraph.zip

Here's the source code. It's kind of nice because it is so simple. You just create a scenegraph with the scale and subdivision you want, then insert objects of any type into it based on their x and z positions using InsertSceneNode(). You can then use ForEachSceneNodeDo() specifying a rectangle and a callback function to perform for each object within the range. This is much faster than adding all the objects to a list. If you delete an object, just use RemoveSceneNode() and if you move it, just call InsertSceneNode() again and the program will detect the old scene node and remove it automatically.

Any values that overrun the edges of the scenegraph get clamped to the scenegraph area, so you don't have to worry about going outside the allowed area. Also, the scenegraph is centered at 0. In most cases you can just create it with the scale you want (number of sectors/size of the area you want covered) and then insert your entities based on their actual x,z positions.

Strict

Rem
bbdoc:
EndRem
Type TSceneGraph
	Field grid:TMap[,]
	Field size
	Field scale:Float
	Field nodes:TMap=New TMap
	
	Method sector:TMap(grid_x,grid_y)
		grid_x=Max(0,grid_x)
		grid_x=Min(size-1,grid_x)
		grid_y=Max(0,grid_y)
		grid_y=Min(size-1,grid_y)
		If Not grid[grid_x,grid_y] grid[grid_x,grid_y]=New TMap
		Return grid[grid_x,grid_y]
	EndMethod
	
EndType

Rem
bbdoc:
EndRem
Function CreateSceneGraph:TSceneGraph(size,scale#=1.0)
	Local graph:TSceneGraph=New TSceneGraph
	Local grid:TMap[size,size]
	graph.grid=grid
	graph.size=size
	graph.scale=scale
	Return graph
EndFunction

Rem
bbdoc:
EndRem
Function InsertSceneNode(graph:TSceneGraph,o:Object,grid_x,grid_y)
	grid_x=grid_x*graph.scale+graph.size/2
	grid_y=grid_Y*graph.scale+graph.size/2
	Local map:TMap=TMap(MapValueForKey(graph.nodes,o))
	If map MapRemove(map,o)
	If Not graph.grid[grid_x,grid_y] graph.grid[grid_x,grid_y]=New TMap
	graph.grid[grid_x,grid_y].insert o,o
	MapInsert graph.nodes,o,graph.grid[grid_x,grid_y]
EndFunction

Rem
bbdoc:
EndRem
Function RemoveSceneNode(graph:TSceneGraph,o:Object)
	Local map:TMap=TMap(MapValueForKey(graph.nodes,o))
	If map
		MapRemove(map,o)
		MapRemove(graph.nodes,o)
	EndIf
EndFunction

Rem
bbdoc:
EndRem
Function ForEachSceneNodeDo(graph:TSceneGraph,grid_x,grid_y,width,height,Callback:Int(o:Object))
	Local x,y
	Local o:Object
	
	grid_x=Floor(grid_x*graph.scale)+graph.size/2
	grid_y=Floor(grid_y*graph.scale)+graph.size/2
	width=Ceil(width*graph.scale)
	height=Ceil(height*graph.scale)
	
	If grid_x>graph.size-1 Return
	If grid_y>graph.size-1 Return
	If width<=0 Or height<=0 Return
	If grid_x<0
		width:+grid_x
		grid_x=0
	EndIf
	If grid_y<0
		height:+grid_y
		grid_y=0
	EndIf
	If grid_x+width>graph.size-1 width=graph.size-1-grid_x
	If grid_y+height>graph.size-1 height=graph.size-1-grid_y
	
	For x=grid_x To grid_x+width
		For y=grid_y To grid_y+height
			If graph.grid[x,y]
				For o=EachIn graph.grid[x,y].values()
					If Callback(o)=False Return
				Next
			EndIf
		Next
	Next
	
EndFunction




'---------------------------------------------------------
' Test Program
'---------------------------------------------------------

Graphics 512,512,0

Local list:TList=New TList

Type Point
	Field x,y
EndType

Local sectors=8
Local points=10000

Local scale#=sectors/512.0

Local graph:TSceneGraph=CreateSceneGraph(sectors,scale)

Global scenex,sceney

Local p:point

For Local n=1 To points
	p=New point
	p.x=Rand(0,511)
	p.y=Rand(0,511)
	InsertSceneNode(graph,p,p.x-256,p.y-256)
	list.addfirst(p)
Next

Local modename$="Scenegraph"

Global size=128,hsize

MoveMouse GraphicsWidth()/2,GraphicsHeight()/2

Global FPSLASTUPDATETIME

Local mode,time

While Not KeyHit(KEY_ESCAPE)

	If AppTerminate() End
	
	Cls()
	
	scenex=MouseX()
	sceney=MouseY()
	
	If KeyHit(KEY_MINUS) size=Max(10,size-10)
	If KeyHit(KEY_EQUALS) size:+10

	hsize=size/2
	
	Select mode
	Case 0
		ForEachSceneNodeDo(graph,scenex-hsize-256,sceney-hsize-256,size,size,Callback)
	Case 1
		For p=EachIn list
			If pointinrect(p.x,p.y,scenex-hsize,sceney-hsize,size,size) Plot p.x,p.y
		Next
	EndSelect
	
	If KeyHit(KEY_SPACE)
		mode=Not mode
		Select mode
		Case 0 modename$="Scenegraph"
		Case 1 modename$="Linear"
		EndSelect
	EndIf
	
	time=MilliSecs()
	
	SetColor 255,255,255
	DrawText "UPS: "+FPS(),0,0
	DrawText "Mode: "+modename,0,20
	DrawText "space: toggle mode",0,40
	DrawText "-/+: change rect size",0,60
	Flip 0
	
	FPSLASTUPDATETIME=FPSLASTUPDATETIME+(MilliSecs()-time)

Wend

End

Function Callback:Int(o:Object)
	Local p:Point=Point(o)
	If Not pointinrect(p.x,p.y,scenex-hsize,sceney-hsize,size,size) Return 1
	Plot p.x,p.y
	Return 1
EndFunction

Function PointInRect:Int(x0,y0,x1,y1,w,h)
	If x0<x1 Return 0
	If y0<y1 Return 0
	If x0>x1+w Return 0
	If y0>y1+h Return 0
	Return 1
EndFunction

Function FPS#(frequency=200)
	Global FPSFRAMECOUNT
	Global FPSLASTCOUNT#
	Local time=MilliSecs()
	FPSFRAMECOUNT=FPSFRAMECOUNT+1
	Local elapsed#=time-FPSLASTUPDATETIME
	If elapsed>=frequency
		FPSLASTCOUNT=FPSFRAMECOUNT/elapsed*1000.0
		FPSFRAMECOUNT=0
		FPSLASTUPDATETIME=time
	EndIf
	Return FPSLASTCOUNT
End Function