src/org/ibex/graphics/Path.java

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