There are doubters everywhere, so I produce an additional example.
64 possible outcomes with four vertices (count them up, there really are 64 figures above). Here's the code I used to build these SVG's
(
To write a generic algorithm capable of producing all possible polygons given arbitrary number of vertices at the command line, I had to come up with
yet another formula. This one is fairly straightfoward. To get coordinates for the polygon's vertices, given radius
R, center point
(
Cx,
Cy), then all you need to do is iterate function
V(
index,
number of vertices) where:
Again, I don't have a proof for this, but based on my trigonometric scribblings on scrap paper I'm sure it's good to go.
The software required a rethinking, and I'm not 100% satisfied with it because of some floating-point arithmetic-related
rounding errors, but overall it handles fairly well.
Source and
32-bit Windows EXE are available
and I've also uploaded some test pages:
Triangles,
Squares, and
Pentagons.
A review of the XHTML source will reveal the rounding error that is taking place. I do not know an effective means of correcting this.
#define _USE_MATH_DEFINES
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <limits.h>
#include <string.h>
const char * baseSvgFull = "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"yes\"?>\n\
<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\" \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n\
<svg xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\" width=\"100px\" height=\"100px\">\n";
const char * baseSvg = "<svg xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\" width=\"100px\" height=\"100px\">\n";
const char * endSvg = "</svg>";
const char * usage = "Usage: polygon.exe [decimal # of vertices, must be > 2]\n";
const unsigned short RADIUS = 35; // radius of the "circle" around which we build a polygon.
const unsigned short CIRCLE_X = 50; // center of circle in +X,+Y cartesian plane.
const unsigned short CIRCLE_Y = 50; // center of circle in +X,+Y cartesian plane.
char ** printable_vertices;
char ** printable_segments;
unsigned long sum_connections (const unsigned long n);
char * vertex (const unsigned long index, const unsigned long total, const unsigned short radius,
const unsigned short cx, const unsigned short cy, unsigned short * vx, unsigned short * vy);
char * segment (const unsigned short x1, const unsigned short y1, const unsigned short x2, const unsigned short y2);
void build_strings(const unsigned long vertices, const unsigned long connections, const unsigned short radius,
const unsigned short cx, const unsigned short cy);
void onClose(void);
/* modified to accept command line arguments for arbitrary number of sides */
int main(int argc, char *argv[])
{
/* figure = sequential ID for the figure we're drawing
edge = sequential ID for the edge of the figure, which we may or may not draw */
unsigned long figure, edge, vertices, connections, possibilities;
atexit(onClose);
if (argc > 1)
{
vertices = strtoul(argv[1], NULL, 10);
}
else
{
fprintf(stderr, "%s", usage);
return(EXIT_SUCCESS);
}
if (vertices < 3)
{
fprintf(stderr, "%s", usage);
return(EXIT_FAILURE);
}
/* overflow protection provided in method; 0 is a valid result */
connections = sum_connections(vertices);
build_strings(vertices, connections, RADIUS, CIRCLE_X, CIRCLE_Y);
/* calculate how many possible figures there are, but first
check that this won't cause overflow */
if (log(ULONG_MAX) / log(2) < connections)
{
fprintf(stderr, "Fatal error: <possibilities> overflow detected.\n");
exit(EXIT_FAILURE);
}
possibilities = (unsigned long) pow(2, connections);
#ifdef DEBUG
fprintf(stderr, "vertices=%d\nconnections=%d\npossibilities=%d\n", vertices, connections, possibilities);
#endif
/* iterate over total possible figures */
for (figure = 0; figure < possibilities; figure++)
{
printf("%s", baseSvg);
unsigned long print_vertices;
for (print_vertices = 0; print_vertices < vertices; print_vertices++)
{
printf("%s", printable_vertices[print_vertices]);
}
/* in this figure, consider each potential edge */
for (edge = 0; edge < connections; edge++)
{
/* is the edge's bit a 1 in the figure ID? */
if ((unsigned short) (1 << edge) & figure)
{
/* if so, draw it. */
printf("%s", printable_segments[edge]);
}
}
printf("%s\n\n", endSvg);
}
return(EXIT_SUCCESS);
}
/* Summation calculates how many connections are possible given polygon of vertices n.
Terminates program if overflow unavoidable. */
unsigned long sum_connections (unsigned long n)
{
unsigned long x = 0;
while (n > 0)
{
if (x > (x + --n))
{
fprintf(stderr, "Fatal error: <connections> overflow detected.\n");
exit(EXIT_FAILURE);
}
else
{
x += n;
}
}
return(x);
}
/* Calculates the vertex location given parameters. Saves x and y position in vx and vy.
Returns string representation formatted for SVG. */
char * vertex (const unsigned long index, const unsigned long total, const unsigned short radius,
const unsigned short cx, const unsigned short cy, unsigned short * vx, unsigned short * vy)
{
* vx = (unsigned short) (ceil(radius * cos(2.0f * M_PI * (double)index / (double)total)) + (double)cx);
* vy = (unsigned short) (ceil(radius * sin(2.0f * M_PI * (double)index / (double)total)) + (double)cy);
char * vertex = calloc(128, sizeof(char));
if (sprintf(vertex, " <circle cx=\"%d\" cy=\"%d\" r=\"5\" stroke=\"black\" stroke-width=\"2\" fill=\"black\" />\n", * vx, * vy) < 0)
{
fprintf(stderr, "Error creating string for vertex (%d, %d).\n", * vx, * vy);
perror("sprintf");
return(NULL);
}
return(vertex);
}
/* Calculates the line segment given two vertices. Returns string representation formatted for SVG. */
char * segment (const unsigned short x1, const unsigned short y1, const unsigned short x2, const unsigned short y2)
{
char * segment = calloc(128, sizeof(char)); // 128 should be "good enough" for most applications.
if (sprintf(segment, " <line x1=\"%d\" y1=\"%d\" x2=\"%d\" y2=\"%d\" style=\"stroke:rgb(99,99,99);stroke-width:5\" />\n", x1, y1, x2, y2) < 0)
{
fprintf(stderr, "Error creating string for segment (%d, %d)->(%d, %d).\n", x1, y1, x2, y2);
perror("sprintf");
return(NULL);
}
return(segment);
}
/* Create the vertices, in both integer and string formats.
Caching them like this should be considerably more efficient than
creating a new formatted string with each pass. */
void build_strings(const unsigned long vertices, const unsigned long connections, const unsigned short radius,
const unsigned short cx, const unsigned short cy)
{
unsigned short vertex_x[vertices];
unsigned short vertex_y[vertices];
char * vertex_s[vertices];
char * segment_s[connections];
unsigned short index_vertex, index_dst, index_segment;
/* create a string representation of each vertex */
for (index_vertex = 0; index_vertex < vertices; index_vertex++)
{
vertex_s[index_vertex] = vertex(index_vertex, vertices, radius, cx, cy,
(unsigned short *) &vertex_x[index_vertex], (unsigned short *) &vertex_y[index_vertex]);
#ifdef DEBUG
fprintf(stderr, "%s", vertex_s[index_vertex]);
#endif
}
/* create a string representation of each possible edge */
index_segment = 0;
for (index_vertex = 0; index_vertex < vertices - 1; index_vertex++)
{
for (index_dst = index_vertex + 1; index_dst < vertices; index_dst++) // ex: 1-2 1-3 2-3...the loop looks trickier than it is.
{
segment_s[index_segment++] = segment(vertex_x[index_vertex], vertex_y[index_vertex], vertex_x[index_dst], vertex_y[index_dst]);
#ifdef DEBUG
fprintf(stderr, "%s", segment_s[index_segment-1]);
#endif
}
}
printable_vertices = malloc(sizeof(vertex_s));
memcpy(printable_vertices, vertex_s, sizeof(vertex_s));
printable_segments = malloc(sizeof(segment_s));
memcpy(printable_segments, segment_s, sizeof(segment_s));
}
/* free up the allocated strings when application closes */
void onClose(void)
{
free(printable_vertices);
free(printable_segments);
}