0   /* 

1    * A javascript port of Potrace (http://potrace.sourceforge.net).

2    * 

3    * Licensed under the GPL

4    * 

5    * Usage

6    *   loadImageFromFile(file) : load image from File API

7    *   loadImageFromUrl(url): load image from URL

8    *     because of the same-origin policy, can not load image from another domain.

9    *     input color/grayscale image is simply converted to binary image. no pre-

10   *     process is performed.

11   * 

12   *   setParameter({para1: value, ...}) : set parameters

13   *     parameters:

14   *        turnpolicy ("black" / "white" / "left" / "right" / "minority" / "majority")

15   *          how to resolve ambiguities in path decomposition. (default: "minority")       

16   *        turdsize

17   *          suppress speckles of up to this size (default: 2)

18   *        optcurve (true / false)

19   *          turn on/off curve optimization (default: true)

20   *        alphamax

21   *          corner threshold parameter (default: 1)

22   *        opttolerance 

23   *          curve optimization tolerance (default: 0.2)

24   *       

25   *   process(callback) : wait for the image be loaded, then run potrace algorithm,

26   *                       then call callback function.

27   * 

28   *   getSVG: getSVG(size, opt_type) : return a string of generated SVG image.

29   *                                    result_image_size = original_image_size * size

30   *                                    optional parameter opt_type can be "curve"

31   */

32  

33  var Potrace = (function() {

34  

35    function Point(x, y) {

36      this.x = x;

37      this.y = y;

38    }

39    

40    Point.prototype.copy = function(){

41      return new Point(this.x, this.y);

42    };

43  

44    function Bitmap(w, h) {

45      this.w = w;

46      this.h = h;

47      this.size = w * h;

48      this.arraybuffer = new ArrayBuffer(this.size);

49      this.data = new Int8Array(this.arraybuffer);

50    }

51  

52    Bitmap.prototype.at = function (x, y) {

53      return (x >= 0 && x < this.w && y >=0 && y < this.h) && 

54          this.data[this.w * y + x] === 1;

55    };

56  

57    Bitmap.prototype.index = function(i) {

58      var point = new Point();

59      point.y = Math.floor(i / this.w);

60      point.x = i - point.y * this.w;

61      return point;

62    };

63  

64    Bitmap.prototype.flip = function(x, y) {

65      if (this.at(x, y)) {

66        this.data[this.w * y + x] = 0;

67      } else {

68        this.data[this.w * y + x] = 1;

69      }

70    };

71      

72    Bitmap.prototype.copy = function() {

73      var bm = new Bitmap(this.w, this.h), i;

74      for (i = 0; i < this.size; i++) {

75        bm.data[i] = this.data[i];

76      }

77      return bm;

78    };

79  

80    function Path() {

81      this.area = 0;

82      this.len = 0;

83      this.curve = {};

84      this.pt = [];

85      this.minX = 100000;

86      this.minY = 100000;

87      this.maxX= -1;

88      this.maxY = -1;

89    }

90  

91    function Curve(n) {

92      this.n = n;

93      this.tag = new Array(n);

94      this.c = new Array(n * 3);

95      this.alphaCurve = 0;

96      this.vertex = new Array(n);

97      this.alpha = new Array(n);

98      this.alpha0 = new Array(n);

99      this.beta = new Array(n);

100   }

101 

102   var imgElement = document.createElement("img"),

103       imgCanvas = document.createElement("canvas"),

104       bm = null,

105       pathlist = [],

106       callback,

107       info = {

108         isReady: false,

109         turnpolicy: "minority", 

110         turdsize: 2,

111         optcurve: true,

112         alphamax: 1,

113         opttolerance: 0.2

114       };

115 

116   imgElement.onload = function() {

117     loadCanvas();

118     loadBm();

119   };

120 

121   function loadImageFromFile(file) {

122     if (info.isReady) {

123       clear();

124     }

125     imgElement.file = file;

126     var reader = new FileReader();

127     reader.onload = (function(aImg) {

128       return function(e) {

129         aImg.src = e.target.result;

130       };

131     })(imgElement);

132     reader.readAsDataURL(file);

133   }

134   

135   function loadImageFromUrl(url) {

136     if (info.isReady) {

137       clear();

138     }

139     imgElement.src = url;

140     

141   }

142   

143   function setParameter(obj) {

144    var key;

145    for (key in obj) {

146      if (obj.hasOwnProperty(key)) {

147        info[key] = obj[key];

148      }

149     }

150   }

151   

152   function loadCanvas() {

153     imgCanvas.width = imgElement.width;

154     imgCanvas.height = imgElement.height;

155     var ctx = imgCanvas.getContext('2d');

156     ctx.drawImage(imgElement, 0, 0);

157   }

158   

159   function loadBm() {

160     var ctx = imgCanvas.getContext('2d');

161     bm = new Bitmap(imgCanvas.width, imgCanvas.height);

162     var imgdataobj = ctx.getImageData(0, 0, bm.w, bm.h);

163     var l = imgdataobj.data.length, i, j, color;

164     for (i = 0, j = 0; i < l; i += 4, j++) {

165       color = 0.2126 * imgdataobj.data[i] + 0.7153 * imgdataobj.data[i + 1] +

166           0.0721 * imgdataobj.data[i + 2];

167       bm.data[j] = (color < 128 ? 1 : 0);

168     }

169     info.isReady = true;

170   }

171   

172   

173   function bmToPathlist() {

174   

175     var bm1 = bm.copy(),

176       currentPoint = new Point(0, 0),

177       path;

178     

179     function findNext(point) {

180       var i = bm1.w * point.y + point.x;

181       while (i < bm1.size && bm1.data[i] !== 1) {

182         i++;

183       }

184       return i < bm1.size && bm1.index(i);

185     }

186     

187     function majority(x, y) {

188       var i, a, ct;

189       for (i = 2; i < 5; i++) {

190         ct = 0;

191         for (a = -i + 1; a <= i - 1; a++) {

192           ct += bm1.at(x + a, y + i - 1) ? 1 : -1;

193           ct += bm1.at(x + i - 1, y + a - 1) ? 1 : -1;

194           ct += bm1.at(x + a - 1, y - i) ? 1 : -1;

195           ct += bm1.at(x - i, y + a) ? 1 : -1;

196         }

197         if (ct > 0) {

198           return 1;

199         } else if (ct < 0) {

200           return 0;

201         }

202       }

203       return 0;

204     }

205     

206     function findPath(point) {

207       var path = new Path(),

208         x = point.x, y = point.y,

209         dirx = 0, diry = 1, tmp;

210       

211       path.sign = bm.at(point.x, point.y) ? "+" : "-";

212       

213       while (1) {

214         path.pt.push(new Point(x, y));

215         if (x > path.maxX)

216           path.maxX = x;

217         if (x < path.minX)

218           path.minX = x;

219         if (y > path.maxY)

220           path.maxY = y;

221         if (y < path.minY)

222           path.minY = y;

223         path.len++;

224         

225         x += dirx;

226         y += diry;

227         path.area -= x * diry;

228         

229         if (x === point.x && y === point.y)

230           break;

231         

232         var l = bm1.at(x + (dirx + diry - 1 ) / 2, y + (diry - dirx - 1) / 2);

233         var r = bm1.at(x + (dirx - diry - 1) / 2, y + (diry + dirx - 1) / 2);

234         

235         if (r && !l) {

236           if (info.turnpolicy === "right" ||

237           (info.turnpolicy === "black" && path.sign === '+') ||

238           (info.turnpolicy === "white" && path.sign === '-') ||

239           (info.turnpolicy === "majority" && majority(x, y)) ||

240           (info.turnpolicy === "minority" && !majority(x, y))) {

241             tmp = dirx;

242             dirx = -diry;

243             diry = tmp;

244           } else {

245             tmp = dirx;

246             dirx = diry;

247             diry = -tmp;

248           }

249         } else if (r) {

250           tmp = dirx;

251           dirx = -diry;

252           diry = tmp;

253         } else if (!l) {

254           tmp = dirx;

255           dirx = diry;

256           diry = -tmp;

257         }

258       }

259       return path;

260     }

261     

262     function xorPath(path){

263       var y1 = path.pt[0].y,

264         len = path.len,

265         x, y, maxX, minY, i, j;

266       for (i = 1; i < len; i++) {

267         x = path.pt[i].x;

268         y = path.pt[i].y;

269         

270         if (y !== y1) {

271           minY = y1 < y ? y1 : y;

272           maxX = path.maxX;

273           for (j = x; j < maxX; j++) {

274             bm1.flip(j, minY);

275           }

276           y1 = y;

277         }

278       }

279       

280     }

281     

282     while (currentPoint = findNext(currentPoint)) {

283 

284       path = findPath(currentPoint);

285       

286       xorPath(path);

287       

288       if (path.area > info.turdsize) {

289         pathlist.push(path);

290       }

291     }

292     

293   }

294   

295 

296   function processPath() {

297   

298     function Quad() {

299       this.data = [0,0,0,0,0,0,0,0,0];

300     }

301 

302     Quad.prototype.at = function(x, y) {

303       return this.data[x * 3 + y];

304     };

305     

306     function Sum(x, y, xy, x2, y2) {

307       this.x = x;

308       this.y = y;

309       this.xy = xy;

310       this.x2 = x2;

311       this.y2 = y2;

312     }

313     

314     function mod(a, n) {

315         return a >= n ? a % n : a>=0 ? a : n-1-(-1-a) % n;

316     }

317   

318     function xprod(p1, p2) {

319       return p1.x * p2.y - p1.y * p2.x;

320     }

321     

322     function cyclic(a, b, c) {

323       if (a <= c) {

324         return (a <= b && b < c);

325       } else {

326         return (a <= b || b < c);

327       }

328     }

329       

330     function sign(i) {

331       return i > 0 ? 1 : i < 0 ? -1 : 0;

332     }

333     

334     function quadform(Q, w) {

335       var v = new Array(3), i, j, sum;

336     

337       v[0] = w.x;

338       v[1] = w.y;

339       v[2] = 1;

340       sum = 0.0;

341     

342       for (i=0; i<3; i++) {

343         for (j=0; j<3; j++) {

344           sum += v[i] * Q.at(i, j) * v[j];

345         }

346       }

347       return sum;

348     }

349   

350     function interval(lambda, a, b) {

351       var res = new Point();

352     

353       res.x = a.x + lambda * (b.x - a.x);

354       res.y = a.y + lambda * (b.y - a.y);

355       return res;

356     }

357     

358     function dorth_infty(p0, p2) {

359       var r = new Point();

360       

361       r.y = sign(p2.x - p0.x);

362       r.x = -sign(p2.y - p0.y);

363     

364       return r;

365     }

366     

367     function ddenom(p0, p2) {

368       var r = dorth_infty(p0, p2);

369     

370       return r.y * (p2.x - p0.x) - r.x * (p2.y - p0.y);

371     }

372     

373     function dpara(p0, p1, p2) {

374       var x1, y1, x2, y2;

375     

376       x1 = p1.x - p0.x;

377       y1 = p1.y - p0.y;

378       x2 = p2.x - p0.x;

379       y2 = p2.y - p0.y;

380     

381       return x1 * y2 - x2 * y1;

382     }

383     

384     function cprod(p0, p1, p2, p3) {

385       var x1, y1, x2, y2;

386     

387       x1 = p1.x - p0.x;

388       y1 = p1.y - p0.y;

389       x2 = p3.x - p2.x;

390       y2 = p3.y - p2.y;

391     

392       return x1 * y2 - x2 * y1;

393     }

394       

395     function iprod(p0, p1, p2) {

396       var x1, y1, x2, y2;

397     

398       x1 = p1.x - p0.x;

399       y1 = p1.y - p0.y;

400       x2 = p2.x - p0.x;

401       y2 = p2.y - p0.y;

402     

403       return x1*x2 + y1*y2;

404     }

405       

406     function iprod1(p0, p1, p2, p3) {

407       var x1, y1, x2, y2;

408     

409       x1 = p1.x - p0.x;

410       y1 = p1.y - p0.y;

411       x2 = p3.x - p2.x;

412       y2 = p3.y - p2.y;

413     

414       return x1 * x2 + y1 * y2;

415     }

416     

417     function ddist(p, q) {

418       return Math.sqrt((p.x - q.x) * (p.x - q.x) + (p.y - q.y) * (p.y - q.y));

419     }

420     

421     function bezier(t, p0, p1, p2, p3) {

422       var s = 1 - t, res = new Point();

423     

424       res.x = s*s*s*p0.x + 3*(s*s*t)*p1.x + 3*(t*t*s)*p2.x + t*t*t*p3.x;

425       res.y = s*s*s*p0.y + 3*(s*s*t)*p1.y + 3*(t*t*s)*p2.y + t*t*t*p3.y;

426     

427       return res;

428     }

429   

430     function tangent(p0, p1, p2, p3, q0, q1) {

431       var A, B, C, a, b, c, d, s, r1, r2;

432     

433       A = cprod(p0, p1, q0, q1);

434       B = cprod(p1, p2, q0, q1);

435       C = cprod(p2, p3, q0, q1);

436     

437       a = A - 2 * B + C;

438       b = -2 * A + 2 * B;

439       c = A;

440       

441       d = b * b - 4 * a * c;

442     

443       if (a===0 || d<0) {

444         return -1.0;

445       }

446     

447       s = Math.sqrt(d);

448     

449       r1 = (-b + s) / (2 * a);

450       r2 = (-b - s) / (2 * a);

451     

452       if (r1 >= 0 && r1 <= 1) {

453         return r1;

454       } else if (r2 >= 0 && r2 <= 1) {

455         return r2;

456       } else {

457         return -1.0;

458       }

459     }

460     

461     function calcSums(path) {

462       var i, x, y;

463       path.x0 = path.pt[0].x;

464       path.y0 = path.pt[0].y;

465       

466       path.sums = [];

467       var s = path.sums;

468       s.push(new Sum(0, 0, 0, 0, 0));

469       for(i = 0; i < path.len; i++){

470         x = path.pt[i].x - path.x0;

471         y = path.pt[i].y - path.y0;

472         s.push(new Sum(s[i].x + x, s[i].y + y, s[i].xy + x * y,

473             s[i].x2 + x * x, s[i].y2 + y * y));

474       }

475     }

476    

477     function calcLon(path) {

478       

479       var n = path.len, pt = path.pt, dir,

480         pivk = new Array(n),

481         nc = new Array(n),

482         ct = new Array(4);

483       path.lon = new Array(n);

484       

485       var constraint = [new Point(), new Point()],

486           cur = new Point(),

487           off = new Point(),

488           dk = new Point(),

489           foundk;

490       

491       var i, j, k1, a, b, c, d, k = 0;

492       for(i = n - 1; i >= 0; i--){

493         if (pt[i].x != pt[k].x && pt[i].y != pt[k].y) {

494           k = i + 1;

495         }

496         nc[i] = k;

497       }

498       

499       for (i = n - 1; i >= 0; i--) {

500         ct[0] = ct[1] = ct[2] = ct[3] = 0;

501         dir = (3 + 3 * (pt[mod(i + 1, n)].x - pt[i].x) + 

502             (pt[mod(i + 1, n)].y - pt[i].y)) / 2;

503         ct[dir]++;

504         

505         constraint[0].x = 0;

506         constraint[0].y = 0;

507         constraint[1].x = 0;

508         constraint[1].y = 0;

509         

510         k = nc[i];

511         k1 = i;

512         while (1) {

513           foundk = 0;

514           dir =  (3 + 3 * sign(pt[k].x - pt[k1].x) + 

515               sign(pt[k].y - pt[k1].y)) / 2;

516           ct[dir]++;

517           

518           if (ct[0] && ct[1] && ct[2] && ct[3]) {

519             pivk[i] = k1;

520             foundk = 1;

521             break;

522           }

523           

524           cur.x = pt[k].x - pt[i].x;

525           cur.y = pt[k].y - pt[i].y;

526           

527           if (xprod(constraint[0], cur) < 0 || xprod(constraint[1], cur) > 0) {

528             break;

529           }

530               

531           if (Math.abs(cur.x) <= 1 && Math.abs(cur.y) <= 1) {

532           

533           } else {

534             off.x = cur.x + ((cur.y >= 0 && (cur.y > 0 || cur.x < 0)) ? 1 : -1);

535             off.y = cur.y + ((cur.x <= 0 && (cur.x < 0 || cur.y < 0)) ? 1 : -1);

536             if (xprod(constraint[0], off) >= 0) {

537               constraint[0].x = off.x;

538               constraint[0].y = off.y;

539             }

540             off.x = cur.x + ((cur.y <= 0 && (cur.y < 0 || cur.x < 0)) ? 1 : -1);

541             off.y = cur.y + ((cur.x >= 0 && (cur.x > 0 || cur.y < 0)) ? 1 : -1);

542             if (xprod(constraint[1], off) <= 0) {

543               constraint[1].x = off.x;

544               constraint[1].y = off.y;

545             }

546           }

547           k1 = k;

548           k = nc[k1];

549           if (!cyclic(k, i, k1)) {

550             break;

551           }

552         }

553         if (foundk === 0) {

554           dk.x = sign(pt[k].x-pt[k1].x);

555           dk.y = sign(pt[k].y-pt[k1].y);

556           cur.x = pt[k1].x - pt[i].x;

557           cur.y = pt[k1].y - pt[i].y;

558   

559           a = xprod(constraint[0], cur);

560           b = xprod(constraint[0], dk);

561           c = xprod(constraint[1], cur);

562           d = xprod(constraint[1], dk);

563   

564           j = 10000000;

565           if (b < 0) {

566             j = Math.floor(a / -b);

567           }

568           if (d > 0) {

569             j = Math.min(j, Math.floor(-c / d));

570           }

571           pivk[i] = mod(k1+j,n);

572         }

573       }

574       

575       j=pivk[n-1];

576       path.lon[n-1]=j;

577       for (i=n-2; i>=0; i--) {

578         if (cyclic(i+1,pivk[i],j)) {

579           j=pivk[i];

580         }

581         path.lon[i]=j;

582       }

583   

584       for (i=n-1; cyclic(mod(i+1,n),j,path.lon[i]); i--) {

585         path.lon[i] = j;

586       }

587     }

588     

589     function bestPolygon(path) {

590       

591       function penalty3(path, i, j) {

592         

593         var n = path.len, pt = path.pt, sums = path.sums;

594         var x, y, xy, x2, y2,

595           k, a, b, c, s,

596           px, py, ex, ey,

597           r = 0;

598         if (j>=n) {

599           j -= n;

600           r = 1;

601         }

602         

603         if (r === 0) {

604           x = sums[j+1].x - sums[i].x;

605           y = sums[j+1].y - sums[i].y;

606           x2 = sums[j+1].x2 - sums[i].x2;

607           xy = sums[j+1].xy - sums[i].xy;

608           y2 = sums[j+1].y2 - sums[i].y2;

609           k = j+1 - i;

610         } else {

611           x = sums[j+1].x - sums[i].x + sums[n].x;

612           y = sums[j+1].y - sums[i].y + sums[n].y;

613           x2 = sums[j+1].x2 - sums[i].x2 + sums[n].x2;

614           xy = sums[j+1].xy - sums[i].xy + sums[n].xy;

615           y2 = sums[j+1].y2 - sums[i].y2 + sums[n].y2;

616           k = j+1 - i + n;

617         } 

618       

619         px = (pt[i].x + pt[j].x) / 2.0 - pt[0].x;

620         py = (pt[i].y + pt[j].y) / 2.0 - pt[0].y;

621         ey = (pt[j].x - pt[i].x);

622         ex = -(pt[j].y - pt[i].y);

623       

624         a = ((x2 - 2*x*px) / k + px*px);

625         b = ((xy - x*py - y*px) / k + px*py);

626         c = ((y2 - 2*y*py) / k + py*py);

627         

628         s = ex*ex*a + 2*ex*ey*b + ey*ey*c;

629       

630         return Math.sqrt(s);

631       }

632       

633       var i, j, m, k,    

634       n = path.len,

635       pen = new Array(n + 1),

636       prev = new Array(n + 1),

637       clip0 = new Array(n),

638       clip1 = new Array(n + 1),

639       seg0 = new Array (n + 1),

640       seg1 = new Array(n + 1),

641       thispen, best, c;

642       

643       for (i=0; i<n; i++) {

644         c = mod(path.lon[mod(i-1,n)]-1,n);

645         if (c == i) {

646           c = mod(i+1,n);

647         }

648         if (c < i) {

649           clip0[i] = n;

650         } else {

651           clip0[i] = c;

652         }

653       }

654       

655       j = 1;

656       for (i=0; i<n; i++) {

657         while (j <= clip0[i]) {

658           clip1[j] = i;

659           j++;

660         }

661       }

662       

663       i = 0;

664       for (j=0; i<n; j++) {

665         seg0[j] = i;

666         i = clip0[i];

667       }

668       seg0[j] = n;

669       m = j;

670     

671       i = n;

672       for (j=m; j>0; j--) {

673         seg1[j] = i;

674         i = clip1[i];

675       }

676       seg1[0] = 0;

677       

678       pen[0]=0;

679       for (j=1; j<=m; j++) {

680         for (i=seg1[j]; i<=seg0[j]; i++) {

681           best = -1;

682           for (k=seg0[j-1]; k>=clip1[i]; k--) {

683             thispen = penalty3(path, k, i) + pen[k];

684             if (best < 0 || thispen < best) {

685               prev[i] = k;

686               best = thispen;

687             }

688           }

689           pen[i] = best;

690         }

691       }

692       path.m = m;

693       path.po = new Array(m);

694     

695       for (i=n, j=m-1; i>0; j--) {

696         i = prev[i];

697         path.po[j] = i;

698       }

699     }

700     <p name="costy"></p>

701     function adjustVertices(path) {

702       

703       function pointslope(path, i, j, ctr, dir) {

704     

705         var n = path.len, sums = path.sums,

706           x, y, x2, xy, y2,

707           k, a, b, c, lambda2, l, r=0;

708       

709         while (j>=n) {

710           j-=n;

711           r+=1;

712         }

713         while (i>=n) {

714           i-=n;

715           r-=1;

716         }

717         while (j<0) {

718           j+=n;

719           r-=1;

720         }

721         while (i<0) {

722           i+=n;

723           r+=1;

724         }

725         

726         x = sums[j+1].x-sums[i].x+r*sums[n].x;

727         y = sums[j+1].y-sums[i].y+r*sums[n].y;

728         x2 = sums[j+1].x2-sums[i].x2+r*sums[n].x2;

729         xy = sums[j+1].xy-sums[i].xy+r*sums[n].xy;

730         y2 = sums[j+1].y2-sums[i].y2+r*sums[n].y2;

731         k = j+1-i+r*n;

732         

733         ctr.x = x/k;

734         ctr.y = y/k;

735       

736         a = (x2-x*x/k)/k;

737         b = (xy-x*y/k)/k;

738         c = (y2-y*y/k)/k;

739         

740         lambda2 = (a+c+Math.sqrt((a-c)*(a-c)+4*b*b))/2;

741       

742         a -= lambda2;

743         c -= lambda2;

744       

745         if (Math.abs(a) >= Math.abs(c)) {

746           l = Math.sqrt(a*a+b*b);

747           if (l!==0) {

748             dir.x = -b/l;

749             dir.y = a/l;

750           }

751         } else {

752           l = Math.sqrt(c*c+b*b);

753           if (l!==0) {

754             dir.x = -c/l;

755             dir.y = b/l;

756           }

757         }

758         if (l===0) {

759           dir.x = dir.y = 0; 

760         }

761       }

762       

763       var m = path.m, po = path.po, n = path.len, pt = path.pt,

764         x0 = path.x0, y0 = path.y0,

765         ctr = new Array(m), dir = new Array(m),

766         q = new Array(m),

767         v = new Array(3), d, i, j, k, l,

768         s = new Point();

769       

770       path.curve = new Curve(m);

771   

772       for (i=0; i<m; i++) {

773         j = po[mod(i+1,m)];

774         j = mod(j-po[i],n)+po[i];

775         ctr[i] = new Point();

776         dir[i] = new Point();

777         pointslope(path, po[i], j, ctr[i], dir[i]);

778       }

779     

780       for (i=0; i<m; i++) {

781         q[i] = new Quad();

782         d = dir[i].x * dir[i].x + dir[i].y * dir[i].y;

783         if (d === 0.0) {

784           for (j=0; j<3; j++) {

785             for (k=0; k<3; k++) {

786               q[i].data[j * 3 + k] = 0;

787             }

788           }

789         } else {

790           v[0] = dir[i].y;

791           v[1] = -dir[i].x;

792           v[2] = - v[1] * ctr[i].y - v[0] * ctr[i].x;

793           for (l=0; l<3; l++) {

794             for (k=0; k<3; k++) {

795               q[i].data[l * 3 + k] = v[l] * v[k] / d;

796             }

797           }

798         }

799       }

800      

801       var Q, w, dx, dy, det, min, cand, xmin, ymin, z;

802       for (i=0; i<m; i++) {

803         Q = new Quad();

804         w = new Point();

805     

806         s.x = pt[po[i]].x-x0;

807         s.y = pt[po[i]].y-y0;

808     

809         j = mod(i-1,m);

810         

811         for (l=0; l<3; l++) {

812           for (k=0; k<3; k++) {

813             Q.data[l * 3 + k] = q[j].at(l, k) + q[i].at(l, k);

814           }

815         }

816         

817         while(1) {

818           

819           det = Q.at(0, 0)*Q.at(1, 1) - Q.at(0, 1)*Q.at(1, 0);

820           if (det !== 0.0) {

821             w.x = (-Q.at(0, 2)*Q.at(1, 1) + Q.at(1, 2)*Q.at(0, 1)) / det;

822             w.y = ( Q.at(0, 2)*Q.at(1, 0) - Q.at(1, 2)*Q.at(0, 0)) / det;

823             break;

824           }

825     

826           if (Q.at(0, 0)>Q.at(1, 1)) {

827             v[0] = -Q.at(0, 1);

828             v[1] = Q.at(0, 0);

829           } else if (Q.at(1, 1)) {

830             v[0] = -Q.at(1, 1);

831             v[1] = Q.at(1, 0);

832           } else {

833             v[0] = 1;

834             v[1] = 0;

835           }

836           d = v[0] * v[0] + v[1] * v[1];

837           v[2] = - v[1] * s.y - v[0] * s.x;

838           for (l=0; l<3; l++) {

839             for (k=0; k<3; k++) {

840               Q.data[l * 3 + k] += v[l] * v[k] / d;

841             }

842           }

843         }

844         dx = Math.abs(w.x-s.x);

845         dy = Math.abs(w.y-s.y);

846         if (dx <= 0.5 && dy <= 0.5) {

847           path.curve.vertex[i] = new Point(w.x+x0, w.y+y0);

848           continue;

849         }

850     

851         min = quadform(Q, s);

852         xmin = s.x;

853         ymin = s.y;

854     

855         if (Q.at(0, 0) !== 0.0) {

856           for (z=0; z<2; z++) {

857             w.y = s.y-0.5+z;

858             w.x = - (Q.at(0, 1) * w.y + Q.at(0, 2)) / Q.at(0, 0);

859             dx = Math.abs(w.x-s.x);

860             cand = quadform(Q, w);

861             if (dx <= 0.5 && cand < min) {

862               min = cand;

863               xmin = w.x;

864               ymin = w.y;

865             }

866           }

867         }

868   

869         if (Q.at(1, 1) !== 0.0) {

870           for (z=0; z<2; z++) {

871             w.x = s.x-0.5+z;

872             w.y = - (Q.at(1, 0) * w.x + Q.at(1, 2)) / Q.at(1, 1);

873             dy = Math.abs(w.y-s.y);

874             cand = quadform(Q, w);

875             if (dy <= 0.5 && cand < min) {

876               min = cand;

877               xmin = w.x;

878               ymin = w.y;

879             }

880           }

881         }

882   

883         for (l=0; l<2; l++) {

884           for (k=0; k<2; k++) {

885             w.x = s.x-0.5+l;

886             w.y = s.y-0.5+k;

887             cand = quadform(Q, w);

888             if (cand < min) {

889               min = cand;

890               xmin = w.x;

891               ymin = w.y;

892             }

893           }

894         }

895     

896         path.curve.vertex[i] = new Point(xmin + x0, ymin + y0);

897       }

898     }

899     

900     function reverse(path) {

901       var curve = path.curve, m = curve.n, v = curve.vertex, i, j, tmp;

902     

903       for (i=0, j=m-1; i<j; i++, j--) {

904         tmp = v[i];

905         v[i] = v[j];

906         v[j] = tmp;

907       }

908     }

909     

910     function smooth(path) {

911       var m = path.curve.n, curve = path.curve;

912 

913       var i, j, k, dd, denom, alpha,

914         p2, p3, p4;

915     

916       for (i=0; i<m; i++) {

917         j = mod(i+1, m);

918         k = mod(i+2, m);

919         p4 = interval(1/2.0, curve.vertex[k], curve.vertex[j]);

920     

921         denom = ddenom(curve.vertex[i], curve.vertex[k]);

922         if (denom !== 0.0) {

923           dd = dpara(curve.vertex[i], curve.vertex[j], curve.vertex[k]) / denom;

924           dd = Math.abs(dd);

925           alpha = dd>1 ? (1 - 1.0/dd) : 0;

926           alpha = alpha / 0.75;

927         } else {

928           alpha = 4/3.0;

929         }

930         curve.alpha0[j] = alpha;

931     

932         if (alpha >= info.alphamax) { 

933           curve.tag[j] = "CORNER";

934           curve.c[3 * j + 1] = curve.vertex[j];

935           curve.c[3 * j + 2] = p4;

936         } else {

937           if (alpha < 0.55) {

938             alpha = 0.55;

939           } else if (alpha > 1) {

940             alpha = 1;

941           }

942           p2 = interval(0.5+0.5*alpha, curve.vertex[i], curve.vertex[j]);

943           p3 = interval(0.5+0.5*alpha, curve.vertex[k], curve.vertex[j]);

944           curve.tag[j] = "CURVE";

945           curve.c[3 * j + 0] = p2;

946           curve.c[3 * j + 1] = p3;

947           curve.c[3 * j + 2] = p4;

948         }

949         curve.alpha[j] = alpha;  

950         curve.beta[j] = 0.5;

951       }

952       curve.alphacurve = 1;

953     }

954     

955     function optiCurve(path) {

956       function Opti(){

957         this.pen = 0;

958         this.c = [new Point(), new Point()];

959         this.t = 0;

960         this.s = 0;

961         this.alpha = 0;

962       }

963       

964       function opti_penalty(path, i, j, res, opttolerance, convc, areac) {

965         var m = path.curve.n, curve = path.curve, vertex = curve.vertex, 

966           k, k1, k2, conv, i1,

967           area, alpha, d, d1, d2,

968           p0, p1, p2, p3, pt,

969           A, R, A1, A2, A3, A4,

970           s, t;

971       

972         if (i==j) {

973           return 1;

974         }

975       

976         k = i;

977         i1 = mod(i+1, m);

978         k1 = mod(k+1, m);

979         conv = convc[k1];

980         if (conv === 0) {

981           return 1;

982         }

983         d = ddist(vertex[i], vertex[i1]);

984         for (k=k1; k!=j; k=k1) {

985           k1 = mod(k+1, m);

986           k2 = mod(k+2, m);

987           if (convc[k1] != conv) {

988             return 1;

989           }

990           if (sign(cprod(vertex[i], vertex[i1], vertex[k1], vertex[k2])) !=

991               conv) {

992             return 1;

993           }

994           if (iprod1(vertex[i], vertex[i1], vertex[k1], vertex[k2]) <

995               d * ddist(vertex[k1], vertex[k2]) * -0.999847695156) {

996             return 1;

997           }

998         }

999     

1000        p0 = curve.c[mod(i,m) * 3 + 2].copy();

1001        p1 = vertex[mod(i+1,m)].copy();

1002        p2 = vertex[mod(j,m)].copy();

1003        p3 = curve.c[mod(j,m) * 3 + 2].copy();

1004      

1005        area = areac[j] - areac[i];

1006        area -= dpara(vertex[0], curve.c[i * 3 + 2], curve.c[j * 3 + 2])/2;

1007        if (i>=j) {

1008          area += areac[m];

1009        }

1010      

1011        A1 = dpara(p0, p1, p2);

1012        A2 = dpara(p0, p1, p3);

1013        A3 = dpara(p0, p2, p3);

1014  

1015        A4 = A1+A3-A2;    

1016        

1017        if (A2 == A1) {

1018          return 1;

1019        }

1020      

1021        t = A3/(A3-A4);

1022        s = A2/(A2-A1);

1023        A = A2 * t / 2.0;

1024        

1025        if (A === 0.0) {

1026          return 1;

1027        }

1028      

1029        R = area / A;

1030        alpha = 2 - Math.sqrt(4 - R / 0.3);

1031      

1032        res.c[0] = interval(t * alpha, p0, p1);

1033        res.c[1] = interval(s * alpha, p3, p2);

1034        res.alpha = alpha;

1035        res.t = t;

1036        res.s = s;

1037      

1038        p1 = res.c[0].copy();

1039        p2 = res.c[1].copy(); 

1040      

1041        res.pen = 0;

1042      

1043        for (k=mod(i+1,m); k!=j; k=k1) {

1044          k1 = mod(k+1,m);

1045          t = tangent(p0, p1, p2, p3, vertex[k], vertex[k1]);

1046          if (t<-0.5) {

1047            return 1;

1048          }

1049          pt = bezier(t, p0, p1, p2, p3);

1050          d = ddist(vertex[k], vertex[k1]);

1051          if (d === 0.0) {

1052            return 1;

1053          }

1054          d1 = dpara(vertex[k], vertex[k1], pt) / d;

1055          if (Math.abs(d1) > opttolerance) {

1056            return 1;

1057          }

1058          if (iprod(vertex[k], vertex[k1], pt) < 0 ||

1059              iprod(vertex[k1], vertex[k], pt) < 0) {

1060            return 1;

1061          }

1062          res.pen += d1 * d1;

1063        }

1064      

1065        for (k=i; k!=j; k=k1) {

1066          k1 = mod(k+1,m);

1067          t = tangent(p0, p1, p2, p3, curve.c[k * 3 + 2], curve.c[k1 * 3 + 2]);

1068          if (t<-0.5) {

1069            return 1;

1070          }

1071          pt = bezier(t, p0, p1, p2, p3);

1072          d = ddist(curve.c[k * 3 + 2], curve.c[k1 * 3 + 2]);

1073          if (d === 0.0) {

1074            return 1;

1075          }

1076          d1 = dpara(curve.c[k * 3 + 2], curve.c[k1 * 3 + 2], pt) / d;

1077          d2 = dpara(curve.c[k * 3 + 2], curve.c[k1 * 3 + 2], vertex[k1]) / d;

1078          d2 *= 0.75 * curve.alpha[k1];

1079          if (d2 < 0) {

1080            d1 = -d1;

1081            d2 = -d2;

1082          }

1083          if (d1 < d2 - opttolerance) {

1084            return 1;

1085          }

1086          if (d1 < d2) {

1087            res.pen += (d1 - d2) * (d1 - d2);

1088          }

1089        }

1090      

1091        return 0;

1092      }

1093    

1094      var curve = path.curve, m = curve.n, vert = curve.vertex, 

1095        pt = new Array(m + 1),

1096        pen = new Array(m + 1),

1097        len = new Array(m + 1),

1098        opt = new Array(m + 1),

1099        om, i,j,r,

1100        o = new Opti(), p0,

1101        i1, area, alpha, ocurve,

1102        s, t;

1103      

1104      var convc = new Array(m), areac = new Array(m + 1);

1105      

1106      for (i=0; i<m; i++) {

1107        if (curve.tag[i] == "CURVE") {

1108          convc[i] = sign(dpara(vert[mod(i-1,m)], vert[i], vert[mod(i+1,m)]));

1109        } else {

1110          convc[i] = 0;

1111        }

1112      }

1113    

1114      area = 0.0;

1115      areac[0] = 0.0;

1116      p0 = curve.vertex[0];

1117      for (i=0; i<m; i++) {

1118        i1 = mod(i+1, m);

1119        if (curve.tag[i1] == "CURVE") {

1120          alpha = curve.alpha[i1];

1121          area += 0.3 * alpha * (4-alpha) *

1122              dpara(curve.c[i * 3 + 2], vert[i1], curve.c[i1 * 3 + 2])/2;

1123          area += dpara(p0, curve.c[i * 3 + 2], curve.c[i1 * 3 + 2])/2;

1124        }

1125        areac[i+1] = area;

1126      }

1127    

1128      pt[0] = -1;

1129      pen[0] = 0;

1130      len[0] = 0;

1131    

1132    

1133      for (j=1; j<=m; j++) {

1134        pt[j] = j-1;

1135        pen[j] = pen[j-1];

1136        len[j] = len[j-1]+1;

1137    

1138        for (i=j-2; i>=0; i--) {

1139          r = opti_penalty(path, i, mod(j,m), o, info.opttolerance, convc, 

1140              areac);

1141          if (r) {

1142            break;

1143          }

1144            if (len[j] > len[i]+1 ||

1145                (len[j] == len[i]+1 && pen[j] > pen[i] + o.pen)) {

1146              pt[j] = i;

1147              pen[j] = pen[i] + o.pen;

1148              len[j] = len[i] + 1;

1149              opt[j] = o;

1150              o = new Opti();

1151            }

1152        }

1153      }

1154      om = len[m];

1155      ocurve = new Curve(om);

1156      s = new Array(om);

1157      t = new Array(om);

1158    

1159      j = m;

1160      for (i=om-1; i>=0; i--) {

1161        if (pt[j]==j-1) {

1162          ocurve.tag[i]     = curve.tag[mod(j,m)];

1163          ocurve.c[i * 3 + 0]    = curve.c[mod(j,m) * 3 + 0];

1164          ocurve.c[i * 3 + 1]    = curve.c[mod(j,m) * 3 + 1];

1165          ocurve.c[i * 3 + 2]    = curve.c[mod(j,m) * 3 + 2];

1166          ocurve.vertex[i]  = curve.vertex[mod(j,m)];

1167          ocurve.alpha[i]   = curve.alpha[mod(j,m)];

1168          ocurve.alpha0[i]  = curve.alpha0[mod(j,m)];

1169          ocurve.beta[i]    = curve.beta[mod(j,m)];

1170          s[i] = t[i] = 1.0;

1171        } else {

1172          ocurve.tag[i] = "CURVE";

1173          ocurve.c[i * 3 + 0] = opt[j].c[0];

1174          ocurve.c[i * 3 + 1] = opt[j].c[1];

1175          ocurve.c[i * 3 + 2] = curve.c[mod(j,m) * 3 + 2];

1176          ocurve.vertex[i] = interval(opt[j].s, curve.c[mod(j,m) * 3 + 2],

1177                                       vert[mod(j,m)]);

1178          ocurve.alpha[i] = opt[j].alpha;

1179          ocurve.alpha0[i] = opt[j].alpha;

1180          s[i] = opt[j].s;

1181          t[i] = opt[j].t;

1182        }

1183        j = pt[j];

1184      }

1185    

1186      for (i=0; i<om; i++) {

1187        i1 = mod(i+1,om);

1188        ocurve.beta[i] = s[i] / (s[i] + t[i1]);

1189      }

1190      ocurve.alphacurve = 1;

1191      path.curve = ocurve;

1192    }

1193    

1194    for (var i = 0; i < pathlist.length; i++) {

1195      var path = pathlist[i];

1196      calcSums(path);

1197      calcLon(path);

1198      bestPolygon(path);

1199      adjustVertices(path);

1200      

1201      if (path.sign === "-") {

1202        reverse(path);

1203      }

1204      

1205      smooth(path);

1206      

1207      if (info.optcurve) {

1208        optiCurve(path);

1209      }

1210    }

1211  

1212  }

1213

1214  function process(c) {

1215    if (c) {

1216      callback = c;

1217    }

1218    if (!info.isReady) {

1219      setTimeout(process, 100);

1220      return;

1221    }

1222    bmToPathlist();

1223    processPath();

1224    callback();

1225    callback = null;

1226  }

1227

1228  function clear() {

1229    bm = null;

1230    pathlist = [];

1231    callback = null;

1232    info.isReady = false;

1233  }

1234  

1235  function getSVG(size, opt_type) {

1236  

1237    function path(curve) {

1238    

1239      function bezier(i) {

1240        var b = 'C ' + (curve.c[i * 3 + 0].x * size).toFixed(3) + ' ' +

1241            (curve.c[i * 3 + 0].y * size).toFixed(3) + ',';

1242        b += (curve.c[i * 3 + 1].x * size).toFixed(3) + ' ' +

1243            (curve.c[i * 3 + 1].y * size).toFixed(3) + ',';

1244        b += (curve.c[i * 3 + 2].x * size).toFixed(3) + ' ' +

1245            (curve.c[i * 3 + 2].y * size).toFixed(3) + ' ';

1246        return b;

1247      }

1248    

1249      function segment(i) {

1250        var s = 'L ' + (curve.c[i * 3 + 1].x * size).toFixed(3) + ' ' +

1251            (curve.c[i * 3 + 1].y * size).toFixed(3) + ' ';

1252        s += (curve.c[i * 3 + 2].x * size).toFixed(3) + ' ' +

1253            (curve.c[i * 3 + 2].y * size).toFixed(3) + ' ';

1254        return s;

1255      }

1256

1257      var n = curve.n, i;

1258      var p = 'M' + (curve.c[(n - 1) * 3 + 2].x * size).toFixed(3) +

1259          ' ' + (curve.c[(n - 1) * 3 + 2].y * size).toFixed(3) + ' ';

1260      for (i = 0; i < n; i++) {

1261        if (curve.tag[i] === "CURVE") {

1262          p += bezier(i);

1263        } else if (curve.tag[i] === "CORNER") {

1264          p += segment(i);

1265        }

1266      }

1267      //p += 

1268      return p;

1269    }

1270

1271    var w = bm.w * size, h = bm.h * size,

1272      len = pathlist.length, c, i, strokec, fillc, fillrule;

1273

1274    var svg = '<svg id="svg" version="1.1" width="' + w + '" height="' + h +

1275        '" xmlns="http://www.w3.org/2000/svg">';

1276    svg += '<path d="';

1277    for (i = 0; i < len; i++) {

1278      c = pathlist[i].curve;

1279      svg += path(c);

1280    }

1281    if (opt_type === "curve") {

1282      strokec = "black";

1283      fillc = "none";

1284      fillrule = '';

1285    } else {

1286      strokec = "none";

1287      fillc = "black";

1288      fillrule = ' fill-rule="evenodd"';

1289    }

1290    svg += '" stroke="' + strokec + '" fill="' + fillc + '"' + fillrule + '/></svg>';

1291    return svg;

1292  }

1293  

1294  return{

1295    loadImageFromFile: loadImageFromFile,

1296    loadImageFromUrl: loadImageFromUrl,

1297    setParameter: setParameter,

1298    process: process,

1299    getSVG: getSVG,

1300    img: imgElement

1301  };

1302})();

1303