How to determine the center of several points

BlitzMax Forums/BlitzMax Beginners Area/How to determine the center of several points

hub	(Posted 2011) [#1]

Hi !
i'm searching a fast method to determine the center m(x,y) of several p(x,y) points on the screen. (After this i need to rotate the p(x,y) points arround M)

Thanks !

GfK	(Posted 2011) [#2]

The easiest way is to iterate through all the points, and find the lowest and highest X and Y value for each; i.e. lowX, lowY, highX, highY.

You can then calculate the centre by working out the half way point between low and high;centreX = highX - ((highX-lowX) * 0.5), probably.

Once you've done that, in order to rotate the points around the centre you'll nee to know two things

1: The angle from the centre to each point. You can use Atan2() to calculate that.
2: The distance from centre to each point; d# = Sqr(((x2-x1)^2) + ((y2-y1)^2))

Bit busy now but I might write the code later if I get bored/can be bothered.

Last edited 2011

GfK	(Posted 2011) [#3]

I get bored quickly:

Strict

SeedRnd(MilliSecs())

Graphics 800,600

Global numPoints:Int = 10
Global pointList:TList
Global centreX:Int, centreY:Int

'make some random points
makePoints()

'find the centre
findCentre(centreX,centreY)

'find distance and angle
findVectors()

While (Not AppTerminate()) And (Not KeyDown(key_Escape))
	Cls
	turnDots()
	drawDots()
	Flip
Wend

Function makePoints()
	Local t:tPoint
	pointList = New TList
	For Local n:Int = 1 To numPoints
		t = New tPoint
		t.x = Rand(0,300) + 250
		t.y = Rand(0,300) + 150
		pointList.addlast(t)
	Next
End Function

Function findCentre(centreX:Int Var, centreY:Int Var)
	Local lowx:Int = 800
	Local lowy:Int = 600
	Local highx:Int = 0
	Local highy:Int = 0
	
	Local t:tPoint
	
	For t = EachIn pointList
		Select True
			Case t.x < lowx
				lowx = t.x
			Case t.x > highx
				highx = t.x
			Case t.y < lowy
				lowy = t.y
			Case t.y > highy
				highy = t.y
		End Select 
	Next
	
	centreX = highx - ((highx-lowx) * 0.5)
	centrey = highy - ((highy-lowy) * 0.5)
End Function

Function findVectors()
	Local t:tPoint
	
	For t = EachIn pointList
		t.angle = ATan2(centrey-t.y,centrex-t.x)
		t.dist = Sqr(((centrex-t.x)^2) + ((centrey-t.y)^2))
	Next
End Function

Function turnDots()
	Local t:tPoint
	For t = EachIn pointList
		t.angle:+1
		t.angle:Mod 360
		t.x = Cos(t.angle) * t.dist + centreX
		t.y = Sin(t.angle) * t.dist + centreY
	Next
End Function

Function drawDots()
	Local t:tPoint
	
	'draw the centre
	SetColor 255,0,0
	DrawOval(centrex-10,centrey-10,20,20)
	
	'draw the dots
	SetColor 255,255,0
	For t = EachIn pointList
		DrawOval(t.x-2,t.y-2,4,4)
	Next
End Function

Type tPoint
	Field x:Float
	Field y:Float
	Field dist:Float
	Field angle:Float
End Type

hub	(Posted 2011) [#4]

Very impressive by this Gfk. Nice code. Next is there a way to 'collapse' contract and 'expand' the points to the center (without rotation). You have a better math skill than myself !

Last edited 2011

GfK	(Posted 2011) [#5]

This version includes a tMultiplier object which you control with cursor left/right.

If you don't want rotation then just comment out the code that increments the angle value in turnDots().

Strict

SeedRnd(MilliSecs())

Graphics 800,600

Global numPoints:Int = 10
Global pointList:TList
Global centreX:Int, centreY:Int

Global multiplier:tMultiplier = New tMultiplier

'make some random points
makePoints()

'find the centre
findCentre(centreX,centreY)

'find distance and angle
findVectors()

While (Not AppTerminate()) And (Not KeyDown(key_Escape))
	Cls
	multiplier.update()
	turnDots()
	drawDots()
	Flip
Wend

Function makePoints()
	Local t:tPoint
	pointList = New TList
	For Local n:Int = 1 To numPoints
		t = New tPoint
		t.x = Rand(0,300) + 250
		t.y = Rand(0,300) + 150
		pointList.addlast(t)
	Next
End Function

Function findCentre(centreX:Int Var, centreY:Int Var)
	Local lowx:Int = 800
	Local lowy:Int = 600
	Local highx:Int = 0
	Local highy:Int = 0
	
	Local t:tPoint
	
	For t = EachIn pointList
		Select True
			Case t.x < lowx
				lowx = t.x
			Case t.x > highx
				highx = t.x
			Case t.y < lowy
				lowy = t.y
			Case t.y > highy
				highy = t.y
		End Select 
	Next
	
	centreX = highx - ((highx-lowx) * 0.5)
	centrey = highy - ((highy-lowy) * 0.5)
End Function

Function findVectors()
	Local t:tPoint
	
	For t = EachIn pointList
		t.angle = ATan2(centrey-t.y,centrex-t.x)
		t.dist = Sqr(((centrex-t.x)^2) + ((centrey-t.y)^2))
	Next
End Function

Function turnDots()
	Local t:tPoint
	For t = EachIn pointList
		t.angle:+1
		t.angle:Mod 360
		t.x = Cos(t.angle) * (t.dist * multiplier.value) + centreX
		t.y = Sin(t.angle) * (t.dist * multiplier.value) + centreY
	Next
End Function

Function drawDots()
	Local t:tPoint
	
	'draw the centre
	SetColor 255,0,0
	DrawOval(centrex-10,centrey-10,20,20)
	
	'draw the dots
	SetColor 255,255,0
	For t = EachIn pointList
		DrawOval(t.x-2,t.y-2,4,4)
	Next
End Function

Type tPoint
	Field x:Float
	Field y:Float
	Field dist:Float
	Field angle:Float
End Type

Type tMultiplier
	Field value:Float = 1
	
	Method update()
		If KeyDown(KEY_LEFT)
			Self.value:-0.01
			If Self.value < 0
				Self.value = 0
			EndIf
		EndIf
		If KeyDown(KEY_RIGHT)
			Self.value:+0.01
		EndIf
	End Method
End Type

Last edited 2011

H&K	(Posted 2011) [#6]

Function findCentre2(centreX:Int Var, centreY:Int Var)

	Local Totx:Int = 0
	Local Toty:Int = 0
	
	Local Cnt:Int = 0
	Local t:tPoint
	
	For t = EachIn pointList
		Cnt = Cnt + 1
		Totx = t.x + Totx
		Toty = t.y + Toty
	Next
	
	If Cnt > 0
		centreX = totx / Cnt
		centreY = toty / Cnt
	Else
		centreX = 0
		centreY = 0
	EndIf
	
End Function

Gfk You arnt finding the only centre of the Points, what you are doing is finding the centre of the most extreme points. That is if you had four points x-coor 100,40,40,0, your centre would be 50
The function above would give 45

X-coor 100,90,90,0 yours would give, 50
Mine would give 70

ImaginaryHuman

(Posted 2011) [#7]

Add them all up and divide?

H&K	(Posted 2011) [#8]

Add them all up and divide?

Yep
Well thats what mine does, (ie finds the Mean), what Gfks does is find half the range Plus the min. Both are valid "Centres"
Gfks would look most correct for images, mine most correct for centres of mass, (ish, that is it assumes all dots weight the same atm))

Last edited 2011

Warpy

(Posted 2011) [#9]

There are in fact loads of ways of defining the centre, even for just three points.

The centroid, H&K's one, is probably the best for what hub wants (assuming the points are fairly regularly spread out) because it will look 'balanced' when rotating.

hub	(Posted 2011) [#10]

Many thanks for your help. I've just finished to adapt this for my game and all is ok now. Note than i use h&k method to determine the center.

ima747

(Posted 2011) [#11]

These are some really valuable snippets, I hope they find their way into a tutorial or something for posterity as I will surely have lost this post by the next time I need them.

hub	(Posted 2011) [#12]

code archive ?