5a434d0559b38467c9cebf4bc231efa76883817d
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.
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
);
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
);
30 if (reverse_dist
< forward_dist
){
31 path
->plot_start_point
=path
->last_point
;
32 path
->plot_end_point
=path
->first_point
;
35 path
->plot_start_point
=path
->first_point
;
36 path
->plot_end_point
=path
->last_point
;
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
;
49 candidate
->plot_start_point
=candidate
->first_point
;
50 candidate
->plot_end_point
=candidate
->last_point
;
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;
61 static void link_reverse(struct path
*path
){
64 for (cur
= path
; cur
->next
; cur
= cur
->next
)
65 cur
->next
->back
= cur
;
68 static void remove_path(struct path
**target
, struct path
*path
){
70 if (path
== *target
){ /* First element! */
74 path
->back
->next
= path
->next
;
76 path
->next
->back
= path
->back
;
79 struct path
*optimize(struct path
*input_list
){
84 struct point
*point
= &__point
;
85 struct path
*result
= NULL
;
86 struct path
*result_last
;
87 struct path
*cur
, *best
;
90 link_reverse(input_list
);
91 // DBG("link_reverse done\n");
94 for (cur
= input_list
; cur
; cur
= cur
->next
)
95 DBG("%4i Input Path (%5.2f,%5.2f) -> (%5.2f,%5.2f)\n",
97 cur
->plot_start_point
->x
,
98 cur
->plot_start_point
->y
,
99 cur
->plot_end_point
->x
,
100 cur
->plot_end_point
->y
105 for (cur
= input_list
; cur
; cur
= cur
->next
) {
106 cur
->dist
= path_distance(point
, cur
);
107 if ((!best
)||(cur
->dist
< best
->dist
)) {
110 DBG("cur->dist = %5.2f, best->dist = %5.2f\n",
111 cur->dist, best->dist);
112 DBG("Cur Path (%5.2f,%5.2f) -> (%5.2f,%5.2f)\n",
113 cur->plot_start_point->x,
114 cur->plot_start_point->y,
115 cur->plot_end_point->x,
116 cur->plot_end_point->y
122 point
= best
->plot_end_point
;
124 DBG("xbest Path (%5.2f,%5.2f) -> (%5.2f,%5.2f)\n",
125 best
->plot_start_point
->x
,
126 best
->plot_start_point
->y
,
127 best
->plot_end_point
->x
,
128 best
->plot_end_point
->y
131 /* Take best result */
132 remove_path(&input_list
, best
);
137 result_last
->next
= best
;
140 result_last
->next
= NULL
;
145 for (cur
= result
; cur
; cur
= cur
->next
)
146 DBG("%4i Path (%5.2f,%5.2f) -> (%5.2f,%5.2f)\n",
148 cur
->plot_start_point
->x
,
149 cur
->plot_start_point
->y
,
150 cur
->plot_end_point
->x
,
151 cur
->plot_end_point
->y
159 struct path
*single_stroke_path(struct point
*a
, struct point
*b
){
160 struct path
*result
=(struct path
*)malloc(sizeof(struct path
));
162 struct point
*aa
=(struct point
*)malloc(sizeof(struct point
));
163 struct point
*bb
=(struct point
*)malloc(sizeof(struct point
));
164 memcpy(aa
,a
,sizeof(struct point
));
165 memcpy(bb
,b
,sizeof(struct point
));
168 aa
->previous_in_path
=NULL
;
169 bb
->previous_in_path
=aa
;
172 result
->first_point
=aa
;
173 result
->plot_start_point
=aa
;
174 result
->last_point
=bb
;
175 result
->plot_end_point
=bb
;
180 struct path
*split_paths(struct path
*source
){
181 struct path
*result
=NULL
;
182 struct path
*last_result
=NULL
;
184 struct path
*current_path
;
185 for (current_path
=source
; current_path
!=NULL
; current_path
=current_path
->next
){
187 struct point
*current_point
;
189 for (current_point
=current_path
->first_point
; current_point
->next
!=NULL
;
190 current_point
=current_point
->next
){
191 struct path
*tmp
=single_stroke_path(current_point
,current_point
->next
);
196 last_result
->next
=tmp
;
197 last_result
=last_result
->next
;
206 void round_path(struct path
*source
){
207 struct path
*current_path
;
208 for (current_path
=source
; current_path
!=NULL
; current_path
=current_path
->next
){
209 struct point
*current_point
;
211 for (current_point
=current_path
->first_point
; current_point
!=NULL
;
212 current_point
=current_point
->next
){
213 current_point
->x
=round(current_point
->x
*100.0)/100.0;
214 current_point
->y
=round(current_point
->y
*100.0)/100.0;