Programming Forums > Community Forums > Coder's Corner Lounge

Wizard1988 · Oct 19th, 2007, 10:04 PM

I am writing a program where I have a grid (16x16) of squares which are 25 by 25 units. Each square is separated from other squares by 4 units. The squares coordinates start at 4 in the top left corner.

My problem is that I want to be able to tell which square contains a given point. For example the point (35,8) would be in square (2,1)

I know I could look thought the array of the squares and use the contains method, but I don't think that would a very good way to do this. So I have been trying to come up with an expression which could be used to figure this out without having to use a loop. I tried using the modulus operator but I'm having a hard time.

Any help would be greatly appreciated.

DaWei · Oct 19th, 2007, 10:45 PM

Your problem probably stems from the fact that you have space between the units. This means that you have some no-man's land that doesn't qualify. Try a two-tiered approach: reject certain ranges around certain multiples, then zero in on the remainder.

OpenLoop · Oct 20th, 2007, 10:28 AM

check rows first (x coordinate) , then check columns(y coordinate) using this:

(63,12):
Check row:
A = 63 / 25 = 2.5 = 3 (change to the next whole number)
63 - 3*4 = 51
B = 51 / 25 = 2.04 = 3 (change to the next whole number)

Since A = B, then the point is in the 3rd row of the grid.
Do the same for the column:
12 / 25 = 1
12 - 1*4 = 8
8 / 25 = 1

Now we know the point is in the 3rd row, 1st column. That's the third square.

If A is not equal to be, then the point is out of range:
(61,12)
A = 61/25 = 3
61 - 3*4 = 49 out
B = 49 / 25 = 2

I haven't test it this mutch, so let me know if it works.

SamReidHughes · Oct 20th, 2007, 12:33 PM

Convert coordinates to square number by computing the following pseudocode algorithm:

(Toggle Plain Text)

if (coord `mod` 29 >= 4)
  then (1 + coord `div` 29)
       -- added one because your unholy square numbers start at 1, not 0.
  else (error "we're in between squares")

You need to find what 29-unit interval it's in, by dividing by 29, and you also need to check if the coordinate is in the part of the interval that comprises your squares, by moduloing it.

WaltP · Oct 20th, 2007, 1:08 PM

Quote:

Originally Posted by Wizard1988

I am writing a program where I have a grid (16x16) of squares which are 25 by 25 units. Each square is separated from other squares by 4 units. The squares coordinates start at 4 in the top left corner.

So each square is effectively 29x29, with the lowest 4 units unused. A simple equation can be designed to test for correct placement, using the % operator.

grimpirate · Oct 20th, 2007, 2:22 PM

Wrote up this little php code snippet which does what you want so the algorithm should hold in whatever language it is you want to implement (no real language dependent functions or anything except for floor())

(Toggle Plain Text)

<?php
$borderWidth = 4;
$squareWidth = 25;
$locationX = 35;
$locationY = 8;
$outerBorderOffset = $borderWidth / 2;
$locationX -= $outerBorderOffset;
$locationY -= $outerBorderOffset;
$squareLocationX = $locationX % ($squareWidth + $borderWidth);
$squareLocationY = $locationY % ($squareWidth + $borderWidth);
if($squareLocationX >= $outerBorderOffset && $squareLocationX < ($squareWidth + $outerBorderOffset)){
	$squareLocationX = floor($locationX / ($squareWidth + $borderWidth));
	$squareLocationX++;
}else{
	$squareLocationX = 'border';
}
if($squareLocationY >= $outerBorderOffset && $squareLocationY < ($squareWidth + $outerBorderOffset)){
	$squareLocationY = floor($locationY / ($squareWidth + $borderWidth));
	$squareLocationY++;
}else{
	$squareLocationY = 'border';
}
echo '(' . $squareLocationX . ',' .$squareLocationY . ')';
?>

Oct 19th, 2007, 10:04 PM	#1
Wizard1988 Professional Programmer Join Date: Oct 2005 Location: Chitown Posts: 417 Rep Power: 3	Weird math problem I am writing a program where I have a grid (16x16) of squares which are 25 by 25 units. Each square is separated from other squares by 4 units. The squares coordinates start at 4 in the top left corner. My problem is that I want to be able to tell which square contains a given point. For example the point (35,8) would be in square (2,1) I know I could look thought the array of the squares and use the contains method, but I don't think that would a very good way to do this. So I have been trying to come up with an expression which could be used to figure this out without having to use a loop. I tried using the modulus operator but I'm having a hard time. Any help would be greatly appreciated. __________________ JG-Webdesign

Oct 19th, 2007, 10:45 PM	#2
DaWei Resident Grouch Join Date: Jun 2005 Posts: 6,453 Rep Power: 10	Re: Weird math problem Your problem probably stems from the fact that you have space between the units. This means that you have some no-man's land that doesn't qualify. Try a two-tiered approach: reject certain ranges around certain multiples, then zero in on the remainder. __________________ Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code. Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

Oct 20th, 2007, 10:28 AM	#3
OpenLoop Expert Programmer Join Date: May 2005 Location: East Lansing, MI Posts: 663 Rep Power: 4	Re: Weird math problem check rows first (x coordinate) , then check columns(y coordinate) using this: (63,12): Check row: A = 63 / 25 = 2.5 = 3 (change to the next whole number) 63 - 34 = 51 B = 51 / 25 = 2.04 = 3 (change to the next whole number) Since A = B, then the point is in the 3rd row of the grid. Do the same for the column: 12 / 25 = 1 12 - 14 = 8 8 / 25 = 1 Now we know the point is in the 3rd row, 1st column. That's the third square. If A is not equal to be, then the point is out of range: (61,12) A = 61/25 = 3 61 - 3*4 = 49 out B = 49 / 25 = 2 I haven't test it this mutch, so let me know if it works.

Oct 20th, 2007, 12:33 PM	#4
SamReidHughes Newbie Join Date: Oct 2007 Posts: 13 Rep Power: 0	Re: Weird math problem Convert coordinates to square number by computing the following pseudocode algorithm: (Toggle Plain Text) if (coord `mod` 29 >= 4) then (1 + coord `div` 29) -- added one because your unholy square numbers start at 1, not 0. else (error "we're in between squares") if (coord `mod` 29 >= 4) then (1 + coord `div` 29) -- added one because your unholy square numbers start at 1, not 0. else (error "we're in between squares") You need to find what 29-unit interval it's in, by dividing by 29, and you also need to check if the coordinate is in the part of the interval that comprises your squares, by moduloing it.

Oct 20th, 2007, 2:22 PM	#6
grimpirate King of Portal Join Date: Sep 2005 Posts: 419 Rep Power: 4	Re: Weird math problem Wrote up this little php code snippet which does what you want so the algorithm should hold in whatever language it is you want to implement (no real language dependent functions or anything except for floor()) (Toggle Plain Text) <?php $borderWidth = 4; $squareWidth = 25; $locationX = 35; $locationY = 8; $outerBorderOffset = $borderWidth / 2; $locationX -= $outerBorderOffset; $locationY -= $outerBorderOffset; $squareLocationX = $locationX % ($squareWidth + $borderWidth); $squareLocationY = $locationY % ($squareWidth + $borderWidth); if($squareLocationX >= $outerBorderOffset && $squareLocationX < ($squareWidth + $outerBorderOffset)){ $squareLocationX = floor($locationX / ($squareWidth + $borderWidth)); $squareLocationX++; }else{ $squareLocationX = 'border'; } if($squareLocationY >= $outerBorderOffset && $squareLocationY < ($squareWidth + $outerBorderOffset)){ $squareLocationY = floor($locationY / ($squareWidth + $borderWidth)); $squareLocationY++; }else{ $squareLocationY = 'border'; } echo '(' . $squareLocationX . ',' .$squareLocationY . ')'; ?> <?php $borderWidth = 4; $squareWidth = 25; $locationX = 35; $locationY = 8; $outerBorderOffset = $borderWidth / 2; $locationX -= $outerBorderOffset; $locationY -= $outerBorderOffset; $squareLocationX = $locationX % ($squareWidth + $borderWidth); $squareLocationY = $locationY % ($squareWidth + $borderWidth); if($squareLocationX >= $outerBorderOffset && $squareLocationX < ($squareWidth + $outerBorderOffset)){ $squareLocationX = floor($locationX / ($squareWidth + $borderWidth)); $squareLocationX++; }else{ $squareLocationX = 'border'; } if($squareLocationY >= $outerBorderOffset && $squareLocationY < ($squareWidth + $outerBorderOffset)){ $squareLocationY = floor($locationY / ($squareWidth + $borderWidth)); $squareLocationY++; }else{ $squareLocationY = 'border'; } echo '(' . $squareLocationX . ',' .$squareLocationY . ')'; ?> __________________ Lo, there do I see my father. 'Lo, there do I see My mother, and my sisters, and my brothers. 'Lo, there do I see The line of my people... Back to the beginning. 'Lo, they do call to me. They bid me take my place among them. In the halls of Valhalla... Where the brave... May live... ...forever.. GrimBB \| Mimesis

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Some weird Yahoo! problem	java_roshan	Coder's Corner Lounge	10	May 3rd, 2006 3:40 AM
Computer Science Prereqs - Math	bigguy	Coder's Corner Lounge	22	Mar 15th, 2006 12:19 AM
weird problem with find(Redhat 9)	InfoGeek	Coder's Corner Lounge	12	Jan 12th, 2006 10:56 AM
Weird Problem	Sane	Python	0	Dec 15th, 2005 12:56 PM
Math problem	sparda	C	10	Nov 5th, 2005 7:33 PM

Programming Forums > Community Forums > Coder's Corner Lounge

Weird math problem