-
Notifications
You must be signed in to change notification settings - Fork 11
/
potracelib.h
executable file
·2466 lines (2428 loc) · 80.2 KB
/
potracelib.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
#define VERSION "1.16"
#include <stdint.h>
/* Copyright (C) 2001-2019 Peter Selinger.
This file is part of Potrace. It is free software and it is covered
by the GNU General Public License. See the file COPYING for details. */
/* private part of the path and curve data structures */
#ifdef HAVE_CONFIG_H
#include <config.h>
#endif
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* Copyright (C) 2001-2019 Peter Selinger.
This file is part of Potrace. It is free software and it is covered
by the GNU General Public License. See the file COPYING for details. */
#ifndef POTRACELIB_H
#define POTRACELIB_H
/* this file defines the API for the core Potrace library. For a more
detailed description of the API, see potracelib.pdf */
#ifdef __cplusplus
extern "C" {
#endif
/* ---------------------------------------------------------------------- */
/* tracing parameters */
/* turn policies */
#define POTRACE_TURNPOLICY_BLACK 0
#define POTRACE_TURNPOLICY_WHITE 1
#define POTRACE_TURNPOLICY_LEFT 2
#define POTRACE_TURNPOLICY_RIGHT 3
#define POTRACE_TURNPOLICY_MINORITY 4
#define POTRACE_TURNPOLICY_MAJORITY 5
#define POTRACE_TURNPOLICY_RANDOM 6
/* structure to hold progress bar callback data */
struct potrace_progress_s {
void (*callback)(double progress, void *privdata); /* callback fn */
void *data; /* callback function's private data */
double min, max; /* desired range of progress, e.g. 0.0 to 1.0 */
double epsilon; /* granularity: can skip smaller increments */
};
typedef struct potrace_progress_s potrace_progress_t;
/* structure to hold tracing parameters */
struct potrace_param_s {
int turdsize; /* area of largest path to be ignored */
int turnpolicy; /* resolves ambiguous turns in path decomposition */
double alphamax; /* corner threshold */
int opticurve; /* use curve optimization? */
double opttolerance; /* curve optimization tolerance */
potrace_progress_t progress; /* progress callback function */
};
typedef struct potrace_param_s potrace_param_t;
/* ---------------------------------------------------------------------- */
/* bitmaps */
/* native word size */
typedef unsigned long potrace_word;
/* Internal bitmap format. The n-th scanline starts at scanline(n) =
(map + n*dy). Raster data is stored as a sequence of potrace_words
(NOT bytes). The leftmost bit of scanline n is the most significant
bit of scanline(n)[0]. */
struct potrace_bitmap_s {
int w, h; /* width and height, in pixels */
int dy; /* words per scanline (not bytes) */
potrace_word *map; /* raw data, dy*h words */
};
typedef struct potrace_bitmap_s potrace_bitmap_t;
/* ---------------------------------------------------------------------- */
/* curves */
/* point */
struct potrace_dpoint_s {
double x, y;
};
typedef struct potrace_dpoint_s potrace_dpoint_t;
/* segment tags */
#define POTRACE_CURVETO 1
#define POTRACE_CORNER 2
/* closed curve segment */
struct potrace_curve_s {
int n; /* number of segments */
int *tag; /* tag[n]: POTRACE_CURVETO or POTRACE_CORNER */
potrace_dpoint_t (*c)[3]; /* c[n][3]: control points.
c[n][0] is unused for tag[n]=POTRACE_CORNER */
};
typedef struct potrace_curve_s potrace_curve_t;
/* Linked list of signed curve segments. Also carries a tree structure. */
struct potrace_path_s {
int area; /* area of the bitmap path */
int sign; /* '+' or '-', depending on orientation */
potrace_curve_t curve; /* this path's vector data */
struct potrace_path_s *next; /* linked list structure */
struct potrace_path_s *childlist; /* tree structure */
struct potrace_path_s *sibling; /* tree structure */
struct potrace_privpath_s *priv; /* private state */
};
typedef struct potrace_path_s potrace_path_t;
/* ---------------------------------------------------------------------- */
/* Potrace state */
#define POTRACE_STATUS_OK 0
#define POTRACE_STATUS_INCOMPLETE 1
struct potrace_state_s {
int status;
potrace_path_t *plist; /* vector data */
struct potrace_privstate_s *priv; /* private state */
};
typedef struct potrace_state_s potrace_state_t;
/* ---------------------------------------------------------------------- */
/* API functions */
/* get default parameters */
potrace_param_t *potrace_param_default(void);
/* free parameter set */
void potrace_param_free(potrace_param_t *p);
/* trace a bitmap */
potrace_state_t *potrace_trace(const potrace_param_t *param,
const potrace_bitmap_t *bm);
/* free a Potrace state */
void potrace_state_free(potrace_state_t *st);
/* return a static plain text version string identifying this version
of potracelib */
const char *potrace_version(void);
#ifdef __cplusplus
} /* end of extern "C" */
#endif
#endif /* POTRACELIB_H */
/* Copyright (C) 2001-2019 Peter Selinger.
This file is part of Potrace. It is free software and it is covered
by the GNU General Public License. See the file COPYING for details. */
#ifndef _PS_LISTS_H
#define _PS_LISTS_H
/* here we define some general list macros. Because they are macros,
they should work on any datatype with a "->next" component. Some of
them use a "hook". If elt and list are of type t* then hook is of
type t**. A hook stands for an insertion point in the list, i.e.,
either before the first element, or between two elements, or after
the last element. If an operation "sets the hook" for an element,
then the hook is set to just before the element. One can insert
something at a hook. One can also unlink at a hook: this means,
unlink the element just after the hook. By "to unlink", we mean the
element is removed from the list, but not deleted. Thus, it and its
components still need to be freed. */
/* Note: these macros are somewhat experimental. Only the ones that
are actually *used* have been tested. So be careful to test any
that you use. Looking at the output of the preprocessor, "gcc -E"
(possibly piped though "indent"), might help too. Also: these
macros define some internal (local) variables that start with
"_". */
/* we enclose macro definitions whose body consists of more than one
statement in MACRO_BEGIN and MACRO_END, rather than '{' and '}'. The
reason is that we want to be able to use the macro in a context
such as "if (...) macro(...); else ...". If we didn't use this obscure
trick, we'd have to omit the ";" in such cases. */
#define MACRO_BEGIN do {
#define MACRO_END } while (0)
/* ---------------------------------------------------------------------- */
/* macros for singly-linked lists */
/* traverse list. At the end, elt is set to NULL. */
#define list_forall(elt, list) for (elt=list; elt!=NULL; elt=elt->next)
/* set elt to the first element of list satisfying boolean condition
c, or NULL if not found */
#define list_find(elt, list, c) \
MACRO_BEGIN list_forall(elt, list) if (c) break; MACRO_END
/* like forall, except also set hook for elt. */
#define list_forall2(elt, list, hook) \
for (elt=list, hook=&list; elt!=NULL; hook=&elt->next, elt=elt->next)
/* same as list_find, except also set hook for elt. */
#define list_find2(elt, list, c, hook) \
MACRO_BEGIN list_forall2(elt, list, hook) if (c) break; MACRO_END
/* same, except only use hook. */
#define _list_forall_hook(list, hook) \
for (hook=&list; *hook!=NULL; hook=&(*hook)->next)
/* same, except only use hook. Note: c may only refer to *hook, not elt. */
#define _list_find_hook(list, c, hook) \
MACRO_BEGIN _list_forall_hook(list, hook) if (c) break; MACRO_END
/* insert element after hook */
#define list_insert_athook(elt, hook) \
MACRO_BEGIN elt->next = *hook; *hook = elt; MACRO_END
/* insert element before hook */
#define list_insert_beforehook(elt, hook) \
MACRO_BEGIN elt->next = *hook; *hook = elt; hook=&elt->next; MACRO_END
/* unlink element after hook, let elt be unlinked element, or NULL.
hook remains. */
#define list_unlink_athook(list, elt, hook) \
MACRO_BEGIN \
elt = hook ? *hook : NULL; if (elt) { *hook = elt->next; elt->next = NULL; }\
MACRO_END
/* unlink the specific element, if it is in the list. Otherwise, set
elt to NULL */
#define list_unlink(listtype, list, elt) \
MACRO_BEGIN \
listtype **_hook; \
_list_find_hook(list, *_hook==elt, _hook); \
list_unlink_athook(list, elt, _hook); \
MACRO_END
/* prepend elt to list */
#define list_prepend(list, elt) \
MACRO_BEGIN elt->next = list; list = elt; MACRO_END
/* append elt to list. */
#define list_append(listtype, list, elt) \
MACRO_BEGIN \
listtype **_hook; \
_list_forall_hook(list, _hook) {} \
list_insert_athook(elt, _hook); \
MACRO_END
/* unlink the first element that satisfies the condition. */
#define list_unlink_cond(listtype, list, elt, c) \
MACRO_BEGIN \
listtype **_hook; \
list_find2(elt, list, c, _hook); \
list_unlink_athook(list, elt, _hook); \
MACRO_END
/* let elt be the nth element of the list, starting to count from 0.
Return NULL if out of bounds. */
#define list_nth(elt, list, n) \
MACRO_BEGIN \
int _x; /* only evaluate n once */ \
for (_x=(n), elt=list; _x && elt; _x--, elt=elt->next) {} \
MACRO_END
/* let elt be the nth element of the list, starting to count from 0.
Return NULL if out of bounds. */
#define list_nth_hook(elt, list, n, hook) \
MACRO_BEGIN \
int _x; /* only evaluate n once */ \
for (_x=(n), elt=list, hook=&list; _x && elt; _x--, hook=&elt->next, elt=elt->next) {} \
MACRO_END
/* set n to the length of the list */
#define list_length(listtype, list, n) \
MACRO_BEGIN \
listtype *_elt; \
n=0; \
list_forall(_elt, list) \
n++; \
MACRO_END
/* set n to the index of the first element satisfying cond, or -1 if
none found. Also set elt to the element, or NULL if none found. */
#define list_index(list, n, elt, c) \
MACRO_BEGIN \
n=0; \
list_forall(elt, list) { \
if (c) break; \
n++; \
} \
if (!elt) \
n=-1; \
MACRO_END
/* set n to the number of elements in the list that satisfy condition c */
#define list_count(list, n, elt, c) \
MACRO_BEGIN \
n=0; \
list_forall(elt, list) { \
if (c) n++; \
} \
MACRO_END
/* let elt be each element of the list, unlinked. At the end, set list=NULL. */
#define list_forall_unlink(elt, list) \
for (elt=list; elt ? (list=elt->next, elt->next=NULL), 1 : 0; elt=list)
/* reverse a list (efficient) */
#define list_reverse(listtype, list) \
MACRO_BEGIN \
listtype *_list1=NULL, *elt; \
list_forall_unlink(elt, list) \
list_prepend(_list1, elt); \
list = _list1; \
MACRO_END
/* insert the element ELT just before the first element TMP of the
list for which COND holds. Here COND must be a condition of ELT and
TMP. Typical usage is to insert an element into an ordered list:
for instance, list_insert_ordered(listtype, list, elt, tmp,
elt->size <= tmp->size). Note: if we give a "less than or equal"
condition, the new element will be inserted just before a sequence
of equal elements. If we give a "less than" condition, the new
element will be inserted just after a list of equal elements.
Note: it is much more efficient to construct a list with
list_prepend and then order it with list_merge_sort, than to
construct it with list_insert_ordered. */
#define list_insert_ordered(listtype, list, elt, tmp, cond) \
MACRO_BEGIN \
listtype **_hook; \
_list_find_hook(list, (tmp=*_hook, (cond)), _hook); \
list_insert_athook(elt, _hook); \
MACRO_END
/* sort the given list, according to the comparison condition.
Typical usage is list_sort(listtype, list, a, b, a->size <
b->size). Note: if we give "less than or equal" condition, each
segment of equal elements will be reversed in order. If we give a
"less than" condition, each segment of equal elements will retain
the original order. The latter is slower but sometimes
prettier. Average running time: n*n/2. */
#define list_sort(listtype, list, a, b, cond) \
MACRO_BEGIN \
listtype *_newlist=NULL; \
list_forall_unlink(a, list) \
list_insert_ordered(listtype, _newlist, a, b, cond); \
list = _newlist; \
MACRO_END
/* a much faster sort algorithm (merge sort, n log n worst case). It
is required that the list type has an additional, unused next1
component. Note there is no curious reversal of order of equal
elements as for list_sort. */
#define list_mergesort(listtype, list, a, b, cond) \
MACRO_BEGIN \
listtype *_elt, **_hook1; \
\
for (_elt=list; _elt; _elt=_elt->next1) { \
_elt->next1 = _elt->next; \
_elt->next = NULL; \
} \
do { \
_hook1 = &(list); \
while ((a = *_hook1) != NULL && (b = a->next1) != NULL ) { \
_elt = b->next1; \
_list_merge_cond(listtype, a, b, cond, *_hook1); \
_hook1 = &((*_hook1)->next1); \
*_hook1 = _elt; \
} \
} while (_hook1 != &(list)); \
MACRO_END
/* merge two sorted lists. Store result at &result */
#define _list_merge_cond(listtype, a, b, cond, result) \
MACRO_BEGIN \
listtype **_hook; \
_hook = &(result); \
while (1) { \
if (a==NULL) { \
*_hook = b; \
break; \
} else if (b==NULL) { \
*_hook = a; \
break; \
} else if (cond) { \
*_hook = a; \
_hook = &(a->next); \
a = a->next; \
} else { \
*_hook = b; \
_hook = &(b->next); \
b = b->next; \
} \
} \
MACRO_END
/* ---------------------------------------------------------------------- */
/* macros for doubly-linked lists */
#define dlist_append(head, end, elt) \
MACRO_BEGIN \
elt->prev = end; \
elt->next = NULL; \
if (end) { \
end->next = elt; \
} else { \
head = elt; \
} \
end = elt; \
MACRO_END
/* let elt be each element of the list, unlinked. At the end, set list=NULL. */
#define dlist_forall_unlink(elt, head, end) \
for (elt=head; elt ? (head=elt->next, elt->next=NULL, elt->prev=NULL), 1 : (end=NULL, 0); elt=head)
/* unlink the first element of the list */
#define dlist_unlink_first(head, end, elt) \
MACRO_BEGIN \
elt = head; \
if (head) { \
head = head->next; \
if (head) { \
head->prev = NULL; \
} else { \
end = NULL; \
} \
elt->prev = NULL; \
elt->next = NULL; \
} \
MACRO_END
#endif /* _PS_LISTS_H */
/* Copyright (C) 2001-2019 Peter Selinger.
This file is part of Potrace. It is free software and it is covered
by the GNU General Public License. See the file COPYING for details. */
#ifndef CURVE_H
#define CURVE_H
/* Copyright (C) 2001-2019 Peter Selinger.
This file is part of Potrace. It is free software and it is covered
by the GNU General Public License. See the file COPYING for details. */
/* This header file collects some general-purpose macros (and static
inline functions) that are used in various places. */
#ifndef AUXILIARY_H
#define AUXILIARY_H
#ifdef HAVE_CONFIG_H
#endif
/* ---------------------------------------------------------------------- */
/* point arithmetic */
struct point_s {
long x;
long y;
};
typedef struct point_s point_t;
typedef potrace_dpoint_t dpoint_t;
/* convert point_t to dpoint_t */
static inline dpoint_t dpoint(point_t p) {
dpoint_t res;
res.x = p.x;
res.y = p.y;
return res;
}
/* range over the straight line segment [a,b] when lambda ranges over [0,1] */
static inline dpoint_t interval(double lambda, dpoint_t a, dpoint_t b) {
dpoint_t res;
res.x = a.x + lambda * (b.x - a.x);
res.y = a.y + lambda * (b.y - a.y);
return res;
}
/* ---------------------------------------------------------------------- */
/* some useful macros. Note: the "mod" macro works correctly for
negative a. Also note that the test for a>=n, while redundant,
speeds up the mod function by 70% in the average case (significant
since the program spends about 16% of its time here - or 40%
without the test). The "floordiv" macro returns the largest integer
<= a/n, and again this works correctly for negative a, as long as
a,n are integers and n>0. */
/* integer arithmetic */
static inline int mod(int a, int n) {
return a>=n ? a%n : a>=0 ? a : n-1-(-1-a)%n;
}
static inline int floordiv(int a, int n) {
return a>=0 ? a/n : -1-(-1-a)/n;
}
/* Note: the following work for integers and other numeric types. */
#undef sign
#undef abs
#undef min
#undef max
#undef sq
#undef cu
#define sign(x) ((x)>0 ? 1 : (x)<0 ? -1 : 0)
#define abs(a) ((a)>0 ? (a) : -(a))
#define min(a,b) ((a)<(b) ? (a) : (b))
#define max(a,b) ((a)>(b) ? (a) : (b))
#define sq(a) ((a)*(a))
#define cu(a) ((a)*(a)*(a))
#endif /* AUXILIARY_H */
/* vertex is c[1] for tag=POTRACE_CORNER, and the intersection of
.c[-1][2]..c[0] and c[1]..c[2] for tag=POTRACE_CURVETO. alpha is only
defined for tag=POTRACE_CURVETO and is the alpha parameter of the curve:
.c[-1][2]..c[0] = alpha*(.c[-1][2]..vertex), and
c[2]..c[1] = alpha*(c[2]..vertex).
Beta is so that (.beta[i])[.vertex[i],.vertex[i+1]] = .c[i][2].
*/
struct privcurve_s {
int n; /* number of segments */
int *tag; /* tag[n]: POTRACE_CORNER or POTRACE_CURVETO */
dpoint_t (*c)[3]; /* c[n][i]: control points.
c[n][0] is unused for tag[n]=POTRACE_CORNER */
/* the remainder of this structure is special to privcurve, and is
used in EPS debug output and special EPS "short coding". These
fields are valid only if "alphacurve" is set. */
int alphacurve; /* have the following fields been initialized? */
dpoint_t *vertex; /* for POTRACE_CORNER, this equals c[1] */
double *alpha; /* only for POTRACE_CURVETO */
double *alpha0; /* "uncropped" alpha parameter - for debug output only */
double *beta;
};
typedef struct privcurve_s privcurve_t;
struct sums_s {
double x;
double y;
double x2;
double xy;
double y2;
};
typedef struct sums_s sums_t;
/* the path structure is filled in with information about a given path
as it is accumulated and passed through the different stages of the
Potrace algorithm. Backends only need to read the fcurve and fm
fields of this data structure, but debugging backends may read
other fields. */
struct potrace_privpath_s {
int len;
point_t *pt; /* pt[len]: path as extracted from bitmap */
int *lon; /* lon[len]: (i,lon[i]) = longest straight line from i */
int x0, y0; /* origin for sums */
sums_t *sums; /* sums[len+1]: cache for fast summing */
int m; /* length of optimal polygon */
int *po; /* po[m]: optimal polygon */
privcurve_t curve; /* curve[m]: array of curve elements */
privcurve_t ocurve; /* ocurve[om]: array of curve elements */
privcurve_t *fcurve; /* final curve: this points to either curve or
ocurve. Do not free this separately. */
};
typedef struct potrace_privpath_s potrace_privpath_t;
/* shorter names */
typedef potrace_privpath_t privpath_t;
typedef potrace_path_t path_t;
path_t *path_new(void);
void path_free(path_t *p);
void pathlist_free(path_t *plist);
int privcurve_init(privcurve_t *curve, int n);
void privcurve_to_curve(privcurve_t *pc, potrace_curve_t *c);
#endif /* CURVE_H */
#define SAFE_CALLOC(var, n, typ) \
if ((var = (typ *)calloc(n, sizeof(typ))) == NULL) goto calloc_error
/* ---------------------------------------------------------------------- */
/* allocate and free path objects */
path_t *path_new(void) {
path_t *p = NULL;
privpath_t *priv = NULL;
SAFE_CALLOC(p, 1, path_t);
memset(p, 0, sizeof(path_t));
SAFE_CALLOC(priv, 1, privpath_t);
memset(priv, 0, sizeof(privpath_t));
p->priv = priv;
return p;
calloc_error:
free(p);
free(priv);
return NULL;
}
/* free the members of the given curve structure. Leave errno unchanged. */
static void privcurve_free_members(privcurve_t *curve) {
free(curve->tag);
free(curve->c);
free(curve->vertex);
free(curve->alpha);
free(curve->alpha0);
free(curve->beta);
}
/* free a path. Leave errno untouched. */
void path_free(path_t *p) {
if (p) {
if (p->priv) {
free(p->priv->pt);
free(p->priv->lon);
free(p->priv->sums);
free(p->priv->po);
privcurve_free_members(&p->priv->curve);
privcurve_free_members(&p->priv->ocurve);
}
free(p->priv);
/* do not free p->fcurve ! */
}
free(p);
}
/* free a pathlist, leaving errno untouched. */
void pathlist_free(path_t *plist) {
path_t *p;
list_forall_unlink(p, plist) {
path_free(p);
}
}
/* ---------------------------------------------------------------------- */
/* initialize and finalize curve structures */
typedef dpoint_t dpoint3_t[3];
/* initialize the members of the given curve structure to size m.
Return 0 on success, 1 on error with errno set. */
int privcurve_init(privcurve_t *curve, int n) {
memset(curve, 0, sizeof(privcurve_t));
curve->n = n;
SAFE_CALLOC(curve->tag, n, int);
SAFE_CALLOC(curve->c, n, dpoint3_t);
SAFE_CALLOC(curve->vertex, n, dpoint_t);
SAFE_CALLOC(curve->alpha, n, double);
SAFE_CALLOC(curve->alpha0, n, double);
SAFE_CALLOC(curve->beta, n, double);
return 0;
calloc_error:
free(curve->tag);
free(curve->c);
free(curve->vertex);
free(curve->alpha);
free(curve->alpha0);
free(curve->beta);
return 1;
}
/* copy private to public curve structure */
void privcurve_to_curve(privcurve_t *pc, potrace_curve_t *c) {
c->n = pc->n;
c->tag = pc->tag;
c->c = pc->c;
}
/* Copyright (C) 2001-2019 Peter Selinger.
This file is part of Potrace. It is free software and it is covered
by the GNU General Public License. See the file COPYING for details. */
/* transform jaggy paths into smooth curves */
#ifdef HAVE_CONFIG_H
#endif
#include <math.h>
/* Copyright (C) 2001-2019 Peter Selinger.
This file is part of Potrace. It is free software and it is covered
by the GNU General Public License. See the file COPYING for details. */
#ifndef TRACE_H
#define TRACE_H
/* Copyright (C) 2001-2019 Peter Selinger.
This file is part of Potrace. It is free software and it is covered
by the GNU General Public License. See the file COPYING for details. */
/* operations on potrace_progress_t objects, which are defined in
potracelib.h. Note: the code attempts to minimize runtime overhead
when no progress monitoring was requested. It also tries to
minimize excessive progress calculations beneath the "epsilon"
threshold. */
#ifndef PROGRESS_H
#define PROGRESS_H
/* structure to hold progress bar callback data */
struct progress_s {
void (*callback)(double progress, void *privdata); /* callback fn */
void *data; /* callback function's private data */
double min, max; /* desired range of progress, e.g. 0.0 to 1.0 */
double epsilon; /* granularity: can skip smaller increments */
double b; /* upper limit of subrange in superrange units */
double d_prev; /* previous value of d */
};
typedef struct progress_s progress_t;
/* notify given progress object of current progress. Note that d is
given in the 0.0-1.0 range, which will be scaled and translated to
the progress object's range. */
static inline void progress_update(double d, progress_t *prog) {
double d_scaled;
if (prog != NULL && prog->callback != NULL) {
d_scaled = prog->min * (1-d) + prog->max * d;
if (d == 1.0 || d_scaled >= prog->d_prev + prog->epsilon) {
prog->callback(prog->min * (1-d) + prog->max * d, prog->data);
prog->d_prev = d_scaled;
}
}
}
/* start a subrange of the given progress object. The range is
narrowed to [a..b], relative to 0.0-1.0 coordinates. If new range
is below granularity threshold, disable further subdivisions. */
static inline void progress_subrange_start(double a, double b, const progress_t *prog, progress_t *sub) {
double min, max;
if (prog == NULL || prog->callback == NULL) {
sub->callback = NULL;
return;
}
min = prog->min * (1-a) + prog->max * a;
max = prog->min * (1-b) + prog->max * b;
if (max - min < prog->epsilon) {
sub->callback = NULL; /* no further progress info in subrange */
sub->b = b;
return;
}
sub->callback = prog->callback;
sub->data = prog->data;
sub->epsilon = prog->epsilon;
sub->min = min;
sub->max = max;
sub->d_prev = prog->d_prev;
return;
}
static inline void progress_subrange_end(progress_t *prog, progress_t *sub) {
if (prog != NULL && prog->callback != NULL) {
if (sub->callback == NULL) {
progress_update(sub->b, prog);
} else {
prog->d_prev = sub->d_prev;
}
}
}
#endif /* PROGRESS_H */
int process_path(path_t *plist, const potrace_param_t *param, progress_t *progress);
#endif /* TRACE_H */
#define INFTY 10000000 /* it suffices that this is longer than any
path; it need not be really infinite */
#define COS179 -0.999847695156 /* the cosine of 179 degrees */
/* ---------------------------------------------------------------------- */
#define SAFE_CALLOC(var, n, typ) \
if ((var = (typ *)calloc(n, sizeof(typ))) == NULL) goto calloc_error
/* ---------------------------------------------------------------------- */
/* auxiliary functions */
/* return a direction that is 90 degrees counterclockwise from p2-p0,
but then restricted to one of the major wind directions (n, nw, w, etc) */
static inline point_t dorth_infty(dpoint_t p0, dpoint_t p2) {
point_t r;
r.y = sign(p2.x-p0.x);
r.x = -sign(p2.y-p0.y);
return r;
}
/* return (p1-p0)x(p2-p0), the area of the parallelogram */
static inline double dpara(dpoint_t p0, dpoint_t p1, dpoint_t p2) {
double x1, y1, x2, y2;
x1 = p1.x-p0.x;
y1 = p1.y-p0.y;
x2 = p2.x-p0.x;
y2 = p2.y-p0.y;
return x1*y2 - x2*y1;
}
/* ddenom/dpara have the property that the square of radius 1 centered
at p1 intersects the line p0p2 iff |dpara(p0,p1,p2)| <= ddenom(p0,p2) */
static inline double ddenom(dpoint_t p0, dpoint_t p2) {
point_t r = dorth_infty(p0, p2);
return r.y*(p2.x-p0.x) - r.x*(p2.y-p0.y);
}
/* return 1 if a <= b < c < a, in a cyclic sense (mod n) */
static inline int cyclic(int a, int b, int c) {
if (a<=c) {
return (a<=b && b<c);
} else {
return (a<=b || b<c);
}
}
/* determine the center and slope of the line i..j. Assume i<j. Needs
"sum" components of p to be set. */
static void pointslope(privpath_t *pp, int i, int j, dpoint_t *ctr, dpoint_t *dir) {
/* assume i<j */
int n = pp->len;
sums_t *sums = pp->sums;
double x, y, x2, xy, y2;
double k;
double a, b, c, lambda2, l;
int r=0; /* rotations from i to j */
while (j>=n) {
j-=n;
r+=1;
}
while (i>=n) {
i-=n;
r-=1;
}
while (j<0) {
j+=n;
r-=1;
}
while (i<0) {
i+=n;
r+=1;
}
x = sums[j+1].x-sums[i].x+r*sums[n].x;
y = sums[j+1].y-sums[i].y+r*sums[n].y;
x2 = sums[j+1].x2-sums[i].x2+r*sums[n].x2;
xy = sums[j+1].xy-sums[i].xy+r*sums[n].xy;
y2 = sums[j+1].y2-sums[i].y2+r*sums[n].y2;
k = j+1-i+r*n;
ctr->x = x/k;
ctr->y = y/k;
a = (x2-(double)x*x/k)/k;
b = (xy-(double)x*y/k)/k;
c = (y2-(double)y*y/k)/k;
lambda2 = (a+c+sqrt((a-c)*(a-c)+4*b*b))/2; /* larger e.value */
/* now find e.vector for lambda2 */
a -= lambda2;
c -= lambda2;
if (fabs(a) >= fabs(c)) {
l = sqrt(a*a+b*b);
if (l!=0) {
dir->x = -b/l;
dir->y = a/l;
}
} else {
l = sqrt(c*c+b*b);
if (l!=0) {
dir->x = -c/l;
dir->y = b/l;
}
}
if (l==0) {
dir->x = dir->y = 0; /* sometimes this can happen when k=4:
the two eigenvalues coincide */
}
}
/* the type of (affine) quadratic forms, represented as symmetric 3x3
matrices. The value of the quadratic form at a vector (x,y) is v^t
Q v, where v = (x,y,1)^t. */
typedef double quadform_t[3][3];
/* Apply quadratic form Q to vector w = (w.x,w.y) */
static inline double quadform(quadform_t Q, dpoint_t w) {
double v[3];
int i, j;
double sum;
v[0] = w.x;
v[1] = w.y;
v[2] = 1;
sum = 0.0;
for (i=0; i<3; i++) {
for (j=0; j<3; j++) {
sum += v[i] * Q[i][j] * v[j];
}
}
return sum;
}
/* calculate p1 x p2 */
static inline int xprod(point_t p1, point_t p2) {
return p1.x*p2.y - p1.y*p2.x;
}
/* calculate (p1-p0)x(p3-p2) */
static inline double cprod(dpoint_t p0, dpoint_t p1, dpoint_t p2, dpoint_t p3) {
double x1, y1, x2, y2;
x1 = p1.x - p0.x;
y1 = p1.y - p0.y;
x2 = p3.x - p2.x;
y2 = p3.y - p2.y;
return x1*y2 - x2*y1;
}
/* calculate (p1-p0)*(p2-p0) */
static inline double iprod(dpoint_t p0, dpoint_t p1, dpoint_t p2) {
double x1, y1, x2, y2;
x1 = p1.x - p0.x;
y1 = p1.y - p0.y;
x2 = p2.x - p0.x;
y2 = p2.y - p0.y;
return x1*x2 + y1*y2;
}
/* calculate (p1-p0)*(p3-p2) */
static inline double iprod1(dpoint_t p0, dpoint_t p1, dpoint_t p2, dpoint_t p3) {
double x1, y1, x2, y2;
x1 = p1.x - p0.x;
y1 = p1.y - p0.y;
x2 = p3.x - p2.x;
y2 = p3.y - p2.y;
return x1*x2 + y1*y2;
}
/* calculate distance between two points */
static inline double ddist(dpoint_t p, dpoint_t q) {
return sqrt(sq(p.x-q.x)+sq(p.y-q.y));
}
/* calculate point of a bezier curve */
static inline dpoint_t bezier(double t, dpoint_t p0, dpoint_t p1, dpoint_t p2, dpoint_t p3) {
double s = 1-t;
dpoint_t res;
/* Note: a good optimizing compiler (such as gcc-3) reduces the
following to 16 multiplications, using common subexpression
elimination. */
res.x = s*s*s*p0.x + 3*(s*s*t)*p1.x + 3*(t*t*s)*p2.x + t*t*t*p3.x;
res.y = s*s*s*p0.y + 3*(s*s*t)*p1.y + 3*(t*t*s)*p2.y + t*t*t*p3.y;
return res;
}
/* calculate the point t in [0..1] on the (convex) bezier curve
(p0,p1,p2,p3) which is tangent to q1-q0. Return -1.0 if there is no
solution in [0..1]. */
static double tangent(dpoint_t p0, dpoint_t p1, dpoint_t p2, dpoint_t p3, dpoint_t q0, dpoint_t q1) {
double A, B, C; /* (1-t)^2 A + 2(1-t)t B + t^2 C = 0 */
double a, b, c; /* a t^2 + b t + c = 0 */
double d, s, r1, r2;
A = cprod(p0, p1, q0, q1);
B = cprod(p1, p2, q0, q1);
C = cprod(p2, p3, q0, q1);
a = A - 2*B + C;
b = -2*A + 2*B;
c = A;
d = b*b - 4*a*c;
if (a==0 || d<0) {
return -1.0;
}
s = sqrt(d);
r1 = (-b + s) / (2 * a);
r2 = (-b - s) / (2 * a);
if (r1 >= 0 && r1 <= 1) {
return r1;
} else if (r2 >= 0 && r2 <= 1) {
return r2;
} else {
return -1.0;
}
}
/* ---------------------------------------------------------------------- */
/* Preparation: fill in the sum* fields of a path (used for later
rapid summing). Return 0 on success, 1 with errno set on
failure. */
static int calc_sums(privpath_t *pp) {
int i, x, y;
int n = pp->len;
SAFE_CALLOC(pp->sums, pp->len+1, sums_t);
/* origin */
pp->x0 = pp->pt[0].x;
pp->y0 = pp->pt[0].y;
/* preparatory computation for later fast summing */
pp->sums[0].x2 = pp->sums[0].xy = pp->sums[0].y2 = pp->sums[0].x = pp->sums[0].y = 0;
for (i=0; i<n; i++) {
x = pp->pt[i].x - pp->x0;
y = pp->pt[i].y - pp->y0;
pp->sums[i+1].x = pp->sums[i].x + x;
pp->sums[i+1].y = pp->sums[i].y + y;
pp->sums[i+1].x2 = pp->sums[i].x2 + (double)x*x;
pp->sums[i+1].xy = pp->sums[i].xy + (double)x*y;
pp->sums[i+1].y2 = pp->sums[i].y2 + (double)y*y;
}
return 0;
calloc_error:
return 1;
}
/* ---------------------------------------------------------------------- */
/* Stage 1: determine the straight subpaths (Sec. 2.2.1). Fill in the
"lon" component of a path object (based on pt/len). For each i,
lon[i] is the furthest index such that a straight line can be drawn
from i to lon[i]. Return 1 on error with errno set, else 0. */
/* this algorithm depends on the fact that the existence of straight
subpaths is a triplewise property. I.e., there exists a straight
line through squares i0,...,in iff there exists a straight line
through i,j,k, for all i0<=i<j<k<=in. (Proof?) */
/* this implementation of calc_lon is O(n^2). It replaces an older
O(n^3) version. A "constraint" means that future points must
satisfy xprod(constraint[0], cur) >= 0 and xprod(constraint[1],
cur) <= 0. */
/* Remark for Potrace 1.1: the current implementation of calc_lon is
more complex than the implementation found in Potrace 1.0, but it
is considerably faster. The introduction of the "nc" data structure
means that we only have to test the constraints for "corner"
points. On a typical input file, this speeds up the calc_lon
function by a factor of 31.2, thereby decreasing its time share
within the overall Potrace algorithm from 72.6% to 7.82%, and
speeding up the overall algorithm by a factor of 3.36. On another
input file, calc_lon was sped up by a factor of 6.7, decreasing its
time share from 51.4% to 13.61%, and speeding up the overall
algorithm by a factor of 1.78. In any case, the savings are
substantial. */
/* returns 0 on success, 1 on error with errno set */
static int calc_lon(privpath_t *pp) {
point_t *pt = pp->pt;
int n = pp->len;
int i, j, k, k1;
int ct[4], dir;
point_t constraint[2];
point_t cur;
point_t off;
int *pivk = NULL; /* pivk[n] */
int *nc = NULL; /* nc[n]: next corner */
point_t dk; /* direction of k-k1 */
int a, b, c, d;
SAFE_CALLOC(pivk, n, int);
SAFE_CALLOC(nc, n, int);
/* initialize the nc data structure. Point from each point to the
furthest future point to which it is connected by a vertical or
horizontal segment. We take advantage of the fact that there is
always a direction change at 0 (due to the path decomposition
algorithm). But even if this were not so, there is no harm, as
in practice, correctness does not depend on the word "furthest"
above. */
k = 0;
for (i=n-1; i>=0; i--) {
if (pt[i].x != pt[k].x && pt[i].y != pt[k].y) {
k = i+1; /* necessarily i<n-1 in this case */
}
nc[i] = k;
}
SAFE_CALLOC(pp->lon, n, int);
/* determine pivot points: for each i, let pivk[i] be the furthest k
such that all j with i<j<k lie on a line connecting i,k. */
for (i=n-1; i>=0; i--) {
ct[0] = ct[1] = ct[2] = ct[3] = 0;
/* keep track of "directions" that have occurred */
dir = (3+3*(pt[mod(i+1,n)].x-pt[i].x)+(pt[mod(i+1,n)].y-pt[i].y))/2;
ct[dir]++;
constraint[0].x = 0;
constraint[0].y = 0;
constraint[1].x = 0;
constraint[1].y = 0;
/* find the next k such that no straight line from i to k */
k = nc[i];
k1 = i;
while (1) {
dir = (3+3*sign(pt[k].x-pt[k1].x)+sign(pt[k].y-pt[k1].y))/2;
ct[dir]++;
/* if all four "directions" have occurred, cut this path */
if (ct[0] && ct[1] && ct[2] && ct[3]) {
pivk[i] = k1;
goto foundk;
}
cur.x = pt[k].x - pt[i].x;
cur.y = pt[k].y - pt[i].y;
/* see if current constraint is violated */
if (xprod(constraint[0], cur) < 0 || xprod(constraint[1], cur) > 0) {
goto constraint_viol;
}
/* else, update constraint */
if (abs(cur.x) <= 1 && abs(cur.y) <= 1) {
/* no constraint */
} else {
off.x = cur.x + ((cur.y>=0 && (cur.y>0 || cur.x<0)) ? 1 : -1);
off.y = cur.y + ((cur.x<=0 && (cur.x<0 || cur.y<0)) ? 1 : -1);
if (xprod(constraint[0], off) >= 0) {
constraint[0] = off;
}
off.x = cur.x + ((cur.y<=0 && (cur.y<0 || cur.x<0)) ? 1 : -1);
off.y = cur.y + ((cur.x>=0 && (cur.x>0 || cur.y<0)) ? 1 : -1);
if (xprod(constraint[1], off) <= 0) {
constraint[1] = off;
}
}
k1 = k;
k = nc[k1];
if (!cyclic(k,i,k1)) {
break;
}
}
constraint_viol:
/* k1 was the last "corner" satisfying the current constraint, and
k is the first one violating it. We now need to find the last
point along k1..k which satisfied the constraint. */
dk.x = sign(pt[k].x-pt[k1].x);
dk.y = sign(pt[k].y-pt[k1].y);
cur.x = pt[k1].x - pt[i].x;
cur.y = pt[k1].y - pt[i].y;
/* find largest integer j such that xprod(constraint[0], cur+j*dk)
>= 0 and xprod(constraint[1], cur+j*dk) <= 0. Use bilinearity
of xprod. */
a = xprod(constraint[0], cur);
b = xprod(constraint[0], dk);
c = xprod(constraint[1], cur);
d = xprod(constraint[1], dk);
/* find largest integer j such that a+j*b>=0 and c+j*d<=0. This
can be solved with integer arithmetic. */