Initial commit

[pdp8.git] / sw / plot_hpgl / pc / optimize.c

#include <stdlib.h>
#include <string.h>
#include <math.h>


//#define DEBUG
#include "hpgl.h"

/*
 * Get plotting distance between points.
 * Distances of X and Y are calculated. The longer one
 * is returned. This applies to plotters that can do
 * diagonal steps. In that case the shorter distance is "hidden"
 * and doesn't consume time. If the plotter is unable to do diagonal
 * steps the sum of both distances must be returned.
 */
double plot_distance(struct point *a, struct point *b){
  //  double dist_x = (a->x>b->x?a->x-b->x:b->x-a->x);
  //double dist_y = (a->y>b->y?a->y-b->y:b->y-a->y);
  //return (dist_x > dist_y?dist_x:dist_y);  
  double dist_x = fabs(a->x - b->x);
  double dist_y = fabs(a->y - b->y);
  return (dist_x > dist_y ? dist_x:dist_y);  
}

static double path_distance(struct point *point, struct path *path){
  double forward_dist=plot_distance(point, path->first_point);
  double reverse_dist=plot_distance(point, path->last_point);

  if (reverse_dist < forward_dist){
    path->plot_start_point=path->last_point;
    path->plot_end_point=path->first_point;
    return reverse_dist;
  } else {
    path->plot_start_point=path->first_point;
    path->plot_end_point=path->last_point;
    return forward_dist;
  }
}

double OLDpath_distance(struct point *origin, struct path *candidate){
  double forward_dist=plot_distance(origin, candidate->first_point);
  double reverse_dist=plot_distance(origin, candidate->last_point);
  if (reverse_dist < forward_dist){
    candidate->plot_start_point=candidate->last_point;
    candidate->plot_end_point=candidate->first_point;
    return reverse_dist;
  } else {
    candidate->plot_start_point=candidate->first_point;
    candidate->plot_end_point=candidate->last_point;
    return forward_dist;
  }
}

int equal(struct point *a, struct point *b){
  if ((a==NULL)||(b==NULL)) return 0;
  if ((a->x == b->x) &&( a->y == b->y)) return 1;
  else return 0;
}

static void link_reverse(struct path *path){
  struct path *cur;
  if (!path) return;
  for (cur = path; cur->next; cur = cur->next)
    cur->next->back = cur;
}

static void remove_path(struct path **target, struct path *path){

  if (path == *target){ /* First element! */
    *target = path->next;
    return;
  }
  path->back->next = path->next;
  if (path->next)
    path->next->back = path->back;
}

struct path *optimize(struct path *input_list){
  struct point __point;
  __point.x=0;
  __point.y=0;

  struct point *point = &__point;
  struct path *result = NULL;
  struct path *result_last;
  struct path *cur, *best;
  int i;

  link_reverse(input_list);
  //  DBG("link_reverse done\n");

  i=0;
  for (cur = input_list; cur; cur = cur->next)
    DBG("%4i Input Path (%5.2f,%5.2f) -> (%5.2f,%5.2f)\n",
	   i++,
	   cur->plot_start_point->x,
	   cur->plot_start_point->y,
	   cur->plot_end_point->x,
	   cur->plot_end_point->y
	   );

  while(input_list) {
    best = NULL;
    for (cur = input_list; cur; cur = cur->next) {
      cur->dist = path_distance(point, cur);
      if ((!best)||(cur->dist < best->dist)) {
	best = cur;
	/*
	DBG("cur->dist = %5.2f, best->dist = %5.2f\n",
	       cur->dist, best->dist);
	DBG("Cur Path (%5.2f,%5.2f) -> (%5.2f,%5.2f)\n",
	   cur->plot_start_point->x,
	   cur->plot_start_point->y,
	   cur->plot_end_point->x,
	   cur->plot_end_point->y
	   );
	*/

      }
    }
    point = best->plot_end_point;

    DBG("xbest Path (%5.2f,%5.2f) -> (%5.2f,%5.2f)\n",
	   best->plot_start_point->x,
	   best->plot_start_point->y,
	   best->plot_end_point->x,
	   best->plot_end_point->y
	   );

    /* Take best result */
    remove_path(&input_list, best);

    if (!result) {
      result = best;
    } else {
      result_last->next = best;
    }
    result_last = best;
    result_last->next = NULL;
  }

#ifdef DEBUG
  i = 0;
  for (cur = result; cur; cur = cur->next)
    DBG("%4i Path (%5.2f,%5.2f) -> (%5.2f,%5.2f)\n",
	   i++,
	   cur->plot_start_point->x,
	   cur->plot_start_point->y,
	   cur->plot_end_point->x,
	   cur->plot_end_point->y
	   );
#endif

  return result;
}


struct path *single_stroke_path(struct point *a, struct point *b){
  struct path *result=(struct path *)malloc(sizeof(struct path));

  struct point *aa=(struct point *)malloc(sizeof(struct point));
  struct point *bb=(struct point *)malloc(sizeof(struct point));
  memcpy(aa,a,sizeof(struct point));
  memcpy(bb,b,sizeof(struct point));
  aa->next=bb;
  bb->next=NULL;
  aa->previous_in_path=NULL;
  bb->previous_in_path=aa;
  
  result->next=NULL;
  result->first_point=aa;
  result->plot_start_point=aa;
  result->last_point=bb;
  result->plot_end_point=bb;
  return result;
}


struct path *split_paths(struct path *source){
  struct path *result=NULL;
  struct path *last_result=NULL;
  
  struct path *current_path;
  for (current_path=source; current_path!=NULL; current_path=current_path->next){
    
    struct point *current_point;

    for (current_point=current_path->first_point; current_point->next!=NULL; 
	 current_point=current_point->next){
      struct path*tmp=single_stroke_path(current_point,current_point->next);
      if (result==NULL){
	result=tmp;
	last_result=tmp;
      } else { 
	last_result->next=tmp;
	last_result=last_result->next;
      }

    }
  }
  return result;
}


void round_path(struct path *source){
  struct path *current_path;
  for (current_path=source; current_path!=NULL; current_path=current_path->next){
        struct point *current_point;
	
    for (current_point=current_path->first_point; current_point!=NULL; 
	 current_point=current_point->next){
      current_point->x=round(current_point->x*100.0)/100.0;
      current_point->y=round(current_point->y*100.0)/100.0;
    }
  }
}