← Back to branch summary

~ubuntu-branches/debian/experimental/inkscape/experimental

« back to all changes in this revision

Viewing changes to src/trace/potrace/decompose.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Thomas Viehmann
  • Date: 2008-09-09 23:29:02 UTC
  • mfrom: (1.1.7 upstream)
  • Revision ID: james.westby@ubuntu.com-20080909232902-c50iujhk1w79u8e7
Tags: 0.46-2.1
http://bugs.debian.org/487623
* Non-maintainer upload.
* Add upstream patch fixing a crash in the open dialog
  in the zh_CN.utf8 locale. Closes: #487623.
  Thanks to Luca Bruno for the patch.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/trace/potrace/decompose.cpp
1
 
/* Copyright (C) 2001-2005 Peter Selinger.
2
 
   This file is part of potrace. It is free software and it is covered
 
1
/* Copyright (C) 2001-2007 Peter Selinger.
 
2
   This file is part of Potrace. It is free software and it is covered
3
3
   by the GNU General Public License. See the file COPYING for details. */
4
4
 
5
 
/* $Id: decompose.cpp 10957 2006-02-28 23:16:27Z ishmal $ */
 
5
/* $Id: /local/inkscape.rel.46/src/trace/potrace/decompose.cpp 16879 2007-10-26T21:01:30.934311Z ishmal  $ */
6
6
 
 
7
#include <stdio.h>
7
8
#include <stdlib.h>
 
9
#include <string.h>
8
10
#include <limits.h>
9
11
 
 
12
#include "potracelib.h"
 
13
#include "curve.h"
10
14
#include "lists.h"
 
15
#include "auxiliary.h"
11
16
#include "bitmap.h"
12
17
#include "decompose.h"
 
18
#include "progress.h"
13
19
 
14
20
/* ---------------------------------------------------------------------- */
15
21
/* auxiliary bitmap manipulations */
49
55
/* ---------------------------------------------------------------------- */
50
56
/* auxiliary functions */
51
57
 
52
 
/* return a "random" value which deterministically depends on x,y */
 
58
/* deterministically and efficiently hash (x,y) into a pseudo-random bit */
53
59
static inline int detrand(int x, int y) {
54
 
  srand(x+123456789*y);
55
 
  return rand();
 
60
  unsigned int z;
 
61
  static const unsigned char t[256] = { 
 
62
    /* non-linear sequence: constant term of inverse in GF(8), 
 
63
       mod x^8+x^4+x^3+x+1 */
 
64
    0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 
 
65
    0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 
 
66
    0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 
 
67
    1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 
 
68
    0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 
 
69
    0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 
 
70
    0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 
 
71
    0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 
 
72
    1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 
 
73
    0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 
 
74
    1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 
 
75
  };
 
76
 
 
77
  /* 0x04b3e375 and 0x05a8ef93 are chosen to contain every possible
 
78
     5-bit sequence */
 
79
  z = ((0x04b3e375 * x) ^ y) * 0x05a8ef93;
 
80
  z = t[z & 0xff] ^ t[(z>>8) & 0xff] ^ t[(z>>16) & 0xff] ^ t[(z>>24) & 0xff];
 
81
  return z & 1;
56
82
}
57
83
 
58
84
/* return the "majority" value of bitmap bm at intersection (x,y). We
86
112
  int xhi = x & -BM_WORDBITS;
87
113
  int xlo = x & (BM_WORDBITS-1);  /* = x % BM_WORDBITS */
88
114
  int i;
89
 
 
 
115
  
90
116
  if (xhi<xa) {
91
117
    for (i = xhi; i < xa; i+=BM_WORDBITS) {
92
118
      *bm_index(bm, i, y) ^= BM_ALLBITS;
183
209
  len = size = 0;
184
210
  pt = NULL;
185
211
  area = 0;
186
 
 
 
212
  
187
213
  while (1) {
188
214
    /* add point to path */
189
215
    if (len>=size) {
190
 
      size+=100;
191
 
      //size*=1.3;
192
 
      size = size * 13 / 10;
 
216
      size += 100;
 
217
      size = (int)(1.3 * size);
193
218
      pt1 = (point_t *)realloc(pt, size * sizeof(point_t));
194
219
      if (!pt1) {
195
220
        goto error;
199
224
    pt[len].x = x;
200
225
    pt[len].y = y;
201
226
    len++;
202
 
 
 
227
    
203
228
    /* move to next point */
204
229
    x += dirx;
205
230
    y += diry;
206
231
    area += x*diry;
207
 
 
 
232
    
208
233
    /* path complete? */
209
234
    if (x==x0 && y==y0) {
210
235
      break;
211
236
    }
212
 
 
 
237
    
213
238
    /* determine next direction */
214
239
    c = BM_GET(bm, x + (dirx+diry-1)/2, y + (diry-dirx-1)/2);
215
240
    d = BM_GET(bm, x + (dirx-diry-1)/2, y + (diry+dirx-1)/2);
216
 
 
 
241
    
217
242
    if (c && !d) {               /* ambiguous turn */
218
243
      if (turnpolicy == POTRACE_TURNPOLICY_RIGHT
219
244
          || (turnpolicy == POTRACE_TURNPOLICY_BLACK && sign == '+')
220
245
          || (turnpolicy == POTRACE_TURNPOLICY_WHITE && sign == '-')
221
 
          || (turnpolicy == POTRACE_TURNPOLICY_RANDOM && (detrand(x,y) & 1))
 
246
          || (turnpolicy == POTRACE_TURNPOLICY_RANDOM && detrand(x,y))
222
247
          || (turnpolicy == POTRACE_TURNPOLICY_MAJORITY && majority(bm, x, y))
223
248
          || (turnpolicy == POTRACE_TURNPOLICY_MINORITY && !majority(bm, x, y))) {
224
249
        tmp = dirx;              /* right turn */
252
277
  p->sign = sign;
253
278
 
254
279
  return p;
255
 
 
 
280
 
256
281
 error:
257
282
   free(pt);
258
 
   return NULL;
 
283
   return NULL; 
259
284
}
260
285
 
261
286
/* Give a tree structure to the given path list, based on "insideness"
281
306
  path_t *head;
282
307
  path_t **hook, **hook_in, **hook_out; /* for fast appending to linked list */
283
308
  bbox_t bbox;
284
 
 
 
309
  
285
310
  bm_clear(bm, 0);
286
311
 
287
312
  /* save original "next" pointers */
289
314
    p->sibling = p->next;
290
315
    p->childlist = NULL;
291
316
  }
292
 
 
 
317
  
293
318
  heap = plist;
294
319
 
295
320
  /* the heap holds a list of lists of paths. Use "childlist" field
304
329
    cur = heap;
305
330
    heap = heap->childlist;
306
331
    cur->childlist = NULL;
307
 
 
 
332
  
308
333
    /* unlink first path */
309
334
    head = cur;
310
335
    cur = cur->next;
347
372
      heap = head->childlist;
348
373
    }
349
374
  }
350
 
 
 
375
  
351
376
  /* copy sibling structure from "next" to "sibling" component */
352
377
  p = plist;
353
378
  while (p) {
373
398
      /* p is a positive path */
374
399
      /* append to linked list */
375
400
      list_insert_beforehook(p, hook);
376
 
 
 
401
      
377
402
      /* go through its children */
378
403
      for (p1=p->childlist; p1; p1=p1->sibling) {
379
404
        /* append to linked list */
441
466
 
442
467
  /* iterate through components */
443
468
  y = bm1->h - 1;
444
 
  while (findnext(bm1, &x, &y) == 0) {
 
469
  while (findnext(bm1, &x, &y) == 0) { 
445
470
    /* calculate the sign by looking at the original */
446
471
    sign = BM_GET(bm, x, y) ? '+' : '-';
447
472