sw/plot_hpgl/pc/optimize.c

   1 #include <stdlib.h>
   2 #include <string.h>
   3 #include <math.h>
   4
   5
   6 //#define DEBUG
   7 #include "hpgl.h"
   8
   9 /*
  10  * Get plotting distance between points.
  11  * Distances of X and Y are calculated. The longer one
  12  * is returned. This applies to plotters that can do
  13  * diagonal steps. In that case the shorter distance is "hidden"
  14  * and doesn't consume time. If the plotter is unable to do diagonal
  15  * steps the sum of both distances must be returned.
  16  */
  17 double plot_distance(struct point *a, struct point *b){
  18   //  double dist_x = (a->x>b->x?a->x-b->x:b->x-a->x);
  19   //double dist_y = (a->y>b->y?a->y-b->y:b->y-a->y);
  20   //return (dist_x > dist_y?dist_x:dist_y);
  21   double dist_x = fabs(a->x - b->x);
  22   double dist_y = fabs(a->y - b->y);
  23   return (dist_x > dist_y ? dist_x:dist_y);
  24 }
  25
  26 static double path_distance(struct point *point, struct path *path){
  27   double forward_dist=plot_distance(point, path->first_point);
  28   double reverse_dist=plot_distance(point, path->last_point);
  29
  30   if (reverse_dist < forward_dist){
  31     path->plot_start_point=path->last_point;
  32     path->plot_end_point=path->first_point;
  33     return reverse_dist;
  34   } else {
  35     path->plot_start_point=path->first_point;
  36     path->plot_end_point=path->last_point;
  37     return forward_dist;
  38   }
  39 }
  40
  41 double OLDpath_distance(struct point *origin, struct path *candidate){
  42   double forward_dist=plot_distance(origin, candidate->first_point);
  43   double reverse_dist=plot_distance(origin, candidate->last_point);
  44   if (reverse_dist < forward_dist){
  45     candidate->plot_start_point=candidate->last_point;
  46     candidate->plot_end_point=candidate->first_point;
  47     return reverse_dist;
  48   } else {
  49     candidate->plot_start_point=candidate->first_point;
  50     candidate->plot_end_point=candidate->last_point;
  51     return forward_dist;
  52   }
  53 }
  54
  55 int equal(struct point *a, struct point *b){
  56   if ((a==NULL)||(b==NULL)) return 0;
  57   if ((a->x == b->x) &&( a->y == b->y)) return 1;
  58   else return 0;
  59 }
  60
  61 static void link_reverse(struct path *path){
  62   struct path *cur;
  63   if (!path) return;
  64   for (cur = path; cur->next; cur = cur->next)
  65     cur->next->back = cur;
  66 }
  67
  68 static void remove_path(struct path **target, struct path *path){
  69
  70   if (path == *target){ /* First element! */
  71     *target = path->next;
  72     return;
  73   }
  74   path->back->next = path->next;
  75   if (path->next)
  76     path->next->back = path->back;
  77 }
  78
  79 struct path *optimize(struct path *input_list){
  80   struct point __point;
  81   __point.x=0;
  82   __point.y=0;
  83
  84   struct point *point = &__point;
  85   struct path *result = NULL;
  86   struct path *result_last;
  87   struct path *cur, *best;
  88 #ifdef DEBUG
  89   int i = 0;
  90 #endif
  91
  92   link_reverse(input_list);
  93   DBG("link_reverse done\n");
  94
  95 #ifdef DEBUG
  96   for (cur = input_list; cur; cur = cur->next)
  97     DBG("%4i Input Path (%5.2f,%5.2f) -> (%5.2f,%5.2f)\n",
  98            i++,
  99            cur->plot_start_point->x,
 100            cur->plot_start_point->y,
 101            cur->plot_end_point->x,
 102            cur->plot_end_point->y
 103            );
 104 #endif
 105
 106   while(input_list) {
 107     best = NULL;
 108     for (cur = input_list; cur; cur = cur->next) {
 109       cur->dist = path_distance(point, cur);
 110       if ((!best)||(cur->dist < best->dist)) {
 111         best = cur;
 112         /*
 113         DBG("cur->dist = %5.2f, best->dist = %5.2f\n",
 114                cur->dist, best->dist);
 115         DBG("Cur Path (%5.2f,%5.2f) -> (%5.2f,%5.2f)\n",
 116            cur->plot_start_point->x,
 117            cur->plot_start_point->y,
 118            cur->plot_end_point->x,
 119            cur->plot_end_point->y
 120            );
 121         */
 122
 123       }
 124     }
 125     point = best->plot_end_point;
 126
 127     DBG("xbest Path (%5.2f,%5.2f) -> (%5.2f,%5.2f)\n",
 128            best->plot_start_point->x,
 129            best->plot_start_point->y,
 130            best->plot_end_point->x,
 131            best->plot_end_point->y
 132            );
 133
 134     /* Take best result */
 135     remove_path(&input_list, best);
 136
 137     if (!result) {
 138       result = best;
 139     } else {
 140       result_last->next = best;
 141     }
 142     result_last = best;
 143     result_last->next = NULL;
 144   }
 145
 146 #ifdef DEBUG
 147   i = 0;
 148   for (cur = result; cur; cur = cur->next)
 149     DBG("%4i Path (%5.2f,%5.2f) -> (%5.2f,%5.2f)\n",
 150            i++,
 151            cur->plot_start_point->x,
 152            cur->plot_start_point->y,
 153            cur->plot_end_point->x,
 154            cur->plot_end_point->y
 155            );
 156 #endif
 157
 158   return result;
 159 }
 160
 161
 162 struct path *single_stroke_path(struct point *a, struct point *b){
 163   struct path *result=(struct path *)malloc(sizeof(struct path));
 164
 165   struct point *aa=(struct point *)malloc(sizeof(struct point));
 166   struct point *bb=(struct point *)malloc(sizeof(struct point));
 167   memcpy(aa,a,sizeof(struct point));
 168   memcpy(bb,b,sizeof(struct point));
 169   aa->next=bb;
 170   bb->next=NULL;
 171   aa->previous_in_path=NULL;
 172   bb->previous_in_path=aa;
 173
 174   result->next=NULL;
 175   result->first_point=aa;
 176   result->plot_start_point=aa;
 177   result->last_point=bb;
 178   result->plot_end_point=bb;
 179   return result;
 180 }
 181
 182
 183 struct path *split_paths(struct path *source){
 184   struct path *result=NULL;
 185   struct path *last_result=NULL;
 186
 187   struct path *current_path;
 188   for (current_path=source; current_path!=NULL; current_path=current_path->next){
 189
 190     struct point *current_point;
 191
 192     for (current_point=current_path->first_point; current_point->next!=NULL;
 193          current_point=current_point->next){
 194       struct path*tmp=single_stroke_path(current_point,current_point->next);
 195       if (result==NULL){
 196         result=tmp;
 197         last_result=tmp;
 198       } else {
 199         last_result->next=tmp;
 200         last_result=last_result->next;
 201       }
 202
 203     }
 204   }
 205   return result;
 206 }
 207
 208
 209 void round_path(struct path *source){
 210   struct path *current_path;
 211   for (current_path=source; current_path!=NULL; current_path=current_path->next){
 212         struct point *current_point;
 213
 214     for (current_point=current_path->first_point; current_point!=NULL;
 215          current_point=current_point->next){
 216       current_point->x=round(current_point->x*100.0)/100.0;
 217       current_point->y=round(current_point->y*100.0)/100.0;
 218     }
 219   }
 220 }