Code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include <math.h>
#include "combination.h"
float distance(int* x, int* y, int i, int j);
int choose(int x, int y);
int indexCompare(const void*, const void*);
main(){
int number_of_points, number_of_sides;
int i, j, k;
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 vertex[number_of_points];
int edges = 0;
float length;
char edge_string[(number_of_sides*2)+1];
int polygons_found = 0;
int count = 0;
char edge_index_name[(number_of_points)*(number_of_points-1)/2][3];
int *combination = (int *)malloc(number_of_sides * sizeof(int));
int **edge_matrix = (int **)malloc((number_of_points*(number_of_points-1)/2) * sizeof(int *));
/* Label all vertices publicly */
for (i=0; i<number_of_points; i++){
if (i < 26)
vertex[i] = (i + 65);
else if ( (26 <= i) && (i < 52) )
vertex[i] = (i + 71);
else if ( (52 <= i) && (i < 67) )
vertex[i] = (i + 172);
else if ( (67 <= i) && (i < 71) )
vertex[i] = (i - 32);
else if ( (71 <= i) && (i < 81) )
vertex[i] = (i - 23);
else if ( (i == 81) )
vertex[i] = 64;
else
vertex[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): ", vertex[i]);
scanf("%d,%d", &x[i], &y[i]);
}
printf("\n");
/* Count the number of edges for structure matrix */
for (i=0; i<number_of_points; i++){
for (j=i; j<number_of_points; j++){
length = distance(x, y, i, j);
if ( ((1.00 - var)*(avg_side_length) <= length) &&
(length <= (1.00 + var)*(avg_side_length)) ){
edge_index_name[edges][0] = vertex[i];
edge_index_name[edges][1] = vertex[j];
edge_index_name[edges][2] = '\0';
edges++;
}
}
}
if (edges == 0){
printf("No segments found within %f percent.\n", variation);
}
if ((edges < number_of_sides) && (edges != 0)){
printf("Not enough viable segments in graph.\n");
}
if (edges >= number_of_sides){
for (i=0; i<(number_of_points*(number_of_points-1)/2); i++){
edge_matrix[i] = (int *)malloc(number_of_sides * sizeof(int));
}
for (i=0; i<number_of_sides; i++){
combination[i] = i;
edge_matrix[0][i] = i;
}
j = 1;
while (next_comb(combination, number_of_sides, edges)){
for (i=0; i<number_of_sides; i++){
edge_matrix[j][i] = combination[i];
}
j++;
}
}
for (i=0; i<choose(edges, number_of_sides); i++){
for (j=0; j<number_of_sides; j++){
if (j == 0){
strncpy(edge_string, edge_index_name[edge_matrix[i][j]],2);
}
if (j > 0){
strncat(edge_string, edge_index_name[edge_matrix[i][j]],2);
}
}
qsort(edge_string, number_of_sides*2, sizeof(edge_string[0]), indexCompare);
for (k=0; k<(number_of_sides*2); k+=2){
if (edge_string[k] == edge_string[k+1]){
count++;
}
}
if (count == number_of_sides){
for (k=0; k<(number_of_sides*2); k+=2){
printf("%c",edge_string[k]);
polygons_found++;
}
printf("\n");
count = 0;
}
}
printf("\n%d %d-sided polygons found.", polygons_found, number_of_sides);
getch();
/* Endless loop for utilizing the same data set */
while (1){
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);
polygons_found = 0;
edges = 0;
count = 0;
combination = (int *)realloc((char *)combination, number_of_sides * sizeof(int));
printf("\n");
/* Count the number of edges for structure matrix */
for (i=0; i<number_of_points; i++){
for (j=i; j<number_of_points; j++){
length = distance(x, y, i, j);
if ( ((1.00 - var)*(avg_side_length) <= length) &&
(length <= (1.00 + var)*(avg_side_length)) ){
edge_index_name[edges][0] = vertex[i];
edge_index_name[edges][1] = vertex[j];
edge_index_name[edges][2] = '\0';
edges++;
}
}
}
if (edges == 0){
printf("No segments found within %f percent.\n", variation);
}
if ((edges < number_of_sides) && (edges != 0)){
printf("Not enough viable segments in graph.\n");
}
if (edges >= number_of_sides){
for (i=0; i<(number_of_points*(number_of_points-1)/2); i++){
edge_matrix[i] = (int *)realloc((char *)edge_matrix[i], number_of_sides * sizeof(int));
}
for (i=0; i<number_of_sides; i++){
combination[i] = i;
edge_matrix[0][i] = i;
}
j = 1;
while (next_comb(combination, number_of_sides, edges)){
for (i=0; i<number_of_sides; i++){
edge_matrix[j][i] = combination[i];
}
j++;
}
}
for (i=0; i<choose(edges, number_of_sides); i++){
for (j=0; j<number_of_sides; j++){
if (j == 0){
strncpy(edge_string, edge_index_name[edge_matrix[i][j]],2);
}
if (j > 0){
strncat(edge_string, edge_index_name[edge_matrix[i][j]],2);
}
}
qsort(edge_string, number_of_sides*2, sizeof(edge_string[0]), indexCompare);
for (k=0; k<(number_of_sides*2); k+=2){
if (edge_string[k] == edge_string[k+1]){
count++;
}
}
if (count == number_of_sides){
for (k=0; k<(number_of_sides*2); k+=2){
printf("%c",edge_string[k]);
polygons_found++;
}
printf("\n");
count = 0;
}
}
printf("\n%d %d-sided polygons found.", polygons_found, 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) ) );
}
int choose(int x, int y){
if (x < y){
return 0;
}
int i;
int term1 = 1;
int term2 = 1;
int term3 = 1;
for (i=1; i<=x; i++){
term1 *= i;
}
for (i=1; i<=y; i++){
term2 *= i;
}
for (i=1; i<=(x-y); i++){
term3 *= i;
}
return (term1/(term2*term3));
}
int indexCompare(const void* element1, const void* element2){
if (*(const char*)element1 > *(const char*)element2){
return 1;
}
if (*(const char*)element1 == *(const char*)element2){
return 0;
}
if (*(const char*)element1 < *(const char*)element2){
return -1;
}
}