0

i got an 8x8 Array and want to convert it into an 1d array with 64 fields. But in this special zig zag order:

enter image description here

I want the smart way but i don't have a clue. I got two possible theories but they are not smart. Any idea?

3
  • 1
    maybe this would help..for each diagonal line, the sum of the indices will be constant..and the direction flips..should be able to comup up with a generic loop for this.
    – PeskyGnat
    Aug 15, 2011 at 12:04
  • Don't judge a book by it's cover. Anyway if you don't want to contribute some productive ideas then avoid such comments.
    – vo1d
    Aug 15, 2011 at 12:06
  • 1
    "I got two possible theories but they are not smart." Tell us about them! Otherwise someone might suggest the same solutions you already have. Aug 15, 2011 at 12:07

3 Answers 3

5

Have an array with 64 entries that holds the indexes in the order that the zig-zag pattern would visit them. You'd probably use them as offsets from some buffer. This is for JPEG stuff right?

int[] zigzag = {0, 1, 8, 16, 9, 2, ... etc};
3
  • This was one of my ideas but i think there a smarter ways. Yes, it's jpeg encoding.
    – vo1d
    Aug 15, 2011 at 12:12
  • Fair enough, but you should be careful. You might be dipping your toes into the world of patents. Any reference code I've seen uses this method, in the real world this is all normally done by hardware.
    – James
    Aug 15, 2011 at 12:16
  • Comment after edit: This is much better then my two ideas. I was thinking the other way. Thank you very much. @James: It's just a trivial PoC it will not be used or published to the public.
    – vo1d
    Aug 15, 2011 at 12:24
2

You can try this: when you start, you take 1 step to the right, and then take a diagonal move in the only direction that permits diagonals (at first this is south-west), and loop all the way till the column[0]. The you move 1 step down (use a flag to check if you took 1 step to the right previously, and you can only move down if this flag was true before; you can change this flag to false and change the down flag to true) and again take a diagonal in the only permitted direction (north-east) till you hit row[0]. This will be fine till AC[70], as there is no down move. At this point, reset both flags for right and down to false and restart the process.

3
  • 1
    This was exactly my second idea but the other one is in my opinion better because its done in 5 Minutes and you find the indices array via google =) Thanks
    – vo1d
    Aug 15, 2011 at 13:18
  • true, but the other one does not generalise for all arrays. you will find that the above method is better if you want to do this for arrays which have dimensions other than 8 X 8. if speed is your concern, then by all means... Aug 15, 2011 at 13:23
  • 1
    @troll, this is why you should have explained the two ways you'd already thrown out. It seems you've wasted the time of others because they posted the ideas you'd dismissed.
    – Paul
    Aug 15, 2011 at 13:45
1

For the help of anyone google searching and can't find an answer, here's a simple perl algorithm I came up with to solve the problem.

sub getPos{
    my ($x,$y,$size)=@_;
    my $d = $x+$y;
    my $m = $d-$size;
    my $p = (($d%2)?$x:$y);
    my $dist = ($d*($d+1))/2;
    my $index = $dist + $p;
    if($d >= $size){
        $index -= ($m+1)**2;
    }
    return $index;
}

And you use it like this:

for(my $x = 0; $x < $size; $x++){
    for(my $y = 0; $y < $size; $y++){
        $OneArray[getPos($x, $y, $size)] = $TwoArray[$x][$y];
    }
}

Where $OneArray is the 1D array you're converting $TwoArray to.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.