package java.awt.geom;
import java.awt.Rectangle;
import java.awt.Shape;
import java.util.Vector;
public class Area implements Shape, Cloneable
{
private static final double EPSILON = 1E-11;
private static final double RS_EPSILON = 1E-13;
private static final double PE_EPSILON = 1E-11;
private Vector solids;
private Vector holes;
private Vector cc_intersections;
private int windingRule;
public Area()
{
solids = new Vector();
holes = new Vector();
}
public Area(Shape s)
{
this();
Vector p = makeSegment(s);
if (p == null)
return;
for (int i = 0; i < p.size(); i++)
if (((Segment) p.elementAt(i)).getSignedArea() == 0.0)
p.remove(i--);
Vector paths = new Vector();
Segment v;
for (int i = 0; i < p.size(); i++)
{
Segment path = (Segment) p.elementAt(i);
createNodesSelf(path);
}
if (p.size() > 1)
{
for (int i = 0; i < p.size() - 1; i++)
for (int j = i + 1; j < p.size(); j++)
{
Segment path1 = (Segment) p.elementAt(i);
Segment path2 = (Segment) p.elementAt(j);
createNodes(path1, path2);
}
}
Vector segments = new Vector();
for (int i = 0; i < p.size(); i++)
{
Segment path = v = (Segment) p.elementAt(i);
do
{
segments.add(v);
v = v.next;
}
while (v != path);
}
paths = weilerAtherton(segments);
deleteRedundantPaths(paths);
}
public void add(Area area)
{
if (equals(area))
return;
if (area.isEmpty())
return;
Area B = (Area) area.clone();
Vector pathA = new Vector();
Vector pathB = new Vector();
pathA.addAll(solids);
pathA.addAll(holes);
pathB.addAll(B.solids);
pathB.addAll(B.holes);
int nNodes = 0;
for (int i = 0; i < pathA.size(); i++)
{
Segment a = (Segment) pathA.elementAt(i);
for (int j = 0; j < pathB.size(); j++)
{
Segment b = (Segment) pathB.elementAt(j);
nNodes += createNodes(a, b);
}
}
Vector paths = new Vector();
Segment v;
Vector segments = new Vector();
for (int i = 0; i < pathA.size(); i++)
{
v = (Segment) pathA.elementAt(i);
Segment path = v;
do
{
if (v.isSegmentOutside(area))
segments.add(v);
v = v.next;
}
while (v != path);
}
for (int i = 0; i < pathB.size(); i++)
{
v = (Segment) pathB.elementAt(i);
Segment path = v;
do
{
if (v.isSegmentOutside(this))
segments.add(v);
v = v.next;
}
while (v != path);
}
paths = weilerAtherton(segments);
deleteRedundantPaths(paths);
}
public void subtract(Area area)
{
if (isEmpty() || area.isEmpty())
return;
if (equals(area))
{
reset();
return;
}
Vector pathA = new Vector();
Area B = (Area) area.clone();
pathA.addAll(solids);
pathA.addAll(holes);
setDirection(B.holes, true);
setDirection(B.solids, false);
Vector pathB = new Vector();
pathB.addAll(B.solids);
pathB.addAll(B.holes);
int nNodes = 0;
for (int i = 0; i < pathA.size(); i++)
{
Segment a = (Segment) pathA.elementAt(i);
for (int j = 0; j < pathB.size(); j++)
{
Segment b = (Segment) pathB.elementAt(j);
nNodes += createNodes(a, b);
}
}
Vector paths = new Vector();
Vector segments = new Vector();
for (int i = 0; i < pathA.size(); i++)
{
Segment v = (Segment) pathA.elementAt(i);
Segment path = v;
if (v.isSegmentOutside(area) && v.node == null)
segments.add(v);
boolean node = false;
do
{
if ((v.node != null || node))
{
node = (v.node != null);
if (v.isSegmentOutside(area))
segments.add(v);
}
v = v.next;
}
while (v != path);
}
for (int i = 0; i < pathB.size(); i++)
{
Segment v = (Segment) pathB.elementAt(i);
Segment path = v;
if (! v.isSegmentOutside(this) && v.node == null)
segments.add(v);
v = v.next;
boolean node = false;
do
{
if ((v.node != null || node))
{
node = (v.node != null);
if (! v.isSegmentOutside(this))
segments.add(v);
}
v = v.next;
}
while (v != path);
}
paths = weilerAtherton(segments);
deleteRedundantPaths(paths);
}
public void intersect(Area area)
{
if (isEmpty() || area.isEmpty())
{
reset();
return;
}
if (equals(area))
return;
Vector pathA = new Vector();
Area B = (Area) area.clone();
pathA.addAll(solids);
pathA.addAll(holes);
Vector pathB = new Vector();
pathB.addAll(B.solids);
pathB.addAll(B.holes);
int nNodes = 0;
for (int i = 0; i < pathA.size(); i++)
{
Segment a = (Segment) pathA.elementAt(i);
for (int j = 0; j < pathB.size(); j++)
{
Segment b = (Segment) pathB.elementAt(j);
nNodes += createNodes(a, b);
}
}
Vector paths = new Vector();
Vector segments = new Vector();
for (int i = 0; i < pathA.size(); i++)
{
Segment v = (Segment) pathA.elementAt(i);
Segment path = v;
if (! v.isSegmentOutside(area) && v.node == null)
segments.add(v);
boolean node = false;
do
{
if ((v.node != null || node))
{
node = (v.node != null);
if (! v.isSegmentOutside(area))
segments.add(v);
}
v = v.next;
}
while (v != path);
}
for (int i = 0; i < pathB.size(); i++)
{
Segment v = (Segment) pathB.elementAt(i);
Segment path = v;
if (! v.isSegmentOutside(this) && v.node == null)
segments.add(v);
v = v.next;
boolean node = false;
do
{
if ((v.node != null || node))
{
node = (v.node != null);
if (! v.isSegmentOutside(this))
segments.add(v);
}
v = v.next;
}
while (v != path);
}
paths = weilerAtherton(segments);
deleteRedundantPaths(paths);
}
public void exclusiveOr(Area area)
{
if (area.isEmpty())
return;
if (isEmpty())
{
Area B = (Area) area.clone();
solids = B.solids;
holes = B.holes;
return;
}
if (equals(area))
{
reset();
return;
}
Vector pathA = new Vector();
Area B = (Area) area.clone();
Vector pathB = new Vector();
pathA.addAll(solids);
pathA.addAll(holes);
setDirection(B.holes, true);
setDirection(B.solids, false);
pathB.addAll(B.solids);
pathB.addAll(B.holes);
int nNodes = 0;
for (int i = 0; i < pathA.size(); i++)
{
Segment a = (Segment) pathA.elementAt(i);
for (int j = 0; j < pathB.size(); j++)
{
Segment b = (Segment) pathB.elementAt(j);
nNodes += createNodes(a, b);
}
}
Vector paths = new Vector();
Segment v;
Vector segments = new Vector();
for (int i = 0; i < pathA.size(); i++)
{
v = (Segment) pathA.elementAt(i);
Segment path = v;
do
{
segments.add(v);
v = v.next;
}
while (v != path);
}
for (int i = 0; i < pathB.size(); i++)
{
v = (Segment) pathB.elementAt(i);
Segment path = v;
do
{
segments.add(v);
v = v.next;
}
while (v != path);
}
paths = weilerAtherton(segments);
deleteRedundantPaths(paths);
}
public void reset()
{
solids = new Vector();
holes = new Vector();
}
public boolean isEmpty()
{
if (solids.size() == 0)
return true;
double totalArea = 0;
for (int i = 0; i < solids.size(); i++)
totalArea += Math.abs(((Segment) solids.elementAt(i)).getSignedArea());
for (int i = 0; i < holes.size(); i++)
totalArea -= Math.abs(((Segment) holes.elementAt(i)).getSignedArea());
if (totalArea <= EPSILON)
return true;
return false;
}
public boolean isPolygonal()
{
for (int i = 0; i < holes.size(); i++)
if (! ((Segment) holes.elementAt(i)).isPolygonal())
return false;
for (int i = 0; i < solids.size(); i++)
if (! ((Segment) solids.elementAt(i)).isPolygonal())
return false;
return true;
}
public boolean isRectangular()
{
if (isEmpty())
return true;
if (holes.size() != 0 || solids.size() != 1)
return false;
Segment path = (Segment) solids.elementAt(0);
if (! path.isPolygonal())
return false;
int nCorners = 0;
Segment s = path;
do
{
Segment s2 = s.next;
double d1 = (s.P2.getX() - s.P1.getX())*(s2.P2.getX() - s2.P1.getX())/
((s.P1.distance(s.P2)) * (s2.P1.distance(s2.P2)));
double d2 = (s.P2.getY() - s.P1.getY())*(s2.P2.getY() - s2.P1.getY())/
((s.P1.distance(s.P2)) * (s2.P1.distance(s2.P2)));
double dotproduct = d1 + d2;
if (d1 != 0 && d2 != 0)
return false;
if (Math.abs(dotproduct) == 0) nCorners++;
else if ((Math.abs(1.0 - dotproduct) > 0)) return false;
s = s.next;
}
while (s != path);
return nCorners == 4;
}
public boolean isSingular()
{
return (holes.size() == 0 && solids.size() <= 1);
}
public Rectangle2D getBounds2D()
{
if (solids.size() == 0)
return new Rectangle2D.Double(0.0, 0.0, 0.0, 0.0);
double xmin;
double xmax;
double ymin;
double ymax;
xmin = xmax = ((Segment) solids.elementAt(0)).P1.getX();
ymin = ymax = ((Segment) solids.elementAt(0)).P1.getY();
for (int path = 0; path < solids.size(); path++)
{
Rectangle2D r = ((Segment) solids.elementAt(path)).getPathBounds();
xmin = Math.min(r.getMinX(), xmin);
ymin = Math.min(r.getMinY(), ymin);
xmax = Math.max(r.getMaxX(), xmax);
ymax = Math.max(r.getMaxY(), ymax);
}
return (new Rectangle2D.Double(xmin, ymin, (xmax - xmin), (ymax - ymin)));
}
public Rectangle getBounds()
{
return getBounds2D().getBounds();
}
public Object clone()
{
try
{
Area clone = new Area();
for (int i = 0; i < solids.size(); i++)
clone.solids.add(((Segment) solids.elementAt(i)).cloneSegmentList());
for (int i = 0; i < holes.size(); i++)
clone.holes.add(((Segment) holes.elementAt(i)).cloneSegmentList());
return clone;
}
catch (CloneNotSupportedException e)
{
throw (Error) new InternalError().initCause(e); }
}
public boolean equals(Area area)
{
if (area == null)
return false;
if (! getBounds2D().equals(area.getBounds2D()))
return false;
if (solids.size() != area.solids.size()
|| holes.size() != area.holes.size())
return false;
Vector pathA = new Vector();
pathA.addAll(solids);
pathA.addAll(holes);
Vector pathB = new Vector();
pathB.addAll(area.solids);
pathB.addAll(area.holes);
int nPaths = pathA.size();
boolean[][] match = new boolean[2][nPaths];
for (int i = 0; i < nPaths; i++)
{
for (int j = 0; j < nPaths; j++)
{
Segment p1 = (Segment) pathA.elementAt(i);
Segment p2 = (Segment) pathB.elementAt(j);
if (! match[0][i] && ! match[1][j])
if (p1.pathEquals(p2))
match[0][i] = match[1][j] = true;
}
}
boolean result = true;
for (int i = 0; i < nPaths; i++)
result = result && match[0][i] && match[1][i];
return result;
}
public void transform(AffineTransform at)
{
for (int i = 0; i < solids.size(); i++)
((Segment) solids.elementAt(i)).transformSegmentList(at);
for (int i = 0; i < holes.size(); i++)
((Segment) holes.elementAt(i)).transformSegmentList(at);
if ((at.getType() & AffineTransform.TYPE_FLIP) != 0)
{
setDirection(holes, false);
setDirection(solids, true);
}
}
public Area createTransformedArea(AffineTransform at)
{
Area a = (Area) clone();
a.transform(at);
return a;
}
public boolean contains(double x, double y)
{
int n = 0;
for (int i = 0; i < solids.size(); i++)
if (((Segment) solids.elementAt(i)).contains(x, y))
n++;
for (int i = 0; i < holes.size(); i++)
if (((Segment) holes.elementAt(i)).contains(x, y))
n--;
return (n != 0);
}
public boolean contains(Point2D p)
{
return contains(p.getX(), p.getY());
}
public boolean contains(double x, double y, double w, double h)
{
LineSegment[] l = new LineSegment[4];
l[0] = new LineSegment(x, y, x + w, y);
l[1] = new LineSegment(x, y + h, x + w, y + h);
l[2] = new LineSegment(x, y, x, y + h);
l[3] = new LineSegment(x + w, y, x + w, y + h);
for (int i = 0; i < 4; i++)
{
for (int path = 0; path < solids.size(); path++)
{
Segment v;
Segment start;
start = v = (Segment) solids.elementAt(path);
do
{
if (l[i].hasIntersections(v))
return false;
v = v.next;
}
while (v != start);
}
for (int path = 0; path < holes.size(); path++)
{
Segment v;
Segment start;
start = v = (Segment) holes.elementAt(path);
do
{
if (l[i].hasIntersections(v))
return false;
v = v.next;
}
while (v != start);
}
}
if (! contains(x, y))
return false;
Rectangle2D r = new Rectangle2D.Double(x, y, w, h);
for (int path = 0; path < holes.size(); path++)
if (! ((Segment) holes.elementAt(path)).isSegmentOutside(r))
return false;
return true;
}
public boolean contains(Rectangle2D r)
{
return contains(r.getX(), r.getY(), r.getWidth(), r.getHeight());
}
public boolean intersects(double x, double y, double w, double h)
{
if (solids.size() == 0)
return false;
LineSegment[] l = new LineSegment[4];
l[0] = new LineSegment(x, y, x + w, y);
l[1] = new LineSegment(x, y + h, x + w, y + h);
l[2] = new LineSegment(x, y, x, y + h);
l[3] = new LineSegment(x + w, y, x + w, y + h);
for (int i = 0; i < 4; i++)
{
for (int path = 0; path < solids.size(); path++)
{
Segment v;
Segment start;
start = v = (Segment) solids.elementAt(path);
do
{
if (l[i].hasIntersections(v))
return true;
v = v.next;
}
while (v != start);
}
for (int path = 0; path < holes.size(); path++)
{
Segment v;
Segment start;
start = v = (Segment) holes.elementAt(path);
do
{
if (l[i].hasIntersections(v))
return true;
v = v.next;
}
while (v != start);
}
}
if (contains(x + w * 0.5, y + h * 0.5))
return true;
Point2D p = ((Segment) solids.elementAt(0)).getMidPoint();
if ((new Rectangle2D.Double(x, y, w, h)).contains(p))
return true;
return false;
}
public boolean intersects(Rectangle2D r)
{
return intersects(r.getX(), r.getY(), r.getWidth(), r.getHeight());
}
public PathIterator getPathIterator(AffineTransform at)
{
return (new AreaIterator(at));
}
public PathIterator getPathIterator(AffineTransform at, double flatness)
{
return new FlatteningPathIterator(getPathIterator(at), flatness);
}
private class AreaIterator implements PathIterator
{
private Vector segments;
private int index;
private AffineTransform at;
class IteratorSegment
{
int type;
double[] coords;
IteratorSegment()
{
coords = new double[6];
}
}
public AreaIterator(AffineTransform at)
{
this.at = at;
index = 0;
segments = new Vector();
Vector allpaths = new Vector();
allpaths.addAll(solids);
allpaths.addAll(holes);
for (int i = 0; i < allpaths.size(); i++)
{
Segment v = (Segment) allpaths.elementAt(i);
Segment start = v;
IteratorSegment is = new IteratorSegment();
is.type = SEG_MOVETO;
is.coords[0] = start.P1.getX();
is.coords[1] = start.P1.getY();
segments.add(is);
do
{
is = new IteratorSegment();
is.type = v.pathIteratorFormat(is.coords);
segments.add(is);
v = v.next;
}
while (v != start);
is = new IteratorSegment();
is.type = SEG_CLOSE;
segments.add(is);
}
}
public int currentSegment(double[] coords)
{
IteratorSegment s = (IteratorSegment) segments.elementAt(index);
if (at != null)
at.transform(s.coords, 0, coords, 0, 3);
else
for (int i = 0; i < 6; i++)
coords[i] = s.coords[i];
return (s.type);
}
public int currentSegment(float[] coords)
{
IteratorSegment s = (IteratorSegment) segments.elementAt(index);
double[] d = new double[6];
if (at != null)
{
at.transform(s.coords, 0, d, 0, 3);
for (int i = 0; i < 6; i++)
coords[i] = (float) d[i];
}
else
for (int i = 0; i < 6; i++)
coords[i] = (float) s.coords[i];
return (s.type);
}
public int getWindingRule()
{
return (PathIterator.WIND_EVEN_ODD);
}
public boolean isDone()
{
return (index >= segments.size());
}
public void next()
{
index++;
}
}
private Vector weilerAtherton(Vector segments)
{
Vector paths = new Vector();
while (segments.size() > 0)
{
Segment start = (Segment) segments.elementAt(0);
Segment s = start;
do
{
segments.remove(s);
if (s.node != null)
{ s.next = s.node;
s.node = null;
}
s = s.next; }
while (s != start);
paths.add(start);
}
return paths;
}
private class Intersection
{
Point2D p; double ta; double tb; Segment seg;
public Intersection(Point2D p, double ta, double tb)
{
this.p = p;
this.ta = ta;
this.tb = tb;
}
}
private int getRecursionDepth(CubicSegment curve)
{
double x0 = curve.P1.getX();
double y0 = curve.P1.getY();
double x1 = curve.cp1.getX();
double y1 = curve.cp1.getY();
double x2 = curve.cp2.getX();
double y2 = curve.cp2.getY();
double x3 = curve.P2.getX();
double y3 = curve.P2.getY();
double L0 = Math.max(Math.max(Math.abs(x0 - 2 * x1 + x2),
Math.abs(x1 - 2 * x2 + x3)),
Math.max(Math.abs(y0 - 2 * y1 + y2),
Math.abs(y1 - 2 * y2 + y3)));
double f = Math.sqrt(2) * 6.0 * L0 / (8.0 * RS_EPSILON);
int r0 = (int) Math.ceil(Math.log(f) / Math.log(4.0));
return (r0);
}
private void recursiveSubdivide(CubicCurve2D c1, CubicCurve2D c2,
int depth1, int depth2, double t1,
double t2, double w1, double w2)
{
boolean flat1 = depth1 <= 0;
boolean flat2 = depth2 <= 0;
if (flat1 && flat2)
{
double xlk = c1.getP2().getX() - c1.getP1().getX();
double ylk = c1.getP2().getY() - c1.getP1().getY();
double xnm = c2.getP2().getX() - c2.getP1().getX();
double ynm = c2.getP2().getY() - c2.getP1().getY();
double xmk = c2.getP1().getX() - c1.getP1().getX();
double ymk = c2.getP1().getY() - c1.getP1().getY();
double det = xnm * ylk - ynm * xlk;
if (det + 1.0 == 1.0)
return;
double detinv = 1.0 / det;
double s = (xnm * ymk - ynm * xmk) * detinv;
double t = (xlk * ymk - ylk * xmk) * detinv;
if ((s < 0.0) || (s > 1.0) || (t < 0.0) || (t > 1.0))
return;
double[] temp = new double[2];
temp[0] = t1 + s * w1;
temp[1] = t2 + t * w1;
cc_intersections.add(temp);
return;
}
CubicCurve2D.Double c11 = new CubicCurve2D.Double();
CubicCurve2D.Double c12 = new CubicCurve2D.Double();
CubicCurve2D.Double c21 = new CubicCurve2D.Double();
CubicCurve2D.Double c22 = new CubicCurve2D.Double();
if (! flat1 && ! flat2)
{
depth1--;
depth2--;
w1 = w1 * 0.5;
w2 = w2 * 0.5;
c1.subdivide(c11, c12);
c2.subdivide(c21, c22);
if (c11.getBounds2D().intersects(c21.getBounds2D()))
recursiveSubdivide(c11, c21, depth1, depth2, t1, t2, w1, w2);
if (c11.getBounds2D().intersects(c22.getBounds2D()))
recursiveSubdivide(c11, c22, depth1, depth2, t1, t2 + w2, w1, w2);
if (c12.getBounds2D().intersects(c21.getBounds2D()))
recursiveSubdivide(c12, c21, depth1, depth2, t1 + w1, t2, w1, w2);
if (c12.getBounds2D().intersects(c22.getBounds2D()))
recursiveSubdivide(c12, c22, depth1, depth2, t1 + w1, t2 + w2, w1, w2);
return;
}
if (! flat1)
{
depth1--;
c1.subdivide(c11, c12);
w1 = w1 * 0.5;
if (c11.getBounds2D().intersects(c2.getBounds2D()))
recursiveSubdivide(c11, c2, depth1, depth2, t1, t2, w1, w2);
if (c12.getBounds2D().intersects(c2.getBounds2D()))
recursiveSubdivide(c12, c2, depth1, depth2, t1 + w1, t2, w1, w2);
return;
}
depth2--;
c2.subdivide(c21, c22);
w2 = w2 * 0.5;
if (c1.getBounds2D().intersects(c21.getBounds2D()))
recursiveSubdivide(c1, c21, depth1, depth2, t1, t2, w1, w2);
if (c1.getBounds2D().intersects(c22.getBounds2D()))
recursiveSubdivide(c1, c22, depth1, depth2, t1, t2 + w2, w1, w2);
}
private Intersection[] cubicCubicIntersect(CubicSegment curve1,
CubicSegment curve2)
{
Rectangle2D r1 = curve1.getBounds();
Rectangle2D r2 = curve2.getBounds();
if (! r1.intersects(r2))
return null;
cc_intersections = new Vector();
recursiveSubdivide(curve1.getCubicCurve2D(), curve2.getCubicCurve2D(),
getRecursionDepth(curve1), getRecursionDepth(curve2),
0.0, 0.0, 1.0, 1.0);
if (cc_intersections.size() == 0)
return null;
Intersection[] results = new Intersection[cc_intersections.size()];
for (int i = 0; i < cc_intersections.size(); i++)
{
double[] temp = (double[]) cc_intersections.elementAt(i);
results[i] = new Intersection(curve1.evaluatePoint(temp[0]), temp[0],
temp[1]);
}
cc_intersections = null;
return (results);
}
private Intersection[] lineQuadIntersect(LineSegment l, QuadSegment c)
{
double[] y = new double[3];
double[] x = new double[3];
double[] r = new double[3];
int nRoots;
double x0 = c.P1.getX();
double y0 = c.P1.getY();
double x1 = c.cp.getX();
double y1 = c.cp.getY();
double x2 = c.P2.getX();
double y2 = c.P2.getY();
double lx0 = l.P1.getX();
double ly0 = l.P1.getY();
double lx1 = l.P2.getX();
double ly1 = l.P2.getY();
double dx = lx1 - lx0;
double dy = ly1 - ly0;
y[0] = y0;
y[1] = 2 * (y1 - y0);
y[2] = (y2 - 2 * y1 + y0);
x[0] = x0;
x[1] = 2 * (x1 - x0);
x[2] = (x2 - 2 * x1 + x0);
if (dy == 0 && dx == 0)
return null;
if (dx == 0 || (dy / dx) > 1.0)
{
double k = dx / dy;
x[0] -= lx0;
y[0] -= ly0;
y[0] *= k;
y[1] *= k;
y[2] *= k;
}
else
{
double k = dy / dx;
x[0] -= lx0;
y[0] -= ly0;
x[0] *= k;
x[1] *= k;
x[2] *= k;
}
for (int i = 0; i < 3; i++)
r[i] = y[i] - x[i];
if ((nRoots = QuadCurve2D.solveQuadratic(r)) > 0)
{
Intersection[] temp = new Intersection[nRoots];
int intersections = 0;
for (int i = 0; i < nRoots; i++)
{
double t = r[i];
if (t >= 0.0 && t <= 1.0)
{
Point2D p = c.evaluatePoint(t);
if (dx == 0)
p.setLocation(lx0, p.getY());
if (dy == 0)
p.setLocation(p.getX(), ly0);
if (p.getX() <= Math.max(lx0, lx1)
&& p.getX() >= Math.min(lx0, lx1)
&& p.getY() <= Math.max(ly0, ly1)
&& p.getY() >= Math.min(ly0, ly1))
{
double lineparameter = p.distance(l.P1) / l.P2.distance(l.P1);
temp[i] = new Intersection(p, lineparameter, t);
intersections++;
}
}
else
temp[i] = null;
}
if (intersections == 0)
return null;
Intersection[] rValues = new Intersection[intersections];
for (int i = 0; i < nRoots; i++)
if (temp[i] != null)
rValues[--intersections] = temp[i];
return (rValues);
}
return null;
}
private Intersection[] lineCubicIntersect(LineSegment l, CubicSegment c)
{
double[] y = new double[4];
double[] x = new double[4];
double[] r = new double[4];
int nRoots;
double x0 = c.P1.getX();
double y0 = c.P1.getY();
double x1 = c.cp1.getX();
double y1 = c.cp1.getY();
double x2 = c.cp2.getX();
double y2 = c.cp2.getY();
double x3 = c.P2.getX();
double y3 = c.P2.getY();
double lx0 = l.P1.getX();
double ly0 = l.P1.getY();
double lx1 = l.P2.getX();
double ly1 = l.P2.getY();
double dx = lx1 - lx0;
double dy = ly1 - ly0;
y[0] = y0;
y[1] = 3 * (y1 - y0);
y[2] = 3 * (y2 + y0 - 2 * y1);
y[3] = y3 - 3 * y2 + 3 * y1 - y0;
x[0] = x0;
x[1] = 3 * (x1 - x0);
x[2] = 3 * (x2 + x0 - 2 * x1);
x[3] = x3 - 3 * x2 + 3 * x1 - x0;
if (dy == 0 && dx == 0)
return null;
if (dx == 0 || (dy / dx) > 1.0)
{
double k = dx / dy;
x[0] -= lx0;
y[0] -= ly0;
y[0] *= k;
y[1] *= k;
y[2] *= k;
y[3] *= k;
}
else
{
double k = dy / dx;
x[0] -= lx0;
y[0] -= ly0;
x[0] *= k;
x[1] *= k;
x[2] *= k;
x[3] *= k;
}
for (int i = 0; i < 4; i++)
r[i] = y[i] - x[i];
if ((nRoots = CubicCurve2D.solveCubic(r)) > 0)
{
Intersection[] temp = new Intersection[nRoots];
int intersections = 0;
for (int i = 0; i < nRoots; i++)
{
double t = r[i];
if (t >= 0.0 && t <= 1.0)
{
Point2D p = c.evaluatePoint(t);
if (dx == 0)
p.setLocation(lx0, p.getY());
if (dy == 0)
p.setLocation(p.getX(), ly0);
if (p.getX() <= Math.max(lx0, lx1)
&& p.getX() >= Math.min(lx0, lx1)
&& p.getY() <= Math.max(ly0, ly1)
&& p.getY() >= Math.min(ly0, ly1))
{
double lineparameter = p.distance(l.P1) / l.P2.distance(l.P1);
temp[i] = new Intersection(p, lineparameter, t);
intersections++;
}
}
else
temp[i] = null;
}
if (intersections == 0)
return null;
Intersection[] rValues = new Intersection[intersections];
for (int i = 0; i < nRoots; i++)
if (temp[i] != null)
rValues[--intersections] = temp[i];
return (rValues);
}
return null;
}
private Intersection linesIntersect(LineSegment a, LineSegment b)
{
Point2D P1 = a.P1;
Point2D P2 = a.P2;
Point2D P3 = b.P1;
Point2D P4 = b.P2;
if (! Line2D.linesIntersect(P1.getX(), P1.getY(), P2.getX(), P2.getY(),
P3.getX(), P3.getY(), P4.getX(), P4.getY()))
return null;
double x1 = P1.getX();
double y1 = P1.getY();
double rx = P2.getX() - x1;
double ry = P2.getY() - y1;
double x2 = P3.getX();
double y2 = P3.getY();
double sx = P4.getX() - x2;
double sy = P4.getY() - y2;
double determinant = sx * ry - sy * rx;
double nom = (sx * (y2 - y1) + sy * (x1 - x2));
if (Math.abs(determinant) < EPSILON)
return null;
nom = nom / determinant;
if (nom == 0.0)
return null;
if (nom == 1.0)
return null;
Point2D p = new Point2D.Double(x1 + nom * rx, y1 + nom * ry);
return new Intersection(p, p.distance(P1) / P1.distance(P2),
p.distance(P3) / P3.distance(P4));
}
private boolean pointEquals(Point2D a, Point2D b)
{
return (a.equals(b) || a.distance(b) < PE_EPSILON);
}
private Vector makeSegment(Shape s)
{
Vector paths = new Vector();
PathIterator pi = s.getPathIterator(null);
double[] coords = new double[6];
Segment subpath = null;
Segment current = null;
double cx;
double cy;
double subpathx;
double subpathy;
cx = cy = subpathx = subpathy = 0.0;
this.windingRule = pi.getWindingRule();
while (! pi.isDone())
{
Segment v;
switch (pi.currentSegment(coords))
{
case PathIterator.SEG_MOVETO:
if (subpath != null)
{ current.next = new LineSegment(cx, cy, subpathx, subpathy);
current = current.next;
current.next = subpath;
}
subpath = null;
subpathx = cx = coords[0];
subpathy = cy = coords[1];
break;
case PathIterator.SEG_CLOSE:
if (subpath != null && (subpathx != cx || subpathy != cy))
{
current.next = new LineSegment(cx, cy, subpathx, subpathy);
current = current.next;
current.next = subpath;
cx = subpathx;
cy = subpathy;
subpath = null;
}
else if (subpath != null)
{
current.next = subpath;
subpath = null;
}
break;
case PathIterator.SEG_LINETO:
if (cx != coords[0] || cy != coords[1])
{
v = new LineSegment(cx, cy, coords[0], coords[1]);
if (subpath == null)
{
subpath = current = v;
paths.add(subpath);
}
else
{
current.next = v;
current = current.next;
}
cx = coords[0];
cy = coords[1];
}
break;
case PathIterator.SEG_QUADTO:
v = new QuadSegment(cx, cy, coords[0], coords[1], coords[2],
coords[3]);
if (subpath == null)
{
subpath = current = v;
paths.add(subpath);
}
else
{
current.next = v;
current = current.next;
}
cx = coords[2];
cy = coords[3];
break;
case PathIterator.SEG_CUBICTO:
v = new CubicSegment(cx, cy, coords[0], coords[1], coords[2],
coords[3], coords[4], coords[5]);
if (subpath == null)
{
subpath = current = v;
paths.add(subpath);
}
else
{
current.next = v;
current = current.next;
}
double[] lpts = ((CubicSegment) v).getLoop();
if (lpts != null)
{
v.subdivideInsert(lpts[0]);
v.next.subdivideInsert((lpts[1] - lpts[0]) / (1.0 - lpts[0]));
CubicSegment loop = (CubicSegment) v.next;
v.next = loop.next;
loop.next = loop;
v.P2 = v.next.P1 = loop.P2 = loop.P1; paths.add(loop);
current = v.next;
}
cx = coords[4];
cy = coords[5];
break;
}
pi.next();
}
if (subpath != null)
{ if (subpathx != cx || subpathy != cy)
{
current.next = new LineSegment(cx, cy, subpathx, subpathy);
current = current.next;
current.next = subpath;
}
else
current.next = subpath;
}
if (paths.size() == 0)
return (null);
return (paths);
}
private int createNodes(Segment A, Segment B)
{
int nNodes = 0;
Segment a = A;
Segment b = B;
do
{
do
{
nNodes += a.splitIntersections(b);
b = b.next;
}
while (b != B);
a = a.next; }
while (a != A);
return (nNodes);
}
private int createNodesSelf(Segment A)
{
int nNodes = 0;
Segment a = A;
if (A.next == A)
return 0;
do
{
Segment b = a.next;
do
{
if (b != a) nNodes += a.splitIntersections(b);
b = b.next;
}
while (b != A);
a = a.next; }
while (a != A);
return (nNodes);
}
private void deleteRedundantPaths(Vector paths)
{
int npaths = paths.size();
int[][] contains = new int[npaths][npaths];
int[][] windingNumbers = new int[npaths][2];
int neg;
Rectangle2D[] bb = new Rectangle2D[npaths];
neg = ((windingRule == PathIterator.WIND_NON_ZERO) ? -1 : 1);
for (int i = 0; i < npaths; i++)
bb[i] = ((Segment) paths.elementAt(i)).getPathBounds();
for (int i = 0; i < npaths; i++)
{
Segment pathA = (Segment) paths.elementAt(i);
pathA.nullNodes(); int windingA = pathA.hasClockwiseOrientation() ? 1 : neg;
for (int j = 0; j < npaths; j++)
if (i != j)
{
Segment pathB = (Segment) paths.elementAt(j);
if (bb[i].intersects(bb[j]))
{
Segment s = pathB.next;
while (s.P1.getY() == s.P2.getY() && s != pathB)
s = s.next;
Point2D p = s.getMidPoint();
if (pathA.contains(p.getX(), p.getY()))
contains[i][j] = windingA;
}
else
contains[i][j] = 0;
}
else
contains[i][j] = windingA; }
for (int i = 0; i < npaths; i++)
{
windingNumbers[i][0] = 0;
for (int j = 0; j < npaths; j++)
windingNumbers[i][0] += contains[j][i];
windingNumbers[i][1] = contains[i][i];
}
Vector solids = new Vector();
Vector holes = new Vector();
if (windingRule == PathIterator.WIND_NON_ZERO)
{
for (int i = 0; i < npaths; i++)
{
if (windingNumbers[i][0] == 0)
holes.add(paths.elementAt(i));
else if (windingNumbers[i][0] - windingNumbers[i][1] == 0
&& Math.abs(windingNumbers[i][0]) == 1)
solids.add(paths.elementAt(i));
}
}
else
{
windingRule = PathIterator.WIND_NON_ZERO;
for (int i = 0; i < npaths; i++)
{
if ((windingNumbers[i][0] & 1) == 0)
holes.add(paths.elementAt(i));
else if ((windingNumbers[i][0] & 1) == 1)
solids.add(paths.elementAt(i));
}
}
setDirection(holes, false);
setDirection(solids, true);
this.holes = holes;
this.solids = solids;
}
private void setDirection(Vector paths, boolean clockwise)
{
Segment v;
for (int i = 0; i < paths.size(); i++)
{
v = (Segment) paths.elementAt(i);
if (clockwise != v.hasClockwiseOrientation())
v.reverseAll();
}
}
private abstract class Segment implements Cloneable
{
Point2D P1;
Point2D P2;
Segment next;
Segment node;
Segment()
{
P1 = P2 = null;
node = next = null;
}
abstract void reverseCoords();
abstract Point2D getMidPoint();
abstract Rectangle2D getBounds();
abstract void transform(AffineTransform at);
abstract int getType();
abstract int splitIntersections(Segment b);
abstract int pathIteratorFormat(double[] coords);
abstract int rayCrossing(double x, double y);
abstract void subdivideInsert(double t);
abstract double curveArea();
abstract boolean equals(Segment b);
boolean contains(double x, double y)
{
Segment v = this;
int crossings = 0;
do
{
int n = v.rayCrossing(x, y);
crossings += n;
v = v.next;
}
while (v != this);
return ((crossings & 1) == 1);
}
void nullNodes()
{
Segment v = this;
do
{
v.node = null;
v = v.next;
}
while (v != this);
}
void transformSegmentList(AffineTransform at)
{
Segment v = this;
do
{
v.transform(at);
v = v.next;
}
while (v != this);
}
boolean hasClockwiseOrientation()
{
return (getSignedArea() > 0.0);
}
public Rectangle2D getPathBounds()
{
double xmin;
double xmax;
double ymin;
double ymax;
xmin = xmax = P1.getX();
ymin = ymax = P1.getY();
Segment v = this;
do
{
Rectangle2D r = v.getBounds();
xmin = Math.min(r.getMinX(), xmin);
ymin = Math.min(r.getMinY(), ymin);
xmax = Math.max(r.getMaxX(), xmax);
ymax = Math.max(r.getMaxY(), ymax);
v = v.next;
}
while (v != this);
return (new Rectangle2D.Double(xmin, ymin, (xmax - xmin), (ymax - ymin)));
}
double getSignedArea()
{
Segment s;
double area = 0.0;
s = this;
do
{
area += s.curveArea();
area += s.P1.getX() * s.next.P1.getY()
- s.P1.getY() * s.next.P1.getX();
s = s.next;
}
while (s != this);
return area;
}
void reverseAll()
{
reverseCoords();
Segment v = next;
Segment former = this;
while (v != this)
{
v.reverseCoords();
Segment vnext = v.next;
v.next = former;
former = v;
v = vnext;
}
next = former;
}
void insert(Segment v)
{
Segment n = next;
next = v;
v.next = n;
}
boolean isPolygonal()
{
Segment v = this;
do
{
if (! (v instanceof LineSegment))
return false;
v = v.next;
}
while (v != this);
return true;
}
Segment cloneSegmentList() throws CloneNotSupportedException
{
Vector list = new Vector();
Segment v = next;
while (v != this)
{
list.add(v);
v = v.next;
}
Segment clone = (Segment) this.clone();
v = clone;
for (int i = 0; i < list.size(); i++)
{
clone.next = (Segment) ((Segment) list.elementAt(i)).clone();
clone = clone.next;
}
clone.next = v;
return v;
}
int createNode(Segment b, Intersection i)
{
Point2D p = i.p;
if ((pointEquals(P1, p) || pointEquals(P2, p))
&& (pointEquals(b.P1, p) || pointEquals(b.P2, p)))
return 0;
subdivideInsert(i.ta);
b.subdivideInsert(i.tb);
b.P2 = b.next.P1 = P2 = next.P1 = i.p;
node = b.next;
b.node = next;
return 1;
}
protected int createNodes(Segment b, Intersection[] x)
{
Vector v = new Vector();
for (int i = 0; i < x.length; i++)
{
Point2D p = x[i].p;
if (! ((pointEquals(P1, p) || pointEquals(P2, p))
&& (pointEquals(b.P1, p) || pointEquals(b.P2, p))))
v.add(x[i]);
}
int nNodes = v.size();
Intersection[] A = new Intersection[nNodes];
Intersection[] B = new Intersection[nNodes];
for (int i = 0; i < nNodes; i++)
A[i] = B[i] = (Intersection) v.elementAt(i);
for (int i = 0; i < nNodes - 1; i++)
{
for (int j = i + 1; j < nNodes; j++)
{
if (A[i].ta > A[j].ta)
{
Intersection swap = A[i];
A[i] = A[j];
A[j] = swap;
}
if (B[i].tb > B[j].tb)
{
Intersection swap = B[i];
B[i] = B[j];
B[j] = swap;
}
}
}
Segment s = this;
for (int i = 0; i < nNodes; i++)
{
s.subdivideInsert(A[i].ta);
for (int j = i + 1; j < nNodes; j++)
A[j].ta = (A[j].ta - A[i].ta) / (1.0 - A[i].ta);
A[i].seg = s;
s = s.next;
}
s = b;
for (int i = 0; i < nNodes; i++)
{
s.subdivideInsert(B[i].tb);
for (int j = i + 1; j < nNodes; j++)
B[j].tb = (B[j].tb - B[i].tb) / (1.0 - B[i].tb);
B[i].seg.node = s.next; s.node = B[i].seg.next;
B[i].seg.P2 = B[i].seg.next.P1 = s.P2 = s.next.P1 = B[i].p;
s = s.next;
}
return nNodes;
}
boolean pathEquals(Segment B)
{
if (! getPathBounds().equals(B.getPathBounds()))
return false;
Segment startA = getTopLeft();
Segment startB = B.getTopLeft();
Segment a = startA;
Segment b = startB;
do
{
if (! a.equals(b))
return false;
if (a instanceof LineSegment)
a = ((LineSegment) a).lastCoLinear();
if (b instanceof LineSegment)
b = ((LineSegment) b).lastCoLinear();
a = a.next;
b = b.next;
}
while (a != startA && b != startB);
return true;
}
Segment getTopLeft()
{
Segment v = this;
Segment tl = this;
do
{
if (v.P1.getY() < tl.P1.getY())
tl = v;
else if (v.P1.getY() == tl.P1.getY())
{
if (v.P1.getX() < tl.P1.getX())
tl = v;
}
v = v.next;
}
while (v != this);
return tl;
}
boolean isSegmentOutside(Shape shape)
{
return ! shape.contains(getMidPoint());
}
}
private class LineSegment extends Segment
{
public LineSegment(double x1, double y1, double x2, double y2)
{
super();
P1 = new Point2D.Double(x1, y1);
P2 = new Point2D.Double(x2, y2);
}
public LineSegment(Point2D p1, Point2D p2)
{
super();
P1 = (Point2D) p1.clone();
P2 = (Point2D) p2.clone();
}
public Object clone()
{
return new LineSegment(P1, P2);
}
void transform(AffineTransform at)
{
P1 = at.transform(P1, null);
P2 = at.transform(P2, null);
}
void reverseCoords()
{
Point2D p = P1;
P1 = P2;
P2 = p;
}
Point2D getMidPoint()
{
return (new Point2D.Double(0.5 * (P1.getX() + P2.getX()),
0.5 * (P1.getY() + P2.getY())));
}
double curveArea()
{
return 0;
}
int getType()
{
return (PathIterator.SEG_LINETO);
}
void subdivideInsert(double t)
{
Point2D p = new Point2D.Double((P2.getX() - P1.getX()) * t + P1.getX(),
(P2.getY() - P1.getY()) * t + P1.getY());
insert(new LineSegment(p, P2));
P2 = p;
next.node = node;
node = null;
}
boolean isCoLinear(LineSegment b)
{
double x1 = P1.getX();
double y1 = P1.getY();
double x2 = P2.getX();
double y2 = P2.getY();
double x3 = b.P1.getX();
double y3 = b.P1.getY();
double x4 = b.P2.getX();
double y4 = b.P2.getY();
if ((y1 - y3) * (x4 - x3) - (x1 - x3) * (y4 - y3) != 0.0)
return false;
return ((x2 - x1) * (y4 - y3) - (y2 - y1) * (x4 - x3) == 0.0);
}
Segment lastCoLinear()
{
Segment prev = this;
Segment v = next;
while (v instanceof LineSegment)
{
if (isCoLinear((LineSegment) v))
{
prev = v;
v = v.next;
}
else
return prev;
}
return prev;
}
boolean equals(Segment b)
{
if (! (b instanceof LineSegment))
return false;
Point2D p1 = P1;
Point2D p3 = b.P1;
if (! p1.equals(p3))
return false;
Point2D p2 = lastCoLinear().P2;
Point2D p4 = ((LineSegment) b).lastCoLinear().P2;
return (p2.equals(p4));
}
int pathIteratorFormat(double[] coords)
{
coords[0] = P2.getX();
coords[1] = P2.getY();
return (PathIterator.SEG_LINETO);
}
boolean hasIntersections(Segment b)
{
if (b instanceof LineSegment)
return (linesIntersect(this, (LineSegment) b) != null);
if (b instanceof QuadSegment)
return (lineQuadIntersect(this, (QuadSegment) b) != null);
if (b instanceof CubicSegment)
return (lineCubicIntersect(this, (CubicSegment) b) != null);
return false;
}
int splitIntersections(Segment b)
{
if (b instanceof LineSegment)
{
Intersection i = linesIntersect(this, (LineSegment) b);
if (i == null)
return 0;
return createNode(b, i);
}
Intersection[] x = null;
if (b instanceof QuadSegment)
x = lineQuadIntersect(this, (QuadSegment) b);
if (b instanceof CubicSegment)
x = lineCubicIntersect(this, (CubicSegment) b);
if (x == null)
return 0;
if (x.length == 1)
return createNode(b, (Intersection) x[0]);
return createNodes(b, x);
}
Rectangle2D getBounds()
{
return (new Rectangle2D.Double(Math.min(P1.getX(), P2.getX()),
Math.min(P1.getY(), P2.getY()),
Math.abs(P1.getX() - P2.getX()),
Math.abs(P1.getY() - P2.getY())));
}
int rayCrossing(double x, double y)
{
double x0 = P1.getX() - x;
double y0 = P1.getY() - y;
double x1 = P2.getX() - x;
double y1 = P2.getY() - y;
if (y0 * y1 > 0)
return 0;
if (x0 < 0 && x1 < 0)
return 0;
if (y0 == 0.0)
y0 -= EPSILON;
if (y1 == 0.0)
y1 -= EPSILON;
if (Line2D.linesIntersect(x0, y0, x1, y1,
EPSILON, 0.0, Double.MAX_VALUE, 0.0))
return 1;
return 0;
}
}
private class QuadSegment extends Segment
{
Point2D cp;
QuadSegment(double x1, double y1, double cx, double cy, double x2,
double y2)
{
super();
P1 = new Point2D.Double(x1, y1);
P2 = new Point2D.Double(x2, y2);
cp = new Point2D.Double(cx, cy);
}
public Object clone()
{
return new QuadSegment(P1.getX(), P1.getY(), cp.getX(), cp.getY(),
P2.getX(), P2.getY());
}
double curveArea()
{
double x0 = P1.getX();
double y0 = P1.getY();
double x1 = cp.getX();
double y1 = cp.getY();
double x2 = P2.getX();
double y2 = P2.getY();
double P = (y2 - 2 * y1 + y0);
double Q = 2 * (y1 - y0);
double A = (x2 - 2 * x1 + x0);
double B = 2 * (x1 - x0);
double area = (B * P - A * Q) / 3.0;
return (area);
}
boolean equals(Segment b)
{
if (! (b instanceof QuadSegment))
return false;
return (P1.equals(b.P1) && cp.equals(((QuadSegment) b).cp)
&& P2.equals(b.P2));
}
Point2D evaluatePoint(double t)
{
double x0 = P1.getX();
double y0 = P1.getY();
double x1 = cp.getX();
double y1 = cp.getY();
double x2 = P2.getX();
double y2 = P2.getY();
return new Point2D.Double(t * t * (x2 - 2 * x1 + x0) + 2 * t * (x1 - x0)
+ x0,
t * t * (y2 - 2 * y1 + y0) + 2 * t * (y1 - y0)
+ y0);
}
Rectangle2D getBounds()
{
double x0 = P1.getX();
double y0 = P1.getY();
double x1 = cp.getX();
double y1 = cp.getY();
double x2 = P2.getX();
double y2 = P2.getY();
double r0;
double r1;
double xmax = Math.max(x0, x2);
double ymax = Math.max(y0, y2);
double xmin = Math.min(x0, x2);
double ymin = Math.min(y0, y2);
r0 = 2 * (y1 - y0);
r1 = 2 * (y2 - 2 * y1 + y0);
if (r1 != 0.0)
{
double t = -r0 / r1;
if (t > 0.0 && t < 1.0)
{
double y = evaluatePoint(t).getY();
ymax = Math.max(y, ymax);
ymin = Math.min(y, ymin);
}
}
r0 = 2 * (x1 - x0);
r1 = 2 * (x2 - 2 * x1 + x0);
if (r1 != 0.0)
{
double t = -r0 / r1;
if (t > 0.0 && t < 1.0)
{
double x = evaluatePoint(t).getY();
xmax = Math.max(x, xmax);
xmin = Math.min(x, xmin);
}
}
return (new Rectangle2D.Double(xmin, ymin, xmax - xmin, ymax - ymin));
}
CubicSegment getCubicSegment()
{
double x1 = P1.getX() + 2.0 * (cp.getX() - P1.getX()) / 3.0;
double y1 = P1.getY() + 2.0 * (cp.getY() - P1.getY()) / 3.0;
double x2 = cp.getX() + (P2.getX() - cp.getX()) / 3.0;
double y2 = cp.getY() + (P2.getY() - cp.getY()) / 3.0;
return new CubicSegment(P1.getX(), P1.getY(), x1, y1, x2, y2, P2.getX(),
P2.getY());
}
Point2D getMidPoint()
{
return evaluatePoint(0.5);
}
int getType()
{
return (PathIterator.SEG_QUADTO);
}
int pathIteratorFormat(double[] coords)
{
coords[0] = cp.getX();
coords[1] = cp.getY();
coords[2] = P2.getX();
coords[3] = P2.getY();
return (PathIterator.SEG_QUADTO);
}
int rayCrossing(double x, double y)
{
double x0 = P1.getX() - x;
double y0 = P1.getY() - y;
double x1 = cp.getX() - x;
double y1 = cp.getY() - y;
double x2 = P2.getX() - x;
double y2 = P2.getY() - y;
double[] r = new double[3];
int nRoots;
int nCrossings = 0;
if ((x0 > 0.0 || x1 > 0.0 || x2 > 0.0) && (y0 * y1 <= 0 || y1 * y2 <= 0))
{
if (y0 == 0.0)
y0 -= EPSILON;
if (y2 == 0.0)
y2 -= EPSILON;
r[0] = y0;
r[1] = 2 * (y1 - y0);
r[2] = (y2 - 2 * y1 + y0);
nRoots = QuadCurve2D.solveQuadratic(r);
for (int i = 0; i < nRoots; i++)
if (r[i] > 0.0f && r[i] < 1.0f)
{
double t = r[i];
if (t * t * (x2 - 2 * x1 + x0) + 2 * t * (x1 - x0) + x0 > 0.0)
nCrossings++;
}
}
return nCrossings;
}
void reverseCoords()
{
Point2D temp = P1;
P1 = P2;
P2 = temp;
}
int splitIntersections(Segment b)
{
if (b instanceof LineSegment)
return (b.splitIntersections(this));
if (b instanceof CubicSegment)
return (b.splitIntersections(this));
if (b instanceof QuadSegment)
{
Intersection[] x = cubicCubicIntersect(getCubicSegment(),
((QuadSegment) b)
.getCubicSegment());
if (x == null)
return 0;
if (x.length == 1)
return createNode(b, (Intersection) x[0]);
return createNodes(b, x);
}
return 0;
}
void subdivideInsert(double t)
{
double x0 = P1.getX();
double y0 = P1.getY();
double x1 = cp.getX();
double y1 = cp.getY();
double x2 = P2.getX();
double y2 = P2.getY();
double p10x = x0 + t * (x1 - x0);
double p10y = y0 + t * (y1 - y0);
double p11x = x1 + t * (x2 - x1);
double p11y = y1 + t * (y2 - y1);
double p20x = p10x + t * (p11x - p10x);
double p20y = p10y + t * (p11y - p10y);
insert(new QuadSegment(p20x, p20y, p11x, p11y, x2, y2));
P2 = next.P1;
cp.setLocation(p10x, p10y);
next.node = node;
node = null;
}
void transform(AffineTransform at)
{
P1 = at.transform(P1, null);
P2 = at.transform(P2, null);
cp = at.transform(cp, null);
}
}
private class CubicSegment extends Segment
{
Point2D cp1; Point2D cp2;
public CubicSegment(double x1, double y1, double c1x, double c1y,
double c2x, double c2y, double x2, double y2)
{
super();
P1 = new Point2D.Double(x1, y1);
P2 = new Point2D.Double(x2, y2);
cp1 = new Point2D.Double(c1x, c1y);
cp2 = new Point2D.Double(c2x, c2y);
}
public Object clone()
{
return new CubicSegment(P1.getX(), P1.getY(), cp1.getX(), cp1.getY(),
cp2.getX(), cp2.getY(), P2.getX(), P2.getY());
}
double curveArea()
{
double x0 = P1.getX();
double y0 = P1.getY();
double x1 = cp1.getX();
double y1 = cp1.getY();
double x2 = cp2.getX();
double y2 = cp2.getY();
double x3 = P2.getX();
double y3 = P2.getY();
double P = y3 - 3 * y2 + 3 * y1 - y0;
double Q = 3 * (y2 + y0 - 2 * y1);
double R = 3 * (y1 - y0);
double A = x3 - 3 * x2 + 3 * x1 - x0;
double B = 3 * (x2 + x0 - 2 * x1);
double C = 3 * (x1 - x0);
double area = (B * P - A * Q) / 5.0 + (C * P - A * R) / 2.0
+ (C * Q - B * R) / 3.0;
return (area);
}
boolean equals(Segment b)
{
if (! (b instanceof CubicSegment))
return false;
return (P1.equals(b.P1) && cp1.equals(((CubicSegment) b).cp1)
&& cp2.equals(((CubicSegment) b).cp2) && P2.equals(b.P2));
}
Point2D evaluatePoint(double t)
{
double x0 = P1.getX();
double y0 = P1.getY();
double x1 = cp1.getX();
double y1 = cp1.getY();
double x2 = cp2.getX();
double y2 = cp2.getY();
double x3 = P2.getX();
double y3 = P2.getY();
return new Point2D.Double(-(t * t * t) * (x0 - 3 * x1 + 3 * x2 - x3)
+ 3 * t * t * (x0 - 2 * x1 + x2)
+ 3 * t * (x1 - x0) + x0,
-(t * t * t) * (y0 - 3 * y1 + 3 * y2 - y3)
+ 3 * t * t * (y0 - 2 * y1 + y2)
+ 3 * t * (y1 - y0) + y0);
}
Rectangle2D getBounds()
{
double x0 = P1.getX();
double y0 = P1.getY();
double x1 = cp1.getX();
double y1 = cp1.getY();
double x2 = cp2.getX();
double y2 = cp2.getY();
double x3 = P2.getX();
double y3 = P2.getY();
double[] r = new double[3];
double xmax = Math.max(x0, x3);
double ymax = Math.max(y0, y3);
double xmin = Math.min(x0, x3);
double ymin = Math.min(y0, y3);
r[0] = 3 * (y1 - y0);
r[1] = 6.0 * (y2 + y0 - 2 * y1);
r[2] = 3.0 * (y3 - 3 * y2 + 3 * y1 - y0);
int n = QuadCurve2D.solveQuadratic(r);
for (int i = 0; i < n; i++)
{
double t = r[i];
if (t > 0 && t < 1.0)
{
double y = evaluatePoint(t).getY();
ymax = Math.max(y, ymax);
ymin = Math.min(y, ymin);
}
}
r[0] = 3 * (x1 - x0);
r[1] = 6.0 * (x2 + x0 - 2 * x1);
r[2] = 3.0 * (x3 - 3 * x2 + 3 * x1 - x0);
n = QuadCurve2D.solveQuadratic(r);
for (int i = 0; i < n; i++)
{
double t = r[i];
if (t > 0 && t < 1.0)
{
double x = evaluatePoint(t).getX();
xmax = Math.max(x, xmax);
xmin = Math.min(x, xmin);
}
}
return (new Rectangle2D.Double(xmin, ymin, (xmax - xmin), (ymax - ymin)));
}
CubicCurve2D getCubicCurve2D()
{
return new CubicCurve2D.Double(P1.getX(), P1.getY(), cp1.getX(),
cp1.getY(), cp2.getX(), cp2.getY(),
P2.getX(), P2.getY());
}
double[] getLoop()
{
double x0 = P1.getX();
double y0 = P1.getY();
double x1 = cp1.getX();
double y1 = cp1.getY();
double x2 = cp2.getX();
double y2 = cp2.getY();
double x3 = P2.getX();
double y3 = P2.getY();
double[] r = new double[4];
double k;
double R;
double T;
double A;
double B;
double[] results = new double[2];
R = x3 - 3 * x2 + 3 * x1 - x0;
T = y3 - 3 * y2 + 3 * y1 - y0;
if (R == 0.0 && T == 0.0)
return null;
if (R != 0.0 && T != 0.0)
{
A = 3 * (x2 + x0 - 2 * x1) / R;
B = 3 * (x1 - x0) / R;
double P = 3 * (y2 + y0 - 2 * y1) / T;
double Q = 3 * (y1 - y0) / T;
if (A == P || Q == B)
return null;
k = (Q - B) / (A - P);
}
else
{
if (R == 0.0)
{
k = -(3 * (x1 - x0)) / (3 * (x2 + x0 - 2 * x1));
A = 3 * (y2 + y0 - 2 * y1) / T;
B = 3 * (y1 - y0) / T;
}
else
{
k = -(3 * (y1 - y0)) / (3 * (y2 + y0 - 2 * y1));
A = 3 * (x2 + x0 - 2 * x1) / R;
B = 3 * (x1 - x0) / R;
}
}
r[0] = -k * k * k - A * k * k - B * k;
r[1] = 3 * k * k + 2 * k * A + 2 * B;
r[2] = -3 * k;
r[3] = 2;
int n = CubicCurve2D.solveCubic(r);
if (n != 3)
return null;
double t;
for (int i = 0; i < 2; i++)
for (int j = i + 1; j < 3; j++)
if (r[j] < r[i])
{
t = r[i];
r[i] = r[j];
r[j] = t;
}
if (Math.abs(r[0] + r[2] - k) < 1E-13)
if (r[0] >= 0.0 && r[0] <= 1.0 && r[2] >= 0.0 && r[2] <= 1.0)
if (evaluatePoint(r[0]).distance(evaluatePoint(r[2])) < PE_EPSILON * 10)
{ results[0] = r[0];
results[1] = r[2];
return (results);
}
return null;
}
Point2D getMidPoint()
{
return evaluatePoint(0.5);
}
int getType()
{
return (PathIterator.SEG_CUBICTO);
}
int pathIteratorFormat(double[] coords)
{
coords[0] = cp1.getX();
coords[1] = cp1.getY();
coords[2] = cp2.getX();
coords[3] = cp2.getY();
coords[4] = P2.getX();
coords[5] = P2.getY();
return (PathIterator.SEG_CUBICTO);
}
int rayCrossing(double x, double y)
{
double x0 = P1.getX() - x;
double y0 = P1.getY() - y;
double x1 = cp1.getX() - x;
double y1 = cp1.getY() - y;
double x2 = cp2.getX() - x;
double y2 = cp2.getY() - y;
double x3 = P2.getX() - x;
double y3 = P2.getY() - y;
double[] r = new double[4];
int nRoots;
int nCrossings = 0;
if ((x0 > 0.0 || x1 > 0.0 || x2 > 0.0 || x3 > 0.0)
&& (y0 * y1 <= 0 || y1 * y2 <= 0 || y2 * y3 <= 0))
{
if (y0 == 0.0)
y0 -= EPSILON;
if (y3 == 0.0)
y3 -= EPSILON;
r[0] = y0;
r[1] = 3 * (y1 - y0);
r[2] = 3 * (y2 + y0 - 2 * y1);
r[3] = y3 - 3 * y2 + 3 * y1 - y0;
if ((nRoots = CubicCurve2D.solveCubic(r)) > 0)
for (int i = 0; i < nRoots; i++)
{
if (r[i] > 0.0 && r[i] < 1.0)
{
double t = r[i];
if (-(t * t * t) * (x0 - 3 * x1 + 3 * x2 - x3)
+ 3 * t * t * (x0 - 2 * x1 + x2) + 3 * t * (x1 - x0)
+ x0 > 0.0)
nCrossings++;
}
}
}
return nCrossings;
}
void reverseCoords()
{
Point2D p = P1;
P1 = P2;
P2 = p;
p = cp1; cp1 = cp2;
cp2 = p;
}
int splitIntersections(Segment b)
{
if (b instanceof LineSegment)
return (b.splitIntersections(this));
Intersection[] x = null;
if (b instanceof QuadSegment)
x = cubicCubicIntersect(this, ((QuadSegment) b).getCubicSegment());
if (b instanceof CubicSegment)
x = cubicCubicIntersect(this, (CubicSegment) b);
if (x == null)
return 0;
if (x.length == 1)
return createNode(b, x[0]);
return createNodes(b, x);
}
void subdivideInsert(double t)
{
CubicSegment s = (CubicSegment) clone();
double p1x = (s.cp1.getX() - s.P1.getX()) * t + s.P1.getX();
double p1y = (s.cp1.getY() - s.P1.getY()) * t + s.P1.getY();
double px = (s.cp2.getX() - s.cp1.getX()) * t + s.cp1.getX();
double py = (s.cp2.getY() - s.cp1.getY()) * t + s.cp1.getY();
s.cp2.setLocation((s.P2.getX() - s.cp2.getX()) * t + s.cp2.getX(),
(s.P2.getY() - s.cp2.getY()) * t + s.cp2.getY());
s.cp1.setLocation((s.cp2.getX() - px) * t + px,
(s.cp2.getY() - py) * t + py);
double p2x = (px - p1x) * t + p1x;
double p2y = (py - p1y) * t + p1y;
double p3x = (s.cp1.getX() - p2x) * t + p2x;
double p3y = (s.cp1.getY() - p2y) * t + p2y;
s.P1.setLocation(p3x, p3y);
insert(s);
cp1.setLocation(p1x, p1y);
cp2.setLocation(p2x, p2y);
P2 = s.P1;
next.node = node;
node = null;
}
void transform(AffineTransform at)
{
P1 = at.transform(P1, null);
P2 = at.transform(P2, null);
cp1 = at.transform(cp1, null);
cp2 = at.transform(cp2, null);
}
} }