| /* |
| * Copyright (c) 1998, 2014, 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<? extends Curve> curves, |
| double xlo, double ylo, |
| double xhi, double yhi) |
| { |
| Crossings cross = new EvenOdd(xlo, ylo, xhi, yhi); |
| Enumeration<? extends Curve> enum_ = curves.elements(); |
| while (enum_.hasMoreElements()) { |
| Curve c = 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() == PathIterator.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<Curve> 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<Curve> enum_ = tmp.elements(); |
| while (enum_.hasMoreElements()) { |
| Curve c = 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<Curve> enum_ = tmp.elements(); |
| while (enum_.hasMoreElements()) { |
| Curve c = enum_.nextElement(); |
| if (c.accumulateCrossings(this)) { |
| return true; |
| } |
| } |
| tmp.clear(); |
| return false; |
| } |
| |
| public static final class EvenOdd extends Crossings { |
| public EvenOdd(double xlo, double ylo, double xhi, double yhi) { |
| super(xlo, ylo, xhi, yhi); |
| } |
| |
| public 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 static final 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 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; |
| } |
| // assert(yrlo == ystart); |
| int newdir = rdir + direction; |
| double newend = Math.min(yend, yrhi); |
| if (newdir == 0) { |
| remove(cur); |
| } else { |
| crosscounts[cur/2] = newdir; |
| yranges[cur++] = ystart; |
| yranges[cur++] = newend; |
| } |
| ystart = yrlo = newend; |
| if (yrlo < yrhi) { |
| insert(cur, yrlo, yrhi, rdir); |
| } |
| } |
| if (ystart < yend) { |
| insert(cur, ystart, yend, direction); |
| } |
| } |
| } |
| } |