+
+typedef struct svp_segment_part
+{
+ double y1;
+ double y2;
+ char active;
+} svp_segment_part_t;
+
+int compare_double(const void*_y1, const void*_y2)
+{
+ const double*y1 = _y1;
+ const double*y2 = _y2;
+ if(*y1<*y2) return -1;
+ if(*y1>*y2) return 1;
+ else return 0;
+}
+
+int compare_seg_start(const void*_s1, const void*_s2)
+{
+ svp_segment_part_t*s1 = *(svp_segment_part_t**)_s1;
+ svp_segment_part_t*s2 = *(svp_segment_part_t**)_s2;
+ if(s1->y1 < s2->y1) return -1;
+ if(s1->y1 > s2->y1) return 1;
+ else return 0;
+}
+
+int compare_seg_end(const void*_s1, const void*_s2)
+{
+ svp_segment_part_t*s1 = *(svp_segment_part_t**)_s1;
+ svp_segment_part_t*s2 = *(svp_segment_part_t**)_s2;
+ if(s1->y2 < s2->y2) return -1;
+ if(s1->y2 > s2->y2) return 1;
+ else return 0;
+}
+
+void clean_svp(ArtSVP*svp)
+{
+ int t;
+ int oldpoints = 0;
+ int newpoints = 0;
+ int oldsegs = 0;
+ int newsegs = 0;
+ for(t=0;t<svp->n_segs;t++) {
+ ArtSVPSeg* seg = &svp->segs[t];
+ int p;
+ int pos=0;
+ double lasty = 0;
+ oldpoints += seg->n_points;
+ for(p=0;p<seg->n_points;p++) {
+ ArtPoint* p1 = &seg->points[p];
+ if(!p || lasty!=p1->y) {
+ seg->points[pos] = seg->points[p];
+ pos++;
+ lasty = p1->y;
+ }
+ }
+ seg->n_points = pos;
+ newpoints += seg->n_points;
+ }
+ int pos = 0;
+ oldsegs = svp->n_segs;
+ for(t=0;t<svp->n_segs;t++) {
+ if(svp->segs[t].n_points > 1) {
+ svp->segs[pos++] = svp->segs[t];
+ }
+ }
+ svp->n_segs = pos;
+ newsegs = svp->n_segs;
+ if(newsegs < oldsegs || newpoints < oldpoints) {
+ msg("<verbose> Simplified polygon from %d points to %d points, %d to %d segs",
+ oldpoints, newpoints, oldsegs, newsegs);
+ }
+}
+
+int check_svp(ArtSVP*svp)
+{
+ /* count number of y coordinates and segs */
+ int t;
+ int num_points = 0;
+ int num_segs = 0;
+ for(t=0;t<svp->n_segs;t++) {
+ if(!svp->segs[t].n_points) {
+ msg("<error> svp contains segment with zero points\n");
+ return 0;
+ }
+ num_points += svp->segs[t].n_points;
+ num_segs += svp->segs[t].n_points - 1;
+ }
+
+ /* create segs and ys */
+ double*y = malloc(sizeof(double)*num_points);
+ svp_segment_part_t*segs = malloc(sizeof(svp_segment_part_t)*num_segs);
+ svp_segment_part_t**seg_start = malloc(sizeof(svp_segment_part_t*)*num_segs);
+ svp_segment_part_t**seg_end = malloc(sizeof(svp_segment_part_t*)*num_segs);
+
+ int c1=0;
+ num_segs = 0;
+ for(t=0;t<svp->n_segs;t++) {
+ ArtSVPSeg* seg = &svp->segs[t];
+ int p;
+ for(p=0;p<seg->n_points;p++) {
+ y[c1++] = seg->points[p].y;
+ assert(c1 <= num_points);
+ }
+ for(p=0;p<seg->n_points-1;p++) {
+ ArtPoint* p1 = &seg->points[p];
+ ArtPoint* p2 = &seg->points[p+1];
+
+ if(p1->y >= p2->y) {
+ if(p1->y > p2->y) {
+ msg("<error> bad svp, y in seg is non-increasing %.16f -> %.16f\n", p1->y, p2->y);
+ }
+ } else {
+ segs[num_segs].y1 = p1->y;
+ segs[num_segs].y2 = p2->y;
+ segs[num_segs].active = 0;
+ seg_start[num_segs] = &segs[num_segs];
+ seg_end[num_segs] = &segs[num_segs];
+ num_segs++;
+ }
+ }
+ }
+
+ qsort(y, num_points, sizeof(double), compare_double);
+ qsort(seg_start, num_segs, sizeof(svp_segment_part_t*), compare_seg_start);
+ qsort(seg_end, num_segs, sizeof(svp_segment_part_t*), compare_seg_end);
+
+ double lasty = num_points?y[0]+1:0;
+ int num_active = 0;
+ int bleed = 0;
+ double bleedy1=0,bleedy2 = 0;
+ for(t=0;t<num_points;t++) {
+ if(lasty == y[t])
+ continue;
+ int s;
+ for(s=0;s<num_segs;s++) {
+ if(segs[s].y1==y[t]) {
+ /* segment is starting */
+ segs[s].active = 1;
+ num_active++;
+ } else if(segs[s].y2==y[t]) {
+ segs[s].active = 0;
+ num_active--;
+ }
+ }
+ if(num_active&1) {
+ bleed = num_active;
+ bleedy1 = y[t];
+ } else {
+ if(bleed) {
+ bleedy2 = y[t];
+ break;
+ }
+ }
+ lasty = y[t];
+ }
+ if(bleed) {
+ msg("<verbose> svp bleeds from y=%.16f to y=%.16f (%d/%d active segments)\n",
+ bleedy1, bleedy2,
+ bleed, num_segs);
+ free(y);free(segs);free(seg_start);free(seg_end);
+ return 0;
+ }
+
+ free(y);
+ free(segs);
+ free(seg_start);
+ free(seg_end);
+
+ return 1;
+}
+
+void write_svp_postscript(const char*filename, ArtSVP*svp)
+{
+ if(!svp)
+ return;
+ FILE*fi = fopen(filename, "wb");
+ int i, j;
+ double xmin=0,ymin=0,xmax=0,ymax=0;
+ fprintf(fi, "%% begin\n");
+ for (i = 0; i < svp->n_segs; i++) {
+ for (j = 0; j < svp->segs[i].n_points; j++) {
+ double x = svp->segs[i].points[j].x;
+ double y = svp->segs[i].points[j].y;
+ if(i==0 && j==0) {
+ xmin = xmax = x;
+ ymin = ymax = y;
+ } else {
+ if(x < xmin) xmin = x;
+ if(x > xmax) xmax = x;
+ if(y < ymin) ymin = y;
+ if(y > ymax) ymax = y;
+ }
+ }
+ }
+ if(xmax == xmin) xmax=xmin+1;
+ if(ymax == ymin) ymax=ymin+1;
+
+ for (i = 0; i < svp->n_segs; i++)
+ {
+ fprintf(fi, "%g setgray\n", svp->segs[i].dir ? 0.7 : 0);
+ for (j = 0; j < svp->segs[i].n_points; j++)
+ {
+ //fprintf(fi, "%g %g %s\n",
+ // 20 + 550*(svp->segs[i].points[j].x-xmin)/(xmax-xmin),
+ // 820 - 800*(svp->segs[i].points[j].y-ymin)/(ymax-ymin),
+ // j ? "lineto" : "moveto");
+ fprintf(fi, "%.32f %.32f %s\n",
+ svp->segs[i].points[j].x,
+ svp->segs[i].points[j].y,
+ j ? "lineto" : "moveto");
+ }
+ fprintf(fi, "stroke\n");
+ }
+
+ fprintf(fi, "showpage\n");
+ fclose(fi);
+}
+
+void write_vpath_postscript(const char*filename, ArtVpath*path)
+{
+ FILE*fi = fopen(filename, "wb");
+ int i, j;
+ double xmin=0,ymin=0,xmax=0,ymax=0;
+ fprintf(fi, "%% begin\n");
+ ArtVpath*p = path;
+ char first = 1;
+ while(p->code != ART_END) {
+ if(p->code == ART_MOVETO || p->code == ART_MOVETO_OPEN) {
+ if(!first)
+ fprintf(fi, "stroke\n");
+ first = 0;
+ fprintf(fi, "0.0 setgray\n");
+ fprintf(fi, "%.32f %.32f moveto\n", p->x, p->y);
+ } else {
+ fprintf(fi, "%.32f %.32f lineto\n", p->x, p->y);
+ }
+ p++;
+ }
+ if(!first)
+ fprintf(fi, "stroke\n");
+ fprintf(fi, "showpage\n");
+ fclose(fi);
+}
+
+void write_gfxline_postscript(const char*filename, gfxline_t*line)
+{
+ FILE*fi = fopen(filename, "wb");
+ int i, j;
+ fprintf(fi, "%% begin\n");
+ char first = 1;
+ while(line) {
+ if(line->type == gfx_moveTo) {
+ if(!first)
+ fprintf(fi, "stroke\n");
+ first = 0;
+ fprintf(fi, "0.0 setgray\n");
+ fprintf(fi, "%.32f %.32f moveto\n", line->x, line->y);
+ } else {
+ fprintf(fi, "%.32f %.32f lineto\n", line->x, line->y);
+ }
+ line = line->next;
+ }
+ if(!first)
+ fprintf(fi, "stroke\n");
+ fprintf(fi, "showpage\n");
+ fclose(fi);
+}
+
+static int vpath_len(ArtVpath*svp)
+{
+ int len = 0;
+ while(svp->code != ART_END) {
+ svp ++;
+ len ++;
+ }
+ return len;
+}
+
+int gfxline_len(gfxline_t*line)
+{
+ gfxline_t*i = line;
+ int len = 0;
+ while(i) {
+ len ++;
+ i = i->next;
+ }
+ return len;
+}
+
+static ArtVpath*pvpath= 0;
+static int cmppos(const void*_p1, const void*_p2)
+{
+ int*p1 = (int*)_p1;
+ int*p2 = (int*)_p2;
+ ArtVpath*v1 = &pvpath[*p1];
+ ArtVpath*v2 = &pvpath[*p2];
+ if(v1->y < v2->y)
+ return -1;
+ else if(v1->y > v2->y)
+ return 1;
+ else if(v1->x < v2->x)
+ return -2;
+ else if(v1->x > v2->x)
+ return 2;
+ else
+ return 0;
+}
+
+#define PERTURBATION 2e-3
+static void my_perturb(ArtVpath*vpath)
+{
+ int t;
+ int len = vpath_len(vpath);
+ int*pos = (int*)malloc(len*sizeof(int));
+ for(t=0;t<len;t++)
+ pos[t] = t;
+ pvpath = vpath;
+ qsort(pos, len, sizeof(int), cmppos);
+ t=0;
+ while(t<len) {
+ int t2=t+1;
+ while(t2<len && !cmppos(&pos[t],&pos[t2])) {
+ t2++;
+ }
+
+ double dx = (PERTURBATION * rand ()) / RAND_MAX - PERTURBATION * 0.5;
+ double dy = (PERTURBATION * rand ()) / RAND_MAX - PERTURBATION * 0.5;
+ int s;
+ for(s=t;s<t2;s++) {
+ vpath[pos[s]].x += dx;
+ vpath[pos[s]].y += dy;
+ }
+ t = t2;
+ }
+ free(pos);
+ pvpath = 0;
+}
+
+static ArtSVP* gfxfillToSVP(gfxline_t*line, int perturb)