# Algorithm Help - Grid Space Calculations

**URL:** <https://www.ruby-forum.com/t/algorithm-help-grid-space-calculations/84798>\
**Category:** Ruby\
**Created:** [February 7, 2007, 7:15pm UTC](https://www.ruby-forum.com/t/algorithm-help-grid-space-calculations/84798 "2007-02-07T19:15:18Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![phrogz](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/p/2acd7d/32.png) [@phrogz](https://www.ruby-forum.com/u/phrogz)\
**Post date:** [February 7, 2007, 7:15pm UTC](https://www.ruby-forum.com/t/algorithm-help-grid-space-calculations/84798/1 "2007-02-07T19:15:18Z")

</div>

I have a problem, and I’m hoping someone will find it interesting  
enough to understand it and come up with a better/more direct  
solution. I’d claim that I need more coffee, but I don’t _drink_  
coffee. The mental failings are all my own. 😉

If you’ve worked with a 3D modeler before, imagine an orthographic  
editing camera. Behind the model a grid of lines is drawn. The camera  
is rendering a particular section of the world to a window on your  
screen.

As you zoom the camera in and out, the grid of lines needs to change  
placement to continue representing the same spot in the world. As you  
resize the window that the camera is rendering to, the placement also  
needs to change.

Like Modo and unlike Maya, I want our orthographic grid to  
automatically change scale as it crosses certain thresholds. If it  
gets too small (the lines are too close together), I want the scale of  
the grid to double - get rid of half the lines. If it gets too large  
(the lines are too far apart) I want the scale of the grid to half -  
draw lines in-between the existing lines. This should occur if the  
user is zooming the camera in and out, or if the user is resizing the  
window.[1]

Below is some Ruby code that reflects what I want to do. It’s non-  
ideal because it uses loops to get to the value I want. I feel that  
there ought to be a simple one-line formula that calculates what I  
want, using rounding or truncation or modding…but I can’t quite  
grasp what it should be.

The particularly complicating factor is that the answer depends on the  
current grid size, since for most camera/window combinations there is  
a pair of grid sizes that would satisfy the conditions. In these  
cases, I want to use the grid size closest to the current grid size  
(which is the same size, when possible). The last set of assertions  
covers this case.

Anyone got a bright idea?

BASE\_GRID\_SIZE = 40

def grid\_size( world\_width, pixel\_width )  
pixels\_per\_unit = pixel\_width / world\_width  
px\_per\_grid\_line = $grid\_spacing \* pixels\_per\_unit  
while px\_per\_grid\_line \> BASE\_GRID\_SIZE \* 2  
$grid\_spacing /= 2  
px\_per\_grid\_line /= 2  
end  
while px\_per\_grid\_line \< BASE\_GRID\_SIZE / 2  
$grid\_spacing \*= 2  
px\_per\_grid\_line \*= 2  
end  
puts "A %dcm wide camera mapped to %dpx " %  
[world\_width,pixel\_width] +  
"will have a grid every %dcm " % [$grid\_spacing] +  
"drawn every %.2f pixels, " % [px\_per\_grid\_line] +  
“resulting in %.2f lines being drawn.” % [pixel\_width/  
px\_per\_grid\_line]  
$grid\_spacing  
end

require ‘test/unit/assertions’  
include Test::Unit::Assertions

begin  
# Use a global to handle overlapping legal ranges  
$grid\_spacing = BASE\_GRID\_SIZE

```
# Changing window size
assert_equal( BASE_GRID_SIZE, grid_size( 400.0, 400 ) )
assert_equal( BASE_GRID_SIZE*2, grid_size( 400.0, 190 ) )
assert_equal( BASE_GRID_SIZE/2, grid_size( 400.0, 810 ) )
assert_equal( BASE_GRID_SIZE/2, grid_size( 400.0, 1200 ) )
assert_equal( BASE_GRID_SIZE/2, grid_size( 400.0, 1600 ) )
assert_equal( BASE_GRID_SIZE/4, grid_size( 400.0, 1601 ) )

# Changing camera zoom
assert_equal( BASE_GRID_SIZE, grid_size( 420.0, 400 ) )
assert_equal( BASE_GRID_SIZE, grid_size( 790.0, 400 ) )
assert_equal( BASE_GRID_SIZE*2, grid_size( 810.0, 400 ) )

# Overlapping range test
assert_equal( BASE_GRID_SIZE*2, grid_size( 1595.0, 400 ) )
assert_equal( BASE_GRID_SIZE*4, grid_size( 1610.0, 400 ) )
assert_equal( BASE_GRID_SIZE*4, grid_size( 1595.0, 400 ) )
assert_equal( BASE_GRID_SIZE*4, grid_size( 810.0, 400 ) )
assert_equal( BASE_GRID_SIZE*2, grid_size( 790.0, 400 ) )
assert_equal( BASE_GRID_SIZE*2, grid_size( 400.0, 400 ) )
assert_equal( BASE_GRID_SIZE, grid_size( 399.0, 400 ) )
assert_equal( BASE_GRID_SIZE, grid_size( 790.0, 400 ) )

```

rescue Test::Unit::AssertionFailedError =\> e  
puts e  
end

[1] I’m not really sure I like having the window resizing change the  
grid size, but for the purposes of this discussion and the code, I’m  
leaving that requirement in there.

---

<div class="post-metadata">

**Author:** ![phrogz](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/p/2acd7d/32.png) [@phrogz](https://www.ruby-forum.com/u/phrogz)\
**Post date:** [February 7, 2007, 7:50pm UTC](https://www.ruby-forum.com/t/algorithm-help-grid-space-calculations/84798/2 "2007-02-07T19:50:22Z")

</div>

I haven’t fully read your code other than to get a general sense of  
what it is you’re trying to do. And since you double or halve the  
spacing until it meets certain constraints, it looks to me like you’re  
ultimately trying to solve a problem like this:

```
2 ** x == y

```

Where you know y but do not know x. Such a problem can be solved with  
logarthims.

```
x * log(2) == log(y)

x == log(y) / log(2)

```

Once you derive x, you can then do a ceiling, floor, round, etc.  
depending on what your preference is.

So the puzzle for you is can you turn the problem you’re trying to  
solve into the form:

```
2 ** x == y ?

```

For example, maybe y would be some formula involving the base grid and  
40, which seems to be a key number to you?

Good luck,

Eric

---

<div class="post-metadata">

**Author:** ![phrogz](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/p/2acd7d/32.png) [@phrogz](https://www.ruby-forum.com/u/phrogz)\
**Post date:** [February 7, 2007, 8:26pm UTC](https://www.ruby-forum.com/t/algorithm-help-grid-space-calculations/84798/3 "2007-02-07T20:26:26Z")

</div>

Here you go:

include Math

BASE\_GRID\_SIZE = 40

def lg2(a)  
log(a) / log(2)  
end

def grid\_size( world\_width, pixel\_width )  
ppu = pixel\_width / world\_width  
factor = 2 \*\* lg2(ppu).ceil  
low = BASE\_GRID\_SIZE / factor  
high = low \* 2  
$grid\_spacing = ($grid\_spacing - high).abs \< ($grid\_spacing -  
low).abs ? high : low

px\_per\_grid\_line = $grid\_spacing \* ppu

puts "A %dcm wide camera mapped to %dpx " % [world\_width,pixel\_width]  
+  
"will have a grid every %dcm " % [$grid\_spacing] +  
"drawn every %.2f pixels, " % [px\_per\_grid\_line] +  
“resulting in %.2f lines being drawn.” % [pixel\_width/  
px\_per\_grid\_line]  
$grid\_spacing  
end

require ‘test/unit/assertions’  
include Test::Unit::Assertions

begin

# Use a global to handle overlapping legal ranges

$grid\_spacing = BASE\_GRID\_SIZE

# Changing window size

assert\_equal( BASE\_GRID\_SIZE, grid\_size( 400.0, 400 ) )  
assert\_equal( BASE\_GRID\_SIZE\*2, grid\_size( 400.0, 190 ) )  
assert\_equal( BASE\_GRID\_SIZE/2, grid\_size( 400.0, 810 ) )  
assert\_equal( BASE\_GRID\_SIZE/2, grid\_size( 400.0, 1200 ) )  
assert\_equal( BASE\_GRID\_SIZE/2, grid\_size( 400.0, 1600 ) )  
assert\_equal( BASE\_GRID\_SIZE/4, grid\_size( 400.0, 1601 ) )

# Changing camera zoom

assert\_equal( BASE\_GRID\_SIZE, grid\_size( 420.0, 400 ) )  
assert\_equal( BASE\_GRID\_SIZE, grid\_size( 790.0, 400 ) )  
assert\_equal( BASE\_GRID\_SIZE\*2, grid\_size( 810.0, 400 ) )

# Overlapping range test

assert\_equal( BASE\_GRID\_SIZE_2, grid\_size( 1595.0, 400 ) )  
assert\_equal( BASE\_GRID\_SIZE_4, grid\_size( 1610.0, 400 ) )  
assert\_equal( BASE\_GRID\_SIZE_4, grid\_size( 1595.0, 400 ) )  
assert\_equal( BASE\_GRID\_SIZE_4, grid\_size( 810.0, 400 ) )  
assert\_equal( BASE\_GRID\_SIZE_2, grid\_size( 790.0, 400 ) )  
assert\_equal( BASE\_GRID\_SIZE_2, grid\_size( 400.0, 400 ) )  
assert\_equal( BASE\_GRID\_SIZE, grid\_size( 399.0, 400 ) )  
assert\_equal( BASE\_GRID\_SIZE, grid\_size( 790.0, 400 ) )  
rescue Test::Unit::AssertionFailedError =\> e  
puts e  
end

martin

---

<div class="post-metadata">

**Author:** ![phrogz](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/p/2acd7d/32.png) [@phrogz](https://www.ruby-forum.com/u/phrogz)\
**Post date:** [February 7, 2007, 9:13pm UTC](https://www.ruby-forum.com/t/algorithm-help-grid-space-calculations/84798/4 "2007-02-07T21:13:36Z")

</div>

On 2/8/07, Phrogz [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> factor in particular). And even though you transcribed into Ruby what  
> I wrote in English with the “nearest to the current setting”  
> constraint, for some reason I couldn’t come up with it.

That was where I really missed the oft-requested min\_by:

$grid\_spacing = [high, low].min\_by {|i| ($grid\_spacing - i).abs}

but I felt defining it for that one use would be overkill 🙂

martin

---

<div class="post-metadata">

**Author:** ![phrogz](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/p/2acd7d/32.png) [@phrogz](https://www.ruby-forum.com/u/phrogz)\
**Post date:** [February 7, 2007, 8:35pm UTC](https://www.ruby-forum.com/t/algorithm-help-grid-space-calculations/84798/5 "2007-02-07T20:35:27Z")

</div>

On Feb 7, 12:25 pm, “Martin DeMello” [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> Here you go:  
> [snip]  
> ppu = pixel\_width / world\_width  
> factor = 2 \*\* lg2(ppu).ceil  
> low = BASE\_GRID\_SIZE / factor  
> high = low \* 2  
> $grid\_spacing = ($grid\_spacing-high).abs \< ($grid\_spacing-low).abs ? high : low  
> [snip]

Excellent, thanks! 🙂

The logarithm stuff is exactly what was needed (translating it to a  
factor in particular). And even though you transcribed into Ruby what  
I wrote in English with the “nearest to the current setting”  
constraint, for some reason I couldn’t come up with it.

---

<div class="post-metadata">

**Author:** ![phrogz](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/p/2acd7d/32.png) [@phrogz](https://www.ruby-forum.com/u/phrogz)\
**Post date:** [February 7, 2007, 9:20pm UTC](https://www.ruby-forum.com/t/algorithm-help-grid-space-calculations/84798/6 "2007-02-07T21:20:37Z")

</div>

On Feb 7, 1:13 pm, “Martin DeMello” [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> That was where I really missed the oft-requested min\_by:
> 
> $grid\_spacing = [high, low].min\_by {|i| ($grid\_spacing - i).abs}
> 
> but I felt defining it for that one use would be overkill 🙂

Though it would be computationally inefficient compared to what it  
could be, you could of course get the same functionality with:  
[high,low].sort\_by{ |i| ($grid\_spacing-i).abs }[0]

---

<div class="post-metadata">

**Author:** ![phrogz](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/p/2acd7d/32.png) [@phrogz](https://www.ruby-forum.com/u/phrogz)\
**Post date:** [February 7, 2007, 9:27pm UTC](https://www.ruby-forum.com/t/algorithm-help-grid-space-calculations/84798/7 "2007-02-07T21:27:38Z")

</div>

On 2/8/07, Phrogz [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> On Feb 7, 1:13 pm, “Martin DeMello” [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:
> 
> > That was where I really missed the oft-requested min\_by:
> > 
> > $grid\_spacing = [high, low].min\_by {|i| ($grid\_spacing - i).abs}
> > 
> > but I felt defining it for that one use would be overkill 🙂
> 
> Though it would be computationally inefficient compared to what it  
> could be, you could of course get the same functionality with:  
> [high,low].sort\_by{ |i| ($grid\_spacing-i).abs }[0]

True, but it would hurt to do that 🙂

martin