Multiple Cycles through Multi-Dimensional Array

This is a discussion on Multiple Cycles through Multi-Dimensional Array within the C Programming forums, part of the General Programming Boards category; I have a problem. I'm trying to write a program to take user-input data points (as one would have on ...

  1. #1
    Registered User
    Join Date
    Nov 2008
    Posts
    38

    Multiple Cycles through Multi-Dimensional Array

    I have a problem. I'm trying to write a program to take user-input data points (as one would have on a standard Cartesian graph ... you know, (x, y) etc.), a user-input number of sides (n), a user-input average side length (d), and a user-input margin of error (e), and have the program return the number of unique (or even non-unique... I'm not picky) polygons with n sides of length d+/-e.

    So far, the program correctly sorts out all the pairs of points whose distance is within d+/-e, and stores the names of those points (A, B, etc.) to the two-dimensional array segment. Thus, if the distance AB was in the range of d+/-e, then segment[0][0] = 'A' and segment[0][1] = 'B'.

    What the program doesn't do correctly is to cycle through all the segments in segment and pick ends that match. When it's done cycling through all possibilities, it should list all the possible "polygons" whose n sides are each length d+/-e ... except that what it actually does is print off a subset of the segments that meet the "segment" criteria and then cheerfully exclaim that there aren't any polygons that are formed from those segments.

    What am I doing wrong? Can anyone help me so that I don't have to write if/then statements for every n? Thanks!

    Code:
    #include <stdio.h>
    #include <conio.h>
    #include <math.h>
    
    float distance(int* x, int* y, int i, int j);
    
    main(){
           int number_of_points, number_of_sides;
           int i,j,k,t;
           float avg_side_length, variation;
    
           printf("How many points are to be considered?: ");
           scanf("%d", &number_of_points);
           
           while (number_of_points < 4){
                 printf("\nCannot generate polygons with the number of points given.\n\n");
                 printf("How many points are to be considered?: ");
                 scanf("%d", &number_of_points);
                 }
           
           printf("How many sides should each polygon have?: ");
           scanf("%d", &number_of_sides);
           
           while ((number_of_sides < 2) || (number_of_sides > number_of_points)){
                 printf("\nCannot generate polygons with %d sides.\n\n", number_of_sides);
                 printf("How many sides should each polygon have?: ");
                 scanf("%d", &number_of_sides);
                 }
                 
           printf("What is the length of an average side?: ");
           scanf("%f", &avg_side_length);
           
           printf("How much variation (in terms of percent) are allowed?: ");
           scanf("%f", &variation);
           
           float var = (variation/100.0);
           
           int x[number_of_points];
           int y[number_of_points];
           char index[number_of_points];
           float segment_length;
           int segments_printed = 0;
           int polygons_printed = 0;
           char segment[(number_of_points*(number_of_points-1)*2)][3];
           char polygon[number_of_sides+1];
           
           for (i=0; i<number_of_sides; i++){
               polygon[i] = ' ';
               }
           polygon[number_of_sides] = '\0';
           
           for (i=0; i<number_of_points; i++){
               if (i < 26)
                  index[i] = (i + 65);
               else if ( (26 <= i) && (i < 52) )
                    index[i] = (i + 71);
               else if ( (52 <= i) && (i < 67) )
                    index[i] = (i + 172);
               else if ( (67 <= i) && (i < 71) )
                    index[i] = (i - 32);
               else if ( (71 <= i) && (i < 81) )
                    index[i] = (i - 23);
               else if ( (i == 81) )
                    index[i] = 64;
               else
                   index[i] = (i + 46);
               }
           
           printf("\n\nFor each point, list the x- and y-coordiates as an ordered pair.\n[Ex., A(x,y): 2,4 ]\n");
           for (i=0; i<number_of_points; i++){
               printf("%c(x,y): ", index[i]);
               scanf("%d,%d", &x[i], &y[i]);
               }
    
           printf("\n\n");
           printf("SEGMENTS\n========\n");
    
           for (i=0; i<number_of_points; i++){
               for (j=(i+1); j<number_of_points; j++){
                   segment_length = distance(x, y, i, j);
                   if ( ((1.00 - var)*(avg_side_length) <= segment_length) && 
                        (segment_length <= (1.00 + var)*(avg_side_length)) ){
                        segment[segments_printed][0] = index[i];
                        segment[segments_printed][1] = index[j];
                        segment[segments_printed][2] = '\0';
                        segments_printed++;
                        }
                   }
               }
           if (segments_printed == 0){
              printf("No segments found within %d percent.\n", variation);
              }
           
           int i_bin, j_bin;
           for (i=0; i<segments_printed; i++){
               for (i_bin=0; i_bin<2; i_bin++){
                   polygon[0] = segment[i][i_bin];
                   polygon[1] = segment[i][((i_bin+1)%2)];
                   polygon[2] = '\0';
                   t = 2;
                   for (j=0; j<segments_printed; j++){
                       for (j_bin=0; j_bin<2; j_bin++){
                           if (segment[j][j_bin] == polygon[(t-1)]){
                                if (i == j){
                                      break;
                                      }
                                for (k=0; k<t, t<=number_of_sides; k++){
                                    if (polygon[k] == segment[j][((j_bin+1)%2)]){
                                       break;
                                       }
                                    if (polygon[k] != segment[j][((j_bin+1)%2)]){
                                       polygon[t] = segment[j][((j_bin+1)%2)];
                                       t++;
                                       j = 0;
                                       j_bin = 0;
                                       }
                                    if (t > number_of_sides){
                                       if (polygon[0] == polygon[t-1]){
                                          polygon[t-1] = '\0';
                                          printf("%s\n", polygon);
                                          polygons_printed++;
                                          t-=2;
                                          }
                                       }
                                    }
                                }
                           }
                       }
                   }
               }
           
           if (polygons_printed == 0){
              printf("No polygons of %d sides found within %f percent.\n", number_of_sides, variation);
              }
           else{
               printf("%d %d-sided polygons found.\n", polygons_printed, number_of_sides);
               }
    
           getch();
    
           while (1){
                 printf("\n");
                 
                 printf("How many sides should each polygon have?: ");
                 scanf("%d", &number_of_sides);
           
                 while ((number_of_sides < 2) || (number_of_sides > number_of_points)){
                       printf("\nCannot generate polygons with %d sides.\n\n", number_of_sides);
                       printf("How many sides should each polygon have?: ");
                       scanf("%d", &number_of_sides);
                       }
                 
                 printf("What is the length of an average side?: ");
                 scanf("%f", &avg_side_length);
           
                 printf("How much variation (in terms of percent) are allowed?: ");
                 scanf("%f", &variation);
           
                 var = (variation/100.0);
                 segments_printed = 0;
                 polygons_printed = 0;
                 
                 for (i=0; i<number_of_sides; i++){
                     polygon[i] = ' ';
                     }
                 polygon[number_of_sides] = '\0';
    
                 printf("\n\n");
                 printf("SEGMENTS\n========\n");
    
                 for (i=0; i<number_of_points; i++){
                     for (j=(i+1); j<number_of_points; j++){
                         segment_length = distance(x, y, i, j);
                         if ( ((1.00 - var)*(avg_side_length) <= segment_length) && 
                              (segment_length <= (1.00 + var)*(avg_side_length)) ){
                              printf("%c%c\n", index[i], index[j]);
                              segments_printed++;
                              }
                         }
                     }
                 if (segments_printed == 0){
                    printf("No segments found within %d percent.\n", variation);
                    }
                 
                 for (i=0; i<segments_printed; i++){
                     for (i_bin=0; i_bin<2; i_bin++){
                         polygon[0] = segment[i][i_bin];
                         polygon[1] = segment[i][((i_bin+1)%2)];
                         polygon[2] = '\0';
                         t = 2;
                         for (j=0; j<segments_printed; j++){
                             for (j_bin=0; j_bin<2; j_bin++){
                                 if (segment[j][j_bin] == polygon[(t-1)]){
                                    if (i == j){
                                       break;
                                       }
                                    for (k=0; k<t, t<=number_of_sides; k++){
                                        if (polygon[k] == segment[j][((j_bin+1)%2)]){
                                           break;
                                           }
                                        if (polygon[k] != segment[j][((j_bin+1)%2)]){
                                           polygon[t] = segment[j][((j_bin+1)%2)];
                                           t++;
                                           j = 0;
                                           j_bin = 0;
                                           }
                                        if (t > number_of_sides){
                                           if (polygon[0] == polygon[t-1]){
                                              polygon[t-1] = '\0';
                                              printf("%s\n", polygon);
                                              polygons_printed++;
                                              t-=2;
                                              }
                                           }
                                        }
                                    }
                                 }
                             }
                         }
                     }
                     
                 if (polygons_printed == 0){
                    printf("No polygons of %d sides found within %f percent.\n", number_of_sides, variation);
                    }
                 else{
                      printf("%d %d-sided polygons found.\n", polygons_printed, number_of_sides);
                      }
               
                 getch();
                 }
              }
           
    float distance(int* x, int* y, int i, int j){
         return ( sqrt( pow((y[i] - y[j]),2) + pow((x[i] - x[j]),2) ) );
         }

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Your title is right -- you are trying to find cycles (in the graph formed by the proper edges). So use any particular cycle-finding algorithm you care to use. Tarjan maybe, or Kosaraju. You'll have to use a proper data structure first, I would guess.

    However, we're not considering the geometry -- what if my sides cross each other? That's not a polygon, but you don't seem to have a way to tell.

  3. #3
    Registered User
    Join Date
    Nov 2008
    Posts
    38
    Indeed, I am trying to find cycles. How astute of you!

    I will be manually validating all returned polygons to guarantee that they are, in fact, polygons (and not, as you suggested, overlapping segments). I just don't care to draw out the graphs of all the individual segments given to me by the program to determine what sets of 4, 5, 6, etc. segments form a cycle.

    That's all I really want the program to do: just spit me out a list of candidates so that I don't have to manually check all possible segments in my range.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Problem within multi dimensional array
    By lolguy in forum C Programming
    Replies: 5
    Last Post: 12-26-2008, 08:02 AM
  2. question about multidimensional arrays
    By richdb in forum C Programming
    Replies: 22
    Last Post: 02-26-2006, 09:51 AM
  3. Dynamic Mutli dimensional Array question.
    By fatdunky in forum C Programming
    Replies: 6
    Last Post: 02-22-2006, 07:07 PM
  4. two dimensional string array question
    By Hoser83 in forum C Programming
    Replies: 8
    Last Post: 02-07-2006, 08:15 PM
  5. string into 2 dimensional array - basic stuff
    By mellisa in forum C++ Programming
    Replies: 11
    Last Post: 01-18-2003, 03:08 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21