Math Monday's

BlitzMax Forums/BlitzMax Programming/Math Monday's

coffeedotbean

(Posted 2013) [#1]

Hope somebody more math savvy can come up with an elegant solution to this.

I have an array of values as below but I want to check if a chosen value is in one of four quadrants, top left/right, bottom left/right.

For example, 08=top left, 26=top right,22=bottom right

The main issue is the array of number can be any size so the method needs to take into account this. The only information about this array of numbers I have is how many rows and columns there are.

top left    top right
          #
 |01|07|13#19|25|31
 |02|08|14#20|26|32
 |03|09|15#21|27|33
####################
 |04|10|16#22|28|34
 |05|11|17#23|29|35
 |06|12|18#24|30|36
          #
bot. left   bot. right

Derron

(Posted 2013) [#2]

I don't know "magic equations" atm but a simplistic approach is:

pseudocode:

for x = left to right
  for y = top to bottom
    if value[x,y] = searchedValue
      isLeft = x < (right-left)/2
      isTop = y < (top-bottom)/2

      if isLeft and isTop then return TopLeft
      if not isLeft and isTop then return TopRight
      if isLeft and not isTop then return BottomLeft
      if not isLeft and not isTop then return BottomRight
    endif
  next
next

If you know the coords in the array (your "x,y") then instead of the for loops just do the one in the middle

bye
Ron

coffeedotbean

(Posted 2013) [#3]

@Derron ah yes should have said I don't know the x:y, what I do know is the how many rows high and wide it is but that's it.

Brucey

(Posted 2013) [#4]

but a simplistic approach is

Heh ;-)

SuperStrict

Framework BRL.StandardIO

' assume a square

Const TOPLEFT:Int = 0
Const BOTTOMLEFT:Int = 1
Const TOPRIGHT:Int = 2
Const BOTTOMRIGHT:Int = 3

Local width:Int = 6
Local height:Int = 6

Local array:Int[] = BuildArray(width, height)

PrintQuadrant(15, array, width, height)
PrintQuadrant(16, array, width, height)
PrintQuadrant(21, array, width, height)
PrintQuadrant(22, array, width, height)



Function LocateQuadrant:Int(num:Int, arr:Int[], width:Int, height:Int)
	
	' 0 indexed array
	num :- 1

	Local y:Int = num Mod width
	Local x:Int = (num  - y) / width

	If x < width/2 Then
		If y < height/2 Then
			Return TOPLEFT
		Else
			Return BOTTOMLEFT
		End If
	Else
		If y < height/2 Then
			Return TOPRIGHT
		Else
			Return BOTTOMRIGHT
		End If
	End If
	
End Function


Function PrintQuadrant(num:Int, arr:Int[], width:Int, height:Int)
	Local quad:Int = LocateQuadrant(num, arr, width, height)
	
	Local s:String = num + " is in the "
	Select quad
		Case TOPLEFT
			s:+ "top left"
		Case BOTTOMLEFT
			s:+ "bottom left"
		Case TOPRIGHT
			s:+ "top right"
		Case BOTTOMRIGHT
			s:+ "bottom right"
	End Select
	
	Print s + " quadrant"
End Function

' utils
Function BuildArray:Int[](width:Int, height:Int)

	Local arr:Int[] = New Int[width * height]
	
	Local i:Int
	For Local x:Int = 0 Until width
		For Local y:Int = 0 Until height
			i :+ 1
			
			arr[x * width + y] = i
		Next
	Next
	
	PrintArray(arr, width, height)
	
	Return arr
End Function

Function PrintArray(arr:Int[], width:Int, height:Int)

	Print ""

	For Local y:Int = 0 Until height
	
		Local s:String = ""
		
		For Local x:Int = 0 Until width
		
			Local num:String = "   " + arr[x * width + y]
			
			s:+ num[num.length - 3..]
			
			If x = (width - 1) / 2 Then
				s:+"#"
			Else
				s:+"|"
			End If
		
		Next
		
		Print s
		
		If y = (height -1) / 2 Then
			s = ""
			For Local x:Int = 0 Until width
				s:+ "####"
			Next
			Print s
		End If
		
	Next

	Print ""
End Function

coffeedotbean

(Posted 2013) [#5]

O.o thanks Brucey - I'll check this out tonight when I get home.

Derron

(Posted 2013) [#6]

@Brucey:

I don't think your code will work well: I assume coffeedotbean wants and has:

having: a number which is unique and stored somewhere in the array
wants: the quadrant.

That is why my "super algorithm" (aka "derrons xy-traversal") checks each array-element for being equal to the searched one.

If you have to do such "find a special part" really often, and such special parts are not that often, you better have another list/map/array just holding the specials.
Instead of accessing them by "x,y => typeID" you better store "typeID => x,y" as you will then just have to "x,y = get(typeID) ".

bye
Ron

edit: @brucey: your printarray-function ignores the "top left / top right / ..."-labels. You should provide a diff file for handy patching.

Brucey

(Posted 2013) [#7]

having: a number which is unique and stored somewhere in the array

Indeed, but based on the original information provided, it solves the problem.

And indeedly, the only other way - given some random number in an array - is to search for it and then apply the LocateQuadrant() function on the resulting array index (+1).

your printarray-function ignores the "top left / top right / ..."-labels

I had considered the labels, but thought I'd leave a little imagination to the reader :-p

coffeedotbean

(Posted 2013) [#8]

Hi guys, I think Brucey's method will work, the numbers in the array will always be in sequence and never random values, I probably should have explained that.

col	(Posted 2013) [#9]

Hey guys,

I just tried Bruceys method and it works very well except that it breaks when using non square shapes for the array, do you even want non-square? You didn't mention it.

For eg.. to see the bugs change the width to 8 and keep the height 6, or change them the other way.

Sorry, I feel a bit of a dick right now as I'm saying Bruceys code doesn't work and I'm not even offering a solution. I really don't have time to even look through the code! I'd guess it's only something very minor though as is it working already.

Then again, do you even want non-square grid shapes of the array?

coffeedotbean

(Posted 2013) [#10]

No I actually do need it square so all is well, be nice to have the flexibility of none-square but I'll cross that bridge if and when.

Floyd

(Posted 2013) [#11]

I worked this out before looking to see what Brucey's code actually did. But I'll contribute an explanation.

A little thought reveals a surprising fact. We can find row and column numbers easily knowing just the number of rows.

row = 1  +  ( N - 1 ) Mod nRows
col = 1  +  ( N - 1 ) / nRows

Here's the idea. The rows are presumably numbered 1,2...nRows and the columns 1,2...nCols.
Each "cell" is identified with a number in the range 1,2...nRows*nCols.

This is all much easier if everything is zero based, so rows are 0,1,2... as are columns and cell numbers. That's why I use N-1, and then add back 1 to get row and column numbers.

Anyway, using this scheme and an example with four rows the numbers are originally

0 4 8
1 5 9
2 6 10 ... we can continue to the right for any number of columns
3 7 11

Notice the first row is 0 4 8 12 16 etc.
Dividing by 4 gives 0 1 2 3 4 which are the column numbers.
We get exactly the same result with lower rows because integer division discards the remainder, which will always be less than 4.

Reading down the first column we see 0 1 2 3, which are row numbers.
The second column is just the first with 4 added to everything. So "Mod 4" turns it into the first column.

To answer the original question, we decide whether N is in the top or bottom half of the rows by comparing the row number with nRows/2.
Likewise we compare col with nCols/2. This is the only place we need to use the number of columns.

Brucey

(Posted 2013) [#12]

One other thing.

Unless you need the array for something else, you don't actually need the array.

Given a square of a specific dimension, you can simply calculate where the number is likely to fall within the square and return the quadrant from those parameters.

coffeedotbean

(Posted 2013) [#13]

That's a really fiendish solution Floyd and works a treat. Thanks.

Derron

(Posted 2013) [#14]

Omfg... when reading the first posting I did not recognize the increasing number ("downwards") - and thought of it being random...

Else it is like when accessing memory blocks... you can just "mod" your row or col value when knowing one width/height (that is the power of multiplication : 3x5 = 15 and therefor 15/5 is 3 ...).

So sorry for my "traversal" approach.

bye
Ron

Brucey

(Posted 2013) [#15]

So sorry for my "traversal" approach.

Still works though :-)

coffeedotbean

(Posted 2013) [#16]

@ Brucey I have no doubt your solution works and thanks for taking the time to post it much appreciated, have a virtual HI-5!

Brucey

(Posted 2013) [#17]

Thanks, but I meant Derrons' traversal approach still works :-p

H&K	(Posted 2013) [#18]

c = 1 * ( X > Xmid) + 2 *( Y > YMid)