public class Point2D implements GeometricObject2D, PointShape2D, Cloneable,
        CirculinearShape2D {

    // ===================================================================
    // class variables

    /** The x coordinate of this point. */
    protected double x;

    /** The y coordinate of this point. */
    protected double y;

    // ===================================================================
    // static methods

    /**
     * Static factory for creating a new point in cartesian coordinates.
     * 
     * @deprecated since 0.11.1
     */
    @Deprecated
    public static Point2D create(double x, double y) {
        return new Point2D(x, y);
    }


    /**
     * Static factory for creating a new point from an existing instance of
     * javageom point.
     * 
     * @since 0.10.0
     */
    public static Point2D create(Point2D point) {
        return new Point2D(point.x, point.y);
    }

    /**
     * Creates a new point from polar coordinates <code>rho</code> and
     * <code>theta</code>.
     */
    public static Point2D createPolar(double rho, double theta) {
        return new Point2D(rho * cos(theta), rho * sin(theta));
    }

    /**
     * Creates a new point from polar coordinates <code>rho</code> and
     * <code>theta</code>, from the given point.
     */
    public static Point2D createPolar(Point2D point, double rho, double theta) {
        return new Point2D(point.x + rho * cos(theta), point.y + rho
                * sin(theta));
    }

    /**
     * Creates a new point from polar coordinates <code>rho</code> and
     * <code>theta</code>, from the position (x0,y0).
     */
    public static Point2D createPolar(double x0, double y0, double rho,
            double theta) {
        return new Point2D(x0 + rho * cos(theta), y0 + rho * sin(theta));
    }

    /**
     * Computes the Euclidean distance between two points, given by their
     * coordinates. Uses robust computation (via Math.hypot() method).
     * 
     * @return the Euclidean distance between p1 and p2.
     */
    public static double distance(double x1, double y1, double x2, double y2) {
        return hypot(x2 - x1, y2 - y1);
    }

    /**
     * Computes the Euclidean distance between two points. Uses robust
     * computation (via Math.hypot() method).
     * 
     * @param p1
     *            the first point
     * @param p2
     *            the second point
     * @return the Euclidean distance between p1 and p2.
     */
    public static double distance(Point2D p1, Point2D p2) {
        return hypot(p1.x - p2.x, p1.y - p2.y);
    }

    /**
     * Tests if the three points are colinear.
     * 
     * @return true if three points lie on the same line.
     */
    public static boolean isColinear(Point2D p1, Point2D p2, Point2D p3) {
        double dx1, dx2, dy1, dy2;
        dx1 = p2.x - p1.x;
        dy1 = p2.y - p1.y;
        dx2 = p3.x - p1.x;
        dy2 = p3.y - p1.y;

        // tests if the two lines are parallel
        return Math.abs(dx1 * dy2 - dy1 * dx2) < Shape2D.ACCURACY;
    }

    /**
     * Computes the orientation of the 3 points: returns +1 is the path
     * P0->P1->P2 turns Counter-Clockwise, -1 if the path turns Clockwise, and 0
     * if the point P2 is located on the line segment [P0 P1]. Algorithm taken
     * from Sedgewick.
     * 
     * @param p0
     *            the initial point
     * @param p1
     *            the middle point
     * @param p2
     *            the last point
     * @return +1, 0 or -1, depending on the relative position of the points
     */
    public static int ccw(Point2D p0, Point2D p1, Point2D p2) {
        double x0 = p0.x;
        double y0 = p0.y;
        double dx1 = p1.x - x0;
        double dy1 = p1.y - y0;
        double dx2 = p2.x - x0;
        double dy2 = p2.y - y0;

        if (dx1 * dy2 > dy1 * dx2)
            return +1;
        if (dx1 * dy2 < dy1 * dx2)
            return -1;
        if ((dx1 * dx2 < 0) || (dy1 * dy2 < 0))
            return -1;
        if (hypot(dx1, dy1) < hypot(dx2, dy2))
            return +1;
        return 0;
    }

    public static Point2D midPoint(Point2D p1, Point2D p2) {
        return new Point2D((p1.x + p2.x) / 2, (p1.y + p2.y) / 2);
    }

    /**
     * Computes the centroid, or center of mass, of an array of points.
     * 
     * @param points
     *            an array of points
     * @return the centroid of the points
     */
    public static Point2D centroid(Point2D[] points) {
        int n = points.length;
        double sx = 0, sy = 0;
        for (int i = 0; i < n; i++) {
            sx += points[i].x;
            sy += points[i].y;
        }
        return new Point2D(sx / n, sy / n);
    }

    /**
     * Computes the weighted centroid, or center of mass, of an array of points.
     * 
     * @param points
     *            an array of points
     * @param weights
     *            an array of weights the same size as points
     * @return the centroid of the points
     */
    public static Point2D centroid(Point2D[] points, double[] weights) {
        // number of points
        int n = points.length;

        // check size of second array
        if (n != weights.length) {
            throw new RuntimeException("Arrays must have the same size");
        }

        // sum up weighted coordinates
        double sx = 0, sy = 0, sw = 0;
        double w;
        for (int i = 0; i < n; i++) {
            w = weights[i];
            sx += points[i].x * w;
            sy += points[i].y * w;
            sw += w;
        }

        // compute weighted average of each coordinate
        return new Point2D(sx / sw, sy / sw);
    }

    /**
     * Computes the centroid, or center of mass, of a collection of points.
     * 
     * @param points
     *            a collection of points
     * @return the centroid of the points
     */
    public static Point2D centroid(Collection<? extends Point2D> points) {
        int n = points.size();
        double sx = 0, sy = 0;
        for (Point2D point : points) {
            sx += point.x;
            sy += point.y;
        }
        return new Point2D(sx / n, sy / n);
    }

    /**
     * Computes the centroid of three points.
     * 
     * @param pt1
     *            the first point
     * @param pt2
     *            the second point
     * @param pt3
     *            the third point
     * @return the centroid of the 3 points
     */
    public static Point2D centroid(Point2D pt1, Point2D pt2, Point2D pt3) {
        return new Point2D((pt1.x + pt2.x + pt3.x) / 3,
                (pt1.y + pt2.y + pt3.y) / 3);
    }

    // ===================================================================
    // class variables

    // coordinates are inherited from java class for Point

    // ===================================================================
    // constructors

    /** Constructs a new Point2D at position (0,0). */
    public Point2D() {
    }

    /**
     * Constructs a new Point2D at the given given position.
     */
    public Point2D(double x, double y) {
        this.x = x;
        this.y = y;
    }

    /**
     * Constructs a new Point2D by copying coordinates of given java point.
     */
    public Point2D(Point point) {
        this(point.x, point.y);
    }

    /**
     * Constructs a new Point2D by copying coordinates of given point.
     * 
     * @deprecated immutable objects do not need copy constructor (0.11.2)
     */
    @Deprecated
    public Point2D(Point2D point) {
        this(point.x, point.y);
    }

    // ===================================================================
    // Methods specific to Point2D

    /**
     * Adds the coordinates of the given point to the coordinates of this point.
     */
    public Point2D plus(Point2D p) {
        return new Point2D(this.x + p.x, this.y + p.y);
    }

    /**
     * Adds the coordinates of the given vector to the coordinates of this
     * point.
     */
    public Point2D plus(Vector2D v) {
        return new Point2D(this.x + v.x, this.y + v.y);
    }

    /**
     * Removes the coordinates of the given point from the coordinates of this
     * point.
     */
    public Point2D minus(Point2D p) {
        return new Point2D(this.x - p.x, this.y - p.y);
    }

    /**
     * Removes the coordinates of the given vector from the coordinates of this
     * point.
     */
    public Point2D minus(Vector2D v) {
        return new Point2D(this.x - v.x, this.y - v.y);
    }

    /**
     * Returns the new point translated by amount given in each direction.
     * 
     * @param tx
     *            the translation in x direction
     * @param ty
     *            the translation in y direction
     * @return the translated point
     */
    public Point2D translate(double tx, double ty) {
        return new Point2D(this.x + tx, this.y + ty);
    }

    /**
     * Returns the new point scaled by amount given in each direction.
     * 
     * @param kx
     *            the scale factor in x direction
     * @param ky
     *            the scale factor in y direction
     * @return the scaled point
     */
    public Point2D scale(double kx, double ky) {
        return new Point2D(this.x * kx, this.y * ky);
    }

    /**
     * Returns the new point scaled by the same amount in each direction.
     * 
     * @param k
     *            the scale factor
     * @return the scaled point
     */
    public Point2D scale(double k) {
        return new Point2D(this.x * k, this.y * k);
    }

    /**
     * Rotates the point by a given angle around the origin.
     * 
     * @param theta
     *            the angle of rotation, in radians
     * @return the rotated point.
     */
    public Point2D rotate(double theta) {
        double cot = cos(theta);
        double sit = sin(theta);
        return new Point2D(x * cot - y * sit, x * sit + y * cot);
    }

    /**
     * Rotates the point by a given angle around an arbitrary center.
     * 
     * @param center
     *            the center of the rotation
     * @param theta
     *            the angle of rotation, in radians
     * @return the rotated point.
     */
    public Point2D rotate(Point2D center, double theta) {
        double cx = center.x;
        double cy = center.y;
        double cot = cos(theta);
        double sit = sin(theta);
        return new Point2D(x * cot - y * sit + (1 - cot) * cx + sit * cy, x
                * sit + y * cot + (1 - cot) * cy - sit * cx);
    }

    // ===================================================================
    // Methods specific to Point2D

    /**
     * Converts point to an integer version. Coordinates are rounded to the
     * nearest integer.
     * 
     * @return an instance of java.awt.Point
     */
    public Point getAsInt() {
        return new Point((int) x, (int) y);
    }

    // ===================================================================
    // Getter and setter

    /**
     * Returns the x-coordinate of this point.
     */
    public double x() {
        return x;
    }

    /**
	 */
    public double getX() {
        return this.x;
    }

    /**
     * Returns the y-coordinate of this point.
     */
    public double y() {
        return y;
    }

    /**
     * Returns the y-coordinate of this point.
     */
    public double getY() {
        return y;
    }

    // ===================================================================
    // Methods implementing CirculinearShape2D interface

    /*
     * (non-Javadoc)
     * 
     * @see math.geom2d.circulinear.CirculinearShape2D#buffer(double)
     */
    public CirculinearDomain2D buffer(double dist) {
        return new GenericCirculinearDomain2D(new Circle2D(this,
                Math.abs(dist), dist > 0));
    }

    /*
     * (non-Javadoc)
     * 
     * @see
     * math.geom2d.circulinear.CirculinearShape2D#transform(CircleInversion2D)
     */
    public Point2D transform(CircleInversion2D inv) {
        // get inversion parameters
        Point2D center = inv.center();
        double r = inv.radius();

        // compute distance and angle of transformed point
        double d = r * r / Point2D.distance(this, center);
        double theta = Angle2D.horizontalAngle(center, this);

        // create the new point
        return Point2D.createPolar(center, d, theta);
    }

    // ===================================================================
    // Methods implementing the PointShape2D interface

    /*
     * (non-Javadoc)
     * 
     * @see math.geom2d.point.PointShape2D#size()
     */
    public int size() {
        return 1;
    }

    /*
     * (non-Javadoc)
     * 
     * @see math.geom2d.point.PointShape2D#points()
     */
    public Collection<Point2D> points() {
        ArrayList<Point2D> array = new ArrayList<Point2D>(1);
        array.add(this);
        return array;
    }

    // ===================================================================
    // Methods implementing Shape2D interface

    /**
     * Computes the distance between this and the point <code>point</code>.
     */
    public double distance(Point2D point) {
        return distance(point.x, point.y);
    }

    /**
     * Computes the distance between current point and point with coordinate
     * <code>(x,y)</code>. Uses the <code>Math.hypot()</code> function for
     * better robustness than simple square root.
     */
    public double distance(double x, double y) {
        return hypot(this.x - x, this.y - y);
    }

    /**
     * Returns true if the point is bounded. A point is unbounded if at least
     * one of its coordinates is infinite or NaN.
     * 
     * @return true if both coordinates of the point are finite
     */
    public boolean isBounded() {
        if (java.lang.Double.isInfinite(this.x))
            return false;
        if (java.lang.Double.isInfinite(this.y))
            return false;
        if (java.lang.Double.isNaN(this.x))
            return false;
        if (java.lang.Double.isNaN(this.y))
            return false;
        return true;
    }

    /**
     * Returns false, as a point can not be empty.
     */
    public boolean isEmpty() {
        return false;
    }

    /**
     * Returns true if the two points are equal.
     */
    public boolean contains(double x, double y) {
        return this.equals(new Point2D(x, y));
    }

    /**
     * Returns true if the two points are equal.
     */
    public boolean contains(Point2D p) {
        return this.equals(p);
    }

    /**
     * Returns a PointSet2D, containing 0 or 1 point, depending on whether the
     * point lies inside the specified box.
     */
    public PointSet2D clip(Box2D box) {
        // init result array
        PointSet2D set = new PointArray2D(0);

        // return empty array if point is clipped
        if (x < box.getMinX())
            return set;
        if (y < box.getMinY())
            return set;
        if (x > box.getMaxX())
            return set;
        if (y > box.getMaxY())
            return set;

        // return an array with the point
        set.add(this);
        return set;
    }

    /**
     * Returns a bounding box with zero width and zero height, whose coordinates
     * limits are point coordinates.
     */
    public Box2D boundingBox() {
        return new Box2D(x, x, y, y);
    }

    /**
     * Returns the transformed point.
     */
    public Point2D transform(AffineTransform2D trans) {
        double[] tab = trans.coefficients();
        return new Point2D(x * tab[0] + y * tab[1] + tab[2], x * tab[3] + y
                * tab[4] + tab[5]);
    }

    // ===================================================================
    // Graphical methods


    /**
     * Draws the point on the specified Graphics2D, by filling a disc with a
     * given radius.
     * 
     * @param g2
     *            the graphics to draw the point
     */
    public void draw(Canvas g2, Paint p) {
        g2.drawPoint((float) x, (float) y, p);
    }

    // ===================================================================
    // methods implementing the GeometricObject2D interface

    /**
     * Test whether this object is the same as another point, with respect to a
     * given threshold along each coordinate.
     */
    public boolean almostEquals(GeometricObject2D obj, double eps) {
        if (this == obj)
            return true;

        if (!(obj instanceof Point2D))
            return false;
        Point2D p = (Point2D) obj;

        if (Math.abs(this.x - p.x) > eps)
            return false;
        if (Math.abs(this.y - p.y) > eps)
            return false;

        return true;
    }

    // ===================================================================
    // methods implementing the Iterable interface

    /*
     * (non-Javadoc)
     * 
     * @see java.lang.Iterable#iterator()
     */
    public Iterator<Point2D> iterator() {
        return this.points().iterator();
    }

    // ===================================================================
    // Override of Object methods

    @Override
    public String toString() {
        return new String("Point2D(" + x + ", " + y + ")");
    }

    /**
     * Two points are considered equal if their Euclidean distance is less than
     * Shape2D.ACCURACY.
     */
    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;

        if (!(obj instanceof Point2D))
            return false;
        Point2D that = (Point2D) obj;

        // Compare each field
        if (!EqualUtils.areEqual(this.x, that.x))
            return false;
        if (!EqualUtils.areEqual(this.y, that.y))
            return false;

        return true;
    }

    /**
     * @deprecated not necessary to clone immutable objects (0.11.2)
     */
    @Deprecated
    @Override
    public Point2D clone() {
        return new Point2D(x, y);
    }
}
 public interface Shape2D extends GeometricObject2D {

    // ===================================================================
    // constants

    /**
     * The constant used for testing results.
     */
    public final static double  ACCURACY  = 1e-12;

    /**
     * Checks if the shape contains the planar point defined by (x,y).
     */
    public abstract boolean contains(double x, double y);

    /**
     * Checks if the shape contains the given point.
     */
    public abstract boolean contains(Point2D p);

    /**
     * Returns the distance of the shape to the given point, or the distance of
     * point to the frontier of the shape in the case of a plain shape.
     */
    public abstract double distance(Point2D p);

    /**
     * Returns the distance of the shape to the given point, specified by x and
     * y, or the distance of point to the frontier of the shape in the case of
     * a plain (i.e. fillable) shape.
     */
    public abstract double distance(double x, double y);

    /**
     * Returns true if the shape is bounded, that is if we can draw a finite
     * rectangle enclosing the shape. For example, a straight line or a parabola
     * are not bounded.
     */
    public abstract boolean isBounded();

    /**
     * Returns true if the shape does not contain any point. This is the case
     * for example for PointSet2D without any point.
     * 
     * @return true if the shape does not contain any point.
     */
    public abstract boolean isEmpty();

    /**
     * Returns the bounding box of the shape.
     * 
     * @return the bounding box of the shape.
     */
    public abstract Box2D boundingBox();

    /**
     * Clip the shape with the given box, and returns a new shape. The box must
     * be bounded.
     * 
     * @param box the clipping box
     * @return the clipped shape
     */
    public abstract Shape2D clip(Box2D box);

    /**
     * Transforms the shape by an affine transform. Subclasses may override the
     * type of returned shape.
     * 
     * @param trans an affine transform
     * @return the transformed shape
     */
    public abstract Shape2D transform(AffineTransform2D trans);

    /**
     * Draws the shape on the given graphics. 
     * If the shape is empty, nothing is drawn.
     * If the shape is unbounded, an exception is thrown.
     */
    public abstract void draw(Canvas c, Paint p);
}
 public class BoundaryPolyCirculinearCurve2D<T extends CirculinearContinuousCurve2D>
        extends PolyCirculinearCurve2D<T> implements
        CirculinearContinuousCurve2D, CirculinearContour2D {

    // ===================================================================
    // static methods



    // ===================================================================
    // constructors

    public BoundaryPolyCirculinearCurve2D() {
        super();
    }

    public BoundaryPolyCirculinearCurve2D(int size) {
        super(size);
    }

    public BoundaryPolyCirculinearCurve2D(T[] curves) {
        super(curves);
    }

    public BoundaryPolyCirculinearCurve2D(T[] curves, boolean closed) {
        super(curves, closed);
    }

    public BoundaryPolyCirculinearCurve2D(Collection<? extends T> curves) {
        super(curves);
    }

    public BoundaryPolyCirculinearCurve2D(Collection<? extends T> curves,
            boolean closed) {
        super(curves, closed);
    }

    // ===================================================================
    // methods implementing the CirculinearCurve2D interface

    /*
     * (non-Javadoc)
     * 
     * @see math.geom2d.circulinear.CirculinearCurve2D#length()
     */
    @Override
    public double length() {
        double sum = 0;
        for (CirculinearCurve2D curve : this.curves())
            sum += curve.length();
        return sum;
    }

    /*
     * (non-Javadoc)
     * 
     * @see math.geom2d.circulinear.CirculinearCurve2D#length(double)
     */
    @Override
    public double length(double pos) {
        return CirculinearCurves2D.getLength(this, pos);
    }

    /*
     * (non-Javadoc)
     * 
     * @see math.geom2d.circulinear.CirculinearCurve2D#position(double)
     */
    @Override
    public double position(double length) {
        return CirculinearCurves2D.getPosition(this, length);
    }

    /*
     * (non-Javadoc)
     * 
     * @see
     * math.geom2d.circulinear.CirculinearContinuousCurve2D#parallel(double)
     */
    @Override
    public CirculinearRing2D parallel(double dist) {
        BufferCalculator bc = BufferCalculator.getDefaultInstance();

        return new GenericCirculinearRing2D(bc.createContinuousParallel(
                this, dist).smoothPieces());
    }

    /*
     * (non-Javadoc)
     * 
     * @see
     * math.geom2d.circulinear.CirculinearCurve2D#transform(math.geom2d.transform
     * .CircleInversion2D)
     */
    @Override
    public BoundaryPolyCirculinearCurve2D<? extends CirculinearContinuousCurve2D> transform(
            CircleInversion2D inv) {
        // Allocate array for result
        int n = curves.size();
        BoundaryPolyCirculinearCurve2D<CirculinearContinuousCurve2D> result = new BoundaryPolyCirculinearCurve2D<CirculinearContinuousCurve2D>(
                n);

        // add each transformed curve
        for (CirculinearContinuousCurve2D curve : curves)
            result.add(curve.transform(inv));
        return result;
    }

    // ===================================================================
    // methods implementing the Boundary2D interface

    /*
     * (non-Javadoc)
     * 
     * @see math.geom2d.domain.Boundary2D#domain()
     */
    public CirculinearDomain2D domain() {
        return new GenericCirculinearDomain2D(this);
    }

    // ===================================================================
    // methods implementing the ContinuousCurve2D interface

    /*
     * (non-Javadoc)
     * 
     * @see math.geom2d.CirculinearContinuousCurve2D#smoothPieces()
     */
    @Override
    public Collection<? extends CirculinearElement2D> smoothPieces() {
        // create array for storing result
        ArrayList<CirculinearElement2D> result = new ArrayList<CirculinearElement2D>();

        // add elements of each curve
        for (CirculinearContinuousCurve2D curve : curves)
            result.addAll(curve.smoothPieces());

        // return the collection
        return result;
    }

    // ===================================================================
    // methods implementing the Curve2D interface

    @Override
    public Collection<? extends BoundaryPolyCirculinearCurve2D<?>> continuousCurves() {
        return wrapCurve(this);
    }

    @Override
    public BoundaryPolyCirculinearCurve2D<? extends CirculinearContinuousCurve2D> reverse() {
        int n = curves.size();
        // create array of reversed curves
        CirculinearContinuousCurve2D[] curves2 = new CirculinearContinuousCurve2D[n];

        // reverse each curve
        for (int i = 0; i < n; i++)
            curves2[i] = curves.get(n - 1 - i).reverse();

        // create the reversed final curve
        return new BoundaryPolyCirculinearCurve2D<CirculinearContinuousCurve2D>(
                curves2);
    }

    @Override
    public PolyCirculinearCurve2D<? extends CirculinearContinuousCurve2D> subCurve(
            double t0, double t1) {
        // Call the superclass method
        PolyOrientedCurve2D<? extends ContinuousOrientedCurve2D> subcurve = super
                .subCurve(t0, t1);

        // prepare result
        int n = subcurve.size();
        PolyCirculinearCurve2D<CirculinearContinuousCurve2D> result = new PolyCirculinearCurve2D<CirculinearContinuousCurve2D>(
                n);

        // add each curve after class cast
        for (Curve2D curve : subcurve) {
            if (curve instanceof CirculinearContinuousCurve2D)
                result.add((CirculinearContinuousCurve2D) curve);
        }

        // return the result
        return result;
    }

    // ===================================================================
    // methods implementing the Shape2D interface

    @Override
    public CirculinearCurveSet2D<? extends CirculinearContinuousCurve2D> clip(
            Box2D box) {
        // Clip the curve
        CurveSet2D<? extends Curve2D> set = Curves2D.clipCurve(this, box);

        // Stores the result in appropriate structure
        int n = set.size();
        CirculinearCurveArray2D<CirculinearContinuousCurve2D> result = new CirculinearCurveArray2D<CirculinearContinuousCurve2D>(
                n);

        // convert the result, class cast each curve
        for (Curve2D curve : set.curves()) {
            if (curve instanceof CirculinearContinuousCurve2D)
                result.add((CirculinearContinuousCurve2D) curve);
        }

        // return the new set of curves
        return result;
    }

    @Override
    public BoundaryPolyCurve2D<? extends ContinuousOrientedCurve2D> transform(
            AffineTransform2D trans) {
        // number of curves
        int n = this.size();

        // create result curve
        BoundaryPolyCurve2D<ContinuousOrientedCurve2D> result = new BoundaryPolyCurve2D<ContinuousOrientedCurve2D>(
                n);

        // add each curve after class cast
        for (ContinuousOrientedCurve2D curve : curves)
            result.add(curve.transform(trans));

        result.setClosed(this.isClosed());
        return result;
    }

} public class CirculinearContourArray2D<T extends CirculinearContour2D> 
extends ContourArray2D<T> implements CirculinearBoundary2D {

    // ===================================================================
    // static constructors

    /**
     * Static factory for creating a new CirculinearContourArray2D from a
     * collection of curves.
     * @since 0.8.1
     */
	//public static <T extends CirculinearContour2D> 
	//CirculinearContourArray2D<T> create(Collection<T> curves) {
   //return new CirculinearContourArray2D<T>(curves);
	//}

    /**
     * Static factory for creating a new CirculinearContourArray2D from an 
     * array of curves.
     * @since 0.8.1
     */
    public static <T extends CirculinearContour2D> 
    CirculinearContourArray2D<T> create(T... curves) {
    	return new CirculinearContourArray2D<T>(curves);
    }

    

    // ===================================================================
    // constructors

	/**
     * Empty constructor. Initializes an empty array of curves.
     */
    public CirculinearContourArray2D() {
    	this.curves = new ArrayList<T>();
    }

    /**
     * Empty constructor. Initializes an empty array of curves, 
     * with a given size for allocating memory.
     */
    public CirculinearContourArray2D(int n) {
    	this.curves = new ArrayList<T>(n);
    }

    /**
     * Constructor from an array of curves.
     * 
     * @param curves the array of curves in the set
     */
    public CirculinearContourArray2D(T... curves) {
    	this.curves = new ArrayList<T>(curves.length);
        for (T element : curves)
            this.add(element);
    }

    /**
     * Constructor from a single curve.
     * 
     * @param curve the initial contour contained in the array
     */
    public CirculinearContourArray2D(T curve) {
    	this.curves = new ArrayList<T>();
        this.curves.add(curve);
    }

    /**
     * Constructor from a collection of curves. The curves are added to the
     * inner collection of curves.
     * 
     * @param curves the collection of curves to add to the set
     */
    public CirculinearContourArray2D(Collection<? extends T> curves) {
    	this.curves = new ArrayList<T>(curves.size());
        this.curves.addAll(curves);
    }

    
    // ===================================================================
    // methods specific to Boundary2D interface

	/* (non-Javadoc)
	 * @see math.geom2d.domain.Boundary2D#domain()
	 */
    public CirculinearDomain2D domain() {
        return new GenericCirculinearDomain2D(this);
    }

    
    // ===================================================================
    // methods implementing the CirculinearCurve2D interface

	/* (non-Javadoc)
	 * @see math.geom2d.circulinear.CirculinearCurve2D#length()
	 */
	public double length() {
		double sum = 0;
		for(CirculinearCurve2D curve : this.curves())
			sum += curve.length();
		return sum;
	}

	/* (non-Javadoc)
	 * @see math.geom2d.circulinear.CirculinearCurve2D#length(double)
	 */
	public double length(double pos) {
		return CirculinearCurves2D.getLength(this, pos);
	}

	/* (non-Javadoc)
	 * @see math.geom2d.circulinear.CirculinearCurve2D#position(double)
	 */
	public double position(double length) {
		return CirculinearCurves2D.getPosition(this, length);
	}

	/* (non-Javadoc)
	 * @see math.geom2d.circulinear.CirculinearShape2D#buffer(double)
	 */
	public CirculinearDomain2D buffer(double dist) {
		BufferCalculator bc = BufferCalculator.getDefaultInstance();
		return bc.computeBuffer(this, dist);
	}

	/* (non-Javadoc)
	 * @see math.geom2d.circulinear.CirculinearContinuousCurve2D#parallel(double)
	 */
	public CirculinearBoundary2D parallel(double d) {
		BufferCalculator bc = BufferCalculator.getDefaultInstance();
		return bc.createParallelBoundary(this, d);
	}
	
	/* (non-Javadoc)
	 * @see math.geom2d.circulinear.CirculinearCurve2D#transform(math.geom2d.transform.CircleInversion2D)
	 */
	public CirculinearContourArray2D<? extends CirculinearContour2D> 
	transform(CircleInversion2D inv) {
    	// Allocate array for result
		CirculinearContourArray2D<CirculinearContour2D> result = 
			new CirculinearContourArray2D<CirculinearContour2D>(
					curves.size());
        
        // add each transformed curve
        for (CirculinearContour2D curve : curves)
            result.add(curve.transform(inv));
        return result;
	}
	
    // ===================================================================
    // methods implementing the Curve2D interface

   
    @Override
    public Collection<T> continuousCurves() {
    	return Collections.unmodifiableCollection(this.curves);
    }

	@Override
	public CirculinearCurveSet2D<? extends CirculinearContinuousCurve2D> clip(
			Box2D box) {
        // Clip the curve
        CurveSet2D<? extends Curve2D> set = Curves2D.clipCurve(this, box);

        // Stores the result in appropriate structure
        int n = set.size();
        CirculinearCurveArray2D<CirculinearContinuousCurve2D> result = 
        	new CirculinearCurveArray2D<CirculinearContinuousCurve2D>(n);

        // convert the result, class cast each curve
        for (Curve2D curve : set.curves()) {
            if (curve instanceof CirculinearContinuousCurve2D)
                result.add((CirculinearContinuousCurve2D) curve);
        }
        
        // return the new set of curves
        return result;
	}
    
	@Override
	public CirculinearContourArray2D<? extends CirculinearContour2D>
	reverse(){
    	int n = curves.size();
        // create array of reversed curves
    	CirculinearContour2D[] curves2 = new CirculinearContour2D[n];
        
        // reverse each curve
        for (int i = 0; i<n; i++)
            curves2[i] = curves.get(n-1-i).reverse();
        
        // create the reversed final curve
        return new CirculinearContourArray2D<CirculinearContour2D>(curves2);
	}
	
    @Override
    public CirculinearCurveSet2D<? extends CirculinearContinuousCurve2D> subCurve(
            double t0, double t1) {
        // get the subcurve
    	CurveSet2D<? extends ContinuousOrientedCurve2D> curveSet =
    		super.subCurve(t0, t1);

        // create subcurve array
        ArrayList<CirculinearContinuousCurve2D> curves = 
        	new ArrayList<CirculinearContinuousCurve2D>(
        			curveSet.size());
        
        // class cast each curve
        for (Curve2D curve : curveSet.curves())
            curves.add((CirculinearContinuousCurve2D) curve);

        // Create CurveSet for the result
        return  new CirculinearCurveArray2D(curves);
    }
}
 public class CirculinearCurveArray2D<T extends CirculinearCurve2D> extends
        CurveArray2D<T> implements CirculinearCurveSet2D<T> {

    // ===================================================================
    // static constructors

    // ===================================================================
    // constructors

    /**
     * Empty constructor. Initializes an empty array of curves.
     */
    public CirculinearCurveArray2D() {
        this.curves = new ArrayList<T>();
    }

    /**
     * Empty constructor. Initializes an empty array of curves, with a given
     * size for allocating memory.
     */
    public CirculinearCurveArray2D(int n) {
        this.curves = new ArrayList<T>(n);
    }

    /**
     * Constructor from an array of curves.
     * 
     * @param curves
     *            the array of curves in the set
     */
    public CirculinearCurveArray2D(T... curves) {
        this.curves = new ArrayList<T>(curves.length);
        for (T element : curves)
            this.add(element);
    }

    /**
     * Constructor from a collection of curves. The curves are added to the
     * inner collection of curves.
     * 
     * @param curves
     *            the collection of curves to add to the set
     */
    public CirculinearCurveArray2D(Collection<? extends T> curves) {
        this.curves = new ArrayList<T>(curves.size());
        this.curves.addAll(curves);
    }

    // ===================================================================
    // methods implementing the CirculinearCurve2D interface

    /*
     * (non-Javadoc)
     * 
     * @see math.geom2d.circulinear.CirculinearCurve2D#length()
     */
    public double length() {
        double sum = 0;
        for (CirculinearCurve2D curve : this.curves())
            sum += curve.length();
        return sum;
    }

    /*
     * (non-Javadoc)
     * 
     * @see math.geom2d.circulinear.CirculinearCurve2D#length(double)
     */
    public double length(double pos) {
        return CirculinearCurves2D.getLength(this, pos);
    }

    /*
     * (non-Javadoc)
     * 
     * @see math.geom2d.circulinear.CirculinearCurve2D#position(double)
     */
    public double position(double length) {
        return CirculinearCurves2D.getPosition(this, length);
    }

    /*
     * (non-Javadoc)
     * 
     * @see math.geom2d.circulinear.CirculinearShape2D#buffer(double)
     */
    public CirculinearDomain2D buffer(double dist) {
        BufferCalculator bc = BufferCalculator.getDefaultInstance();
        return bc.computeBuffer(this, dist);
    }

    /*
     * (non-Javadoc)
     * 
     * @see
     * math.geom2d.circulinear.CirculinearContinuousCurve2D#parallel(double)
     */
    public CirculinearCurve2D parallel(double d) {
        BufferCalculator bc = BufferCalculator.getDefaultInstance();
        return bc.createParallel(this, d);
    }

    /*
     * (non-Javadoc)
     * 
     * @see
     * math.geom2d.circulinear.CirculinearCurve2D#transform(math.geom2d.transform
     * .CircleInversion2D)
     */
    public CirculinearCurveArray2D<CirculinearCurve2D> transform(
            CircleInversion2D inv) {
        // Allocate array for result
        CirculinearCurveArray2D<CirculinearCurve2D> result = new CirculinearCurveArray2D<CirculinearCurve2D>(
                curves.size());

        // add each transformed curve
        for (CirculinearCurve2D curve : curves)
            result.add(curve.transform(inv));
        return result;
    }

    // ===================================================================
    // methods implementing the Curve2D interface

    @Override
    public Collection<? extends CirculinearContinuousCurve2D> continuousCurves() {
        // create array for storing result
        ArrayList<CirculinearContinuousCurve2D> result = new ArrayList<CirculinearContinuousCurve2D>();

        // iterate on curves, and extract each set of continuous curves
        for (CirculinearCurve2D curve : curves)
            result.addAll(curve.continuousCurves());

        // return the set of curves
        return result;
    }

    @Override
    public CirculinearCurveArray2D<? extends CirculinearCurve2D> clip(Box2D box) {
        // Clip the curve
        CurveSet2D<? extends Curve2D> set = Curves2D.clipCurve(this, box);

        // Stores the result in appropriate structure
        int n = set.size();
        CirculinearCurveArray2D<CirculinearCurve2D> result = new CirculinearCurveArray2D<CirculinearCurve2D>(
                n);

        // convert the result, class cast each curve
        for (Curve2D curve : set.curves()) {
            if (curve instanceof CirculinearCurve2D)
                result.add((CirculinearCurve2D) curve);
        }

        // return the new set of curves
        return result;
    }

    @Override
    public CirculinearCurveArray2D<? extends CirculinearCurve2D> subCurve(
            double t0, double t1) {
        // Call the superclass method
        CurveSet2D<? extends Curve2D> subcurve = super.subCurve(t0, t1);

        // prepare result
        CirculinearCurveArray2D<CirculinearCurve2D> result = new CirculinearCurveArray2D<CirculinearCurve2D>(
                subcurve.size());

        // add each curve after class,cast
        for (Curve2D curve : subcurve) {
            if (curve instanceof CirculinearCurve2D)
                result.add((CirculinearCurve2D) curve);
            else
                System.err
                        .println("CirculinearCurveArray2D.getSubCurve: error in class cast");
        }

        // return the result
        return result;
    }

    @Override
    public CirculinearCurveArray2D<? extends CirculinearCurve2D> reverse() {
        int n = curves.size();
        // create array of reversed curves
        CirculinearCurve2D[] curves2 = new CirculinearCurve2D[n];

        // reverse each curve
        for (int i = 0; i < n; i++)
            curves2[i] = curves.get(n - 1 - i).reverse();

        // create the reversed final curve
        return new CirculinearCurveArray2D<CirculinearCurve2D>(curves2);
    }
}
 @TargetApi(Build.VERSION_CODES.GINGERBREAD)
public class CirculinearCurves2D {

	/**
	 * Converts a curve to a circulinear curve, by concatenating all elements of
	 * the curve to the appropriate circulinear curve type. If the curve
	 * contains one or more non-circulinear smooth curve, a
	 * NonCirculinearClassException is thrown.
	 */
	public static CirculinearCurve2D convert(Curve2D curve) {
		// first check type, to avoid unnecessary computations
		if (curve instanceof CirculinearCurve2D)
			return (CirculinearCurve2D) curve;

		// If the curve is continuous, creates a CirculinearContinuousCurve2D
		if (curve instanceof ContinuousCurve2D) {
			// extract smooth pieces
			ContinuousCurve2D continuous = (ContinuousCurve2D) curve;
			Collection<? extends SmoothCurve2D> smoothPieces = 
				continuous.smoothPieces();

			// prepare array of elements
			ArrayList<CirculinearElement2D> elements = new ArrayList<CirculinearElement2D>(
					smoothPieces.size());

			// class cast for each element, or throw an exception
			for (SmoothCurve2D smooth : smoothPieces) {
				if (smooth instanceof CirculinearElement2D)
					elements.add((CirculinearElement2D) smooth);
				else
					throw new NonCirculinearClassException(smooth);
			}

			// create the resulting CirculinearContinuousCurve2D
			return new PolyCirculinearCurve2D<CirculinearElement2D>(elements);
		}

		// If the curve is continuous, creates a CirculinearContinuousCurve2D
		if (curve instanceof CurveSet2D<?>) {
			// extract smooth pieces
			CurveSet2D<?> set = (CurveSet2D<?>) curve;
			Collection<? extends ContinuousCurve2D> continuousCurves = set
					.continuousCurves();

			// prepare array of elements
			ArrayList<CirculinearContinuousCurve2D> curves = 
				new ArrayList<CirculinearContinuousCurve2D>(continuousCurves.size());

			// class cast for each element, or throw an exception
			for (ContinuousCurve2D continuous : continuousCurves) {
				if (continuous instanceof CirculinearContinuousCurve2D)
					curves.add((CirculinearContinuousCurve2D) continuous);
				else
					curves.add((CirculinearContinuousCurve2D) convert(continuous));
			}

			// create the resulting CirculinearContinuousCurve2D
			return new CirculinearCurveArray2D(curves);
		}

		//TODO: throw exception ?
		return null;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see math.geom2d.circulinear.CirculinearCurve2D#length(double)
	 */
	public static double getLength(
			CurveSet2D<? extends CirculinearCurve2D> curve, double pos) {
		// init
		double length = 0;

		// add length of each curve before current curve
		int index = curve.curveIndex(pos);
		for (int i = 0; i < index; i++)
			length += curve.get(i).length();

		// add portion of length for last curve
		if (index < curve.size()) {
			double pos2 = curve.localPosition(pos - 2 * index);
			length += curve.get(index).length(pos2);
		}

		// return result
		return length;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see math.geom2d.circulinear.CirculinearCurve2D#position(double)
	 */
	public static double getPosition(
			CurveSet2D<? extends CirculinearCurve2D> curveSet, double length) {

		// position to compute
		double pos = 0;

		// index of current curve
		int index = 0;

		// cumulative length
		double cumLength = getLength(curveSet, curveSet.t0());

		// iterate on all curves
		for (CirculinearCurve2D curve : curveSet.curves()) {
			// length of current curve
			double curveLength = curve.length();

			// add either 2, or fraction of length
			if (cumLength + curveLength < length) {
				cumLength += curveLength;
				index++;
			} else {
				// add local position on current curve
				double pos2 = curve.position(length - cumLength);
				pos = curveSet.globalPosition(index, pos2);
				break;
			}
		}

		// return the result
		return pos;
	}

	/**
	 * Computes intersection point of a single curve, by iterating on pair of
	 * Circulinear elements composing the curve.
	 * 
	 * @return the set of self-intersection points
	 */
	public static Collection<Point2D> findSelfIntersections(
			CirculinearCurve2D curve) {

		// create array of circulinear elements
		ArrayList<CirculinearElement2D> elements = new ArrayList<CirculinearElement2D>();

		// extract all circulinear elements of the curve
		for (CirculinearContinuousCurve2D cont : curve.continuousCurves())
			elements.addAll(cont.smoothPieces());

		// create array for storing result
		ArrayList<Point2D> result = new ArrayList<Point2D>(0);

		// iterate on each couple of elements
		int n = elements.size();
		for (int i = 0; i < n - 1; i++) {
			CirculinearElement2D elem1 = elements.get(i);
			for (int j = i; j < n; j++) {
				CirculinearElement2D elem2 = elements.get(j);
				// iterate on intersections between consecutive elements
				for (Point2D inter : findIntersections(elem1, elem2)) {
					// do not keep extremities
					if (isCommonVertex(inter, elem1, elem2))
						continue;

					result.add(inter);
				}
			}
		}

		// return the set of intersections
		return result;
	}

	public static double[][] locateSelfIntersections(
			CurveSet2D<? extends CirculinearElement2D> curve) {

		// create array for storing result
		ArrayList<Double> list1 = new ArrayList<Double>(0);
		ArrayList<Double> list2 = new ArrayList<Double>(0);
		double dt;

		// iterate on each couple of elements
		int n = curve.size();
		for (int i = 0; i < n - 1; i++) {
			CirculinearElement2D elem1 = curve.get(i);
			for (int j = i + 1; j < n; j++) {
				CirculinearElement2D elem2 = curve.get(j);
				// iterate on intersection between consecutive elements
				for (Point2D inter : findIntersections(elem1, elem2)) {
					// do not keep extremities
					if (isCommonVertex(inter, elem1, elem2))
						continue;

					// add the intersection if we keep it
					dt = Curves2D.toUnitSegment(elem1.position(inter),
							elem1.t0(), elem1.t1());
					list1.add(2 * i + dt);

					dt = Curves2D.toUnitSegment(elem2.position(inter),
							elem2.t0(), elem2.t1());
					list2.add(2 * j + dt);
				}
			}
		}

		// convert the 2 lists into a n*2 array
		int np = list1.size();
		double[][] result = new double[np][2];
		for (int i = 0; i < np; i++) {
			result[i][0] = list1.get(i);
			result[i][1] = list2.get(i);
		}

		// return the array of positions
		return result;
	}

	/**
	 * Checks if the point is a common extremity between the two curve elements.
	 */
	private static boolean isCommonVertex(Point2D inter,
			CirculinearCurve2D elem1, CirculinearCurve2D elem2) {

		double eps = Shape2D.ACCURACY;

		// Test end of elem1 and start of elem2
		if (!Double.isInfinite(elem1.t1())
				&& !Double.isInfinite(elem2.t0()))
			if (inter.almostEquals(elem1.lastPoint(), eps)
					&& inter.almostEquals(elem2.firstPoint(), eps))
				return true;

		// Test end of elem2 and start of elem1
		if (!Double.isInfinite(elem1.t0())
				&& !Double.isInfinite(elem2.t1()))
			if (inter.almostEquals(elem1.firstPoint(), eps)
					&& inter.almostEquals(elem2.lastPoint(), eps))
				return true;

		return false;
	}

	/**
	 * Compute the set of intersection points between the two curves.
	 * 
	 * @return a collection of intersection points
	 */
	public static Collection<Point2D> findIntersections(
			CirculinearCurve2D curve1, CirculinearCurve2D curve2) {

		// create array of circulinear elements
		ArrayList<CirculinearElement2D> elements1 = new ArrayList<CirculinearElement2D>();
		ArrayList<CirculinearElement2D> elements2 = new ArrayList<CirculinearElement2D>();

		// extract all circulinear elements of the curve
		for (CirculinearContinuousCurve2D cont : curve1.continuousCurves())
			elements1.addAll(cont.smoothPieces());
		for (CirculinearContinuousCurve2D cont : curve2.continuousCurves())
			elements2.addAll(cont.smoothPieces());

		// create array for storing result
		ArrayList<Point2D> result = new ArrayList<Point2D>(0);

		// iterate on each couple of elements
		int n1 = elements1.size();
		int n2 = elements2.size();
		for (int i = 0; i < n1; i++) {
			CirculinearElement2D elem1 = elements1.get(i);
			for (int j = 0; j < n2; j++) {
				CirculinearElement2D elem2 = elements2.get(j);
				// iterate on intersection between consecutive elements
				for (Point2D inter : findIntersections(elem1, elem2)) {
					// add the intersection if we keep it
					result.add(inter);
				}
			}
		}

		// return the set of intersections
		return result;
	}

	/**
	 * Locate intersection points of two curves. The result is a N-by-2 array of
	 * double, where N is the number of intersections. For each row, the first
	 * element is the position on the first curve, and the second element is the
	 * position on the second curve.
	 */
	public static double[][] locateIntersections(CirculinearCurve2D curve1,
			CirculinearCurve2D curve2) {

		// create array for storing result
		ArrayList<Double> list1 = new ArrayList<Double>(0);
		ArrayList<Double> list2 = new ArrayList<Double>(0);

		// create array of circulinear elements
		ArrayList<CirculinearElement2D> elements1 = new ArrayList<CirculinearElement2D>();
		ArrayList<CirculinearElement2D> elements2 = new ArrayList<CirculinearElement2D>();

		// extract all circulinear elements of the curve
		for (CirculinearContinuousCurve2D cont : curve1.continuousCurves())
			elements1.addAll(cont.smoothPieces());
		for (CirculinearContinuousCurve2D cont : curve2.continuousCurves())
			elements2.addAll(cont.smoothPieces());

		// iterate on each couple of elements
		int n1 = elements1.size();
		int n2 = elements2.size();
		for (int i = 0; i < n1; i++) {
			CirculinearElement2D elem1 = elements1.get(i);
			for (int j = 0; j < n2; j++) {
				CirculinearElement2D elem2 = elements2.get(j);
				// iterate on intersections between consecutive elements
				for (Point2D inter : findIntersections(elem1, elem2)) {
					double pos1 = curve1.position(inter);
					double pos2 = curve2.position(inter);
					if (curve1.isSingular(pos1) && curve2.isSingular(pos2))
						continue;
					// add the intersection if we keep it
					list1.add(pos1);
					list2.add(pos2);
				}
			}
		}

		// convert the 2 lists into a n*2 array
		int np = list1.size();
		double[][] result = new double[np][2];
		for (int i = 0; i < np; i++) {
			result[i][0] = list1.get(i);
			result[i][1] = list2.get(i);
		}

		// return the array of positions
		return result;
	}

	/**
	 * Computes the intersections, if they exist, of two circulinear elements.
	 */
	public static Collection<Point2D> findIntersections(
			CirculinearElement2D elem1, CirculinearElement2D elem2) {

		// find which shapes are linear
		boolean b1 = elem1 instanceof LinearShape2D;
		boolean b2 = elem2 instanceof LinearShape2D;
		
		// if both elements are linear, check parallism to avoid computing
		// intersection of parallel lines
		if (b1 && b2) {
			LinearShape2D line1 = (LinearShape2D) elem1;
			LinearShape2D line2 = (LinearShape2D) elem2;
			
			// test parallel elements
			Vector2D v1 = line1.direction(); 
			Vector2D v2 = line2.direction(); 
			if (Vector2D.isColinear(v1, v2))
				return new ArrayList<Point2D>(0);
			
			return line1.intersections(line2);
		}
		
		// First try to use linear shape methods
		if (elem1 instanceof LinearShape2D) {
			return elem2.intersections((LinearShape2D) elem1);
		}
		if (elem2 instanceof LinearShape2D) {
			return elem1.intersections((LinearShape2D) elem2);
		}

		// From now, both elem1 and elem2 are instances of CircleShape2D
		// It is therefore possible to extract support circles
		Circle2D circ1 = ((CircularShape2D) elem1).supportingCircle();
		Circle2D circ2 = ((CircularShape2D) elem2).supportingCircle();

		// create array for storing result (max 2 possible intersections)
		ArrayList<Point2D> pts = new ArrayList<Point2D>(2);

		// for each of the circle intersections, check if they belong to
		// both elements
		for (Point2D inter : Circle2D.circlesIntersections(circ1, circ2)) {
			if (elem1.contains(inter) && elem2.contains(inter))
				pts.add(inter);
		}

		// return found intersections
		return pts;
	}

	/**
	 * Split a continuous curve which self-intersects into a set of continuous
	 * circulinear curves which do not self-intersect.
	 * 
	 * @param curve
	 *            the curve to split
	 * @return a set of non-self-intersecting continuous curves
	 */
	public static Collection<CirculinearContinuousCurve2D> splitContinuousCurve(
			CirculinearContinuousCurve2D curve) {

		double pos0, pos1, pos2;

		// create the array of resulting curves
		ArrayList<CirculinearContinuousCurve2D> result = 
			new ArrayList<CirculinearContinuousCurve2D>();

		// Instances of CirculinearElement2D can not self-intersect
		if (curve instanceof CirculinearElement2D) {
			result.add(curve);
			return result;
		}

		// convert the curve to a poly-circulinear curve, to be able to call
		// the "locateSelfIntersections" method.
		PolyCirculinearCurve2D<CirculinearElement2D> polyCurve = createPolyCurve(
				curve.smoothPieces(), curve.isClosed());

		// identify couples of intersections
		double[][] couples = locateSelfIntersections(polyCurve);

		// case of curve without self-intersections
		if (couples.length == 0) {
			// create continuous curve formed only by circulinear elements
			result.add(createPolyCurve(polyCurve.smoothPieces(),
					curve.isClosed()));
			return result;
		}

		// put all positions into a tree map
		TreeMap<Double, Double> twins = new TreeMap<Double, Double>();
		for (int i = 0; i < couples.length; i++) {
			pos1 = couples[i][0];
			pos2 = couples[i][1];
			twins.put(pos1, pos2);
			twins.put(pos2, pos1);
		}

		// an array for the portions of curves
		ArrayList<CirculinearElement2D> elements;

		// Process the first curve

		// create new empty array of elements for current continuous curve
		elements = new ArrayList<CirculinearElement2D>();

		// get first intersection
		pos1 = polyCurve.t0();
		pos2 = twins.firstKey();
		pos0 = pos2;

		// add the first portion of curve, starting from the beginning
		addElements(elements, polyCurve.subCurve(pos1, pos2));
		do {
			// get the position of the new portion of curve
			pos1 = twins.remove(pos2);

			// check if there are still intersections to process
			if (twins.higherKey(pos1) == null)
				break;

			// get position of next intersection on the curve
			pos2 = twins.higherKey(pos1);

			// add elements
			addElements(elements, polyCurve.subCurve(pos1, pos2));
		} while (true);

		// add the last portion of curve, going to the end of original curve
		pos2 = polyCurve.t1();
		addElements(elements, polyCurve.subCurve(pos1, pos2));

		// add the continuous curve formed only by circulinear elements
		result.add(createPolyCurve(elements, curve.isClosed()));

		// Process other curves, while there are intersections left
		while (!twins.isEmpty()) {
			// create new empty array of elements for current continuous curve
			elements = new ArrayList<CirculinearElement2D>();

			// get first intersection
			pos0 = twins.firstKey();
			pos1 = twins.get(pos0);
			pos2 = twins.higherKey(pos1);

			// add the first portion of curve, starting from the beginning
			addElements(elements, polyCurve.subCurve(pos1, pos2));

			while (pos2 != pos0) {
				// get the position of the new portion of curve
				pos1 = twins.remove(pos2);

				// check if there are still intersections to process
				if (twins.higherKey(pos1) == null)
					break;

				// get position of next intersection on the curve
				pos2 = twins.higherKey(pos1);

				// add elements
				addElements(elements, polyCurve.subCurve(pos1, pos2));
			}

			pos1 = twins.remove(pos2);

			// create continuous curve formed only by circulinear elements
			// and add it to the set of curves
			result.add(createPolyCurve(elements, true));
		}

		return result;
	}

	/**
	 * This is a helper method, used to avoid excessive use of generics within
	 * other methods of the class.
	 */
	private static PolyCirculinearCurve2D<CirculinearElement2D> createPolyCurve(
			Collection<? extends CirculinearElement2D> elements, boolean closed) {
		return new PolyCirculinearCurve2D<CirculinearElement2D>(elements,
				closed);
	}

	public static Collection<CirculinearContour2D> splitIntersectingContours(
			CirculinearContour2D curve1, CirculinearContour2D curve2) {

		double pos0, pos1, pos2;

		// ----------------
		// Initializations

		// create the array of resulting curves
		ArrayList<CirculinearContour2D> contours = new ArrayList<CirculinearContour2D>();

		// identify couples of intersections
		double[][] couples = locateIntersections(curve1, curve2);

		// case no intersection between the curves
		if (couples.length == 0) {
			// create continuous curve formed only by circulinear elements
			contours.add(curve1);
			contours.add(curve2);
			return contours;
		}

		// stores couple of points in 'twins'
		TreeMap<Double, Double> twins1 = new TreeMap<Double, Double>();
		TreeMap<Double, Double> twins2 = new TreeMap<Double, Double>();

		// stores also positions on each curve in an ordered tree
		TreeSet<Double> positions1 = new TreeSet<Double>();
		TreeSet<Double> positions2 = new TreeSet<Double>();

		// iterate on intersections to populate the data
		for (int i = 0; i < couples.length; i++) {
			pos1 = couples[i][0];
			pos2 = couples[i][1];
			twins1.put(pos1, pos2);
			twins2.put(pos2, pos1);
			positions1.add(pos1);
			positions2.add(pos2);
		}

		// an array for the portions of curves
		ArrayList<CirculinearElement2D> elements;

		// Process other curves, while there are intersections left
		while (!twins1.isEmpty()) {
			// create new empty array of elements for current contour
			elements = new ArrayList<CirculinearElement2D>();

			// get first intersection
			pos0 = twins2.firstEntry().getValue();
			pos1 = pos0;

			do {
				pos2 = nextValue(positions1, pos1);

				// add a portion of the first curve
				addElements(elements, curve1.subCurve(pos1, pos2));

				// get the position of end intersection on second curve
				pos1 = twins1.remove(pos2);

				// get position of next intersection on the second curve
				pos2 = nextValue(positions2, pos1);

				// add a portion of the second curve
				addElements(elements, curve2.subCurve(pos1, pos2));

				// get the position of end intersection on first curve
				pos1 = twins2.remove(pos2);

			} while (pos1 != pos0);

			// create continuous curve formed only by circulinear elements
			// and add it to the set of curves
			contours.add(new BoundaryPolyCirculinearCurve2D(elements, true));
		}

		return contours;
	}

	/**
	 * Split a collection of contours which possibly intersect each other to a
	 * set of contours which do not intersect each others. Each contour is
	 * assumed not to self-intersect.
	 */
	public static Collection<CirculinearContour2D> splitIntersectingContours(
			Collection<? extends CirculinearContour2D> curves) {

		double pos0 = 0, pos1, pos2;

		// ----------------
		// Initializations

		// convert collection to array
		CirculinearContour2D[] curveArray = 
			curves.toArray(new CirculinearContour2D[0]);

		// Create array of tree maps for storing
		// 1) index of crossing curve for each intersection of i-th curve
		// 2) position on crossing curve of the intersection point
		int nCurves = curves.size();
		ArrayList<TreeMap<Double, Integer>> twinIndices = 
			new ArrayList<TreeMap<Double, Integer>>(nCurves);
		ArrayList<TreeMap<Double, Double>> twinPositions = 
			new ArrayList<TreeMap<Double, Double>>(nCurves);

		// Populate the two arrays with empty trees
		for (int i = 0; i < nCurves; i++) {
			twinIndices.add(i, new TreeMap<Double, Integer>());
			twinPositions.add(i, new TreeMap<Double, Double>());
		}

		// Create array of tree sets for storing positions of intersections
		// on each curve
		ArrayList<TreeSet<Double>> positions = 
			new ArrayList<TreeSet<Double>>(nCurves);

		// populate the array with empty tree sets
		for (int i = 0; i < nCurves; i++) {
			positions.add(i, new TreeSet<Double>());
		}

		// identify couples of intersections on each couple (i,j) of curves
		for (int i = 0; i < nCurves - 1; i++) {
			CirculinearContour2D curve1 = curveArray[i];

			for (int j = i + 1; j < nCurves; j++) {
				CirculinearContour2D curve2 = curveArray[j];
				double[][] couples = locateIntersections(curve1, curve2);

				// iterate on intersections to populate the data
				for (int k = 0; k < couples.length; k++) {
					// position on each curve
					pos1 = couples[k][0];
					pos2 = couples[k][1];

					// add positions in their tree sets
					positions.get(i).add(pos1);
					positions.get(j).add(pos2);

					// store indices of corresponding intersecting curves
					twinIndices.get(i).put(pos1, j);
					twinIndices.get(j).put(pos2, i);

					// store positions of intersection point on the
					// corresponding curve
					twinPositions.get(i).put(pos1, pos2);
					twinPositions.get(j).put(pos2, pos1);
				}
			}
		}

		// create the array of resulting curves
		ArrayList<CirculinearContour2D> contours = new ArrayList<CirculinearContour2D>();

		// process curves without intersections
		for (int i = 0; i < nCurves; i++) {
			// If the curve has no intersection, use it as contour
			if (twinPositions.get(i).isEmpty()) {
				contours.add(curveArray[i]);
			}
		}

		// process infinite curves
		for (int i = 0; i < nCurves; i++) {
			// filter bounded curves
			if (curveArray[i].isBounded())
				continue;

			// If the curve has no intersection, it was already processed
			if (twinPositions.get(i).isEmpty()) {
				continue;
			}

			// find first unprocessed intersection
			pos0 = twinPositions.get(i).firstEntry().getKey();
			int ind0 = twinIndices.get(i).firstEntry().getValue();

			// create new empty array of elements for current contour
			ArrayList<CirculinearElement2D> elements = new ArrayList<CirculinearElement2D>();

			// add portion of curve until intersection
			CirculinearContour2D curve0 = curveArray[i];
			addElements(elements, curve0.subCurve(curve0.t0(), pos0));

			// init
			pos1 = twinPositions.get(i).firstEntry().getValue();
			int ind = ind0;

			do {
				// the current contour
				CirculinearContour2D curve = curveArray[ind];

				// extract next position
				pos2 = nextValue(positions.get(ind), pos1);

				if ((pos2 < pos1) && !curve.isBounded()) {
					// We got the last point of an infinite curve.
					// That means we just finished the current free contour
					// and we just need to add elements
					addElements(elements,
							curve.subCurve(pos1, curve.t1()));
				} else {
					// simple case:
					// add a portion of the current curve to the element list
					addElements(elements, curve.subCurve(pos1, pos2));

					// get the position of end intersection on second curve
					pos1 = twinPositions.get(ind).remove(pos2);
					ind = twinIndices.get(ind).remove(pos2);
				}
			} while (ind != ind0);

			twinPositions.get(i).remove(pos0);
			twinIndices.get(i).remove(pos0);

			// create continuous curve formed only by circulinear elements
			// and add it to the set of curves
			contours.add(new BoundaryPolyCirculinearCurve2D(elements, true));
		}

		// Process other curves, while there are intersections left
		while (!isAllEmpty(twinPositions)) {
			// create new empty array of elements for current contour
			ArrayList<CirculinearElement2D> elements = new ArrayList<CirculinearElement2D>();

			// indices of the two considered curves.
			int ind0 = 0, ind;

			// get first intersection
			for (int i = 0; i < nCurves; i++) {
				// find a curve with unprocessed intersections
				if (twinPositions.get(i).isEmpty())
					continue;

				// find first unprocessed intersection
				pos0 = twinPositions.get(i).firstEntry().getValue();
				ind0 = twinIndices.get(i).firstEntry().getValue();
				break;
			}

			if (ind0 == 0) {
				System.out.println("No more intersections, but was not detected");
			}

			pos1 = pos0;
			ind = ind0;

			do {
				pos2 = nextValue(positions.get(ind), pos1);

				// add a portion of the first curve
				addElements(elements, curveArray[ind].subCurve(pos1, pos2));

				// get the position of end intersection on second curve
				pos1 = twinPositions.get(ind).remove(pos2);
				ind = twinIndices.get(ind).remove(pos2);
			} while (pos1 != pos0 || ind != ind0);

			// create continuous curve formed only by circulinear elements
			// and add it to the set of curves
			contours.add(new BoundaryPolyCirculinearCurve2D(elements, true));
		}

		return contours;
	}

	/**
	 * Add all circulinear elements of the given curve to the collection of
	 * circulinear elements.
	 */
	private static void addElements(Collection<CirculinearElement2D> elements,
			CirculinearContinuousCurve2D curve) {
		elements.addAll(curve.smoothPieces());
	}

	private static boolean isAllEmpty(Collection<TreeMap<Double, Double>> coll) {
		for (TreeMap<?, ?> map : coll) {
			if (!map.isEmpty())
				return false;
		}
		return true;
	}

	/**
	 * Returns either the next value, or the first value of the tree if the
	 * given value is the last one of the tree.
	 */
	private static double nextValue(TreeSet<Double> tree, double value) {
		if (tree.higher(value) == null)
			return tree.first();
		else
			return tree.higher(value);
	}

	public static double getDistanceCurvePoints(CirculinearCurve2D curve,
			Collection<? extends Point2D> points) {
		double minDist = Double.MAX_VALUE;
		for (Point2D point : points) {
			minDist = Math.min(minDist, curve.distance(point));
		}
		return minDist;
	}
}
 public class GenericCirculinearDomain2D extends GenericDomain2D implements
        CirculinearDomain2D {

    // ===================================================================
    // Static factories

    public static GenericCirculinearDomain2D create(
            CirculinearBoundary2D boundary) {
        return new GenericCirculinearDomain2D(boundary);
    }

    // ===================================================================
    // constructors

    public GenericCirculinearDomain2D(CirculinearBoundary2D boundary) {
        super(boundary);
    }

    @Override
    public CirculinearBoundary2D boundary() {
        return (CirculinearBoundary2D) boundary;
    }

    /*
     * (non-Javadoc)
     * 
     * @see math.geom2d.domain.Domain2D#contours()
     */
    public Collection<? extends CirculinearContour2D> contours() {
        return ((CirculinearBoundary2D) this.boundary).continuousCurves();
    }

    @Override
    public CirculinearDomain2D complement() {
        return new GenericCirculinearDomain2D(
                (CirculinearBoundary2D) boundary.reverse());
    }

    /*
     * (non-Javadoc)
     * 
     * @see math.geom2d.circulinear.CirculinearShape2D#buffer(double)
     */
    public CirculinearDomain2D buffer(double dist) {

        CirculinearBoundary2D newBoundary = ((CirculinearBoundary2D) this.boundary)
                .parallel(dist);
        return new GenericCirculinearDomain2D(new CirculinearContourArray2D(
                CirculinearCurves2D.splitIntersectingContours(newBoundary
                        .continuousCurves())));
    }

    /*
     * (non-Javadoc)
     * 
     * @see
     * math.geom2d.circulinear.CirculinearDomain2D#transform(math.geom2d.transform
     * .CircleInversion2D)
     */
    public CirculinearDomain2D transform(CircleInversion2D inv) {
        // class cast
        CirculinearBoundary2D boundary2 = (CirculinearBoundary2D) boundary;

        // transform and reverse
        boundary2 = boundary2.transform(inv).reverse();

        // create the result domain
        return new GenericCirculinearDomain2D(boundary2);
    }

    // ===================================================================
    // methods overriding the Object class

    @Override
    public String toString() {
        return "GenericCirculinearDomain2D(boundary=" + boundary + ")";
    }

}
 public class GenericCirculinearRing2D extends
        PolyCirculinearCurve2D<CirculinearElement2D> implements
        CirculinearRing2D {
    // TODO: parameterize with curve type ?

    // ===================================================================
    // static methods


    // ===================================================================
    // constructors

    public GenericCirculinearRing2D() {
        super();
        this.closed = true;
    }

    public GenericCirculinearRing2D(int size) {
        super(size);
        this.closed = true;
    }

    public GenericCirculinearRing2D(CirculinearElement2D... curves) {
        super(curves);
        this.closed = true;
    }

    public GenericCirculinearRing2D(
            Collection<? extends CirculinearElement2D> curves) {
        super(curves);
        this.closed = true;
    }

    // ===================================================================
    // methods specific to GenericCirculinearRing2D

    @Override
    public CirculinearRing2D parallel(double dist) {
        BufferCalculator bc = BufferCalculator.getDefaultInstance();

        return new GenericCirculinearRing2D(bc.createContinuousParallel(this,
                dist).smoothPieces());
    }

    public Collection<? extends GenericCirculinearRing2D> continuousCurves() {
        return wrapCurve(this);
    }

    @Override
    public GenericCirculinearRing2D transform(CircleInversion2D inv) {
        // Allocate array for result
        GenericCirculinearRing2D result = new GenericCirculinearRing2D(
                curves.size());

        // add each transformed element
        for (CirculinearElement2D element : curves)
            result.add(element.transform(inv));
        return result;
    }


    /*
     * (non-Javadoc)
     * 
     * @see math.geom2d.domain.Boundary2D#domain()
     */
    public CirculinearDomain2D domain() {
        return new GenericCirculinearDomain2D(this);
    }

    @Override
    public GenericCirculinearRing2D reverse() {
        int n = curves.size();
        // create array of reversed curves
        CirculinearElement2D[] curves2 = new CirculinearElement2D[n];

        // reverse each curve
        for (int i = 0; i < n; i++)
            curves2[i] = curves.get(n - 1 - i).reverse();

        // create the reversed final curve
        return new GenericCirculinearRing2D(curves2);
    }

    @Override
    public BoundaryPolyCurve2D<ContinuousOrientedCurve2D> transform(
            AffineTransform2D trans) {
        // number of curves
        int n = this.size();

        // create result curve
        BoundaryPolyCurve2D<ContinuousOrientedCurve2D> result = new BoundaryPolyCurve2D<ContinuousOrientedCurve2D>(
                n);

        // add each curve after class cast
        for (ContinuousOrientedCurve2D curve : curves)
            result.add(curve.transform(trans));
        return result;
    }

}
 public class PolyCirculinearCurve2D<T extends CirculinearContinuousCurve2D>
        extends PolyOrientedCurve2D<T> implements CirculinearContinuousCurve2D {

    // ===================================================================
    // static constructors

    /**
     * Static factory for creating a new PolyCirculinearCurve2D from a
     * collection of curves.
     * 
     * @since 0.8.1
     */
    // public static <T extends CirculinearContinuousCurve2D>
    // PolyCirculinearCurve2D<T> create(Collection<T> curves) {
    // return new PolyCirculinearCurve2D<T>(curves);
    // }

    /**
     * Static factory for creating a new PolyCirculinearCurve2D from an array of
     * curves.
     * 
     * @since 0.8.1
     */
    // public static <T extends CirculinearContinuousCurve2D>
    // PolyCirculinearCurve2D<T> create(T... curves) {
    // return new PolyCirculinearCurve2D<T>(curves);
    // }

    /**
     * Static factory for creating a new PolyCirculinearCurve2D from a
     * collection of curves and a flag indicating if the curve is closed.
     * 
     * @since 0.9.0
     */
    // public static <T extends CirculinearContinuousCurve2D>
    // PolyCirculinearCurve2D<T> create(Collection<T> curves, boolean closed) {
    // return new PolyCirculinearCurve2D<T>(curves, closed);
    // }

    /**
     * Static factory for creating a new PolyCirculinearCurve2D from an array of
     * curves and a flag indicating if the curve is closed.
     * 
     * @since 0.9.0
     */
    // public static <T extends CirculinearContinuousCurve2D>
    // PolyCirculinearCurve2D<T> create(T[] curves, boolean closed) {
    // return new PolyCirculinearCurve2D<T>(curves, closed);
    // }

    /**
     * Static factory for creating a new PolyCirculinearCurve2D from an array of
     * curves and a flag indicating if the curve is closed.
     * 
     * @since 0.9.0
     */
    // public static <T extends CirculinearContinuousCurve2D>
    // PolyCirculinearCurve2D<T> createClosed(T... curves) {
    // return new PolyCirculinearCurve2D<T>(curves, true);
    // }

    // ===================================================================
    // constructors

    public PolyCirculinearCurve2D() {
        super();
    }

    public PolyCirculinearCurve2D(int size) {
        super(size);
    }

    public PolyCirculinearCurve2D(T[] curves) {
        super(curves);
    }

    public PolyCirculinearCurve2D(T[] curves, boolean closed) {
        super(curves, closed);
    }

    public PolyCirculinearCurve2D(Collection<? extends T> curves) {
        super(curves);
    }

    public PolyCirculinearCurve2D(Collection<? extends T> curves, boolean closed) {
        super(curves, closed);
    }

    // ===================================================================
    // methods implementing the CirculinearCurve2D interface

    /*
     * (non-Javadoc)
     * 
     * @see math.geom2d.circulinear.CirculinearCurve2D#length()
     */
    public double length() {
        double sum = 0;
        for (CirculinearCurve2D curve : this.curves())
            sum += curve.length();
        return sum;
    }

    /*
     * (non-Javadoc)
     * 
     * @see math.geom2d.circulinear.CirculinearCurve2D#length(double)
     */
    public double length(double pos) {
        return CirculinearCurves2D.getLength(this, pos);
    }

    /*
     * (non-Javadoc)
     * 
     * @see math.geom2d.circulinear.CirculinearCurve2D#position(double)
     */
    public double position(double length) {
        return CirculinearCurves2D.getPosition(this, length);
    }

    /*
     * (non-Javadoc)
     * 
     * @see math.geom2d.circulinear.CirculinearShape2D#buffer(double)
     */
    public CirculinearDomain2D buffer(double dist) {
        BufferCalculator bc = BufferCalculator.getDefaultInstance();
        return bc.computeBuffer(this, dist);
    }

    /*
     * (non-Javadoc)
     * 
     * @see
     * math.geom2d.circulinear.CirculinearContinuousCurve2D#parallel(double)
     */
    public CirculinearContinuousCurve2D parallel(double d) {
        BufferCalculator bc = BufferCalculator.getDefaultInstance();
        return bc.createContinuousParallel(this, d);
    }

    /*
     * (non-Javadoc)
     * 
     * @see
     * math.geom2d.circulinear.CirculinearCurve2D#transform(math.geom2d.transform
     * .CircleInversion2D)
     */
    public PolyCirculinearCurve2D<? extends CirculinearContinuousCurve2D> transform(
            CircleInversion2D inv) {
        // Allocate array for result
        int n = curves.size();
        PolyCirculinearCurve2D<CirculinearContinuousCurve2D> result = new PolyCirculinearCurve2D<CirculinearContinuousCurve2D>(
                n);

        // add each transformed curve
        for (CirculinearContinuousCurve2D curve : curves)
            result.add(curve.transform(inv));
        return result;
    }

    // ===================================================================
    // methods implementing the ContinuousCurve2D interface

    /*
     * (non-Javadoc)
     * 
     * @see math.geom2d.CirculinearContinuousCurve2D#smoothPieces()
     */
    @Override
    public Collection<? extends CirculinearElement2D> smoothPieces() {
        // create array for storing result
        ArrayList<CirculinearElement2D> result = new ArrayList<CirculinearElement2D>();

        // add elements of each curve
        for (CirculinearContinuousCurve2D curve : curves)
            result.addAll(curve.smoothPieces());

        // return the collection
        return result;
    }

    // ===================================================================
    // methods implementing the Curve2D interface

    @Override
    public Collection<? extends PolyCirculinearCurve2D<?>> continuousCurves() {
        return wrapCurve(this);
    }

    @Override
    public CirculinearCurveSet2D<? extends CirculinearContinuousCurve2D> clip(
            Box2D box) {
        // Clip the curve
        CurveSet2D<? extends Curve2D> set = Curves2D.clipCurve(this, box);

        // Stores the result in appropriate structure
        int n = set.size();
        CirculinearCurveArray2D<CirculinearContinuousCurve2D> result = new CirculinearCurveArray2D<CirculinearContinuousCurve2D>(
                n);

        // convert the result, class cast each curve
        for (Curve2D curve : set.curves()) {
            if (curve instanceof CirculinearContinuousCurve2D)
                result.add((CirculinearContinuousCurve2D) curve);
        }

        // return the new set of curves
        return result;
    }

    @Override
    public PolyCirculinearCurve2D<? extends CirculinearContinuousCurve2D> reverse() {
        // create array of reversed curves
        int n = curves.size();
        CirculinearContinuousCurve2D[] curves2 = new CirculinearContinuousCurve2D[n];

        // reverse each curve
        for (int i = 0; i < n; i++)
            curves2[i] = curves.get(n - 1 - i).reverse();

        // create the reversed final curve
        return new PolyCirculinearCurve2D(curves2, this.closed);
    }

    @Override
    public PolyCirculinearCurve2D<? extends CirculinearContinuousCurve2D> subCurve(
            double t0, double t1) {
        // Call the superclass method
        PolyOrientedCurve2D<? extends ContinuousOrientedCurve2D> subcurve = super
                .subCurve(t0, t1);

        // prepare result
        int n = subcurve.size();
        PolyCirculinearCurve2D<CirculinearContinuousCurve2D> result = new PolyCirculinearCurve2D<CirculinearContinuousCurve2D>(
                n);

        // add each curve after class cast
        for (Curve2D curve : subcurve) {
            if (curve instanceof CirculinearContinuousCurve2D)
                result.add((CirculinearContinuousCurve2D) curve);
        }

        // return the result
        return result;
    }

} public class Circle2D extends AbstractSmoothCurve2D implements EllipseShape2D,
        CircleLine2D, CircularShape2D, CirculinearRing2D, Cloneable {

    // ===================================================================
    // Static methods

    /**
     * Creates a circle from a center and a radius.
     * 
     * @deprecated since 0.11.1
     */
    @Deprecated
    public static Circle2D create(Point2D center, double radius) {
        return new Circle2D(center, radius);
    }

    /**
     * Creates a circle from a center, a radius, and a flag indicating
     * orientation.
     * 
     * @deprecated since 0.11.1
     */
    @Deprecated
    public static Circle2D create(Point2D center, double radius, boolean direct) {
        return new Circle2D(center, radius, direct);
    }

    /**
     * Creates a circle containing 3 points.
     * 
     * @deprecated replaced by createCircle(Point2D, Point2D, Point2D) (0.11.1)
     */
    @Deprecated
    public static Circle2D create(Point2D p1, Point2D p2, Point2D p3) {
        if (Point2D.isColinear(p1, p2, p3))
            throw new ColinearPoints2DException(p1, p2, p3);

        // create two median lines
        StraightLine2D line12 = StraightLine2D.createMedian(p1, p2);
        StraightLine2D line23 = StraightLine2D.createMedian(p2, p3);

        // check medians are not parallel
        // assert !AbstractLine2D.isParallel(line12, line23) : "If points are not colinear, medians should not be parallel";

        // Compute intersection of the medians, and circle radius
        Point2D center = AbstractLine2D.getIntersection(line12, line23);
        double radius = Point2D.distance(center, p2);

        // return the created circle
        return new Circle2D(center, radius);
    }

    /**
     * @deprecated replaced by circlesIntersections(Circle2D, Circle2D) (0.11.1)
     */
    @Deprecated
    public static Collection<Point2D> getIntersections(Circle2D circle1,
            Circle2D circle2) {
        ArrayList<Point2D> intersections = new ArrayList<Point2D>(2);

        // extract center and radius of each circle
        Point2D center1 = circle1.center();
        Point2D center2 = circle2.center();
        double r1 = circle1.radius();
        double r2 = circle2.radius();

        double d = Point2D.distance(center1, center2);

        // case of no intersection
        if (d < abs(r1 - r2) || d > (r1 + r2))
            return intersections;

        // Angle of line from center1 to center2
        double angle = Angle2D.horizontalAngle(center1, center2);

        // position of intermediate point
        double d1 = d / 2 + (r1 * r1 - r2 * r2) / (2 * d);
        Point2D tmp = Point2D.createPolar(center1, d1, angle);

        // Add the 2 intersection points
        double h = sqrt(r1 * r1 - d1 * d1);
        intersections.add(Point2D.createPolar(tmp, h, angle + PI / 2));
        intersections.add(Point2D.createPolar(tmp, h, angle - PI / 2));

        return intersections;
    }

    /**
     * Computes intersections of a circle with a line. Returns an array of
     * Point2D, of size 0, 1 or 2 depending on the distance between circle and
     * line. If there are 2 intersections points, the first one in the array is
     * the first one on the line.
     * 
     * @deprecated replaced by lineCircleIntersections(LinearShape2D,
     *             CircularShape2D) (0.11.1)
     */
    @Deprecated
    public static Collection<Point2D> getIntersections(CircularShape2D circle,
            LinearShape2D line) {
        // initialize array of points (maximum 2 intersections)
        ArrayList<Point2D> intersections = new ArrayList<Point2D>(2);

        // extract parameters of the circle
        Circle2D parent = circle.supportingCircle();
        Point2D center = parent.center();
        double radius = parent.radius();

        // Compute line perpendicular to the test line, and going through the
        // circle center
        StraightLine2D perp = StraightLine2D.createPerpendicular(line, center);

        // Compute distance between line and circle center
        Point2D inter = perp.intersection(new StraightLine2D(line));
        // assert (inter != null);
        double dist = inter.distance(center);

        // if the distance is the radius of the circle, return the
        // intersection point
        if (abs(dist - radius) < Shape2D.ACCURACY) {
            if (line.contains(inter) && circle.contains(inter))
                intersections.add(inter);
            return intersections;
        }

        // compute angle of the line, and distance between 'inter' point and
        // each intersection point
        double angle = line.horizontalAngle();
        double d2 = sqrt(radius * radius - dist * dist);

        // Compute position and angle of intersection points
        Point2D p1 = Point2D.createPolar(inter, d2, angle + Math.PI);
        Point2D p2 = Point2D.createPolar(inter, d2, angle);

        // add points to the array only if they belong to the line
        if (line.contains(p1) && circle.contains(p1))
            intersections.add(p1);
        if (line.contains(p2) && circle.contains(p2))
            intersections.add(p2);

        // return the result
        return intersections;
    }

    /**
     * Computes the circumscribed circle of the 3 input points.
     * 
     * @return the circle that contains the three input points
     * @throws ColinearPoints2DException
     *             if the 3 points are colinear
     */
    public static Circle2D circumCircle(Point2D p1, Point2D p2, Point2D p3) {
        // Computes circum center, possibly throwing ColinearPoints2DException
        Point2D center = circumCenter(p1, p2, p3);

        // compute radius
        double radius = Point2D.distance(center, p2);

        // return the created circle
        return new Circle2D(center, radius);
    }

    /**
     * Computes the center of the circumscribed circle of the three input
     * points.
     * 
     * @throws ColinearPoints2DException
     *             if the 3 points are colinear
     */
    public static Point2D circumCenter(Point2D p1, Point2D p2, Point2D p3) {
        if (Point2D.isColinear(p1, p2, p3))
            throw new ColinearPoints2DException(p1, p2, p3);

        // create two median lines
        StraightLine2D line12 = StraightLine2D.createMedian(p1, p2);
        StraightLine2D line23 = StraightLine2D.createMedian(p2, p3);

        // check medians are not parallel
        // assert !AbstractLine2D.isParallel(line12, line23) : "If points are not colinear, medians should not be parallel";

        // Compute intersection of the medians, and circle radius
        Point2D center = AbstractLine2D.getIntersection(line12, line23);

        // return the center
        return center;
    }

    /**
     * Computes the intersections points between two circles or circular shapes.
     * 
     * @param circle1
     *            an instance of circle or circle arc
     * @param circle2
     *            an instance of circle or circle arc
     * @return a collection of 0, 1 or 2 intersection points
     */
    public static Collection<Point2D> circlesIntersections(Circle2D circle1,
            Circle2D circle2) {
        // extract center and radius of each circle
        Point2D center1 = circle1.center();
        Point2D center2 = circle2.center();
        double r1 = circle1.radius();
        double r2 = circle2.radius();

        double d = Point2D.distance(center1, center2);

        // case of no intersection
        if (d < abs(r1 - r2) || d > (r1 + r2))
            return new ArrayList<Point2D>(0);

        // Angle of line from center1 to center2
        double angle = Angle2D.horizontalAngle(center1, center2);

        // position of intermediate point
        double d1 = d / 2 + (r1 * r1 - r2 * r2) / (2 * d);
        Point2D tmp = Point2D.createPolar(center1, d1, angle);

        // distance between intermediate point and each intersection
        double h = sqrt(r1 * r1 - d1 * d1);

        // create empty array
        ArrayList<Point2D> intersections = new ArrayList<Point2D>(2);

        // Add the 2 intersection points
        Point2D p1 = Point2D.createPolar(tmp, h, angle + PI / 2);
        intersections.add(p1);
        Point2D p2 = Point2D.createPolar(tmp, h, angle - PI / 2);
        intersections.add(p2);

        return intersections;
    }

    /**
     * Computes intersections of a circle with a line. Returns an array of
     * Point2D, of size 0, 1 or 2 depending on the distance between circle and
     * line. If there are 2 intersections points, the first one in the array is
     * the first one on the line.
     * 
     * @return a collection of intersection points
     * @since 0.11.1
     */
    public static Collection<Point2D> lineCircleIntersections(
            LinearShape2D line, CircularShape2D circle) {
        // initialize array of points (maximum 2 intersections)
        ArrayList<Point2D> intersections = new ArrayList<Point2D>(2);

        // extract parameters of the circle
        Circle2D parent = circle.supportingCircle();
        Point2D center = parent.center();
        double radius = parent.radius();

        // Compute line perpendicular to the test line, and going through the
        // circle center
        StraightLine2D perp = StraightLine2D.createPerpendicular(line, center);

        // Compute distance between line and circle center
        Point2D inter = perp.intersection(new StraightLine2D(line));
        if (inter == null) {
            throw new RuntimeException(
                    "Could not compute intersection point when computing line-cicle intersection");
        }
        double dist = inter.distance(center);

        // if the distance is the radius of the circle, return the
        // intersection point
        if (abs(dist - radius) < Shape2D.ACCURACY) {
            if (line.contains(inter) && circle.contains(inter))
                intersections.add(inter);
            return intersections;
        }

        // compute angle of the line, and distance between 'inter' point and
        // each intersection point
        double angle = line.horizontalAngle();
        double d2 = sqrt(radius * radius - dist * dist);

        // Compute position and angle of intersection points
        Point2D p1 = Point2D.createPolar(inter, d2, angle + Math.PI);
        Point2D p2 = Point2D.createPolar(inter, d2, angle);

        // add points to the array only if they belong to the line
        if (line.contains(p1) && circle.contains(p1))
            intersections.add(p1);
        if (line.contains(p2) && circle.contains(p2))
            intersections.add(p2);

        // return the result
        return intersections;
    }

    /**
     * Computes the radical axis of the two circles.
     * 
     * @since 0.11.1
     * @return the radical axis of the two circles.
     * @throws IllegalArgumentException
     *             if the two circles have same center
     */
    public static StraightLine2D radicalAxis(Circle2D circle1, Circle2D circle2) {

        // extract center and radius of each circle
        double r1 = circle1.radius();
        double r2 = circle2.radius();
        Point2D p1 = circle1.center();
        Point2D p2 = circle2.center();

        // compute horizontal angle of joining line
        double angle = Angle2D.horizontalAngle(p1, p2);

        // distance between centers
        double dist = p1.distance(p2);
        if (dist < Shape2D.ACCURACY) {
            throw new IllegalArgumentException(
                    "Input circles must have distinct centers");
        }

        // position of the radical axis on the joining line
        double d = (dist * dist + r1 * r1 - r2 * r2) * .5 / dist;

        // pre-compute trigonometric functions
        double cot = Math.cos(angle);
        double sit = Math.sin(angle);

        // compute parameters of the line
        double x0 = p1.x() + d * cot;
        double y0 = p1.y() + d * sit;
        double dx = -sit;
        double dy = cot;

        // update state of current line
        return new StraightLine2D(x0, y0, dx, dy);
    }

    // ===================================================================
    // Class variables

    /** Coordinate of center. */
    protected double xc;
    protected double yc;

    /** the radius of the circle. */
    protected double r = 0;

    /** Directed circle or not */
    protected boolean direct = true;

    /** Orientation of major semi-axis, in radians, between 0 and 2*PI. */
    protected double theta = 0;

    // ===================================================================
    // Constructors

    /** Empty constructor: center 0,0 and radius 0. */
    public Circle2D() {
        this(0, 0, 0, true);
    }

    /** Create a new circle with specified point center and radius */
    public Circle2D(Point2D center, double radius) {
        this(center.x(), center.y(), radius, true);
    }

    /** Create a new circle with specified center, radius and orientation */
    public Circle2D(Point2D center, double radius, boolean direct) {
        this(center.x(), center.y(), radius, direct);
    }

    /** Create a new circle with specified center and radius */
    public Circle2D(double xcenter, double ycenter, double radius) {
        this(xcenter, ycenter, radius, true);
    }

    /** Create a new circle with specified center, radius and orientation. */
    public Circle2D(double xcenter, double ycenter, double radius,
            boolean direct) {
        this.xc = xcenter;
        this.yc = ycenter;
        this.r = radius;
        this.direct = direct;
    }

    // ===================================================================
    // methods specific to class Circle2D

    /**
     * Returns the radius of the circle.
     */
    public double radius() {
        return r;
    }

    /**
     * Returns the intersection points with another circle. The result is a
     * collection with 0, 1 or 2 points.
     */
    public Collection<Point2D> intersections(Circle2D circle) {
        return Circle2D.circlesIntersections(this, circle);
    }

    // ===================================================================
    // methods implementing CircularShape2D interface

    /**
     * Returns the circle itself.
     */
    public Circle2D supportingCircle() {
        return this;
    }

    // ===================================================================
    // Methods implementing the Ellipse2D interface

    /**
     * Returns true if circle has a direct orientation.
     */
    public boolean isDirect() {
        return direct;
    }

    /**
     * Returns center of the circle.
     */
    public Point2D center() {
        return new Point2D(xc, yc);
    }

    /**
     * Returns the first direction vector of the circle, in the direction of the
     * major axis.
     */
    public Vector2D vector1() {
        return new Vector2D(cos(theta), sin(theta));
    }

    /**
     * Returns the second direction vector of the circle, in the direction of
     * the minor axis.
     */
    public Vector2D vector2() {
        if (direct)
            return new Vector2D(-sin(theta), cos(theta));
        else
            return new Vector2D(sin(theta), -cos(theta));
    }

    /**
     * Returns the angle of the circle main axis with the Ox axis.
     */
    public double angle() {
        return theta;
    }

    /**
     * Returns the first focus, which for a circle is the same point as the
     * center.
     */
    public Point2D focus1() {
        return new Point2D(xc, yc);
    }

    /**
     * Returns the second focus, which for a circle is the same point as the
     * center.
     */
    public Point2D focus2() {
        return new Point2D(xc, yc);
    }

    public boolean isCircle() {
        return true;
    }

    /**
     * Converts this circle to an instance of Ellipse2D.
     * 
     * @return a new instance of Ellipse2D that corresponds to this circle
     */
    public Ellipse2D asEllipse() {
        return new Ellipse2D(this.xc, this.yc, this.r, this.r, this.theta,
                this.direct);
    }

    // ===================================================================
    // methods implementing the Conic2D interface

    public Type conicType() {
        return Conic2D.Type.CIRCLE;
    }

    /**
     * Returns Cartesian equation of the circle:
     * <p>
     * <code>(x-xc)^2 + (y-yc)^2 = r^2</code>, giving:
     * <p>
     * <code>x^2 + 0*x*y + y^2 -2*xc*x -2*yc*y + xc*xc+yc*yc-r*r = 0</code>.
     */
    public double[] conicCoefficients() {
        return new double[] { 1, 0, 1, -2 * xc, -2 * yc,
                xc * xc + yc * yc - r * r };
    }

    /**
     * Returns 0, which is the eccentricity of a circle by definition.
     */
    public double eccentricity() {
        return 0;
    }

    // ===================================================================
    // Methods implementing the CirculinearCurve2D interface

    /*
     * (non-Javadoc)
     * 
     * @see math.geom2d.circulinear.CirculinearShape2D#buffer(double)
     */
    public CirculinearDomain2D buffer(double dist) {
        BufferCalculator bc = BufferCalculator.getDefaultInstance();
        return bc.computeBuffer(this, dist);
    }

    /**
     * Returns the parallel circle located at a distance d from this circle. For
     * direct circle, distance is positive outside of the circle, and negative
     * inside. This is the contrary for indirect circles.
     */
    public Circle2D parallel(double d) {
        double rp = max(direct ? r + d : r - d, 0);
        return new Circle2D(xc, yc, rp, direct);
    }

    /** Returns perimeter of the circle (equal to 2*PI*radius). */
    public double length() {
        return PI * 2 * r;
    }

    /**
     * Returns the geodesic leangth until the given position.
     * 
     * @see math.geom2d.circulinear.CirculinearCurve2D#length(double)
     */
    public double length(double pos) {
        return pos * this.r;
    }

    /*
     * (non-Javadoc)
     * 
     * @see math.geom2d.circulinear.CirculinearCurve2D#position(double)
     */
    public double position(double length) {
        return length / this.r;
    }

    /*
     * (non-Javadoc)
     * 
     * @see
     * math.geom2d.circulinear.CirculinearCurve2D#transform(math.geom2d.transform
     * .CircleInversion2D)
     */
    public CircleLine2D transform(CircleInversion2D inv) {
        // Extract inversion parameters
        Point2D center = inv.center();
        Point2D c1 = this.center();

        // If circles are concentric, creates directly the new circle
        if (center.distance(c1) < Shape2D.ACCURACY) {
            double r0 = inv.radius();
            double r2 = r0 * r0 / this.r;
            return new Circle2D(center, r2, this.direct);
        }

        // line joining centers of the two circles
        StraightLine2D centersLine = new StraightLine2D(center, c1);

        // get the two intersection points with the line joining the circle
        // centers
        Collection<Point2D> points = this.intersections(centersLine);
        if (points.size() < 2) {
            throw new RuntimeException(
                    "Intersection of circle with line through center has less than 2 points");
        }
        Iterator<Point2D> iter = points.iterator();
        Point2D p1 = iter.next();
        Point2D p2 = iter.next();

        // If the circle contains the inversion center, it transforms into a
        // straight line
        if (this.distance(center) < Shape2D.ACCURACY) {
            // choose the intersection point that is not the center
            double dist1 = center.distance(p1);
            double dist2 = center.distance(p2);
            Point2D p0 = dist1 < dist2 ? p2 : p1;

            // transform the point, and return the perpendicular
            p0 = p0.transform(inv);
            return StraightLine2D.createPerpendicular(centersLine, p0);
        }

        // For regular cases, the circle transforms into an other circle

        // transform the two extreme points of the circle,
        // resulting in a diameter of the new circle
        p1 = p1.transform(inv);
        p2 = p2.transform(inv);

        // compute center and diameter of transformed circle
        double diam = p1.distance(p2);
        c1 = Point2D.midPoint(p1, p2);

        // create the transformed circle
        boolean direct = !this.isDirect() ^ this.isInside(inv.center());
        return new Circle2D(c1, diam / 2, direct);
    }

    // ===================================================================
    // methods implementing the Boundary2D interface

    public CirculinearDomain2D domain() {
        return new GenericCirculinearDomain2D(this);
    }

    // ===================================================================
    // methods implementing OrientedCurve2D interface

    /**
     * Return either 0, 2*PI or -2*PI, depending whether the point is located
     * inside the interior of the ellipse or not.
     */
    public double windingAngle(Point2D point) {
        if (this.signedDistance(point) > 0)
            return 0;
        else
            return direct ? PI * 2 : -PI * 2;
    }

    // ===================================================================
    // methods of SmoothCurve2D interface

    public Vector2D tangent(double t) {
        if (!direct)
            t = -t;
        double cot = cos(theta);
        double sit = sin(theta);
        double cost = cos(t);
        double sint = sin(t);

        if (direct)
            return new Vector2D(-r * sint * cot - r * cost * sit, -r * sint
                    * sit + r * cost * cot);
        else
            return new Vector2D(r * sint * cot + r * cost * sit, r * sint * sit
                    - r * cost * cot);
    }

    /**
     * Returns the inverse of the circle radius. If the circle is indirect, the
     * curvature is negative.
     */
    public double curvature(double t) {
        double k = 1 / r;
        return direct ? k : -k;
    }

    // ===================================================================
    // methods of ContinuousCurve2D interface

    /**
     * Returns a set of smooth curves, which contains only the circle.
     */
    @Override
    public Collection<? extends Circle2D> smoothPieces() {
        return wrapCurve(this);
    }

    /**
     * Returns true, as an ellipse is always closed.
     */
    public boolean isClosed() {
        return true;
    }

    /*
     * (non-Javadoc)
     * 
     * @see math.geom2d.curve.ContinuousCurve2D#asPolyline(int)
     */
    public LinearRing2D asPolyline(int n) {
        return this.asPolylineClosed(n);
    }

    // ===================================================================
    // methods of OrientedCurve2D interface

    /**
     * Test whether the point is inside the circle. The test is performed by
     * translating the point, and re-scaling it such that its coordinates are
     * expressed in unit circle basis.
     */
    public boolean isInside(Point2D point) {
        double xp = (point.x() - this.xc) / this.r;
        double yp = (point.y() - this.yc) / this.r;
        return (xp * xp + yp * yp < 1) ^ !direct;
    }

    public double signedDistance(Point2D point) {
        return signedDistance(point.x(), point.y());
    }

    public double signedDistance(double x, double y) {
        if (direct)
            return Point2D.distance(xc, yc, x, y) - r;
        else
            return r - Point2D.distance(xc, yc, x, y);
    }

    // ===================================================================
    // methods of Curve2D interface

    /** Always returns true. */
    public boolean isBounded() {
        return true;
    }

    /** Always returns false. */
    public boolean isEmpty() {
        return false;
    }

    /**
     * Returns the parameter of the first point of the ellipse, set to 0.
     */
    public double t0() {
        return 0;
    }

    /**
     * @deprecated replaced by t0() (since 0.11.1).
     */
    @Deprecated
    public double getT0() {
        return t0();
    }

    /**
     * Returns the parameter of the last point of the ellipse, set to 2*PI.
     */
    public double t1() {
        return 2 * PI;
    }

    /**
     * @deprecated replaced by t1() (since 0.11.1).
     */
    @Deprecated
    public double getT1() {
        return t1();
    }

    /**
     * Get the position of the curve from internal parametric representation,
     * depending on the parameter t. This parameter is between the two limits 0
     * and 2*Math.PI.
     */
    public Point2D point(double t) {
        double angle = theta + t;
        if (!direct)
            angle = theta - t;
        return new Point2D(xc + r * cos(angle), yc + r * sin(angle));
    }

    /**
     * Get the first point of the circle, which is the same as the last point.
     * 
     * @return the first point of the curve
     */
    public Point2D firstPoint() {
        return new Point2D(xc + r * cos(theta), yc + r * sin(theta));
    }

    /**
     * Get the last point of the circle, which is the same as the first point.
     * 
     * @return the last point of the curve.
     */
    public Point2D lastPoint() {
        return new Point2D(xc + r * cos(theta), yc + r * sin(theta));
    }

    public double position(Point2D point) {
        double angle = Angle2D.horizontalAngle(xc, yc, point.x(), point.y());
        if (direct)
            return Angle2D.formatAngle(angle - theta);
        else
            return Angle2D.formatAngle(theta - angle);
    }

    /**
     * Computes the projection position of the point on the circle, by computing
     * angle with horizonrtal
     */
    public double project(Point2D point) {
        double xp = point.x() - this.xc;
        double yp = point.y() - this.yc;

        // compute angle
        return Angle2D.horizontalAngle(xp, yp);
    }

    /**
     * Returns the circle with same center and same radius, but with the
     * opposite orientation.
     */
    public Circle2D reverse() {
        return new Circle2D(this.xc, this.yc, this.r, !this.direct);
    }

    /**
     * Returns a new CircleArc2D. t0 and t1 are position on circle.
     */
    public CircleArc2D subCurve(double t0, double t1) {
        double startAngle, extent;
        if (this.direct) {
            startAngle = t0;
            extent = Angle2D.formatAngle(t1 - t0);
        } else {
            extent = -Angle2D.formatAngle(t1 - t0);
            startAngle = Angle2D.formatAngle(-t0);
        }
        return new CircleArc2D(this, startAngle, extent);
    }

    public Collection<? extends Circle2D> continuousCurves() {
        return wrapCurve(this);
    }

    // ===================================================================
    // methods of Shape2D interface

    public double distance(Point2D point) {
        return abs(Point2D.distance(xc, yc, point.x(), point.y()) - r);
    }

    public double distance(double x, double y) {
        return abs(Point2D.distance(xc, yc, x, y) - r);
    }

    /**
     * Computes intersections of the circle with a line. Return an array of
     * Point2D, of size 0, 1 or 2 depending on the distance between circle and
     * line. If there are 2 intersections points, the first one in the array is
     * the first one on the line.
     */
    public Collection<Point2D> intersections(LinearShape2D line) {
        return Circle2D.lineCircleIntersections(line, this);
    }

    /**
     * Clips the circle by a box. The result is an instance of CurveSet2D, which
     * contains only instances of CircleArc2D or Circle2D. If the circle is not
     * clipped, the result is an instance of CurveSet2D which contains 0 curves.
     */
    public CurveSet2D<? extends CircularShape2D> clip(Box2D box) {
        // Clip the curve
        CurveSet2D<SmoothCurve2D> set = Curves2D.clipSmoothCurve(this, box);

        // Stores the result in appropriate structure
        CurveArray2D<CircularShape2D> result = new CurveArray2D<CircularShape2D>(
                set.size());

        // convert the result
        for (Curve2D curve : set.curves()) {
            if (curve instanceof CircleArc2D)
                result.add((CircleArc2D) curve);
            if (curve instanceof Circle2D)
                result.add((Circle2D) curve);
        }
        return result;
    }

    // ===================================================================
    // methods of Shape interface

    /**
     * Returns true if the point p lies on the ellipse, with precision given by
     * Shape2D.ACCURACY.
     */
    public boolean contains(Point2D p) {
        return contains(p.x(), p.y());
    }

    /**
     * Returns true if the point (x, y) lies exactly on the circle.
     */
    public boolean contains(double x, double y) {
        return abs(distance(x, y)) <= Shape2D.ACCURACY;
    }

    public Path appendPath(Path path) {
        double cot = cos(theta);
        double sit = sin(theta);
        double cost, sint;

        if (direct) {
            // Counter-clockwise circle
            for (double t = .1; t < PI * 2; t += .1) {
                cost = cos(t);
                sint = sin(t);
                path.lineTo((float) (xc + r * cost * cot - r * sint * sit),
                        (float) (yc + r * cost * sit + r * sint * cot));
            }
        } else {
            // Clockwise circle
            for (double t = .1; t < PI * 2; t += .1) {
                cost = cos(t);
                sint = sin(t);
                path.lineTo((float) (xc + r * cost * cot + r * sint * sit),
                        (float) (yc + r * cost * sit - r * sint * cot));
            }
        }

        // line to first point
        path.lineTo((float) (xc + r * cot), (float) (yc + r * sit));

        return path;
    }

    public void draw(Canvas g2, Paint p) {
        g2.drawCircle((float) (xc - r), (float) (yc - r),
                (float) ((float) 2 * r), p);
    }

    // ===================================================================
    // methods implementing GeometricObject2D interface

    /*
     * (non-Javadoc)
     * 
     * @see
     * math.geom2d.GeometricObject2D#almostEquals(math.geom2d.GeometricObject2D,
     * double)
     */
    public boolean almostEquals(GeometricObject2D obj, double eps) {
        if (!(obj instanceof Circle2D))
            return false;

        Circle2D circle = (Circle2D) obj;

        if (abs(circle.xc - xc) > eps)
            return false;
        if (abs(circle.yc - yc) > eps)
            return false;
        if (abs(circle.r - r) > eps)
            return false;
        if (circle.direct != direct)
            return false;
        return true;
    }

    /**
     * Returns bounding box of the circle.
     */
    public Box2D boundingBox() {
        return new Box2D(xc - r, xc + r, yc - r, yc + r);
    }

    /**
     * Transforms this circle by an affine transform. If the transformed shape
     * is a circle (ellipse with equal axis lengths), returns an instance of
     * Circle2D. The resulting ellipse is direct if this ellipse and the
     * transform are either both direct or both indirect.
     */
    public EllipseShape2D transform(AffineTransform2D trans) {
        // When the transform is not a similarity, should switch to EllipseArc
        // computation
        if (!AffineTransform2D.isSimilarity(trans)) {
            return this.asEllipse().transform(trans);
        }

        // If transform is a similarity, the result is a circle
        Point2D center = this.center().transform(trans);
        Point2D p1 = this.firstPoint().transform(trans);

        boolean direct = !this.direct ^ trans.isDirect();
        Circle2D result = new Circle2D(center, center.distance(p1), direct);
        return result;
    }

    // ===================================================================
    // methods of Object interface

    @Override
    public String toString() {
        return String.format(Locale.US, "Circle2D(%7.2f,%7.2f,%7.2f,%s)", xc,
                yc, r, direct ? "true" : "false");
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj instanceof Circle2D) {
            Circle2D that = (Circle2D) obj;

            // Compare each field
            if (!EqualUtils.areEqual(this.xc, that.xc))
                return false;
            if (!EqualUtils.areEqual(this.yc, that.yc))
                return false;
            if (!EqualUtils.areEqual(this.r, that.r))
                return false;
            if (this.direct != that.direct)
                return false;

            return true;
        }
        return super.equals(obj);
    }

    /**
     * @deprecated use copy constructor instead (0.11.2)
     */
    @Deprecated
    @Override
    public Circle2D clone() {
        return new Circle2D(xc, yc, r, direct);
    }

}
 public abstract class Curves2D {

    // ===================================================================
    // static methods

    /**
     * Mapping of the parameter t, relative to the local curve, into the
     * interval [0 1], [0 1[, ]0 1], or ]0 1[, depending on the values of t0 and
     * t1.
     * 
     * @param t
     *            a value between t0 and t1
     * @param t0
     *            the lower bound of parameterization domain
     * @param t1
     *            the upper bound of parameterization domain
     * @return a value between 0 and 1
     */
    public static double toUnitSegment(double t, double t0, double t1) {
        if (t <= t0)
            return 0;
        if (t >= t1)
            return 1;

        if (t0 == NEGATIVE_INFINITY && t1 == POSITIVE_INFINITY)
            return Math.atan(t) / Math.PI + .5;

        if (t0 == NEGATIVE_INFINITY)
            return Math.atan(t - t1) * 2 / Math.PI + 1;

        if (t1 == POSITIVE_INFINITY)
            return Math.atan(t - t0) * 2 / Math.PI;

        // t0 and t1 are both finite
        return (t - t0) / (t1 - t0);
    }

    /**
     * Transforms the value t between 0 and 1 in a value comprised between t0
     * and t1.
     * 
     * @param t
     *            a value between 0 and 1
     * @param t0
     *            the lower bound of parameterization domain
     * @param t1
     *            the upper bound of parameterization domain
     * @return a value between t0 and t1
     */
    public static double fromUnitSegment(double t, double t0, double t1) {
        if (t <= 0)
            return t0;
        if (t >= 1)
            return t1;

        if (t0 == NEGATIVE_INFINITY && t1 == POSITIVE_INFINITY)
            return Math.tan((t - .5) * Math.PI);

        if (t0 == NEGATIVE_INFINITY)
            return Math.tan((t - 1) * Math.PI / 2) + t1;

        if (t1 == POSITIVE_INFINITY)
            return Math.tan(t * Math.PI / 2) + t0;

        // t0 and t1 are both finite
        return t * (t1 - t0) + t0;
    }

    /**
     * Clip a curve, and return a CurveSet2D. If the curve is totally outside
     * the box, return a CurveSet2D with 0 curves inside. If the curve is
     * totally inside the box, return a CurveSet2D with only one curve, which is
     * the original curve.
     */
    public static CurveSet2D<? extends Curve2D> clipCurve(Curve2D curve,
            Box2D box) {
        // Case of continuous curve:
        // convert the result of ClipContinuousCurve to CurveSet of Curve2D
        if (curve instanceof ContinuousCurve2D)
            return Curves2D.clipContinuousCurve((ContinuousCurve2D) curve, box);

        // case of a CurveSet2D
        if (curve instanceof CurveSet2D<?>)
            return Curves2D.clipCurveSet((CurveSet2D<?>) curve, box);

        // Unknown case
        System.err.println("Unknown curve class in Box2D.clipCurve()");
        return new CurveArray2D<Curve2D>();
    }

    /**
     * clip a CurveSet2D.
     */
    public static CurveSet2D<? extends Curve2D> clipCurveSet(
            CurveSet2D<?> curveSet, Box2D box) {
        // Clip the current curve
        CurveArray2D<Curve2D> result = new CurveArray2D<Curve2D>();
        CurveSet2D<?> clipped;

        // a clipped parts of current curve to the result
        for (Curve2D curve : curveSet) {
            clipped = Curves2D.clipCurve(curve, box);
            for (Curve2D clippedPart : clipped)
                result.add(clippedPart);
        }

        // return a set of curves
        return result;
    }

    /**
     * <p>
     * Clips a continuous curve and returns a set of continuous curves.
     * </p>
     * <p>
     * Algorithm is the following one:
     * <ul>
     * <li>Compute intersections between curve and box boundary</li>
     * <li>Sort intersections according to their position on the curve</li>
     * <li>Remove intersections which do not cross (they only touch) the box
     * boundary</li>
     * <li>Add portions of curves located between two intersections and inside
     * of the box</li>
     * </ul>
     * </p>
     * <p>
     * Special processing is added when the first point of the curve lies on the
     * boundary of the box, and when the curve is closed (when the first point
     * of the curve is inside the box, the method return a portion of curve
     * between the last intersection and the first intersection).
     * </p>
     */
    public static CurveSet2D<ContinuousCurve2D> clipContinuousCurve(
            ContinuousCurve2D curve, Box2D box) {

        // Create CurveSet2D for storing the result
        CurveArray2D<ContinuousCurve2D> res = new CurveArray2D<ContinuousCurve2D>();

        // ------ Compute ordered list of intersections

        // create array of intersection points
        ArrayList<Point2D> points = new ArrayList<Point2D>();

        // add all the intersections with edges of the box boundary
        for (LinearShape2D edge : box.edges())
            points.addAll(curve.intersections(edge));

        // convert list to point array, sorted wrt to their position on the
        // curve
        SortedSet<Double> set = new TreeSet<Double>();
        for (Point2D p : points)
            set.add(Double.valueOf(curve.position(p)));

        // iterator on the intersection positions
        Iterator<Double> iter = set.iterator();

        // ----- remove intersections which do not cross the boundary

        // init arrays
        int nInter = set.size();
        double[] positions = new double[nInter + 2];
        double[] between = new double[nInter + 1];

        // fill up array of positions, with extreme positions of curve
        positions[0] = curve.t0();
        for (int i = 0; i < nInter; i++)
            positions[i + 1] = iter.next();
        positions[nInter + 1] = curve.t1();

        // compute positions of points between intersections
        for (int i = 0; i < nInter + 1; i++)
            between[i] = choosePosition(positions[i], positions[i + 1]);

        // array of positions to remove
        ArrayList<Double> toRemove = new ArrayList<Double>();

        // remove an intersection point if the curve portions before and after
        // are both either inside or outside of the box.
        for (int i = 0; i < nInter; i++) {
            Point2D p1 = curve.point(between[i]);
            Point2D p2 = curve.point(between[i + 1]);
            boolean b1 = box.contains(p1);
            boolean b2 = box.contains(p2);
            if (b1 == b2)
                toRemove.add(positions[i + 1]);
        }

        // remove unnecessary intersections
        set.removeAll(toRemove);

        // iterator on the intersection positions
        iter = set.iterator();

        // ----- Check case of no intersection point

        // if no intersection point, the curve is totally either inside or
        // outside the box
        if (set.size() == 0) {
            // compute position of an arbitrary point on the curve
            Point2D point;
            if (curve.isBounded()) {
                point = curve.firstPoint();
            } else {
                double pos = choosePosition(curve.t0(), curve.t1());
                point = curve.point(pos);
            }

            // if the box contains a point, it contains the whole curve
            if (box.contains(point))
                res.add(curve);
            return res;
        }

        // ----- Check if the curve starts inside of the box

        // the flag for a curve that starts inside the box
        boolean inside = false;
        boolean touch = false;

        // different behavior if curve is bounded or not
        double t0 = curve.t0();
        if (isLeftInfinite(curve)) {
            // choose point between -infinite and first intersection
            double pos = choosePosition(t0, set.iterator().next());
            inside = box.contains(curve.point(pos));
        } else {
            // extract first point of the curve
            Point2D point = curve.firstPoint();
            inside = box.contains(point);

            // if first point is on the boundary, then choose another point
            // located between first point and first intersection
            if (box.boundary().contains(point)) {
                touch = true;

                double pos = choosePosition(t0, iter.next());
                while (Math.abs(pos - t0) < Shape2D.ACCURACY && iter.hasNext())
                    pos = choosePosition(t0, iter.next());
                if (Math.abs(pos - t0) < Shape2D.ACCURACY)
                    pos = choosePosition(t0, curve.t1());
                point = curve.point(pos);

                // remove the first point from the list of intersections
                set.remove(t0);

                // if inside, adds the first portion of the curve,
                // and remove next intersection
                if (box.contains(point)) {
                    pos = set.iterator().next();
                    res.add(curve.subCurve(t0, pos));
                    set.remove(pos);
                }

                // update iterator
                iter = set.iterator();

                inside = false;
            }
        }

        // different behavior depending if first point lies inside the box
        double pos0 = Double.NaN;
        if (inside && !touch)
            if (curve.isClosed())
                pos0 = iter.next();
            else
                res.add(curve.subCurve(curve.t0(), iter.next()));

        // ----- add portions of curve between each couple of intersections

        double pos1, pos2;
        while (iter.hasNext()) {
            pos1 = iter.next().doubleValue();
            if (iter.hasNext())
                pos2 = iter.next().doubleValue();
            else
                pos2 = curve.isClosed() && !touch ? pos0 : curve.t1();
            res.add(curve.subCurve(pos1, pos2));
        }

        return res;
    }

    /**
     * Clip a continuous smooth curve. Currently just call the static method
     * clipContinuousCurve, and cast clipped curves.
     */
    public static CurveSet2D<SmoothCurve2D> clipSmoothCurve(
            SmoothCurve2D curve, Box2D box) {
        CurveArray2D<SmoothCurve2D> result = new CurveArray2D<SmoothCurve2D>();
        for (ContinuousCurve2D cont : Curves2D.clipContinuousCurve(curve, box))
            if (cont instanceof SmoothCurve2D)
                result.add((SmoothCurve2D) cont);

        return result;
    }

    /**
     * Clip a continuous smooth curve by the half-plane defined by a line. This
     * method is mainly used to help debugging when implementing curves.
     */
    public static CurveSet2D<SmoothCurve2D> clipSmoothCurve(
            SmoothCurve2D curve, StraightLine2D line) {

        // get the list of intersections with the line
        ArrayList<Point2D> list = new ArrayList<Point2D>();
        list.addAll(curve.intersections(line));

        // convert list to point array, sorted with respect to their position
        // on the curve, but do not add tangent points with curvature greater
        // than 0
        SortedSet<java.lang.Double> set = new TreeSet<java.lang.Double>();
        double position;
        Vector2D vector = line.direction();
        for (Point2D point : list) {
            // get position of intersection on the curve (use project to avoid
            // round-off problems)
            position = curve.project(point);

            // Condition of colinearity with direction vector of line
            Vector2D tangent = curve.tangent(position);
            if (Vector2D.isColinear(tangent, vector)) {
                // condition on the curvature (close to zero = cusp point)
                double curv = curve.curvature(position);
                if (Math.abs(curv) > Shape2D.ACCURACY)
                    continue;
            }
            set.add(new java.lang.Double(position));
        }

        // Create CurveSet2D for storing the result
        CurveArray2D<SmoothCurve2D> res = new CurveArray2D<SmoothCurve2D>();

        // extract first point of the curve, or a point arbitrarily far
        Point2D point1;
        if (Double.isInfinite(curve.t0()))
            point1 = curve.point(-1000);
        else
            point1 = curve.firstPoint();

        // Extract first valid intersection point, if it exists
        double pos1, pos2;
        Iterator<java.lang.Double> iter = set.iterator();

        // if no intersection point, the curve is either totally inside
        // or totally outside the box
        if (!iter.hasNext()) {
            // Find a point on the curve and not on the line
            // First tries with first point
            double t0 = curve.t0();
            if (t0 == NEGATIVE_INFINITY)
                t0 = -100;
            while (line.contains(point1)) {
                double t1 = curve.t1();
                if (t1 == POSITIVE_INFINITY)
                    t1 = +100;
                t0 = (t0 + t1) / 2;
                point1 = curve.point(t0);
            }
            if (line.signedDistance(point1) < 0)
                res.add(curve);
            return res;
        }

        // different behavior depending if first point lies inside the box
        if (line.signedDistance(point1) < 0 && !line.contains(point1)) {
            pos1 = iter.next().doubleValue();
            res.add(curve.subCurve(curve.t0(), pos1));
        }

        // add the portions of curve between couples of intersections
        while (iter.hasNext()) {
            pos1 = iter.next().doubleValue();
            if (iter.hasNext())
                pos2 = iter.next().doubleValue();
            else
                pos2 = curve.t1();
            res.add(curve.subCurve(pos1, pos2));
        }

        return res;
    }

    public static int findNextCurveIndex(double[] positions, double pos) {
        int ind = -1;
        double posMin = java.lang.Double.MAX_VALUE;
        for (int i = 0; i < positions.length; i++) {
            // avoid NaN
            if (java.lang.Double.isNaN(positions[i]))
                continue;
            // avoid values before
            if (positions[i] - pos < Shape2D.ACCURACY)
                continue;

            // test if closer that other points
            if (positions[i] < posMin) {
                ind = i;
                posMin = positions[i];
            }
        }

        if (ind != -1)
            return ind;

        // if not found, return index of smallest value (mean that pos is last
        // point on the boundary, so we need to start at the beginning).
        for (int i = 0; i < positions.length; i++) {
            if (java.lang.Double.isNaN(positions[i]))
                continue;
            if (positions[i] - posMin < Shape2D.ACCURACY) {
                ind = i;
                posMin = positions[i];
            }
        }
        return ind;
    }

    /**
     * Choose an arbitrary position between positions t0 and t1, which can be
     * infinite.
     * 
     * @param t0
     *            the first bound of a curve parameterization
     * @param t1
     *            the second bound of a curve parameterization
     * @return a position located between t0 and t1
     */
    public static double choosePosition(double t0, double t1) {
        if (Double.isInfinite(t0)) {
            if (Double.isInfinite(t1))
                return 0;
            return t1 - 10;
        }

        if (Double.isInfinite(t1))
            return t0 + 10;

        return (t0 + t1) / 2;
    }

    public static boolean isLeftInfinite(Curve2D curve) {
        // basic check
        if (curve.isBounded())
            return false;

        // extract the first smooth curve
        ContinuousCurve2D cont = curve.continuousCurves().iterator().next();
        SmoothCurve2D smooth = cont.smoothPieces().iterator().next();

        // check first position of first curve
        return Double.isInfinite(smooth.t0());
    }

    public static boolean isRightInfinite(Curve2D curve) {
        // basic check
        if (curve.isBounded())
            return false;

        // extract the first smooth curve
        SmoothCurve2D lastCurve = null;
        for (ContinuousCurve2D cont : curve.continuousCurves())
            for (SmoothCurve2D smooth : cont.smoothPieces())
                lastCurve = smooth;

        // check last position of last curve
        return Double.isInfinite(lastCurve.t1());
    }

    public static ContinuousCurve2D getFirstContinuousCurve(Curve2D curve) {
        if (curve instanceof ContinuousCurve2D)
            return (ContinuousCurve2D) curve;

        Collection<? extends ContinuousCurve2D> curves = curve
                .continuousCurves();
        if (curves.size() == 0)
            return null;

        return curves.iterator().next();
    }

    public static ContinuousCurve2D getLastContinuousCurve(Curve2D curve) {
        if (curve instanceof ContinuousCurve2D)
            return (ContinuousCurve2D) curve;
        ContinuousCurve2D res = null;
        for (ContinuousCurve2D continuous : curve.continuousCurves())
            res = continuous;
        return res;
    }

    public static SmoothCurve2D getFirstSmoothCurve(Curve2D curve) {
        if (curve instanceof SmoothCurve2D)
            return (SmoothCurve2D) curve;

        // Extract last continuous piece of the last continuous curve
        ContinuousCurve2D continuous = getFirstContinuousCurve(curve);
        if (continuous == null)
            return null;

        Collection<? extends SmoothCurve2D> curves = continuous.smoothPieces();
        if (curves.size() == 0)
            return null;

        return curves.iterator().next();
    }

    public static SmoothCurve2D getLastSmoothCurve(Curve2D curve) {
        if (curve instanceof SmoothCurve2D)
            return (SmoothCurve2D) curve;

        // Extract last continuous piece of the last continuous curve
        ContinuousCurve2D continuous = getLastContinuousCurve(curve);
        SmoothCurve2D res = null;
        for (SmoothCurve2D smooth : continuous.smoothPieces())
            res = smooth;
        return res;
    }

    public enum JunctionType {
        SALIENT, REENTRANT, FLAT
    }

    /**
     * Returns the junction type between the end of first curve and the
     * beginning of second curve.
     */
    public static JunctionType getJunctionType(Curve2D prev, Curve2D next) {

        // Extract corresponding smooth curves
        SmoothCurve2D smoothPrev = getLastSmoothCurve(prev);
        SmoothCurve2D smoothNext = getFirstSmoothCurve(next);

        // tangent vectors of the 2 neighbor curves
        Vector2D v1 = computeTangent(smoothPrev, smoothPrev.t1());
        Vector2D v2 = computeTangent(smoothNext, smoothNext.t0());

        // check if angle between vectors is acute or obtuse
        double diff = Angle2D.angle(v1, v2);
        double eps = 1e-12;
        if (diff < eps || diff > (2 * PI - eps)) {
            return JunctionType.FLAT;
        }

        if (diff < PI - eps) {
            // Acute angle
            return JunctionType.SALIENT;
        }

        if (diff > PI + eps) {
            // obtuse angle
            return JunctionType.REENTRANT;
        }

        // Extract curvatures of both curves around singular point
        double kappaPrev = smoothPrev.curvature(smoothPrev.t1());
        double kappaNext = smoothNext.curvature(smoothNext.t0());

        // get curvature signs
        double sp = Math.signum(kappaPrev);
        double sn = Math.signum(kappaNext);

        // Both curvatures have same sign
        if (sn * sp > 0) {
            if (sn > 0)
                return JunctionType.REENTRANT;
            else
                return JunctionType.SALIENT;
        }

        // One of the curvature is zero (straight curve)
        if (sp == 0) {
            if (sn < 0)
                return JunctionType.SALIENT;
            else if (sn > 0)
                return JunctionType.REENTRANT;
            else {
                // Both curvatures are zero => problem...
                throw new IllegalArgumentException("colinear lines...");
            }
        } else if (sn == 0) {
            if (sp < 0)
                return JunctionType.SALIENT;
            else if (sp > 0)
                return JunctionType.REENTRANT;
        }

        // curvatures have opposite signs: curves point in opposite directions.
        // We need to check curvature values
        if (sp == 1 && sn == -1) {
            return abs(kappaPrev) < abs(kappaNext) ? JunctionType.SALIENT
                    : JunctionType.REENTRANT;
        } else if (sp == -1 && sn == 1) {
            return abs(kappaPrev) > abs(kappaNext) ? JunctionType.SALIENT
                    : JunctionType.REENTRANT;
        }

        throw new RuntimeException("Could not determine junction type");
    }

    /**
     * Computes the tangent of the curve at the given position.
     */
    private static Vector2D computeTangent(ContinuousCurve2D curve, double pos) {
        // For smooth curves, simply call the getTangent() method
        if (curve instanceof SmoothCurve2D)
            return ((SmoothCurve2D) curve).tangent(pos);

        // Extract sub curve and recursively call this method on the sub curve
        if (curve instanceof CurveSet2D<?>) {
            CurveSet2D<?> curveSet = (CurveSet2D<?>) curve;
            double pos2 = curveSet.localPosition(pos);
            Curve2D subCurve = curveSet.childCurve(pos);
            return computeTangent((ContinuousCurve2D) subCurve, pos2);
        }

        throw new IllegalArgumentException(
                "Unknown type of curve: should be either continuous or curveset");
    }

}
 public class StraightLine2D extends AbstractLine2D implements SmoothContour2D,
        Cloneable, CircleLine2D {

    // ===================================================================
    // constants

    // ===================================================================
    // class variables

    // ===================================================================
    // static methods

    /**
     * Creates a straight line going through a point and with a given angle.
     * 
     * @deprecated since 0.11.1
     */
    @Deprecated
    public static StraightLine2D create(Point2D point, double angle) {
        return new StraightLine2D(point.x(), point.y(), Math.cos(angle),
                Math.sin(angle));
    }

    /**
     * Creates a straight line through 2 points.
     * 
     * @deprecated since 0.11.1
     */
    @Deprecated
    public static StraightLine2D create(Point2D p1, Point2D p2) {
        return new StraightLine2D(p1, p2);
    }

    /**
     * Creates a straight line through a point and with a given direction
     * vector.
     * 
     * @deprecated since 0.11.1
     */
    @Deprecated
    public static StraightLine2D create(Point2D origin, Vector2D direction) {
        return new StraightLine2D(origin, direction);
    }

    /**
     * Creates a vertical straight line through the given point.
     * 
     * @since 0.10.3
     */
    public static StraightLine2D createHorizontal(Point2D origin) {
        return new StraightLine2D(origin, new Vector2D(1, 0));
    }

    /**
     * Creates a vertical straight line through the given point.
     * 
     * @since 0.10.3
     */
    public static StraightLine2D createVertical(Point2D origin) {
        return new StraightLine2D(origin, new Vector2D(0, 1));
    }

    /**
     * Creates a median between 2 points.
     * 
     * @param p1
     *            one point
     * @param p2
     *            another point
     * @return the median of points p1 and p2
     * @since 0.6.3
     */
    public static StraightLine2D createMedian(Point2D p1, Point2D p2) {
        Point2D mid = Point2D.midPoint(p1, p2);
        StraightLine2D line = StraightLine2D.create(p1, p2);
        return StraightLine2D.createPerpendicular(line, mid);
    }

    /**
     * Returns a new Straight line, parallel to another straight object (ray,
     * straight line or edge), and going through the given point.
     * 
     * @since 0.6.3
     */
    public static StraightLine2D createParallel(LinearShape2D line,
            Point2D point) {
        return new StraightLine2D(line, point);
    }

    /**
     * Returns a new Straight line, parallel to another straight object (ray,
     * straight line or edge), and going through the given point.
     * 
     * @since 0.6.3
     */
    public static StraightLine2D createParallel(LinearShape2D linear, double d) {
        StraightLine2D line = linear.supportingLine();
        double d2 = d / Math.hypot(line.dx, line.dy);
        return new StraightLine2D(line.x0 + line.dy * d2, line.y0 - line.dx
                * d2, line.dx, line.dy);
    }

    /**
     * Returns a new Straight line, perpendicular to a straight object (ray,
     * straight line or edge), and going through the given point.
     * 
     * @since 0.6.3
     */
    public static StraightLine2D createPerpendicular(LinearShape2D linear,
            Point2D point) {
        StraightLine2D line = linear.supportingLine();
        return new StraightLine2D(point, -line.dy, line.dx);
    }

    /**
     * Returns a new Straight line, with the given coefficient of the cartesian
     * equation (a*x + b*y + c = 0).
     */
    public static StraightLine2D createCartesian(double a, double b, double c) {
        return new StraightLine2D(a, b, c);
    }

    /**
     * Computes the intersection point of the two (infinite) lines going through
     * p1 and p2 for the first one, and p3 and p4 for the second one. Returns
     * null if two lines are parallel.
     */
    public static Point2D getIntersection(Point2D p1, Point2D p2, Point2D p3,
            Point2D p4) {
        StraightLine2D line1 = new StraightLine2D(p1, p2);
        StraightLine2D line2 = new StraightLine2D(p3, p4);
        return line1.intersection(line2);
    }

    // ===================================================================
    // constructors

    /** Empty constructor: a straight line corresponding to horizontal axis. */
    public StraightLine2D() {
        this(0, 0, 1, 0);
    }

    /** Defines a new Straight line going through the two given points. */
    public StraightLine2D(Point2D point1, Point2D point2) {
        this(point1, new Vector2D(point1, point2));
    }

    /**
     * Defines a new Straight line going through the given point, and with the
     * specified direction vector.
     */
    public StraightLine2D(Point2D point, Vector2D direction) {
        this(point.x(), point.y(), direction.x(), direction.y());
    }

    /**
     * Defines a new Straight line going through the given point, and with the
     * specified direction vector.
     */
    public StraightLine2D(Point2D point, double dx, double dy) {
        this(point.x(), point.y(), dx, dy);
    }

    /**
     * Defines a new Straight line going through the given point, and with the
     * specified direction given by angle.
     */
    public StraightLine2D(Point2D point, double angle) {
        this(point.x(), point.y(), Math.cos(angle), Math.sin(angle));
    }

    /*
     * Defines a new Straight line going through the point (xp, yp) and with the
     * direction dx, dy.
     */
    public StraightLine2D(double xp, double yp, double dx, double dy) {
        super(xp, yp, dx, dy);
    }

    /**
     * Copy constructor: Defines a new Straight line at the same position and
     * with the same direction than an other straight object (line, edge or
     * ray).
     */
    public StraightLine2D(LinearShape2D line) {
        this(line.origin(), line.direction());
    }

    /**
     * Defines a new Straight line, parallel to another straigth object (ray,
     * straight line or edge), and going through the given point.
     */
    public StraightLine2D(LinearShape2D line, Point2D point) {
        this(point, line.direction());
    }

    /**
     * Defines a new straight line, from the coefficients of the cartesian
     * equation. The starting point of the line is then the point of the line
     * closest to the origin, and the direction vector has unit norm.
     */
    public StraightLine2D(double a, double b, double c) {
        this(0, 0, 1, 0);
        double d = a * a + b * b;
        x0 = -a * c / d;
        y0 = -b * c / d;
        double theta = Math.atan2(-a, b);
        dx = Math.cos(theta);
        dy = Math.sin(theta);
    }

    // ===================================================================
    // methods specific to StraightLine2D

    /**
     * Returns a new Straight line, parallel to another straight object (ray,
     * straight line or edge), and going through the given point.
     */
    public StraightLine2D parallel(Point2D point) {
        return new StraightLine2D(point, dx, dy);
    }

    // ===================================================================
    // methods implementing the CirculinearCurve2D interface

    /**
     * Returns the parallel line located at a distance d from the line. Distance
     * is positive in the 'right' side of the line (outside of the limiting
     * half-plane), and negative in the 'left' of the line.
     * 
     * @throws DegeneratedLine2DException
     *             if line direction vector is null
     */
    public StraightLine2D parallel(double d) {
        double d2 = Math.hypot(this.dx, this.dy);
        if (Math.abs(d2) < Shape2D.ACCURACY)
            throw new DegeneratedLine2DException(
                    "Can not compute parallel of degenerated line", this);
        d2 = d / d2;
        return new StraightLine2D(x0 + dy * d2, y0 - dx * d2, dx, dy);
    }

    /**
     * Returns a new Straight line, parallel to another straight object (ray,
     * straight line or edge), and going through the given point.
     */
    @Override
    public StraightLine2D perpendicular(Point2D point) {
        return new StraightLine2D(point, -dy, dx);
    }

    /*
     * (non-Javadoc)
     * 
     * @see
     * math.geom2d.circulinear.CirculinearCurve2D#transform(math.geom2d.transform
     * .CircleInversion2D)
     */
    @Override
    public CircleLine2D transform(CircleInversion2D inv) {
        // Extract inversion parameters
        Point2D center = inv.center();
        double r = inv.radius();

        // projection of inversion center on the line
        Point2D po = this.projectedPoint(center);
        double d = this.distance(center);

        // Degenerate case of a point belonging to the line:
        // the transform is the line itself.
        if (Math.abs(d) < Shape2D.ACCURACY) {
            return new StraightLine2D(this);
        }

        // angle from center to line
        double angle = Angle2D.horizontalAngle(center, po);

        // center of transformed circle
        double r2 = r * r / d / 2;
        Point2D c2 = Point2D.createPolar(center, r2, angle);

        // choose direction of circle arc
        boolean direct = this.isInside(center);

        // return the created circle
        return new Circle2D(c2, r2, direct);
    }

    // ===================================================================
    // methods specific to Boundary2D interface

    /*
     * (non-Javadoc)
     * 
     * @see math.geom2d.domain.Boundary2D#domain()
     */
    public CirculinearDomain2D domain() {
        return new GenericCirculinearDomain2D(this);
    }

    public void draw(Canvas g2, Paint p) {
        g2.drawPath(getGeneralPath(), p);
        // g2.fill(this.getGeneralPath());
    }

    // ===================================================================
    // methods specific to OrientedCurve2D interface

    /*
     * (non-Javadoc)
     * 
     * @see math.geom2d.domain.OrientedCurve2D#windingAngle(Point2D)
     */
    @Override
    public double windingAngle(Point2D point) {

        double angle1 = Angle2D.horizontalAngle(-dx, -dy);
        double angle2 = Angle2D.horizontalAngle(dx, dy);

        if (this.isInside(point)) {
            if (angle2 > angle1)
                return angle2 - angle1;
            else
                return 2 * Math.PI - angle1 + angle2;
        } else {
            if (angle2 > angle1)
                return angle2 - angle1 - 2 * Math.PI;
            else
                return angle2 - angle1;
        }
    }

    // ===================================================================
    // methods implementing the ContinuousCurve2D interface

    /**
     * Throws an exception when called.
     */
    @Override
    public Polyline2D asPolyline(int n) {
        throw new UnboundedShape2DException(this);
    }

    // ===================================================================
    // methods implementing the Curve2D interface

    /** Throws an infiniteShapeException */
    @Override
    public Point2D firstPoint() {
        throw new UnboundedShape2DException(this);
    }

    /** Throws an infiniteShapeException */
    @Override
    public Point2D lastPoint() {
        throw new UnboundedShape2DException(this);
    }

    /** Returns an empty list of points. */
    @Override
    public Collection<Point2D> singularPoints() {
        return new ArrayList<Point2D>(0);
    }

    /** Returns false, whatever the position. */
    @Override
    public boolean isSingular(double pos) {
        return false;
    }

    /**
     * Returns the parameter of the first point of the line, which is always
     * Double.NEGATIVE_INFINITY.
     */
    public double t0() {
        return Double.NEGATIVE_INFINITY;
    }

    /**
     * @deprecated replaced by t0() (since 0.11.1).
     */
    @Deprecated
    public double getT0() {
        return t0();
    }

    /**
     * Returns the parameter of the last point of the line, which is always
     * Double.POSITIVE_INFINITY.
     */
    public double t1() {
        return Double.POSITIVE_INFINITY;
    }

    /**
     * @deprecated replaced by t1() (since 0.11.1).
     */
    @Deprecated
    public double getT1() {
        return this.t1();
    }

    /**
     * Returns the point specified with the parametric representation of the
     * line.
     */
    public Point2D point(double t) {
        return new Point2D(x0 + dx * t, y0 + dy * t);
    }

    /**
     * Need to override to cast the type.
     */
    @Override
    public Collection<? extends StraightLine2D> continuousCurves() {
        ArrayList<StraightLine2D> list = new ArrayList<StraightLine2D>(1);
        list.add(this);
        return list;
    }

    /**
     * Returns the straight line with same origin but with opposite direction
     * vector.
     */
    public StraightLine2D reverse() {
        return new StraightLine2D(this.x0, this.y0, -this.dx, -this.dy);
    }

    public Path appendPath(Path path) {
        throw new UnboundedShape2DException(this);
    }

    // ===================================================================
    // methods implementing the Shape2D interface

    /** Always returns false, because a line is not bounded. */
    public boolean isBounded() {
        return false;
    }

    /**
     * Returns the distance of the point (x, y) to this straight line.
     */
    @Override
    public double distance(double x, double y) {
        Point2D proj = super.projectedPoint(x, y);
        return proj.distance(x, y);
    }

    public Box2D boundingBox() {
        if (Math.abs(dx) < Shape2D.ACCURACY)
            return new Box2D(x0, x0, Double.NEGATIVE_INFINITY,
                    Double.POSITIVE_INFINITY);
        if (Math.abs(dy) < Shape2D.ACCURACY)
            return new Box2D(Double.NEGATIVE_INFINITY,
                    Double.POSITIVE_INFINITY, x0, y0);

        return new Box2D(Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY,
                Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY);
    }

    /**
     * Returns the transformed line. The result is still a StraightLine2D.
     */
    @Override
    public StraightLine2D transform(AffineTransform2D trans) {
        double[] tab = trans.coefficients();
        return new StraightLine2D(x0 * tab[0] + y0 * tab[1] + tab[2], x0
                * tab[3] + y0 * tab[4] + tab[5], dx * tab[0] + dy * tab[1], dx
                * tab[3] + dy * tab[4]);
    }

    // ===================================================================
    // methods implementing the Shape interface

    /**
     * Returns true if the point (x, y) lies on the line, with precision given
     * by Shape2D.ACCURACY.
     */
    public boolean contains(double x, double y) {
        return super.supportContains(x, y);
    }

    /**
     * Returns true if the point p lies on the line, with precision given by
     * Shape2D.ACCURACY.
     */
    @Override
    public boolean contains(Point2D p) {
        return super.supportContains(p.x(), p.y());
    }

    /** Throws an infiniteShapeException */
    public Path getGeneralPath() {
        throw new UnboundedShape2DException(this);
    }

    // ===================================================================
    // methods implementing the GeometricObject2D interface

    /*
     * (non-Javadoc)
     * 
     * @see
     * math.geom2d.GeometricObject2D#almostEquals(math.geom2d.GeometricObject2D,
     * double)
     */
    public boolean almostEquals(GeometricObject2D obj, double eps) {
        if (this == obj)
            return true;

        if (!(obj instanceof StraightLine2D))
            return false;
        StraightLine2D line = (StraightLine2D) obj;

        if (Math.abs(x0 - line.x0) > eps)
            return false;
        if (Math.abs(y0 - line.y0) > eps)
            return false;
        if (Math.abs(dx - line.dx) > eps)
            return false;
        if (Math.abs(dy - line.dy) > eps)
            return false;

        return true;
    }

    // ===================================================================
    // methods overriding the Object class

    @Override
    public String toString() {
        return new String("StraightLine2D(" + x0 + "," + y0 + "," + dx + ","
                + dy + ")");
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (!(obj instanceof StraightLine2D))
            return false;
        StraightLine2D that = (StraightLine2D) obj;

        // Compare each field
        if (!EqualUtils.areEqual(this.x0, that.x0))
            return false;
        if (!EqualUtils.areEqual(this.y0, that.y0))
            return false;
        if (!EqualUtils.areEqual(this.dx, that.dx))
            return false;
        if (!EqualUtils.areEqual(this.dy, that.dy))
            return false;

        return true;
    }

    /**
     * @deprecated use copy constructor instead (0.11.2)
     */
    @Deprecated
    @Override
    public StraightLine2D clone() {
        return new StraightLine2D(x0, y0, dx, dy);
    }
}
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import math.geom2d.Point2D;
import math.geom2d.Shape2D;
import math.geom2d.circulinear.BoundaryPolyCirculinearCurve2D;
import math.geom2d.circulinear.CirculinearBoundary2D;
import math.geom2d.circulinear.CirculinearContinuousCurve2D;
import math.geom2d.circulinear.CirculinearContour2D;
import math.geom2d.circulinear.CirculinearContourArray2D;
import math.geom2d.circulinear.CirculinearCurve2D;
import math.geom2d.circulinear.CirculinearCurveArray2D;
import math.geom2d.circulinear.CirculinearCurves2D;
import math.geom2d.circulinear.CirculinearDomain2D;
import math.geom2d.circulinear.CirculinearElement2D;
import math.geom2d.circulinear.GenericCirculinearDomain2D;
import math.geom2d.circulinear.GenericCirculinearRing2D;
import math.geom2d.circulinear.PolyCirculinearCurve2D;
import math.geom2d.conic.Circle2D;
import math.geom2d.curve.Curves2D;
import math.geom2d.line.StraightLine2D;
import math.geom2d.point.PointSet2D;

        }

        // extract collection of parallel curves, that connect each other
        Collection<CirculinearContinuousCurve2D> parallelCurves = getParallelElements(
                curve, dist);

        // Create a new circulinear continuous curve with the set of parallel
        // curves
        return new PolyCirculinearCurve2D(parallelCurves, curve.isClosed());
    }

    private Collection<CirculinearContinuousCurve2D> getParallelElements(
            CirculinearContinuousCurve2D curve, double dist) {

        // extract collection of circulinear elements
        Collection<? extends CirculinearElement2D> elements = curve
                .smoothPieces();

        Iterator<? extends CirculinearElement2D> iterator = elements.iterator();

        // previous curve
        CirculinearElement2D previous = null;
        CirculinearElement2D current = null;

        // create array for storing result
        ArrayList<CirculinearContinuousCurve2D> parallelCurves = new ArrayList<CirculinearContinuousCurve2D>();

        // check if curve is empty
        if (!iterator.hasNext())
            return parallelCurves;

        // add parallel to the first curve
        current = iterator.next();
        CirculinearElement2D parallel = current.parallel(dist);
        parallelCurves.add(parallel);

        // iterate on circulinear element couples
        CirculinearContinuousCurve2D join;
        while (iterator.hasNext()) {
            // update the couple of circulinear elements
            previous = current;
            current = iterator.next();

            // add circle arc between the two curve elements
            join = joinFactory.createJoin(previous, current, dist);
            if (join.length() > 0)
                parallelCurves.add(join);

            // add parallel to set of parallels
            parallelCurves.add(current.parallel(dist));
        }

        // Add eventually a circle arc to close the parallel curve
        if (curve.isClosed()) {
            previous = current;
            current = elements.iterator().next();

            join = joinFactory.createJoin(previous, current, dist);
            if (join.length() > 0)
                parallelCurves.add(join);
        }

        return parallelCurves;
    }

    /**
     * Compute the buffer of a circulinear curve.
     * <p>
     * The algorithm is as follow:
     * <ol>
     * <li>split the curve into a set of curves without self-intersections
     * <li>for each split curve, compute the contour of its buffer
     * <li>split self-intersecting contours into set of disjoint contours
     * <li>split all contour which intersect each other to disjoint contours
     * <li>remove contours which are too close from the original curve
     * <li>create a new domain with the final set of contours
     * </ol>
     */
    public CirculinearDomain2D computeBuffer(CirculinearCurve2D curve,
            double dist) {

        ArrayList<CirculinearContour2D> contours = new ArrayList<CirculinearContour2D>();

        // iterate on all continuous curves
        for (CirculinearContinuousCurve2D cont : curve.continuousCurves()) {
            // split the curve into a set of non self-intersecting curves
            for (CirculinearContinuousCurve2D splitted : CirculinearCurves2D
                    .splitContinuousCurve(cont)) {
                // compute the rings composing the simple curve buffer
                contours.addAll(computeBufferSimpleCurve(splitted, dist));
            }
        }

        // split contours which intersect each others
        contours = new ArrayList<CirculinearContour2D>(
                CirculinearCurves2D.splitIntersectingContours(contours));

        // Remove contours that cross or that are too close from base curve
        ArrayList<CirculinearContour2D> contours2 = new ArrayList<CirculinearContour2D>(
                contours.size());
        Collection<Point2D> intersects;
        Collection<Point2D> vertices;

        for (CirculinearContour2D contour : contours) {

            // do not keep contours which cross original curve
            intersects = CirculinearCurves2D.findIntersections(curve, contour);

            // remove intersection points that are vertices of the reference
            // curve
            vertices = curve.singularPoints();
            vertices = curve.vertices();
            intersects.removeAll(vertices);

            if (intersects.size() > 0)
                continue;

            // check that vertices of contour are not too close from original
            // curve
            double distCurves = getDistanceCurveSingularPoints(curve, contour);

            if (distCurves < dist - Shape2D.ACCURACY)
