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
;
92 link_reverse(input_list
);
93 DBG("link_reverse done\n");
96 for (cur
= input_list
; cur
; cur
= cur
->next
)
97 DBG("%4i Input Path (%5.2f,%5.2f) -> (%5.2f,%5.2f)\n",
99 cur
->plot_start_point
->x
,
100 cur
->plot_start_point
->y
,
101 cur
->plot_end_point
->x
,
102 cur
->plot_end_point
->y
108 for (cur
= input_list
; cur
; cur
= cur
->next
) {
109 cur
->dist
= path_distance(point
, cur
);
110 if ((!best
)||(cur
->dist
< best
->dist
)) {
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
125 point
= best
->plot_end_point
;
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
134 /* Take best result */
135 remove_path(&input_list
, best
);
140 result_last
->next
= best
;
143 result_last
->next
= NULL
;
148 for (cur
= result
; cur
; cur
= cur
->next
)
149 DBG("%4i Path (%5.2f,%5.2f) -> (%5.2f,%5.2f)\n",
151 cur
->plot_start_point
->x
,
152 cur
->plot_start_point
->y
,
153 cur
->plot_end_point
->x
,
154 cur
->plot_end_point
->y
162 struct path
*single_stroke_path(struct point
*a
, struct point
*b
){
163 struct path
*result
=(struct path
*)malloc(sizeof(struct path
));
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
));
171 aa
->previous_in_path
=NULL
;
172 bb
->previous_in_path
=aa
;
175 result
->first_point
=aa
;
176 result
->plot_start_point
=aa
;
177 result
->last_point
=bb
;
178 result
->plot_end_point
=bb
;
183 struct path
*split_paths(struct path
*source
){
184 struct path
*result
=NULL
;
185 struct path
*last_result
=NULL
;
187 struct path
*current_path
;
188 for (current_path
=source
; current_path
!=NULL
; current_path
=current_path
->next
){
190 struct point
*current_point
;
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
);
199 last_result
->next
=tmp
;
200 last_result
=last_result
->next
;
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
;
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;