0N/A/*
2362N/A * Copyright (c) 1998, 2003, Oracle and/or its affiliates. All rights reserved.
0N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
0N/A *
0N/A * This code is free software; you can redistribute it and/or modify it
0N/A * under the terms of the GNU General Public License version 2 only, as
2362N/A * published by the Free Software Foundation. Oracle designates this
0N/A * particular file as subject to the "Classpath" exception as provided
2362N/A * by Oracle in the LICENSE file that accompanied this code.
0N/A *
0N/A * This code is distributed in the hope that it will be useful, but WITHOUT
0N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
0N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
0N/A * version 2 for more details (a copy is included in the LICENSE file that
0N/A * accompanied this code).
0N/A *
0N/A * You should have received a copy of the GNU General Public License version
0N/A * 2 along with this work; if not, write to the Free Software Foundation,
0N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
0N/A *
2362N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
2362N/A * or visit www.oracle.com if you need additional information or have any
2362N/A * questions.
0N/A */
0N/A
0N/Apackage sun.awt.geom;
0N/A
0N/Aimport java.util.Vector;
0N/Aimport java.util.Enumeration;
0N/Aimport java.util.Comparator;
0N/Aimport java.util.Arrays;
0N/A
0N/Apublic abstract class AreaOp {
0N/A public static abstract class CAGOp extends AreaOp {
0N/A boolean inLeft;
0N/A boolean inRight;
0N/A boolean inResult;
0N/A
0N/A public void newRow() {
0N/A inLeft = false;
0N/A inRight = false;
0N/A inResult = false;
0N/A }
0N/A
0N/A public int classify(Edge e) {
0N/A if (e.getCurveTag() == CTAG_LEFT) {
0N/A inLeft = !inLeft;
0N/A } else {
0N/A inRight = !inRight;
0N/A }
0N/A boolean newClass = newClassification(inLeft, inRight);
0N/A if (inResult == newClass) {
0N/A return ETAG_IGNORE;
0N/A }
0N/A inResult = newClass;
0N/A return (newClass ? ETAG_ENTER : ETAG_EXIT);
0N/A }
0N/A
0N/A public int getState() {
0N/A return (inResult ? RSTAG_INSIDE : RSTAG_OUTSIDE);
0N/A }
0N/A
0N/A public abstract boolean newClassification(boolean inLeft,
0N/A boolean inRight);
0N/A }
0N/A
0N/A public static class AddOp extends CAGOp {
0N/A public boolean newClassification(boolean inLeft, boolean inRight) {
0N/A return (inLeft || inRight);
0N/A }
0N/A }
0N/A
0N/A public static class SubOp extends CAGOp {
0N/A public boolean newClassification(boolean inLeft, boolean inRight) {
0N/A return (inLeft && !inRight);
0N/A }
0N/A }
0N/A
0N/A public static class IntOp extends CAGOp {
0N/A public boolean newClassification(boolean inLeft, boolean inRight) {
0N/A return (inLeft && inRight);
0N/A }
0N/A }
0N/A
0N/A public static class XorOp extends CAGOp {
0N/A public boolean newClassification(boolean inLeft, boolean inRight) {
0N/A return (inLeft != inRight);
0N/A }
0N/A }
0N/A
0N/A public static class NZWindOp extends AreaOp {
0N/A private int count;
0N/A
0N/A public void newRow() {
0N/A count = 0;
0N/A }
0N/A
0N/A public int classify(Edge e) {
0N/A // Note: the right curves should be an empty set with this op...
0N/A // assert(e.getCurveTag() == CTAG_LEFT);
0N/A int newCount = count;
0N/A int type = (newCount == 0 ? ETAG_ENTER : ETAG_IGNORE);
0N/A newCount += e.getCurve().getDirection();
0N/A count = newCount;
0N/A return (newCount == 0 ? ETAG_EXIT : type);
0N/A }
0N/A
0N/A public int getState() {
0N/A return ((count == 0) ? RSTAG_OUTSIDE : RSTAG_INSIDE);
0N/A }
0N/A }
0N/A
0N/A public static class EOWindOp extends AreaOp {
0N/A private boolean inside;
0N/A
0N/A public void newRow() {
0N/A inside = false;
0N/A }
0N/A
0N/A public int classify(Edge e) {
0N/A // Note: the right curves should be an empty set with this op...
0N/A // assert(e.getCurveTag() == CTAG_LEFT);
0N/A boolean newInside = !inside;
0N/A inside = newInside;
0N/A return (newInside ? ETAG_ENTER : ETAG_EXIT);
0N/A }
0N/A
0N/A public int getState() {
0N/A return (inside ? RSTAG_INSIDE : RSTAG_OUTSIDE);
0N/A }
0N/A }
0N/A
0N/A private AreaOp() {
0N/A }
0N/A
0N/A /* Constants to tag the left and right curves in the edge list */
0N/A public static final int CTAG_LEFT = 0;
0N/A public static final int CTAG_RIGHT = 1;
0N/A
0N/A /* Constants to classify edges */
0N/A public static final int ETAG_IGNORE = 0;
0N/A public static final int ETAG_ENTER = 1;
0N/A public static final int ETAG_EXIT = -1;
0N/A
0N/A /* Constants used to classify result state */
0N/A public static final int RSTAG_INSIDE = 1;
0N/A public static final int RSTAG_OUTSIDE = -1;
0N/A
0N/A public abstract void newRow();
0N/A
0N/A public abstract int classify(Edge e);
0N/A
0N/A public abstract int getState();
0N/A
0N/A public Vector calculate(Vector left, Vector right) {
0N/A Vector edges = new Vector();
0N/A addEdges(edges, left, AreaOp.CTAG_LEFT);
0N/A addEdges(edges, right, AreaOp.CTAG_RIGHT);
0N/A edges = pruneEdges(edges);
0N/A if (false) {
0N/A System.out.println("result: ");
0N/A int numcurves = edges.size();
0N/A Curve[] curvelist = (Curve[]) edges.toArray(new Curve[numcurves]);
0N/A for (int i = 0; i < numcurves; i++) {
0N/A System.out.println("curvelist["+i+"] = "+curvelist[i]);
0N/A }
0N/A }
0N/A return edges;
0N/A }
0N/A
0N/A private static void addEdges(Vector edges, Vector curves, int curvetag) {
0N/A Enumeration enum_ = curves.elements();
0N/A while (enum_.hasMoreElements()) {
0N/A Curve c = (Curve) enum_.nextElement();
0N/A if (c.getOrder() > 0) {
0N/A edges.add(new Edge(c, curvetag));
0N/A }
0N/A }
0N/A }
0N/A
0N/A private static Comparator YXTopComparator = new Comparator() {
0N/A public int compare(Object o1, Object o2) {
0N/A Curve c1 = ((Edge) o1).getCurve();
0N/A Curve c2 = ((Edge) o2).getCurve();
0N/A double v1, v2;
0N/A if ((v1 = c1.getYTop()) == (v2 = c2.getYTop())) {
0N/A if ((v1 = c1.getXTop()) == (v2 = c2.getXTop())) {
0N/A return 0;
0N/A }
0N/A }
0N/A if (v1 < v2) {
0N/A return -1;
0N/A }
0N/A return 1;
0N/A }
0N/A };
0N/A
0N/A private Vector pruneEdges(Vector edges) {
0N/A int numedges = edges.size();
0N/A if (numedges < 2) {
0N/A return edges;
0N/A }
0N/A Edge[] edgelist = (Edge[]) edges.toArray(new Edge[numedges]);
0N/A Arrays.sort(edgelist, YXTopComparator);
0N/A if (false) {
0N/A System.out.println("pruning: ");
0N/A for (int i = 0; i < numedges; i++) {
0N/A System.out.println("edgelist["+i+"] = "+edgelist[i]);
0N/A }
0N/A }
0N/A Edge e;
0N/A int left = 0;
0N/A int right = 0;
0N/A int cur = 0;
0N/A int next = 0;
0N/A double yrange[] = new double[2];
0N/A Vector subcurves = new Vector();
0N/A Vector chains = new Vector();
0N/A Vector links = new Vector();
0N/A // Active edges are between left (inclusive) and right (exclusive)
0N/A while (left < numedges) {
0N/A double y = yrange[0];
0N/A // Prune active edges that fall off the top of the active y range
0N/A for (cur = next = right - 1; cur >= left; cur--) {
0N/A e = edgelist[cur];
0N/A if (e.getCurve().getYBot() > y) {
0N/A if (next > cur) {
0N/A edgelist[next] = e;
0N/A }
0N/A next--;
0N/A }
0N/A }
0N/A left = next + 1;
0N/A // Grab a new "top of Y range" if the active edges are empty
0N/A if (left >= right) {
0N/A if (right >= numedges) {
0N/A break;
0N/A }
0N/A y = edgelist[right].getCurve().getYTop();
0N/A if (y > yrange[0]) {
0N/A finalizeSubCurves(subcurves, chains);
0N/A }
0N/A yrange[0] = y;
0N/A }
0N/A // Incorporate new active edges that enter the active y range
0N/A while (right < numedges) {
0N/A e = edgelist[right];
0N/A if (e.getCurve().getYTop() > y) {
0N/A break;
0N/A }
0N/A right++;
0N/A }
0N/A // Sort the current active edges by their X values and
0N/A // determine the maximum valid Y range where the X ordering
0N/A // is correct
0N/A yrange[1] = edgelist[left].getCurve().getYBot();
0N/A if (right < numedges) {
0N/A y = edgelist[right].getCurve().getYTop();
0N/A if (yrange[1] > y) {
0N/A yrange[1] = y;
0N/A }
0N/A }
0N/A if (false) {
0N/A System.out.println("current line: y = ["+
0N/A yrange[0]+", "+yrange[1]+"]");
0N/A for (cur = left; cur < right; cur++) {
0N/A System.out.println(" "+edgelist[cur]);
0N/A }
0N/A }
0N/A // Note: We could start at left+1, but we need to make
0N/A // sure that edgelist[left] has its equivalence set to 0.
0N/A int nexteq = 1;
0N/A for (cur = left; cur < right; cur++) {
0N/A e = edgelist[cur];
0N/A e.setEquivalence(0);
0N/A for (next = cur; next > left; next--) {
0N/A Edge prevedge = edgelist[next-1];
0N/A int ordering = e.compareTo(prevedge, yrange);
0N/A if (yrange[1] <= yrange[0]) {
0N/A throw new InternalError("backstepping to "+yrange[1]+
0N/A " from "+yrange[0]);
0N/A }
0N/A if (ordering >= 0) {
0N/A if (ordering == 0) {
0N/A // If the curves are equal, mark them to be
0N/A // deleted later if they cancel each other
0N/A // out so that we avoid having extraneous
0N/A // curve segments.
0N/A int eq = prevedge.getEquivalence();
0N/A if (eq == 0) {
0N/A eq = nexteq++;
0N/A prevedge.setEquivalence(eq);
0N/A }
0N/A e.setEquivalence(eq);
0N/A }
0N/A break;
0N/A }
0N/A edgelist[next] = prevedge;
0N/A }
0N/A edgelist[next] = e;
0N/A }
0N/A if (false) {
0N/A System.out.println("current sorted line: y = ["+
0N/A yrange[0]+", "+yrange[1]+"]");
0N/A for (cur = left; cur < right; cur++) {
0N/A System.out.println(" "+edgelist[cur]);
0N/A }
0N/A }
0N/A // Now prune the active edge list.
0N/A // For each edge in the list, determine its classification
0N/A // (entering shape, exiting shape, ignore - no change) and
0N/A // record the current Y range and its classification in the
0N/A // Edge object for use later in constructing the new outline.
0N/A newRow();
0N/A double ystart = yrange[0];
0N/A double yend = yrange[1];
0N/A for (cur = left; cur < right; cur++) {
0N/A e = edgelist[cur];
0N/A int etag;
0N/A int eq = e.getEquivalence();
0N/A if (eq != 0) {
0N/A // Find one of the segments in the "equal" range
0N/A // with the right transition state and prefer an
0N/A // edge that was either active up until ystart
0N/A // or the edge that extends the furthest downward
0N/A // (i.e. has the most potential for continuation)
0N/A int origstate = getState();
0N/A etag = (origstate == AreaOp.RSTAG_INSIDE
0N/A ? AreaOp.ETAG_EXIT
0N/A : AreaOp.ETAG_ENTER);
0N/A Edge activematch = null;
0N/A Edge longestmatch = e;
0N/A double furthesty = yend;
0N/A do {
0N/A // Note: classify() must be called
0N/A // on every edge we consume here.
0N/A classify(e);
0N/A if (activematch == null &&
0N/A e.isActiveFor(ystart, etag))
0N/A {
0N/A activematch = e;
0N/A }
0N/A y = e.getCurve().getYBot();
0N/A if (y > furthesty) {
0N/A longestmatch = e;
0N/A furthesty = y;
0N/A }
0N/A } while (++cur < right &&
0N/A (e = edgelist[cur]).getEquivalence() == eq);
0N/A --cur;
0N/A if (getState() == origstate) {
0N/A etag = AreaOp.ETAG_IGNORE;
0N/A } else {
0N/A e = (activematch != null ? activematch : longestmatch);
0N/A }
0N/A } else {
0N/A etag = classify(e);
0N/A }
0N/A if (etag != AreaOp.ETAG_IGNORE) {
0N/A e.record(yend, etag);
0N/A links.add(new CurveLink(e.getCurve(), ystart, yend, etag));
0N/A }
0N/A }
0N/A // assert(getState() == AreaOp.RSTAG_OUTSIDE);
0N/A if (getState() != AreaOp.RSTAG_OUTSIDE) {
0N/A System.out.println("Still inside at end of active edge list!");
0N/A System.out.println("num curves = "+(right-left));
0N/A System.out.println("num links = "+links.size());
0N/A System.out.println("y top = "+yrange[0]);
0N/A if (right < numedges) {
0N/A System.out.println("y top of next curve = "+
0N/A edgelist[right].getCurve().getYTop());
0N/A } else {
0N/A System.out.println("no more curves");
0N/A }
0N/A for (cur = left; cur < right; cur++) {
0N/A e = edgelist[cur];
0N/A System.out.println(e);
0N/A int eq = e.getEquivalence();
0N/A if (eq != 0) {
0N/A System.out.println(" was equal to "+eq+"...");
0N/A }
0N/A }
0N/A }
0N/A if (false) {
0N/A System.out.println("new links:");
0N/A for (int i = 0; i < links.size(); i++) {
0N/A CurveLink link = (CurveLink) links.elementAt(i);
0N/A System.out.println(" "+link.getSubCurve());
0N/A }
0N/A }
0N/A resolveLinks(subcurves, chains, links);
0N/A links.clear();
0N/A // Finally capture the bottom of the valid Y range as the top
0N/A // of the next Y range.
0N/A yrange[0] = yend;
0N/A }
0N/A finalizeSubCurves(subcurves, chains);
0N/A Vector ret = new Vector();
0N/A Enumeration enum_ = subcurves.elements();
0N/A while (enum_.hasMoreElements()) {
0N/A CurveLink link = (CurveLink) enum_.nextElement();
0N/A ret.add(link.getMoveto());
0N/A CurveLink nextlink = link;
0N/A while ((nextlink = nextlink.getNext()) != null) {
0N/A if (!link.absorb(nextlink)) {
0N/A ret.add(link.getSubCurve());
0N/A link = nextlink;
0N/A }
0N/A }
0N/A ret.add(link.getSubCurve());
0N/A }
0N/A return ret;
0N/A }
0N/A
0N/A public static void finalizeSubCurves(Vector subcurves, Vector chains) {
0N/A int numchains = chains.size();
0N/A if (numchains == 0) {
0N/A return;
0N/A }
0N/A if ((numchains & 1) != 0) {
0N/A throw new InternalError("Odd number of chains!");
0N/A }
0N/A ChainEnd[] endlist = new ChainEnd[numchains];
0N/A chains.toArray(endlist);
0N/A for (int i = 1; i < numchains; i += 2) {
0N/A ChainEnd open = endlist[i - 1];
0N/A ChainEnd close = endlist[i];
0N/A CurveLink subcurve = open.linkTo(close);
0N/A if (subcurve != null) {
0N/A subcurves.add(subcurve);
0N/A }
0N/A }
0N/A chains.clear();
0N/A }
0N/A
0N/A private static CurveLink[] EmptyLinkList = new CurveLink[2];
0N/A private static ChainEnd[] EmptyChainList = new ChainEnd[2];
0N/A
0N/A public static void resolveLinks(Vector subcurves,
0N/A Vector chains,
0N/A Vector links)
0N/A {
0N/A int numlinks = links.size();
0N/A CurveLink[] linklist;
0N/A if (numlinks == 0) {
0N/A linklist = EmptyLinkList;
0N/A } else {
0N/A if ((numlinks & 1) != 0) {
0N/A throw new InternalError("Odd number of new curves!");
0N/A }
0N/A linklist = new CurveLink[numlinks+2];
0N/A links.toArray(linklist);
0N/A }
0N/A int numchains = chains.size();
0N/A ChainEnd[] endlist;
0N/A if (numchains == 0) {
0N/A endlist = EmptyChainList;
0N/A } else {
0N/A if ((numchains & 1) != 0) {
0N/A throw new InternalError("Odd number of chains!");
0N/A }
0N/A endlist = new ChainEnd[numchains+2];
0N/A chains.toArray(endlist);
0N/A }
0N/A int curchain = 0;
0N/A int curlink = 0;
0N/A chains.clear();
0N/A ChainEnd chain = endlist[0];
0N/A ChainEnd nextchain = endlist[1];
0N/A CurveLink link = linklist[0];
0N/A CurveLink nextlink = linklist[1];
0N/A while (chain != null || link != null) {
0N/A /*
0N/A * Strategy 1:
0N/A * Connect chains or links if they are the only things left...
0N/A */
0N/A boolean connectchains = (link == null);
0N/A boolean connectlinks = (chain == null);
0N/A
0N/A if (!connectchains && !connectlinks) {
0N/A // assert(link != null && chain != null);
0N/A /*
0N/A * Strategy 2:
0N/A * Connect chains or links if they close off an open area...
0N/A */
0N/A connectchains = ((curchain & 1) == 0 &&
0N/A chain.getX() == nextchain.getX());
0N/A connectlinks = ((curlink & 1) == 0 &&
0N/A link.getX() == nextlink.getX());
0N/A
0N/A if (!connectchains && !connectlinks) {
0N/A /*
0N/A * Strategy 3:
0N/A * Connect chains or links if their successor is
0N/A * between them and their potential connectee...
0N/A */
0N/A double cx = chain.getX();
0N/A double lx = link.getX();
0N/A connectchains =
0N/A (nextchain != null && cx < lx &&
0N/A obstructs(nextchain.getX(), lx, curchain));
0N/A connectlinks =
0N/A (nextlink != null && lx < cx &&
0N/A obstructs(nextlink.getX(), cx, curlink));
0N/A }
0N/A }
0N/A if (connectchains) {
0N/A CurveLink subcurve = chain.linkTo(nextchain);
0N/A if (subcurve != null) {
0N/A subcurves.add(subcurve);
0N/A }
0N/A curchain += 2;
0N/A chain = endlist[curchain];
0N/A nextchain = endlist[curchain+1];
0N/A }
0N/A if (connectlinks) {
0N/A ChainEnd openend = new ChainEnd(link, null);
0N/A ChainEnd closeend = new ChainEnd(nextlink, openend);
0N/A openend.setOtherEnd(closeend);
0N/A chains.add(openend);
0N/A chains.add(closeend);
0N/A curlink += 2;
0N/A link = linklist[curlink];
0N/A nextlink = linklist[curlink+1];
0N/A }
0N/A if (!connectchains && !connectlinks) {
0N/A // assert(link != null);
0N/A // assert(chain != null);
0N/A // assert(chain.getEtag() == link.getEtag());
0N/A chain.addLink(link);
0N/A chains.add(chain);
0N/A curchain++;
0N/A chain = nextchain;
0N/A nextchain = endlist[curchain+1];
0N/A curlink++;
0N/A link = nextlink;
0N/A nextlink = linklist[curlink+1];
0N/A }
0N/A }
0N/A if ((chains.size() & 1) != 0) {
0N/A System.out.println("Odd number of chains!");
0N/A }
0N/A }
0N/A
0N/A /*
0N/A * Does the position of the next edge at v1 "obstruct" the
0N/A * connectivity between current edge and the potential
0N/A * partner edge which is positioned at v2?
0N/A *
0N/A * Phase tells us whether we are testing for a transition
0N/A * into or out of the interior part of the resulting area.
0N/A *
0N/A * Require 4-connected continuity if this edge and the partner
0N/A * edge are both "entering into" type edges
0N/A * Allow 8-connected continuity for "exiting from" type edges
0N/A */
0N/A public static boolean obstructs(double v1, double v2, int phase) {
0N/A return (((phase & 1) == 0) ? (v1 <= v2) : (v1 < v2));
0N/A }
0N/A}