/* * Copyright (c) 1998, 2003, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License version 2 only, as * published by the Free Software Foundation. Oracle designates this * particular file as subject to the "Classpath" exception as provided * by Oracle in the LICENSE file that accompanied this code. * * This code is distributed in the hope that it will be useful, but WITHOUT * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License * version 2 for more details (a copy is included in the LICENSE file that * accompanied this code). * * You should have received a copy of the GNU General Public License version * 2 along with this work; if not, write to the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. * * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA * or visit www.oracle.com if you need additional information or have any * questions. */ package sun.awt.geom; import java.awt.geom.PathIterator;import java.util.Vector;import java.util.Enumeration; public abstract class Crossings { public static final boolean debug = false; int limit = 0; double yranges[] = new double[10]; double xlo, ylo, xhi, yhi; public Crossings(double xlo, double ylo, double xhi, double yhi) { this.xlo = xlo; this.ylo = ylo; this.xhi = xhi; this.yhi = yhi; } public final double getXLo() { return xlo; } public final double getYLo() { return ylo; } public final double getXHi() { return xhi; } public final double getYHi() { return yhi; } public abstract void record(double ystart, double yend, int direction); public void print() { System.out.println("Crossings ["); System.out.println(" bounds = ["+ylo+", "+yhi+"]"); for (int i = 0; i < limit; i += 2) { System.out.println(" ["+yranges[i]+", "+yranges[i+1]+"]"); } System.out.println("]"); } public final boolean isEmpty() { return (limit == 0); } public abstract boolean covers(double ystart, double yend); public static Crossings findCrossings(Vector curves, double xlo, double ylo, double xhi, double yhi) { Crossings cross = new EvenOdd(xlo, ylo, xhi, yhi); Enumeration enum_ = curves.elements(); while (enum_.hasMoreElements()) { Curve c = (Curve) enum_.nextElement(); if (c.accumulateCrossings(cross)) { return null; } } if (debug) { cross.print(); } return cross; } public static Crossings findCrossings(PathIterator pi, double xlo, double ylo, double xhi, double yhi) { Crossings cross; if (pi.getWindingRule() == pi.WIND_EVEN_ODD) { cross = new EvenOdd(xlo, ylo, xhi, yhi); } else { cross = new NonZero(xlo, ylo, xhi, yhi); } // coords array is big enough for holding: // coordinates returned from currentSegment (6) // OR // two subdivided quadratic curves (2+4+4=10) // AND // 0-1 horizontal splitting parameters // OR // 2 parametric equation derivative coefficients // OR // three subdivided cubic curves (2+6+6+6=20) // AND // 0-2 horizontal splitting parameters // OR // 3 parametric equation derivative coefficients double coords[] = new double[23]; double movx = 0; double movy = 0; double curx = 0; double cury = 0; double newx, newy; while (!pi.isDone()) { int type = pi.currentSegment(coords); switch (type) { case PathIterator.SEG_MOVETO: if (movy != cury && cross.accumulateLine(curx, cury, movx, movy)) { return null; } movx = curx = coords[0]; movy = cury = coords[1]; break; case PathIterator.SEG_LINETO: newx = coords[0]; newy = coords[1]; if (cross.accumulateLine(curx, cury, newx, newy)) { return null; } curx = newx; cury = newy; break; case PathIterator.SEG_QUADTO: newx = coords[2]; newy = coords[3]; if (cross.accumulateQuad(curx, cury, coords)) { return null; } curx = newx; cury = newy; break; case PathIterator.SEG_CUBICTO: newx = coords[4]; newy = coords[5]; if (cross.accumulateCubic(curx, cury, coords)) { return null; } curx = newx; cury = newy; break; case PathIterator.SEG_CLOSE: if (movy != cury && cross.accumulateLine(curx, cury, movx, movy)) { return null; } curx = movx; cury = movy; break; } pi.next(); } if (movy != cury) { if (cross.accumulateLine(curx, cury, movx, movy)) { return null; } } if (debug) { cross.print(); } return cross; } public boolean accumulateLine(double x0, double y0, double x1, double y1) { if (y0 <= y1) { return accumulateLine(x0, y0, x1, y1, 1); } else { return accumulateLine(x1, y1, x0, y0, -1); } } public boolean accumulateLine(double x0, double y0, double x1, double y1, int direction) { if (yhi <= y0 || ylo >= y1) { return false; } if (x0 >= xhi && x1 >= xhi) { return false; } if (y0 == y1) { return (x0 >= xlo || x1 >= xlo); } double xstart, ystart, xend, yend; double dx = (x1 - x0); double dy = (y1 - y0); if (y0 < ylo) { xstart = x0 + (ylo - y0) * dx / dy; ystart = ylo; } else { xstart = x0; ystart = y0; } if (yhi < y1) { xend = x0 + (yhi - y0) * dx / dy; yend = yhi; } else { xend = x1; yend = y1; } if (xstart >= xhi && xend >= xhi) { return false; } if (xstart > xlo || xend > xlo) { return true; } record(ystart, yend, direction); return false; } private Vector tmp = new Vector(); public boolean accumulateQuad(double x0, double y0, double coords[]) { if (y0 < ylo && coords[1] < ylo && coords[3] < ylo) { return false; } if (y0 > yhi && coords[1] > yhi && coords[3] > yhi) { return false; } if (x0 > xhi && coords[0] > xhi && coords[2] > xhi) { return false; } if (x0 < xlo && coords[0] < xlo && coords[2] < xlo) { if (y0 < coords[3]) { record(Math.max(y0, ylo), Math.min(coords[3], yhi), 1); } else if (y0 > coords[3]) { record(Math.max(coords[3], ylo), Math.min(y0, yhi), -1); } return false; } Curve.insertQuad(tmp, x0, y0, coords); Enumeration enum_ = tmp.elements(); while (enum_.hasMoreElements()) { Curve c = (Curve) enum_.nextElement(); if (c.accumulateCrossings(this)) { return true; } } tmp.clear(); return false; } public boolean accumulateCubic(double x0, double y0, double coords[]) { if (y0 < ylo && coords[1] < ylo && coords[3] < ylo && coords[5] < ylo) { return false; } if (y0 > yhi && coords[1] > yhi && coords[3] > yhi && coords[5] > yhi) { return false; } if (x0 > xhi && coords[0] > xhi && coords[2] > xhi && coords[4] > xhi) { return false; } if (x0 < xlo && coords[0] < xlo && coords[2] < xlo && coords[4] < xlo) { if (y0 <= coords[5]) { record(Math.max(y0, ylo), Math.min(coords[5], yhi), 1); } else { record(Math.max(coords[5], ylo), Math.min(y0, yhi), -1); } return false; } Curve.insertCubic(tmp, x0, y0, coords); Enumeration enum_ = tmp.elements(); while (enum_.hasMoreElements()) { Curve c = (Curve) enum_.nextElement(); if (c.accumulateCrossings(this)) { return true; } } tmp.clear(); return false; } public final static class EvenOdd extends Crossings { public EvenOdd(double xlo, double ylo, double xhi, double yhi) { super(xlo, ylo, xhi, yhi); } public final boolean covers(double ystart, double yend) { return (limit == 2 && yranges[0] <= ystart && yranges[1] >= yend); } public void record(double ystart, double yend, int direction) { if (ystart >= yend) { return; } int from = 0; // Quickly jump over all pairs that are completely "above" while (from < limit && ystart > yranges[from+1]) { from += 2; } int to = from; while (from < limit) { double yrlo = yranges[from++]; double yrhi = yranges[from++]; if (yend < yrlo) { // Quickly handle insertion of the new range yranges[to++] = ystart; yranges[to++] = yend; ystart = yrlo; yend = yrhi; continue; } // The ranges overlap - sort, collapse, insert, iterate double yll, ylh, yhl, yhh; if (ystart < yrlo) { yll = ystart; ylh = yrlo; } else { yll = yrlo; ylh = ystart; } if (yend < yrhi) { yhl = yend; yhh = yrhi; } else { yhl = yrhi; yhh = yend; } if (ylh == yhl) { ystart = yll; yend = yhh; } else { if (ylh > yhl) { ystart = yhl; yhl = ylh; ylh = ystart; } if (yll != ylh) { yranges[to++] = yll; yranges[to++] = ylh; } ystart = yhl; yend = yhh; } if (ystart >= yend) { break; } } if (to < from && from < limit) { System.arraycopy(yranges, from, yranges, to, limit-from); } to += (limit-from); if (ystart < yend) { if (to >= yranges.length) { double newranges[] = new double[to+10]; System.arraycopy(yranges, 0, newranges, 0, to); yranges = newranges; } yranges[to++] = ystart; yranges[to++] = yend; } limit = to; } } public final static class NonZero extends Crossings { private int crosscounts[]; public NonZero(double xlo, double ylo, double xhi, double yhi) { super(xlo, ylo, xhi, yhi); crosscounts = new int[yranges.length / 2]; } public final boolean covers(double ystart, double yend) { int i = 0; while (i < limit) { double ylo = yranges[i++]; double yhi = yranges[i++]; if (ystart >= yhi) { continue; } if (ystart < ylo) { return false; } if (yend <= yhi) { return true; } ystart = yhi; } return (ystart >= yend); } public void remove(int cur) { limit -= 2; int rem = limit - cur; if (rem > 0) { System.arraycopy(yranges, cur+2, yranges, cur, rem); System.arraycopy(crosscounts, cur/2+1, crosscounts, cur/2, rem/2); } } public void insert(int cur, double lo, double hi, int dir) { int rem = limit - cur; double oldranges[] = yranges; int oldcounts[] = crosscounts; if (limit >= yranges.length) { yranges = new double[limit+10]; System.arraycopy(oldranges, 0, yranges, 0, cur); crosscounts = new int[(limit+10)/2]; System.arraycopy(oldcounts, 0, crosscounts, 0, cur/2); } if (rem > 0) { System.arraycopy(oldranges, cur, yranges, cur+2, rem); System.arraycopy(oldcounts, cur/2, crosscounts, cur/2+1, rem/2); } yranges[cur+0] = lo; yranges[cur+1] = hi; crosscounts[cur/2] = dir; limit += 2; } public void record(double ystart, double yend, int direction) { if (ystart >= yend) { return; } int cur = 0; // Quickly jump over all pairs that are completely "above" while (cur < limit && ystart > yranges[cur+1]) { cur += 2; } if (cur < limit) { int rdir = crosscounts[cur/2]; double yrlo = yranges[cur+0]; double yrhi = yranges[cur+1]; if (yrhi == ystart && rdir == direction) { // Remove the range from the list and collapse it // into the range being inserted. Note that the // new combined range may overlap the following range // so we must not simply combine the ranges in place // unless we are at the last range. if (cur+2 == limit) { yranges[cur+1] = yend; return; } remove(cur); ystart = yrlo; rdir = crosscounts[cur/2]; yrlo = yranges[cur+0]; yrhi = yranges[cur+1]; } if (yend < yrlo) { // Just insert the new range at the current location insert(cur, ystart, yend, direction); return; } if (yend == yrlo && rdir == direction) { // Just prepend the new range to the current one yranges[cur] = ystart; return; } // The ranges must overlap - (yend > yrlo && yrhi > ystart) if (ystart < yrlo) { insert(cur, ystart, yrlo, direction); cur += 2; ystart = yrlo; } else if (yrlo < ystart) { insert(cur, yrlo, ystart, rdir); cur += 2; yrlo = ystart;Lines 1–500 of 522. Load more
/* * Copyright (c) 1998, 2003, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License version 2 only, as * published by the Free Software Foundation. Oracle designates this * particular file as subject to the "Classpath" exception as provided * by Oracle in the LICENSE file that accompanied this code. * * This code is distributed in the hope that it will be useful, but WITHOUT * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License * version 2 for more details (a copy is included in the LICENSE file that * accompanied this code). * * You should have received a copy of the GNU General Public License version * 2 along with this work; if not, write to the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. * * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA * or visit www.oracle.com if you need additional information or have any * questions. */ package sun.awt.geom; import java.awt.geom.PathIterator; import java.util.Vector; import java.util.Enumeration; public abstract class Crossings { public static final boolean debug = false; int limit = 0; double yranges[] = new double[10]; double xlo, ylo, xhi, yhi; public Crossings(double xlo, double ylo, double xhi, double yhi) { this.xlo = xlo; this.ylo = ylo; this.xhi = xhi; this.yhi = yhi; } public final double getXLo() { return xlo; } public final double getYLo() { return ylo; } public final double getXHi() { return xhi; } public final double getYHi() { return yhi; } public abstract void record(double ystart, double yend, int direction); public void print() { System.out.println("Crossings ["); System.out.println(" bounds = ["+ylo+", "+yhi+"]"); for (int i = 0; i < limit; i += 2) { System.out.println(" ["+yranges[i]+", "+yranges[i+1]+"]"); } System.out.println("]"); } public final boolean isEmpty() { return (limit == 0); } public abstract boolean covers(double ystart, double yend); public static Crossings findCrossings(Vector curves, double xlo, double ylo, double xhi, double yhi) { Crossings cross = new EvenOdd(xlo, ylo, xhi, yhi); Enumeration enum_ = curves.elements(); while (enum_.hasMoreElements()) { Curve c = (Curve) enum_.nextElement(); if (c.accumulateCrossings(cross)) { return null; } } if (debug) { cross.print(); } return cross; } public static Crossings findCrossings(PathIterator pi, double xlo, double ylo, double xhi, double yhi) { Crossings cross; if (pi.getWindingRule() == pi.WIND_EVEN_ODD) { cross = new EvenOdd(xlo, ylo, xhi, yhi); } else { cross = new NonZero(xlo, ylo, xhi, yhi); } // coords array is big enough for holding: // coordinates returned from currentSegment (6) // OR // two subdivided quadratic curves (2+4+4=10) // AND // 0-1 horizontal splitting parameters // OR // 2 parametric equation derivative coefficients // OR // three subdivided cubic curves (2+6+6+6=20) // AND // 0-2 horizontal splitting parameters // OR // 3 parametric equation derivative coefficients double coords[] = new double[23]; double movx = 0; double movy = 0; double curx = 0; double cury = 0; double newx, newy; while (!pi.isDone()) { int type = pi.currentSegment(coords); switch (type) { case PathIterator.SEG_MOVETO: if (movy != cury && cross.accumulateLine(curx, cury, movx, movy)) { return null; } movx = curx = coords[0]; movy = cury = coords[1]; break; case PathIterator.SEG_LINETO: newx = coords[0]; newy = coords[1]; if (cross.accumulateLine(curx, cury, newx, newy)) { return null; } curx = newx; cury = newy; break; case PathIterator.SEG_QUADTO: newx = coords[2]; newy = coords[3]; if (cross.accumulateQuad(curx, cury, coords)) { return null; } curx = newx; cury = newy; break; case PathIterator.SEG_CUBICTO: newx = coords[4]; newy = coords[5]; if (cross.accumulateCubic(curx, cury, coords)) { return null; } curx = newx; cury = newy; break; case PathIterator.SEG_CLOSE: if (movy != cury && cross.accumulateLine(curx, cury, movx, movy)) { return null; } curx = movx; cury = movy; break; } pi.next(); } if (movy != cury) { if (cross.accumulateLine(curx, cury, movx, movy)) { return null; } } if (debug) { cross.print(); } return cross; } public boolean accumulateLine(double x0, double y0, double x1, double y1) { if (y0 <= y1) { return accumulateLine(x0, y0, x1, y1, 1); } else { return accumulateLine(x1, y1, x0, y0, -1); } } public boolean accumulateLine(double x0, double y0, double x1, double y1, int direction) { if (yhi <= y0 || ylo >= y1) { return false; } if (x0 >= xhi && x1 >= xhi) { return false; } if (y0 == y1) { return (x0 >= xlo || x1 >= xlo); } double xstart, ystart, xend, yend; double dx = (x1 - x0); double dy = (y1 - y0); if (y0 < ylo) { xstart = x0 + (ylo - y0) * dx / dy; ystart = ylo; } else { xstart = x0; ystart = y0; } if (yhi < y1) { xend = x0 + (yhi - y0) * dx / dy; yend = yhi; } else { xend = x1; yend = y1; } if (xstart >= xhi && xend >= xhi) { return false; } if (xstart > xlo || xend > xlo) { return true; } record(ystart, yend, direction); return false; } private Vector tmp = new Vector(); public boolean accumulateQuad(double x0, double y0, double coords[]) { if (y0 < ylo && coords[1] < ylo && coords[3] < ylo) { return false; } if (y0 > yhi && coords[1] > yhi && coords[3] > yhi) { return false; } if (x0 > xhi && coords[0] > xhi && coords[2] > xhi) { return false; } if (x0 < xlo && coords[0] < xlo && coords[2] < xlo) { if (y0 < coords[3]) { record(Math.max(y0, ylo), Math.min(coords[3], yhi), 1); } else if (y0 > coords[3]) { record(Math.max(coords[3], ylo), Math.min(y0, yhi), -1); } return false; } Curve.insertQuad(tmp, x0, y0, coords); Enumeration enum_ = tmp.elements(); while (enum_.hasMoreElements()) { Curve c = (Curve) enum_.nextElement(); if (c.accumulateCrossings(this)) { return true; } } tmp.clear(); return false; } public boolean accumulateCubic(double x0, double y0, double coords[]) { if (y0 < ylo && coords[1] < ylo && coords[3] < ylo && coords[5] < ylo) { return false; } if (y0 > yhi && coords[1] > yhi && coords[3] > yhi && coords[5] > yhi) { return false; } if (x0 > xhi && coords[0] > xhi && coords[2] > xhi && coords[4] > xhi) { return false; } if (x0 < xlo && coords[0] < xlo && coords[2] < xlo && coords[4] < xlo) { if (y0 <= coords[5]) { record(Math.max(y0, ylo), Math.min(coords[5], yhi), 1); } else { record(Math.max(coords[5], ylo), Math.min(y0, yhi), -1); } return false; } Curve.insertCubic(tmp, x0, y0, coords); Enumeration enum_ = tmp.elements(); while (enum_.hasMoreElements()) { Curve c = (Curve) enum_.nextElement(); if (c.accumulateCrossings(this)) { return true; } } tmp.clear(); return false; } public final static class EvenOdd extends Crossings { public EvenOdd(double xlo, double ylo, double xhi, double yhi) { super(xlo, ylo, xhi, yhi); } public final boolean covers(double ystart, double yend) { return (limit == 2 && yranges[0] <= ystart && yranges[1] >= yend); } public void record(double ystart, double yend, int direction) { if (ystart >= yend) { return; } int from = 0; // Quickly jump over all pairs that are completely "above" while (from < limit && ystart > yranges[from+1]) { from += 2; } int to = from; while (from < limit) { double yrlo = yranges[from++]; double yrhi = yranges[from++]; if (yend < yrlo) { // Quickly handle insertion of the new range yranges[to++] = ystart; yranges[to++] = yend; ystart = yrlo; yend = yrhi; continue; } // The ranges overlap - sort, collapse, insert, iterate double yll, ylh, yhl, yhh; if (ystart < yrlo) { yll = ystart; ylh = yrlo; } else { yll = yrlo; ylh = ystart; } if (yend < yrhi) { yhl = yend; yhh = yrhi; } else { yhl = yrhi; yhh = yend; } if (ylh == yhl) { ystart = yll; yend = yhh; } else { if (ylh > yhl) { ystart = yhl; yhl = ylh; ylh = ystart; } if (yll != ylh) { yranges[to++] = yll; yranges[to++] = ylh; } ystart = yhl; yend = yhh; } if (ystart >= yend) { break; } } if (to < from && from < limit) { System.arraycopy(yranges, from, yranges, to, limit-from); } to += (limit-from); if (ystart < yend) { if (to >= yranges.length) { double newranges[] = new double[to+10]; System.arraycopy(yranges, 0, newranges, 0, to); yranges = newranges; } yranges[to++] = ystart; yranges[to++] = yend; } limit = to; } } public final static class NonZero extends Crossings { private int crosscounts[]; public NonZero(double xlo, double ylo, double xhi, double yhi) { super(xlo, ylo, xhi, yhi); crosscounts = new int[yranges.length / 2]; } public final boolean covers(double ystart, double yend) { int i = 0; while (i < limit) { double ylo = yranges[i++]; double yhi = yranges[i++]; if (ystart >= yhi) { continue; } if (ystart < ylo) { return false; } if (yend <= yhi) { return true; } ystart = yhi; } return (ystart >= yend); } public void remove(int cur) { limit -= 2; int rem = limit - cur; if (rem > 0) { System.arraycopy(yranges, cur+2, yranges, cur, rem); System.arraycopy(crosscounts, cur/2+1, crosscounts, cur/2, rem/2); } } public void insert(int cur, double lo, double hi, int dir) { int rem = limit - cur; double oldranges[] = yranges; int oldcounts[] = crosscounts; if (limit >= yranges.length) { yranges = new double[limit+10]; System.arraycopy(oldranges, 0, yranges, 0, cur); crosscounts = new int[(limit+10)/2]; System.arraycopy(oldcounts, 0, crosscounts, 0, cur/2); } if (rem > 0) { System.arraycopy(oldranges, cur, yranges, cur+2, rem); System.arraycopy(oldcounts, cur/2, crosscounts, cur/2+1, rem/2); } yranges[cur+0] = lo; yranges[cur+1] = hi; crosscounts[cur/2] = dir; limit += 2; } public void record(double ystart, double yend, int direction) { if (ystart >= yend) { return; } int cur = 0; // Quickly jump over all pairs that are completely "above" while (cur < limit && ystart > yranges[cur+1]) { cur += 2; } if (cur < limit) { int rdir = crosscounts[cur/2]; double yrlo = yranges[cur+0]; double yrhi = yranges[cur+1]; if (yrhi == ystart && rdir == direction) { // Remove the range from the list and collapse it // into the range being inserted. Note that the // new combined range may overlap the following range // so we must not simply combine the ranges in place // unless we are at the last range. if (cur+2 == limit) { yranges[cur+1] = yend; return; } remove(cur); ystart = yrlo; rdir = crosscounts[cur/2]; yrlo = yranges[cur+0]; yrhi = yranges[cur+1]; } if (yend < yrlo) { // Just insert the new range at the current location insert(cur, ystart, yend, direction); return; } if (yend == yrlo && rdir == direction) { // Just prepend the new range to the current one yranges[cur] = ystart; return; } // The ranges must overlap - (yend > yrlo && yrhi > ystart) if (ystart < yrlo) { insert(cur, ystart, yrlo, direction); cur += 2; ystart = yrlo; } else if (yrlo < ystart) { insert(cur, yrlo, ystart, rdir); cur += 2; yrlo = ystart;