src/org/ibex/graphics/Path.java

   1 // Copyright 2000-2005 the Contributors, as shown in the revision logs.
   2 // Licensed under the GNU General Public License version 2 ("the License").
   3 // You may not use this file except in compliance with the License.
   4
   5 // FIXME
   6 package org.ibex.graphics;
   7 import java.util.*;
   8
   9 /** an abstract path; may contain splines and arcs */
  10 public class Path {
  11
  12     public static final float PX_PER_INCH = 72;
  13     public static final float INCHES_PER_CM = (float)0.3937;
  14     public static final float INCHES_PER_MM = INCHES_PER_CM / 10;
  15     private static final int DEFAULT_PATHLEN = 1000;
  16     private static final float PI = (float)Math.PI;
  17
  18     // the number of vertices on this path
  19     int numvertices = 0;
  20
  21     // the vertices of the path
  22     float[] x = new float[DEFAULT_PATHLEN];
  23     float[] y = new float[DEFAULT_PATHLEN];
  24
  25     // the type of each edge; type[i] is the type of the edge from x[i],y[i] to x[i+1],y[i+1]
  26     byte[] type = new byte[DEFAULT_PATHLEN];
  27
  28     // bezier control points
  29     float[] c1x = new float[DEFAULT_PATHLEN];  // or rx (arcto)
  30     float[] c1y = new float[DEFAULT_PATHLEN];  // or ry (arcto)
  31     float[] c2x = new float[DEFAULT_PATHLEN];  // or x-axis-rotation (arcto)
  32     float[] c2y = new float[DEFAULT_PATHLEN];  // or large-arc << 1 | sweep (arcto)
  33
  34     boolean closed = false;
  35
  36     static final byte TYPE_MOVETO = 0;
  37     static final byte TYPE_LINETO = 1;
  38     static final byte TYPE_ARCTO = 2;
  39     static final byte TYPE_CUBIC = 3;
  40     static final byte TYPE_QUADRADIC = 4;
  41
  42     public static Path parse(String s) { return Tokenizer.parse(s); }
  43
  44     // FIXME: hack
  45     private String toString;
  46     private Path(String s) { this.toString = s; }
  47     public String toString() { return toString; }
  48
  49     public static class Tokenizer {
  50         // FIXME: check array bounds exception for improperly terminated string
  51         String s;
  52         int i = 0;
  53         char lastCommand = 'M';
  54         public Tokenizer(String s) { this.s = s; }
  55
  56         public static Path parse(String s) {
  57             if (s == null) return null;
  58             Tokenizer t = new Tokenizer(s);
  59             Path ret = new Path(s);
  60             char last_command = 'M';
  61             boolean first = true;
  62             while(t.hasMoreTokens()) {
  63                 char command = t.parseCommand();
  64                 if (first && command != 'M') throw new RuntimeException("the first command of a path must be 'M'");
  65                 first = false;
  66                 boolean relative = Character.toLowerCase(command) == command;
  67                 command = Character.toLowerCase(command);
  68                 ret.parseSingleCommandAndArguments(t, command, relative);
  69                 last_command = command;
  70             }
  71             return ret;
  72         }
  73
  74         private void consumeWhitespace() {
  75             while(i < s.length() && (Character.isWhitespace(s.charAt(i)))) i++;
  76             if (i < s.length() && s.charAt(i) == ',') i++;
  77             while(i < s.length() && (Character.isWhitespace(s.charAt(i)))) i++;
  78         }
  79         public boolean hasMoreTokens() { consumeWhitespace(); return i < s.length(); }
  80         public char parseCommand() {
  81             consumeWhitespace();
  82             char c = s.charAt(i);
  83             if (!Character.isLetter(c)) return lastCommand;
  84             i++;
  85             return lastCommand = c;
  86         }
  87         public float parseFloat() {
  88             consumeWhitespace();
  89             int start = i;
  90             float multiplier = 1;
  91             for(; i < s.length(); i++) {
  92                 char c = s.charAt(i);
  93                 if (Character.isWhitespace(c) || c == ',' || (c == '-' && i != start)) break;
  94                 if (!((c >= '0' && c <= '9') || c == '.' || c == 'e' || c == 'E' || c == '-')) {
  95                     if (c == '%') {                                // FIXME
  96                     } else if (s.regionMatches(i, "pt", 0, i+2)) { // FIXME
  97                     } else if (s.regionMatches(i, "em", 0, i+2)) { // FIXME
  98                     } else if (s.regionMatches(i, "pc", 0, i+2)) { // FIXME
  99                     } else if (s.regionMatches(i, "ex", 0, i+2)) { // FIXME
 100                     } else if (s.regionMatches(i, "mm", 0, i+2)) { i += 2; multiplier = INCHES_PER_MM * PX_PER_INCH; break;
 101                     } else if (s.regionMatches(i, "cm", 0, i+2)) { i += 2; multiplier = INCHES_PER_CM * PX_PER_INCH; break;
 102                     } else if (s.regionMatches(i, "in", 0, i+2)) { i += 2; multiplier = PX_PER_INCH; break;
 103                     } else if (s.regionMatches(i, "px", 0, i+2)) { i += 2; break;
 104                     } else if (Character.isLetter(c)) break;
 105                     throw new RuntimeException("didn't expect character \"" + c + "\" in a numeric constant");
 106                 }
 107             }
 108             if (start == i) throw new RuntimeException("FIXME");
 109             return Float.parseFloat(s.substring(start, i)) * multiplier;
 110         }
 111     }
 112
 113     /** Creates a concrete vector path transformed through the given matrix. */
 114     public Raster realize(Affine a) {
 115
 116         Raster ret = new Raster();
 117         int NUMSTEPS = 5;  // FIXME
 118         ret.numvertices = 1;
 119         ret.x[0] = (int)Math.round(a.multiply_px(x[0], y[0]));
 120         ret.y[0] = (int)Math.round(a.multiply_py(x[0], y[0]));
 121
 122         for(int i=1; i<numvertices; i++) {
 123             if (type[i] == TYPE_LINETO) {
 124                 float rx = x[i];
 125                 float ry = y[i];
 126                 ret.x[ret.numvertices] = (int)Math.round(a.multiply_px(rx, ry));
 127                 ret.y[ret.numvertices] = (int)Math.round(a.multiply_py(rx, ry));
 128                 ret.edges[ret.numedges++] = ret.numvertices - 1; ret.numvertices++;
 129
 130             } else if (type[i] == TYPE_MOVETO) {
 131                 float rx = x[i];
 132                 float ry = y[i];
 133                 ret.x[ret.numvertices] = (int)Math.round(a.multiply_px(rx, ry));
 134                 ret.y[ret.numvertices] = (int)Math.round(a.multiply_py(rx, ry));
 135                 ret.numvertices++;
 136
 137             } else if (type[i] == TYPE_ARCTO) {
 138                 float rx = c1x[i];
 139                 float ry = c1y[i];
 140                 float phi = c2x[i];
 141                 float fa = ((int)c2y[i]) >> 1;
 142                 float fs = ((int)c2y[i]) & 1;
 143                 float x1 = x[i];
 144                 float y1 = y[i];
 145                 float x2 = x[i+1];
 146                 float y2 = y[i+1];
 147
 148                 // F.6.5: given x1,y1,x2,y2,fa,fs, compute cx,cy,theta1,dtheta
 149                 float x1_ = (float)Math.cos(phi) * (x1 - x2) / 2 + (float)Math.sin(phi) * (y1 - y2) / 2;
 150                 float y1_ = -1 * (float)Math.sin(phi) * (x1 - x2) / 2 + (float)Math.cos(phi) * (y1 - y2) / 2;
 151                 float tmp = (float)Math.sqrt((rx * rx * ry * ry - rx * rx * y1_ * y1_ - ry * ry * x1_ * x1_) /
 152                                              (rx * rx * y1_ * y1_ + ry * ry * x1_ * x1_));
 153                 float cx_ = (fa == fs ? -1 : 1) * tmp * (rx * y1_ / ry);
 154                 float cy_ = (fa == fs ? -1 : 1) * -1 * tmp * (ry * x1_ / rx);
 155                 float cx = (float)Math.cos(phi) * cx_ - (float)Math.sin(phi) * cy_ + (x1 + x2) / 2;
 156                 float cy = (float)Math.sin(phi) * cx_ + (float)Math.cos(phi) * cy_ + (y1 + y2) / 2;
 157
 158                 // F.6.4 Conversion from center to endpoint parameterization
 159                 float ux = 1, uy = 0, vx = (x1_ - cx_) / rx, vy = (y1_ - cy_) / ry;
 160                 float det = ux * vy - uy * vx;
 161                 float theta1 = (det < 0 ? -1 : 1) *
 162                     (float)Math.acos((ux * vx + uy * vy) /
 163                                      ((float)Math.sqrt(ux * ux + uy * uy) * (float)Math.sqrt(vx * vx + vy * vy)));
 164                 ux = (x1_ - cx_) / rx; uy = (y1_ - cy_) / ry;
 165                 vx = (-1 * x1_ - cx_) / rx; vy = (-1 * y1_ - cy_) / ry;
 166                 det = ux * vy - uy * vx;
 167                 float dtheta = (det < 0 ? -1 : 1) *
 168                     (float)Math.acos((ux * vx + uy * vy) /
 169                                      ((float)Math.sqrt(ux * ux + uy * uy) * (float)Math.sqrt(vx * vx + vy * vy)));
 170                 dtheta = dtheta % (float)(2 * Math.PI);
 171
 172                 if (fs == 0 && dtheta > 0) theta1 -= 2 * PI;
 173                 if (fs == 1 && dtheta < 0) theta1 += 2 * PI;
 174
 175                 if (fa == 1 && dtheta < 0) dtheta = 2 * PI + dtheta;
 176                 else if (fa == 1 && dtheta > 0) dtheta = -1 * (2 * PI - dtheta);
 177
 178                 // FIXME: integrate F.6.6
 179                 // FIXME: isn't quite ending where it should...
 180
 181                 // F.6.3: Parameterization alternatives
 182                 float theta = theta1;
 183                 for(int j=0; j<NUMSTEPS; j++) {
 184                     float rasterx = rx * (float)Math.cos(theta) * (float)Math.cos(phi) -
 185                         ry * (float)Math.sin(theta) * (float)Math.sin(phi) + cx;
 186                     float rastery = rx * (float)Math.cos(theta) * (float)Math.sin(phi) +
 187                         ry * (float)Math.cos(phi) * (float)Math.sin(theta) + cy;
 188                     ret.x[ret.numvertices] = (int)Math.round(a.multiply_px(rasterx, rastery));
 189                     ret.y[ret.numvertices] = (int)Math.round(a.multiply_py(rasterx, rastery));
 190                     ret.edges[ret.numedges++] = ret.numvertices - 1; ret.numvertices++;
 191                     theta += dtheta / NUMSTEPS;
 192                 }
 193
 194             } else if (type[i] == TYPE_CUBIC) {
 195
 196                 float ax = x[i+1] - 3 * c2x[i] + 3 * c1x[i] - x[i];
 197                 float bx = 3 * c2x[i] - 6 * c1x[i] + 3 * x[i];
 198                 float cx = 3 * c1x[i] - 3 * x[i];
 199                 float dx = x[i];
 200                 float ay = y[i+1] - 3 * c2y[i] + 3 * c1y[i] - y[i];
 201                 float by = 3 * c2y[i] - 6 * c1y[i] + 3 * y[i];
 202                 float cy = 3 * c1y[i] - 3 * y[i];
 203                 float dy = y[i];
 204
 205                 for(float t=0; t<1; t += 1 / (float)NUMSTEPS) {
 206                     float rx = ax * t * t * t + bx * t * t + cx * t + dx;
 207                     float ry = ay * t * t * t + by * t * t + cy * t + dy;
 208                     ret.x[ret.numvertices] = (int)Math.round(a.multiply_px(rx, ry));
 209                     ret.y[ret.numvertices] = (int)Math.round(a.multiply_py(rx, ry));
 210                     ret.edges[ret.numedges++] = ret.numvertices - 1; ret.numvertices++;
 211                 }
 212
 213
 214             } else if (type[i] == TYPE_QUADRADIC) {
 215
 216                 float bx = x[i+1] - 2 * c1x[i] + x[i];
 217                 float cx = 2 * c1x[i] - 2 * x[i];
 218                 float dx = x[i];
 219                 float by = y[i+1] - 2 * c1y[i] + y[i];
 220                 float cy = 2 * c1y[i] - 2 * y[i];
 221                 float dy = y[i];
 222
 223                 for(float t=0; t<1; t += 1 / (float)NUMSTEPS) {
 224                     float rx = bx * t * t + cx * t + dx;
 225                     float ry = by * t * t + cy * t + dy;
 226                     ret.x[ret.numvertices] = (int)Math.round(a.multiply_px(rx, ry));
 227                     ret.y[ret.numvertices] = (int)Math.round(a.multiply_py(rx, ry));
 228                     ret.edges[ret.numedges++] = ret.numvertices - 1; ret.numvertices++;
 229                 }
 230
 231             }
 232
 233         }
 234
 235         if (ret.numedges > 0) ret.sort(0, ret.numedges - 1, false);
 236         return ret;
 237     }
 238
 239     protected void parseSingleCommandAndArguments(Tokenizer t, char command, boolean relative) {
 240         if (numvertices == 0 && command != 'm') throw new RuntimeException("first command MUST be an 'm'");
 241         if (numvertices > x.length - 2) {
 242             float[] new_x = new float[x.length * 2]; System.arraycopy(x, 0, new_x, 0, x.length); x = new_x;
 243             float[] new_y = new float[y.length * 2]; System.arraycopy(y, 0, new_y, 0, y.length); y = new_y;
 244         }
 245         switch(command) {
 246             case 'z': {
 247                 int where;
 248                 type[numvertices-1] = TYPE_LINETO;
 249                 for(where = numvertices - 1; where > 0; where--)
 250                     if (type[where - 1] == TYPE_MOVETO) break;
 251                 x[numvertices] = x[where];
 252                 y[numvertices] = y[where];
 253                 numvertices++;
 254                 closed = true;
 255                 break;
 256             }
 257
 258             case 'm': {
 259                 if (numvertices > 0) type[numvertices-1] = TYPE_MOVETO;
 260                 x[numvertices] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
 261                 y[numvertices] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
 262                 numvertices++;
 263                 break;
 264             }
 265
 266             case 'l': case 'h': case 'v': {
 267                 type[numvertices-1] = TYPE_LINETO;
 268                 float first = t.parseFloat(), second;
 269                 if (command == 'h') {
 270                     second = relative ? 0 : y[numvertices - 1];
 271                 } else if (command == 'v') {
 272                     second = first; first = relative ? 0 : x[numvertices - 1];
 273                 } else {
 274                     second = t.parseFloat();
 275                 }
 276                 x[numvertices] = first + (relative ? x[numvertices - 1] : 0);
 277                 y[numvertices] = second + (relative ? y[numvertices - 1] : 0);
 278                 numvertices++;
 279                 break;
 280             }
 281
 282             case 'a': {
 283                 type[numvertices-1] = TYPE_ARCTO;
 284                 c1x[numvertices-1] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
 285                 c1y[numvertices-1] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
 286                 c2x[numvertices-1] = (t.parseFloat() / 360) * 2 * PI;
 287                 c2y[numvertices-1] = (((int)t.parseFloat()) << 1) | (int)t.parseFloat();
 288                 x[numvertices] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
 289                 y[numvertices] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
 290                 numvertices++;
 291                 break;
 292             }
 293
 294             case 's': case 'c': {
 295                 type[numvertices-1] = TYPE_CUBIC;
 296                 if (command == 'c') {
 297                     c1x[numvertices-1] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
 298                     c1y[numvertices-1] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
 299                 } else if (numvertices > 1 && type[numvertices-2] == TYPE_CUBIC) {
 300                     c1x[numvertices-1] = 2 * x[numvertices - 1] - c2x[numvertices-2];
 301                     c1y[numvertices-1] = 2 * y[numvertices - 1] - c2y[numvertices-2];
 302                 } else {
 303                     c1x[numvertices-1] = x[numvertices-1];
 304                     c1y[numvertices-1] = y[numvertices-1];
 305                 }
 306                 c2x[numvertices-1] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
 307                 c2y[numvertices-1] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
 308                 x[numvertices] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
 309                 y[numvertices] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
 310                 numvertices++;
 311                 break;
 312             }
 313
 314             case 't': case 'q': {
 315                 type[numvertices-1] = TYPE_QUADRADIC;
 316                 if (command == 'q') {
 317                     c1x[numvertices-1] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
 318                     c1y[numvertices-1] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
 319                 } else if (numvertices > 1 && type[numvertices-2] == TYPE_QUADRADIC) {
 320                     c1x[numvertices-1] = 2 * x[numvertices - 1] - c1x[numvertices-2];
 321                     c1y[numvertices-1] = 2 * y[numvertices - 1] - c1y[numvertices-2];
 322                 } else {
 323                     c1x[numvertices-1] = x[numvertices-1];
 324                     c1y[numvertices-1] = y[numvertices-1];
 325                 }
 326                 x[numvertices] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
 327                 y[numvertices] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
 328                 numvertices++;
 329                 break;
 330             }
 331
 332             default:
 333                 // FIXME
 334         }
 335
 336         /*
 337         // invariant: after this loop, no two lines intersect other than at a vertex
 338         // FIXME: cleanup
 339         int index = numvertices - 2;
 340         for(int i=0; i<Math.min(numvertices - 3, index); i++) {
 341         for(int j = index; j < numvertices - 1; j++) {
 342
 343         // I'm not sure how to deal with vertical lines...
 344         if (x[i+1] == x[i] || x[j+1] == x[j]) continue;
 345
 346         float islope = (y[i+1] - y[i]) / (x[i+1] - x[i]);
 347         float jslope = (y[j+1] - y[j]) / (x[j+1] - x[j]);
 348         if (islope == jslope) continue;   // parallel lines can't intersect
 349
 350         float _x = (islope * x[i] - jslope * x[j] + y[j] - y[i]) / (islope - jslope);
 351         float _y = islope * (_x - x[i]) + y[i];
 352
 353         if (_x > Math.min(x[i+1], x[i]) && _x < Math.max(x[i+1], x[i]) &&
 354         _x > Math.min(x[j+1], x[j]) && _x < Math.max(x[j+1], x[j])) {
 355         // FIXME: something's not right in here.  See if we can do without fracturing line 'i'.
 356         for(int k = ++numvertices; k>i; k--) { x[k] = x[k - 1]; y[k] = y[k - 1]; }
 357         x[i+1] = _x;
 358         y[i+1] = _y;
 359         x[numvertices] = x[numvertices - 1];  x[numvertices - 1] = _x;
 360         y[numvertices] = y[numvertices - 1];  y[numvertices - 1] = _y;
 361         edges[numedges++] = numvertices - 1; numvertices++;
 362         index++;
 363         break;  // actually 'continue' the outermost loop
 364         }
 365         }
 366         }
 367         */
 368
 369     }
 370
 371
 372     // Rasterized Vector Path //////////////////////////////////////////////////////////////////////////////
 373
 374     /** a vector path */
 375     public static class Raster {
 376
 377         // the vertices of this path
 378         int[] x = new int[DEFAULT_PATHLEN];
 379         int[] y = new int[DEFAULT_PATHLEN];
 380         int numvertices = 0;
 381
 382         /**
 383          *  A list of the vertices on this path which *start* an *edge* (rather than a moveto), sorted by increasing y.
 384          *  example: x[edges[1]],y[edges[1]] - x[edges[i]+1],y[edges[i]+1] is the second-topmost edge
 385          *  note that if x[i],y[i] - x[i+1],y[i+1] is a MOVETO, then no element in edges will be equal to i
 386          */
 387         int[] edges = new int[DEFAULT_PATHLEN];
 388         int numedges = 0;
 389
 390         /** translate a rasterized path */
 391         public void translate(int dx, int dy) { for(int i=0; i<numvertices; i++) { x[i] += dx; y[i] += dy; } }
 392
 393         /** simple quicksort, from http://sourceforge.net/snippet/detail.php?type=snippet&id=100240 */
 394         int sort(int left, int right, boolean partition) {
 395             if (partition) {
 396                 int i, j, middle;
 397                 middle = (left + right) / 2;
 398                 int s = edges[right]; edges[right] = edges[middle]; edges[middle] = s;
 399                 for (i = left - 1, j = right; ; ) {
 400                     while (y[edges[++i]] < y[edges[right]]);
 401                     while (j > left && y[edges[--j]] > y[edges[right]]);
 402                     if (i >= j) break;
 403                     s = edges[i]; edges[i] = edges[j]; edges[j] = s;
 404                 }
 405                 s = edges[right]; edges[right] = edges[i]; edges[i] = s;
 406                 return i;
 407             } else {
 408                 if (left >= right) return 0;
 409                 int p = sort(left, right, true);
 410                 sort(left, p - 1, false);
 411                 sort(p + 1, right, false);
 412                 return 0;
 413             }
 414         }
 415
 416         /** finds the x value at which the line intercepts the line y=_y */
 417         private int intercept(int i, float _y, boolean includeTop, boolean includeBottom) {
 418             if (includeTop ? (_y < Math.min(y[i], y[i+1])) : (_y <= Math.min(y[i], y[i+1])))
 419                 return Integer.MIN_VALUE;
 420             if (includeBottom ? (_y > Math.max(y[i], y[i+1])) : (_y >= Math.max(y[i], y[i+1])))
 421                 return Integer.MIN_VALUE;
 422             return (int)Math.round((((float)(x[i + 1] - x[i])) /
 423                                     ((float)(y[i + 1] - y[i])) ) * ((float)(_y - y[i])) + x[i]);
 424         }
 425
 426         /** fill the interior of the path */
 427         public void fill(PixelBuffer buf, Paint paint) {
 428             if (numedges == 0) return;
 429             int y0 = y[edges[0]], y1 = y0;
 430             boolean useEvenOdd = false;
 431
 432             // we iterate over all endpoints in increasing y-coordinate order
 433             for(int index = 1; index<numedges; index++) {
 434                 int count = 0;
 435
 436                 // we now examine the horizontal band between y=y0 and y=y1
 437                 y0 = y1;
 438                 y1 = y[edges[index]];
 439                 if (y0 == y1) continue;
 440
 441                 // within this band, we iterate over all edges
 442                 int x0 = Integer.MIN_VALUE;
 443                 int leftSegment = -1;
 444                 while(true) {
 445                     int x1 = Integer.MAX_VALUE;
 446                     int rightSegment = Integer.MAX_VALUE;
 447                     for(int i=0; i<numedges; i++) {
 448                         if (y[edges[i]] == y[edges[i]+1]) continue; // ignore horizontal lines; they are irrelevant.
 449                         // we order the segments by the x-coordinate of their midpoint;
 450                         // since segments cannot intersect, this is a well-ordering
 451                         int i0 = intercept(edges[i], y0, true, false);
 452                         int i1 = intercept(edges[i], y1, false, true);
 453                         if (i0 == Integer.MIN_VALUE || i1 == Integer.MIN_VALUE) continue;
 454                         int midpoint = i0 + i1;
 455                         if (midpoint < x0) continue;
 456                         if (midpoint == x0 && i <= leftSegment) continue;
 457                         if (midpoint > x1) continue;
 458                         if (midpoint == x1 && i >= rightSegment) continue;
 459                         rightSegment = i;
 460                         x1 = midpoint;
 461                     }
 462                     if (leftSegment == rightSegment || rightSegment == Integer.MAX_VALUE) break;
 463                     if (leftSegment != -1)
 464                         if ((useEvenOdd && count % 2 != 0) || (!useEvenOdd && count != 0))
 465                             paint.fillTrapezoid(intercept(edges[leftSegment], y0, true, true),
 466                                                 intercept(edges[rightSegment], y0, true, true), y0,
 467                                                 intercept(edges[leftSegment], y1, true, true),
 468                                                 intercept(edges[rightSegment], y1, true, true), y1,
 469                                                 buf);
 470                     if (useEvenOdd) count++;
 471                     else count += (y[edges[rightSegment]] < y[edges[rightSegment]+1]) ? -1 : 1;
 472                     leftSegment = rightSegment; x0 = x1;
 473                 }
 474             }
 475         }
 476
 477         /** stroke the outline of the path */
 478         public void stroke(PixelBuffer buf, int width, int color) { stroke(buf, width, color, null, 0, 0); }
 479         public void stroke(PixelBuffer buf, int width, int color, String dashArray, int dashOffset, float segLength) {
 480
 481             if (dashArray == null) {
 482                 for(int i=0; i<numedges; i++)
 483                     buf.drawLine((int)x[edges[i]],
 484                                  (int)y[edges[i]], (int)x[edges[i]+1], (int)y[edges[i]+1], width, color, false);
 485                 return;
 486             }
 487
 488             float ratio = 1;
 489             if (segLength > 0) {
 490                 float actualLength = 0;
 491                 for(int i=0; i<numvertices; i++) {
 492                     // skip over MOVETOs -- they do not contribute to path length
 493                     if (x[i] == x[i+1] && y[i] == y[i+1]) continue;
 494                     if (x[i+1] == x[i+2] && y[i+1] == y[i+2]) continue;
 495                     int x1 = x[i];
 496                     int x2 = x[i + 1];
 497                     int y1 = y[i];
 498                     int y2 = y[i + 1];
 499                     actualLength += java.lang.Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
 500                 }
 501                 ratio = actualLength / segLength;
 502             }
 503             Tokenizer pt = new Tokenizer(dashArray);
 504             Vector v = new Vector();
 505             while (pt.hasMoreTokens()) v.addElement(new Float(pt.parseFloat()));
 506             float[] dashes = new float[v.size() % 2 == 0 ? v.size() : 2 * v.size()];
 507             for(int i=0; i<dashes.length; i++) dashes[i] = ((Float)v.elementAt(i % v.size())).floatValue();
 508             int dashpos = dashOffset;
 509             boolean on = dashpos % 2 == 0;
 510             for(int i=0; i<numvertices; i++) {
 511                 // skip over MOVETOs -- they do not contribute to path length
 512                 if (x[i] == x[i+1] && y[i] == y[i+1]) continue;
 513                 if (x[i+1] == x[i+2] && y[i+1] == y[i+2]) continue;
 514                 int x1 = (int)x[i];
 515                 int x2 = (int)x[i + 1];
 516                 int y1 = (int)y[i];
 517                 int y2 = (int)y[i + 1];
 518                 float segmentLength = (float)java.lang.Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
 519                 int _x1 = x1, _y1 = y1;
 520                 float pos = 0;
 521                 do {
 522                     pos = Math.min(segmentLength, pos + dashes[dashpos] * ratio);
 523                     if (pos != segmentLength) dashpos = (dashpos + 1) % dashes.length;
 524                     int _x2 = (int)((x2 * pos + x1 * (segmentLength - pos)) / segmentLength);
 525                     int _y2 = (int)((y2 * pos + y1 * (segmentLength - pos)) / segmentLength);
 526                     if (on) buf.drawLine(_x1, _y1, _x2, _y2, width, color, false);
 527                     on = !on;
 528                     _x1 = _x2; _y1 = _y2;
 529                 } while(pos < segmentLength);
 530             }
 531         }
 532
 533         // FEATURE: make this faster and cache it; also deal with negative coordinates
 534         public int boundingBoxWidth() {
 535             int ret = 0;
 536             for(int i=0; i<numvertices; i++) ret = Math.max(ret, x[i]);
 537             return ret;
 538         }
 539
 540         // FEATURE: make this faster and cache it; also deal with negative coordinates
 541         public int boundingBoxHeight() {
 542             int ret = 0;
 543             for(int i=0; i<numvertices; i++) ret = Math.max(ret, y[i]);
 544             return ret;
 545         }
 546     }
 547 }