Jump to content

  • Log In with Google      Sign In   
  • Create Account

Searching horizontal / vertical lines in 2D arrays


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
4 replies to this topic

#1 Manabreak   Members   -  Reputation: 141

Like
0Likes
Like

Posted 17 March 2012 - 12:29 PM

Heya,

I've got a bit of a problem that I can't figure out. I have 2D arrays of arbitrary sizes, and they contain characters like 'a', 'b', 'c' and so on. I need to break the arrays down into individual horizontal and vertical lines of the same characters, while a single character is only in one "partial array."

For example, let's concider this array:

  0 1 2 3 4 . . .
0 a a a a a
1   a
2   a a a a
3   a
4   a
.
.

Now, the result I want would be something like this:


Array 1:
  0 1 2 3 4
0 a a a a a
1
2
3
4

Array 2:
  0 1 2 3 4
0
1   a
2   a
3   a
4   a

Array 3:
  0 1 2 3 4
0
1
2     a a a
3
4

These arrays would of course be converted into coordinate lists for smaller memory. I've tried to think through this for a while, but can't really find any practical ways to do so. Any help is appreciated. Posted Image

Sponsor:

#2 Álvaro   Crossbones+   -  Reputation: 13316

Like
1Likes
Like

Posted 17 March 2012 - 01:10 PM

Loop through every row counting how many equal 'a's you have found. Remember the maximum so far and where it was. Do the same thing column by column. Now take the place where the maximum was achieved, write down the corresponding line and remove it from the data. Rinse, repeat.

This might not be very fast, but it will at least serve as a basic implementation to get you going. You can speed it up a lot by remembering the places where you found the longest rows. Also, your example doesn't allow me to tell if you are OK describing a cross as two lines, or if you would rather describe it as one column and two rows, because you don't want to repeat the intersection. In any case, there are ways to make the process fast and I am sure you'll find them.

#3 Manabreak   Members   -  Reputation: 141

Like
0Likes
Like

Posted 17 March 2012 - 01:16 PM

Loop through every row counting how many equal 'a's you have found. Remember the maximum so far and where it was. Do the same thing column by column. Now take the place where the maximum was achieved, write down the corresponding line and remove it from the data. Rinse, repeat.

This might not be very fast, but it will at least serve as a basic implementation to get you going. You can speed it up a lot by remembering the places where you found the longest rows. Also, your example doesn't allow me to tell if you are OK describing a cross as two lines, or if you would rather describe it as one column and two rows, because you don't want to repeat the intersection. In any case, there are ways to make the process fast and I am sure you'll find them.


The speed is not important since it won't be done runtime. The cross would indeed be one column and two rows (or vice versa), because a single char can only be part of a single line.

I didn't quite understand your suggestion, but it may just be my awful after-flu-stupidity and tiredness, hopefully I'll get it clear tomorrow with a bright mind. :D

#4 Álvaro   Crossbones+   -  Reputation: 13316

Like
1Likes
Like

Posted 17 March 2012 - 04:22 PM

Something like this:
#include <iostream>

bool get_longest_line(char array[5][5], int &x, int &y, int &dx, int &dy, int &length) {
  length = 0;
  for (int j=0; j<5; ++j) {
    int current_length = 0;
    for (int i=0; i<5; ++i) {
      current_length = array[j][i] == 'a' ? current_length+1 : 0;
      if (current_length > length) {
length = current_length;
x = i-length+1;
y = j;
dx = 1;
dy = 0;
      }
      else
current_length = 0;
    }
  }
  for (int i=0; i<5; ++i) {
    int current_length = 0;
    for (int j=0; j<5; ++j) {
      current_length = array[j][i] == 'a' ? current_length+1 : 0;
      if (current_length > length) {
length = current_length;
x = i;
y = j-length+1;
dx = 0;
dy = 1;
      }
    }
  }
  return length > 0;
}

int main () {
  char array[5][5] = {
    {'a','a','a','a','a'},
    {' ','a',' ',' ',' '},
    {' ','a','a','a','a'},
    {' ','a',' ',' ',' '},
    {' ','a',' ',' ',' '}
  };

  int x, y, dx, dy, length;

  while (get_longest_line(array, x, y, dx, dy, length)) {
    std::cout << '(' << x << ',' << y << ") d=("
     << dx << ',' << dy << ')' << length << '\n';
    for (int i=0; i<length; ++i)
      array[y+i*dy][x+i*dx] = ' ';
  }
}


#5 Manabreak   Members   -  Reputation: 141

Like
0Likes
Like

Posted 17 March 2012 - 11:39 PM

Gee, thanks for the code! I also got some advice from Daniweb, which will produce even distribution for horizontal and vertical segments. Thank :)




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS