palette sorter

[Kelly Lynn Martin <kelly@xxxxxxxxxxxxxxxxxxxxxxxxx>]

In a fit of boredom today, I wrote a palette sorter for my gradient
generator.  This seems to work pretty well, so I thought I'd share.

Really bad C code follows.  

Kelly

~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

#include <stdio.h>

#define MAXV 1024
#define MAXE (MAXV*MAXV/2)

struct _Vert {
  double r, g, b;
  short component;
  short incount;
} vert[MAXV];

struct _Edge {
  short v1, v2;
  double dist;
} edge[MAXE];

int selected[MAXV];

int newpalette[MAXV];

int nvert, nedge;

int
edge_compare (struct _Edge *e1, struct _Edge *e2)
{
  if      (e1->dist < e2->dist) return -1;
  else if (e1->dist > e2->dist) return 1;
  else                          return 0;
}

double
colordist (struct _Vert *v1, struct _Vert *v2)
{
  double r = v1->r - v2->r;
  double g = v1->g - v2->g;
  double b = v1->b - v2->b;

  return (r*r)+(g*g)+(b*b);
}

int
main (int argc, char **argv)
{
  double r, g, b;
  int edgecursor;
  int i;
  int start, next;
  int count;

  nvert = 0;
  nedge = 0;

  while (scanf("%lf %lf %lf", &r, &g, &b) != EOF) {
    int i = nvert;
    int j;

    vert[i].r = r;
    vert[i].g = g;
    vert[i].b = b;
    vert[i].component = nvert;
    vert[i].incount = 0;
    nvert++;
    for (j=0; j<i; j++) {
      int k = nedge;
      edge[k].v1 = i; edge[k].v2 = j;
      edge[k].dist = colordist(&(vert[i]), &(vert[j]));
      nedge++;
    }
  }

  qsort(edge, nedge, sizeof(edge[0]), &edge_compare);

  count = nvert-1;
  edgecursor = 0;

  while (count) {
    int delcomp, keepcomp;
    int e = edgecursor++;
    int a = edge[e].v1;
    int b = edge[e].v2;
    if (vert[a].component == vert[b].component ||
	vert[a].incount > 1 ||
	vert[b].incount > 1) continue;
    vert[a].incount++;
    vert[b].incount++;

    selected[--count] = e;

    keepcomp = vert[a].component;
    delcomp  = vert[b].component;

    for (i=0; i<nvert; i++) {
      if (vert[i].component == delcomp) vert[i].component = keepcomp;
    }
  }

  for (i=0; i<nvert; i++) {
    if (vert[i].incount < 2) {
      start = i; break;
    }
  }

  for (count = nvert-1; count; count--) {
    next = -1;
    for (i = 0; i<nvert; i++) {
      if (selected[i] == -1) {
	continue;
      } else if (edge[selected[i]].v1 == start) {
	next = edge[selected[i]].v2; break;
      } else if (edge[selected[i]].v2 == start) {
	next = edge[selected[i]].v1; break;
      }
    }
    if (next == -1) abort();
    selected[i] = -1;
    newpalette[count] = start;
    start = next;
  }

  newpalette[0] = start;

  for (i = nvert-1; i; i--) {
    printf("%d %lg %lg %lg\n", 
	   newpalette[i],
	   vert[newpalette[i]].r,
	   vert[newpalette[i]].g,
	   vert[newpalette[i]].b);
  }

}