Grid/Map and how to calculate distance over different types of cells

[Etinnet]

Hey all,

I have a conceptual question. I have a 2-dimensional grid with on/off (0/1) values for every cell it.
What I would like to do is to calculate the distance covered over cells with a value 0 and the distance covered over cells with a value of 1 when moving (or tracing a line) between point A (with coordinates x1,y1) and B (with coordinates x2,y2).

Now, I know, that the calculation of the distance mathematically is the sqrt ((x1-x2)^2 + (y1-y2)^2 ) but I don't really know how to differentiate between the 1 and 0 values.

Anyone having an idea on how to do this?

Thanks a lot everyone!

[TrustyTony]

Check out my ball moving algorithm, you can speed it up, if you transform it recursive from destination expanding neighbours until whole grid is covered and then do the final iterations of the algorithm on whole grid.
http://www.daniweb.com/forums/post1202455.html#post1202455

To calculate distance on 1, consider 0 wall, and vice versa.

[woooee]

when moving (or tracing a line) between point A (with coordinates x1,y1) and B (with coordinates x2,y2).

If you know how to get from A to B, can't you count the number of grids as you go. Assuming that each grid is the same size, you can then multiply, or do you want to know how to trace a line between the two points as well?

[Etinnet]

Thanks for your replies! :)

More exactly, what I would like to do is: calculate the distance covered in cells which fulfill a given condition (for example =1). As the distance covered in every cell is potentially different (they are not necessarily crossed diagonally for example) this is more precise than calculating the number of cells crossed.

Any ideas on this?

[TrustyTony]

Any concrete data of input exists?

[Etinnet]

Sure. I just don't know how to post them here. It's a grid representing the world (with 360x360 cells) each cell "containing" (1 or 0).

[TrustyTony]

so you want straight path and one square is representing area which can be crosed on one path that crosses two sides of square and the length can be anything almost 0 (through corner) and sqrt(2) (through opposite corners)
You can attach files in advanced view through manage attachments button.

[Etinnet]

Alright, that's exactly it indeed.
I attached a file in this reply, thanks for the tip about attachments by the way :)

[TrustyTony]

I only tested the style of importing the data to Python and which kind of amounts of 0 and 1 it has. I saved it first tab delimited as I am not XML guru.

import pretty
data=[i.rstrip().split('\t') for i in open('testdatadaniweb.txt').readlines()]
data_noh=[ ''.join(x)       ## without headers as list of '01' strings
           for x in [
               d[1:] for d in data[1:]
               ]
           ]

print " %i x %i (%i cells) " % (len(data_noh),len(data_noh[0]),len(data_noh)*len(data_noh[0]))
for i in data_noh: print i
pretty.ppr('Statistics of 0 and 1 counts (0 count,1 count)')
pretty.ppr( [(x.count('0'),x.count('1')) for x in data_noh] )
print 'Total: ', "".join(data_noh).count('0'), ':', "".join(data_noh).count('1'),

[TrustyTony]

My basic idea for you is:
Do line formula
Solve it for each crossing of cell both x and y direction.
Register tag of next square entered by cell crossing to list
Multiply the tag info by string coefficient (or some trig function to be figured out, the line length mathematical formula for pieces)
Multiply by size of cell
Sum up for the tag you want.

This can also be done recursively:
first x and y crossing save info to totalling variables
do the function from this crossing until end of the string

There however we hit, however, the limited functionality of Python recursion (recursion limit), so better to do in a loop.

[Etinnet]

Great!:icon_cool: Thanks a lot for your help!!!

[TrustyTony]

You should not need to do the line formula again as you can solve the formula for point x=1, and multiply by the difference of x in crossing points (only change of scale).

[Etinnet]

Hey thanks again for your input everyone!

Just an additional question: If the map represents the Earth, how could I make sure that when passing the left (West) limit of the map, I end up on the right (East) side of it again? Anyone having any idea on this?

Cheers!

[TrustyTony]

What is value range. Basically usually we use modulo calculations. If we have values in range -180..180 (x+1)%360-180 to go east and (x+359)%360-180 west.

[TrustyTony]

Sorry, that post was without testing in reality you must also add 180 in brackets

>>> x=-180
>>> (x+1+180)%360-180
-179
>>> x=180
>>> (x+359+180)%360-180
179
>>> x=-180
>>> (x+359+180)%360-180 ## -1 -> 360-1=+359
179