- // FIXME
- }
-
- /*
- // invariant: after this loop, no two lines intersect other than at a vertex
- // FIXME: cleanup
- int index = numvertices - 2;
- for(int i=0; i<Math.min(numvertices - 3, index); i++) {
- for(int j = index; j < numvertices - 1; j++) {
-
- // I'm not sure how to deal with vertical lines...
- if (x[i+1] == x[i] || x[j+1] == x[j]) continue;
-
- float islope = (y[i+1] - y[i]) / (x[i+1] - x[i]);
- float jslope = (y[j+1] - y[j]) / (x[j+1] - x[j]);
- if (islope == jslope) continue; // parallel lines can't intersect
-
- float _x = (islope * x[i] - jslope * x[j] + y[j] - y[i]) / (islope - jslope);
- float _y = islope * (_x - x[i]) + y[i];
-
- if (_x > Math.min(x[i+1], x[i]) && _x < Math.max(x[i+1], x[i]) &&
- _x > Math.min(x[j+1], x[j]) && _x < Math.max(x[j+1], x[j])) {
- // FIXME: something's not right in here. See if we can do without fracturing line 'i'.
- for(int k = ++numvertices; k>i; k--) { x[k] = x[k - 1]; y[k] = y[k - 1]; }
- x[i+1] = _x;
- y[i+1] = _y;
- x[numvertices] = x[numvertices - 1]; x[numvertices - 1] = _x;
- y[numvertices] = y[numvertices - 1]; y[numvertices - 1] = _y;
- edges[numedges++] = numvertices - 1; numvertices++;
- index++;
- break; // actually 'continue' the outermost loop
- }
- }
- }
- */
-
- }
- }
-
-
-
-
- // Rasterized Vector Path //////////////////////////////////////////////////////////////////////////////
-
- /** a vector path */
- public static class RasterPath {
-
- // the vertices of this path
- int[] x = new int[DEFAULT_PATHLEN];
- int[] y = new int[DEFAULT_PATHLEN];
- int numvertices = 0;
-
- /**
- * A list of the vertices on this path which *start* an *edge* (rather than a moveto), sorted by increasing y.
- * example: x[edges[1]],y[edges[1]] - x[edges[i]+1],y[edges[i]+1] is the second-topmost edge
- * 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
- */
- int[] edges = new int[DEFAULT_PATHLEN];
- int numedges = 0;
-
- /** translate a rasterized path */
- public void translate(int dx, int dy) { for(int i=0; i<numvertices; i++) { x[i] += dx; y[i] += dy; } }
-
- /** simple quicksort, from http://sourceforge.net/snippet/detail.php?type=snippet&id=100240 */
- int sort(int left, int right, boolean partition) {
- if (partition) {
- int i, j, middle;
- middle = (left + right) / 2;
- int s = edges[right]; edges[right] = edges[middle]; edges[middle] = s;
- for (i = left - 1, j = right; ; ) {
- while (y[edges[++i]] < y[edges[right]]);
- while (j > left && y[edges[--j]] > y[edges[right]]);
- if (i >= j) break;
- s = edges[i]; edges[i] = edges[j]; edges[j] = s;
- }
- s = edges[right]; edges[right] = edges[i]; edges[i] = s;
- return i;
- } else {
- if (left >= right) return 0;
- int p = sort(left, right, true);
- sort(left, p - 1, false);
- sort(p + 1, right, false);
- return 0;
- }
- }
-
- /** finds the x value at which the line intercepts the line y=_y */
- private int intercept(int i, float _y, boolean includeTop, boolean includeBottom) {
- if (includeTop ? (_y < Math.min(y[i], y[i+1])) : (_y <= Math.min(y[i], y[i+1])))
- return Integer.MIN_VALUE;
- if (includeBottom ? (_y > Math.max(y[i], y[i+1])) : (_y >= Math.max(y[i], y[i+1])))
- return Integer.MIN_VALUE;
- return (int)Math.round((((float)(x[i + 1] - x[i])) /
- ((float)(y[i + 1] - y[i])) ) * ((float)(_y - y[i])) + x[i]);
- }
-
- /** fill the interior of the path */
- public void fill(PixelBuffer buf, Paint paint) {
- if (numedges == 0) return;
- int y0 = y[edges[0]], y1 = y0;
- boolean useEvenOdd = false;
-
- // we iterate over all endpoints in increasing y-coordinate order
- for(int index = 1; index<numedges; index++) {
- int count = 0;
-
- // we now examine the horizontal band between y=y0 and y=y1
- y0 = y1;
- y1 = y[edges[index]];
- if (y0 == y1) continue;
-
- // within this band, we iterate over all edges
- int x0 = Integer.MIN_VALUE;
- int leftSegment = -1;
- while(true) {
- int x1 = Integer.MAX_VALUE;
- int rightSegment = Integer.MAX_VALUE;
- for(int i=0; i<numedges; i++) {
- if (y[edges[i]] == y[edges[i]+1]) continue; // ignore horizontal lines; they are irrelevant.
- // we order the segments by the x-coordinate of their midpoint;
- // since segments cannot intersect, this is a well-ordering
- int i0 = intercept(edges[i], y0, true, false);
- int i1 = intercept(edges[i], y1, false, true);
- if (i0 == Integer.MIN_VALUE || i1 == Integer.MIN_VALUE) continue;
- int midpoint = i0 + i1;
- if (midpoint < x0) continue;
- if (midpoint == x0 && i <= leftSegment) continue;
- if (midpoint > x1) continue;
- if (midpoint == x1 && i >= rightSegment) continue;
- rightSegment = i;
- x1 = midpoint;
- }
- if (leftSegment == rightSegment || rightSegment == Integer.MAX_VALUE) break;
- if (leftSegment != -1)
- if ((useEvenOdd && count % 2 != 0) || (!useEvenOdd && count != 0))
- paint.fillTrapezoid(intercept(edges[leftSegment], y0, true, true),
- intercept(edges[rightSegment], y0, true, true), y0,
- intercept(edges[leftSegment], y1, true, true),
- intercept(edges[rightSegment], y1, true, true), y1,
- buf);
- if (useEvenOdd) count++;
- else count += (y[edges[rightSegment]] < y[edges[rightSegment]+1]) ? -1 : 1;
- leftSegment = rightSegment; x0 = x1;
- }
- }
- }
-
- /** stroke the outline of the path */
- public void stroke(PixelBuffer buf, int width, int color) { stroke(buf, width, color, null, 0, 0); }
- public void stroke(PixelBuffer buf, int width, int color, String dashArray, int dashOffset, float segLength) {
-
- if (dashArray == null) {
- for(int i=0; i<numedges; i++)
- buf.drawLine((int)x[edges[i]],
- (int)y[edges[i]], (int)x[edges[i]+1], (int)y[edges[i]+1], width, color, false);
- return;
- }
-
- float ratio = 1;
- if (segLength > 0) {
- float actualLength = 0;
- for(int i=0; i<numvertices; i++) {
- // skip over MOVETOs -- they do not contribute to path length
- if (x[i] == x[i+1] && y[i] == y[i+1]) continue;
- if (x[i+1] == x[i+2] && y[i+1] == y[i+2]) continue;
- int x1 = x[i];
- int x2 = x[i + 1];
- int y1 = y[i];
- int y2 = y[i + 1];
- actualLength += java.lang.Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
- }
- ratio = actualLength / segLength;
- }
- PathTokenizer pt = new PathTokenizer(dashArray);
- Vector v = new Vector();
- while (pt.hasMoreTokens()) v.addElement(new Float(pt.parseFloat()));
- float[] dashes = new float[v.size() % 2 == 0 ? v.size() : 2 * v.size()];
- for(int i=0; i<dashes.length; i++) dashes[i] = ((Float)v.elementAt(i % v.size())).floatValue();
- int dashpos = dashOffset;
- boolean on = dashpos % 2 == 0;
- for(int i=0; i<numvertices; i++) {
- // skip over MOVETOs -- they do not contribute to path length
- if (x[i] == x[i+1] && y[i] == y[i+1]) continue;
- if (x[i+1] == x[i+2] && y[i+1] == y[i+2]) continue;
- int x1 = (int)x[i];
- int x2 = (int)x[i + 1];
- int y1 = (int)y[i];
- int y2 = (int)y[i + 1];
- float segmentLength = (float)java.lang.Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
- int _x1 = x1, _y1 = y1;
- float pos = 0;
- do {
- pos = Math.min(segmentLength, pos + dashes[dashpos] * ratio);
- if (pos != segmentLength) dashpos = (dashpos + 1) % dashes.length;
- int _x2 = (int)((x2 * pos + x1 * (segmentLength - pos)) / segmentLength);
- int _y2 = (int)((y2 * pos + y1 * (segmentLength - pos)) / segmentLength);
- if (on) buf.drawLine(_x1, _y1, _x2, _y2, width, color, false);
- on = !on;
- _x1 = _x2; _y1 = _y2;
- } while(pos < segmentLength);
- }
- }
-
- // FEATURE: make this faster and cache it; also deal with negative coordinates
- public int boundingBoxWidth() {
- int ret = 0;
- for(int i=0; i<numvertices; i++) ret = Math.max(ret, x[i]);
- return ret;