Thread: 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) ) );
     }

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.

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.