package geomExtension;

import java.awt.geom.*;
import java.util.*;
import util.*;

public class Curve2DUtil{
    
    final static double pai=Math.PI;
    final static double largeNumber=1e+5;
    final static double eps10=1e-10;
    final static double eps12=1e-12;
    final static double eps4=1e-4;
    final static double eps3=1e-3;
    public static long sectionTime=0;
	
	public static int getIntersectionPts_debug=0;
	public static int intersectionPTOfLineAndArc_debug=0;
	public static int intersectionPTOfCircles_debug=0;
	public static int intersectionPTOfLineAndQuad_debug=0;
	public static int intersectionPTOfLineAndCubic_debug=0;
	public static int intersectionPTOfArbitraries_debug=0;
	public static int multisectionForInterSection_debug=0;
	public static int NewtonRaphsonForInterSection_debug=0;
	public static int getProjectionLine_debug=0;
	public static int projectionToCircularArc_debug=0;
	public static int bisectionForProjectionLine_debug=0;
	public static int projectionToArbitrary_debug=0;
	public static int NewtonRaphsonForProjectionLine_debug=0;
	public static int getNormalLines_debug=0;
	public static int normalToArbitrary_debug=0;
	public static int bisectionForNormalLines_debug=0;
	public static int NewtonRaphsonForNormalLines_debug=0;
	public static int getNormalsBetweenShapes_debug=0;
	public static int segmentsNormalsBetweenLines_debug=0;
	public static int segmentsNormalsBetweenCircles_debug=0;
	public static int segmentsNormalsBetweenArbitraries_debug=0;
	public static int roughCheck_debug=0;
	public static int segmentHit_debug=0;
	public static int ptPosition_debug=0;
	public static int rectHit_debug=0;
	public static int NewtonRaphsonForNormalsBetweenShapes_debug=0;
	public static int getShortestLineBetweenShapes_debug=0;
	public static int getSimpleCurve2D_debug=0;
	public static int arrangeCurveSegment_debug=0;
	public static int uniteSegment2Ds_debug=0;
	public static int extendCurve2D_debug=0;
	public static int extendSegment2D_debug=0;
	public static int extendCurve2DByPT_debug=0;
	public static int extendSegment2DByPT_debug=0;
	public static int distanceBetweenBoxes_debug=0;
	public static int NormalsInfo_debug=0;

//****++++-----------------//
//  getIntersectionPts
//-------------------------//
    public static CrossCurvePT[] getIntersectionPts(Curve2D curve1, Curve2D curve2){
		int debug=getIntersectionPts_debug;
        if(debug>0) System.out.println("** Curve2DUtil.getIntersectionPts started");
        sectionTime=0;
        long startTime = System.currentTimeMillis();
        int numSeg1=curve1.getNumOfSegments();
        int numSeg2=curve2.getNumOfSegments();
        CrossCurvePT[] segmentPoints=null;
        Vector vector=new Vector();
        Rectangle2D box1=curve1.getBoundingBox();
        Rectangle2D box2=curve1.getBoundingBox();
        curve2.getBoundingBox();
        if(!boxCheck(box1, box2)){
            return (new CrossCurvePT[0]);
        }
        for(int j=0;j<numSeg2;j++){
            Segment2D segment2=curve2.getSegment2D(j);
            for(int i=0;i<numSeg1;i++){
                Segment2D segment1=curve1.getSegment2D(i);
              //------------------------------------------------------------------------//   
                segmentPoints=Curve2DUtil.getIntersectionPtsOfSegments(segment1, segment2);
              //------------------------------------------------------------------------//    
                if(segmentPoints!=null) {
                    for(int k=0;k<segmentPoints.length;k++) {
                        double t1=segmentPoints[k].t1;
                        double t2=segmentPoints[k].t2;
                        if(t1>-eps10&&t1<1+eps10&&t2>-eps10&&t2<1+eps10){
                            segmentPoints[k].t1=segmentPoints[k].t1+i;
                            segmentPoints[k].t2=segmentPoints[k].t2+j;
                            vector.add(segmentPoints[k]);
                        }
                    }
                }
            }
        }
        int size=vector.size();
        CrossCurvePT[] curvePoints=new CrossCurvePT[size];
        for(int i=0;i<size;i++) curvePoints[i]=(CrossCurvePT)vector.get(i);
        CrossCurvePT[] newCrossPTs=curvePoints;
        if(size>=2) {
          //----------------------------------------------------------//  
            newCrossPTs=eliminateCrossPtsDuplication(curvePoints, 1e-8);
          //----------------------------------------------------------//  
        }
        long endTime = System.currentTimeMillis();
        if(debug>0&&newCrossPTs.length>0) System.out.println("** Curve2DUtil.getIntersectionPts" +
                ",  total used time="+(endTime-startTime)+" milisecond"+
                ",  section used time="+sectionTime+" milisecond");
        for(int i=0;i<newCrossPTs.length;i++){
            newCrossPTs[i].setCurve1(curve1);
            newCrossPTs[i].setCurve2(curve2);
        }
        return newCrossPTs;
    }
//-++++------------------------//
//  eliminateCrossPtsDuplication
//------------------------------//
    protected static CrossCurvePT[] eliminateCrossPtsDuplication(CrossCurvePT[] PTs, double tolerance){
		int debug=getIntersectionPts_debug;
        int size=PTs.length;

        double[] tTemp=new double[size];
        for(int i=0;i<size;i++) tTemp[i]=PTs[i].getParameterT1();
      //--------------------------------------------//  
        int[] indices=Util.indexedSimpleSort(tTemp);
      //--------------------------------------------//  

		if( debug>0){
		  	System.out.print(" -- ");
			for(int i=0;i<indices.length;i++) System.out.print(" indices["+i+"]="+indices[i]);
			System.out.println("");
		}

        Vector vector=new Vector();
        vector.add(indices[0]);
		int index=0;
        for(int i=1;i<indices.length;i++){
			if(debug>0) System.out.println("    i="+i+", index="+index+
					", indices[index]="+indices[index]+ ", indices[i]="+indices[i]);
            if(Math.abs(tTemp[indices[index]]-tTemp[indices[i]])>tolerance) {
			// Update 2018.05.14
			//if(Math.abs(tTemp[indices[index]]-tTemp[i])>tolerance) {	
				vector.add(indices[i]);
				index=i;
			}
        }

        size=vector.size();
        CrossCurvePT[] newPTs=new CrossCurvePT[size];
        for(int i=0;i<size;i++){
            index=((Integer)vector.get(i)).intValue();
            newPTs[i]=PTs[index];
        }
		if(debug>0) {
			System.out.println("- Curve2DUtil.eliminateCrossPtsDuplication Out");
			for(int i=0;i<newPTs.length;i++) System.out.println(" -- newPTs["+i+"]="+newPTs[i].toString());
		}
        return newPTs;
    }
//-++++------------------------//
// getIntersectionPtsOfSegments
//------------------------------//     
    protected static CrossCurvePT[] getIntersectionPtsOfSegments(Segment2D segment1, Segment2D segment2){
		int debug=intersectionPTOfLineAndArc_debug;
        CrossCurvePT curvePT=null;
        CrossCurvePT[] curvePTs=new CrossCurvePT[0];
        Vector vector=new Vector();
        int type1=segment1.getType();
        int type2=segment2.getType();
        boolean affine1=segment1.isAffineTransform();
        boolean affine2=segment2.isAffineTransform();
        int type=9;
        if(type1==Segment2D.MOVETO||type2==Segment2D.MOVETO) return curvePTs;
        if(type1==Segment2D.LINE&&type2==Segment2D.LINE) type=1;
        if(type1==Segment2D.LINE&&type2==Segment2D.ARC) type=2;
        if(type1==Segment2D.ARC&&type2==Segment2D.LINE) type=3;
		if(type1==Segment2D.ARC&type2==Segment2D.ARC) type=4;
        if(type1==Segment2D.LINE&&type2==Segment2D.QUAD) type=5;
        if(type1==Segment2D.QUAD&&type2==Segment2D.LINE) type=6;
        if(type1==Segment2D.LINE&&type2==Segment2D.CUBIC) type=7;
        if(type1==Segment2D.CUBIC&&type2==Segment2D.LINE) type=8;

        switch(type){
            case 1: {
              //------------------------------------------------------------//   
                curvePT=Curve2DUtil.intersectionPtOfLines(segment1, segment2);
              //------------------------------------------------------------//  
                if(curvePT!=null) vector.add(curvePT);
                break;
            }
            case 2: {
              //-----------------------------------------------------------------//   
                curvePTs=Curve2DUtil.intersectionPtsOfLineAndArc(segment1,segment2);
              //----------------------------------------------------------------//   
                if(curvePTs!=null) {
                    for(int i=0;i<curvePTs.length;i++) vector.add(curvePTs[i]);
                }
                break;
            }
            case 3: {
              //------------------------------------------------------------------// 
                curvePTs=Curve2DUtil.intersectionPtsOfLineAndArc(segment2, segment1);
              //------------------------------------------------------------------//    
                if(curvePTs!=null) {
                    for(int i=0;i<curvePTs.length;i++) {
                        curvePTs[i]=curvePTs[i].exchangeData();
                        vector.add(curvePTs[i]);
                    }
                }
                break;
            }
            case 4: {
				Rectangle2D box1=segment1.getBoundingBox();
				Rectangle2D box2=segment2.getBoundingBox();
				boolean circle1=Math.abs(box1.getWidth()-box1.getHeight())<Curve2DUtil.eps4;
				boolean circle2=Math.abs(box2.getWidth()-box2.getHeight())<Curve2DUtil.eps4;
				System.out.println("** getIntersectionPtsOfSegments circle1="+circle1+", circle2="+circle2);
              //-----------------------------------------------------------------//   
                if(circle1&&circle2) curvePTs=Curve2DUtil.intersectionPtsOfCircles(segment1,segment2);
				else curvePTs=Curve2DUtil.intersectionPtsOfArbitraries(segment1, segment2);
              //----------------------------------------------------------------//   
                if(curvePTs!=null) {
                    for(int i=0;i<curvePTs.length;i++) vector.add(curvePTs[i]);
                }
                break;
            }
            case 5: {
              //-----------------------------------------------------------------//   
                curvePTs=Curve2DUtil.intersectionPtsOfLineAndQuad(segment1,segment2);
              //----------------------------------------------------------------//   
                if(curvePTs!=null) {
                    for(int i=0;i<curvePTs.length;i++) vector.add(curvePTs[i]);
                }
                break;
            }
            case 6: {
              //------------------------------------------------------------------// 
                curvePTs=Curve2DUtil.intersectionPtsOfLineAndQuad(segment2, segment1);
              //------------------------------------------------------------------//    
                if(curvePTs!=null) {
                    for(int i=0;i<curvePTs.length;i++) {
                        curvePTs[i]=curvePTs[i].exchangeData();
                        vector.add(curvePTs[i]);
                    }
                }
                break;
            }
            case 7: {
              //-----------------------------------------------------------------//   
                curvePTs=Curve2DUtil.intersectionPtsOfLineAndCubic(segment1,segment2);
              //----------------------------------------------------------------//   
                if(curvePTs!=null) {
                    for(int i=0;i<curvePTs.length;i++) vector.add(curvePTs[i]);
                }
                break;
            }
            case 8: {
              //------------------------------------------------------------------// 
                curvePTs=Curve2DUtil.intersectionPtsOfLineAndCubic(segment2, segment1);
              //------------------------------------------------------------------//    
                if(curvePTs!=null) {
                    for(int i=0;i<curvePTs.length;i++) {
                        curvePTs[i]=curvePTs[i].exchangeData();
                        vector.add(curvePTs[i]);
                    }
                }
                break;
            }
            case 9: {
              //------------------------------------------------------------------//   
                curvePTs=Curve2DUtil.intersectionPtsOfArbitraries(segment1, segment2);
              //------------------------------------------------------------------//    
                if(curvePTs!=null) {
                    for(int i=0;i<curvePTs.length;i++) vector.add(curvePTs[i]);
                }
                break;
            }
        }
        int size=vector.size();
        if(size==0) return null;
        curvePTs=new CrossCurvePT[size];
        for(int i=0;i<size;i++) curvePTs[i]=(CrossCurvePT)vector.get(i);
        return curvePTs;
    }
//-++++------------------------//
// intersectionPTOfLines
//------------------------------//    
    protected static CrossCurvePT intersectionPtOfLines(Segment2D segment1, Segment2D segment2){
        Rectangle2D boundingBox1=segment1.getBoundingBox();
        Rectangle2D boundingBox2=segment2.getBoundingBox();
      //----------------------------------------------------------------// 
        if(!Curve2DUtil.boxCheck(boundingBox1, boundingBox2)) return null;
      //---------------------------------------------------------------//  
        Vector2D tangentVec1=segment1.getTangent(0);
        Vector2D tangentVec2=segment2.getTangent(0);
        tangentVec2=Vector2D.multiply(-1d, tangentVec2);
        Vector2D p1=new Vector2D(segment1.getP(0));
        Vector2D p2=new Vector2D(segment2.getP(0));
        Vector2D subVec=Vector2D.sub(p2,p1);
        double det=tangentVec1.getX()*tangentVec2.getY()-tangentVec1.getY()*tangentVec2.getX();
        if(Math.abs(det)<Curve2DUtil.eps4) return null;
        double t1=(subVec.getX()*tangentVec2.getY()-subVec.getY()*tangentVec2.getX())/det;
        double t2=(tangentVec1.getX()*subVec.getY()-tangentVec1.getY()*subVec.getX())/det;
        CrossCurvePT curvePT=null;
        if(t1<-eps10||t1>1d+eps10||t2<-eps10||t2>1d+eps10) return null;
        curvePT=new CrossCurvePT(t1, t2, segment1.getP(t1), segment2.getP(t2));
        return curvePT;
    }
//-++++------------------------//
// intersectionPTOfLineAndArc
//------------------------------//    
    protected static CrossCurvePT[] intersectionPtsOfLineAndArc(Segment2D segment1, 
            Segment2D segment2){
		int debug=intersectionPTOfLineAndArc_debug;
        //System.out.println("** Curve2D.IntersectionPTOfLineAndArc start");
        Rectangle2D boundingBox1=segment1.getBoundingBox();
        Rectangle2D boundingBox2=segment2.getBoundingBox();
      //---------------------------------------------------------------//  
        if(!Curve2DUtil.boxCheck(boundingBox1, boundingBox2)) return null;
      //---------------------------------------------------------------//  
        Vector vector=new Vector();
        Line2D line=(Line2D)segment1.getAwtGeom();
        Arc2D arc=(Arc2D)segment2.getAwtGeom();
        double width=arc.getWidth();
        double height=arc.getHeight();
        double angleStart=arc.getAngleStart();
        double angleExtent=arc.getAngleExtent();
        AffineTransform affine=segment2.getAffineTransform();
        Point2D P1=line.getP1();
        Point2D P2=line.getP2();
        AffineTransform inverseAffine=null;
        if(affine!=null){
            try{
                inverseAffine=affine.createInverse();
                P1=inverseAffine.transform(P1, null);
                P2=inverseAffine.transform(P2, null);
            } catch(NoninvertibleTransformException e){
                System.out.println("Curve2DUtil.IntersectionPTOfLineAndArc"
                        + "  NoninvertibleTransformException");
                e.printStackTrace();
            }
        }
        Vector2D p1=new Vector2D(P1);
        Vector2D p2=new Vector2D(P2);
        Vector2D T=Vector2D.sub(p2,p1);
        Vector2D P=new Vector2D(P1);
        Vector2D Q=new Vector2D(arc.getX()+0.5*width, arc.getY()+0.5*height);
        P=Vector2D.sub(P, Q);
        double Px=P.getX(), Py=P.getY();
        double Tx=T.getX(), Ty=T.getY();
        double a=0.5*width, b=0.5*height;
        double a2=a*a, b2=b*b;
        double coeff0=Tx*Tx/a2+Ty*Ty/b2;
        double coeff1=2*Tx*Px/a2+2*Ty*Py/b2;
        double coeff2=Px*Px/a2+Py*Py/b2-1;
        double X=coeff1*coeff1-4*coeff0*coeff2;
        if(X<0) return null;
            double t1=0;
            for(int i=0;i<2;i++){
                if(i==0) t1=(-coeff1+Math.sqrt(X))/(2*coeff0);
                else t1=(-coeff1-Math.sqrt(X))/(2*coeff0);
                if(t1<-eps10||t1>1d+eps10) continue;
                Point2D PT1=segment1.getP(t1);
                if(inverseAffine!=null){
                    PT1=inverseAffine.transform(PT1, null);
                }
                double theta=Math.atan2(-(PT1.getY()-Q.getY())/b, (PT1.getX()-Q.getX())/a);
				if( debug>0 ) System.out.println(" ++ Curve2DUtil.IntersectionPTOfLineAndArc i="+i+", theta="+theta);
				//Update 2018.05.14
                //for(int j=-1;j<=1;j++){
				//for(int j=-1;j<=1;j++){
				//double thetaShift=theta;
				if(theta<0.0) theta+=2*pai;
                double t2=(theta*180/pai-angleStart)/angleExtent;
                if(t2<-eps10||t2>1d+eps10) continue;
                Point2D PT2=segment2.getP(t2);
                CrossCurvePT curvePT=new CrossCurvePT(t1, t2, PT1, PT2);
                vector.add(curvePT);
                //} // for j
            } // for i

        CrossCurvePT[] curvePTs=null;
        int size=vector.size();
        if(size==0) return null;
        curvePTs=new CrossCurvePT[size];
        for(int i=0;i<size;i++) {
            curvePTs[i]=(CrossCurvePT)vector.get(i);
            if(debug>1) System.out.println("-- Curve2DUtil.IntersectionPTOfLineAndArc " +
                    "\n    curvePTs["+i+"]="+curvePTs[i].toString());
        }
        return curvePTs;
    }
//-++++------------------------//
// intersectionPTOfCircles
//------------------------------//    
    private static CrossCurvePT[] intersectionPtsOfCircles(Segment2D segment1, 
            Segment2D segment2){
		int debug=intersectionPTOfCircles_debug;
        if(debug>0) System.out.println("** Curve2DUtil.intersectionPTOfCircles start");
        Rectangle2D box1=segment1.getBoundingBox();
        Rectangle2D box2=segment2.getBoundingBox();
        Arc2D arc1=(Arc2D)segment1.getAwtGeom();
        Arc2D arc2=(Arc2D)segment2.getAwtGeom();
        double angleStart1=arc1.getAngleStart();
        double angleExtent1=arc1.getAngleExtent();
        double angleStart2=arc2.getAngleStart();
        double angleExtent2=arc2.getAngleExtent();
		AffineTransform affine1=segment1.getAffineTransform();
        AffineTransform affine2=segment2.getAffineTransform();
		double x1=box1.getCenterX();
		double y1=box1.getCenterY();
		double x2=box2.getCenterX();
		double y2=box2.getCenterY();
		double r1=0.5*box1.getWidth();
		double r2=0.5*box2.getWidth();
		double dist=Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
      //---------------------------------------------------------------//  
		if(dist>r1+r2) return null;
        if(!Curve2DUtil.boxCheck(box1, box2)) return null;
      //---------------------------------------------------------------//  
		
		Rectangle2D maxBox=Curve2DUtil.getMaxBox(box1, box2);
		if(debug>0) {
			System.out.println("-- (x1, y1)=("+x1+","+y1+")"+", (x2, x2)=("+x2+","+y2+")"
					+", r1="+r1+" ,r2="+r2+"\n-- maxBox="+Util.Rect(maxBox));;
		}
		Point2D p1=null;
		Point2D p2=null;
		double R=0.5*(x1*x1+y1*y1-x2*x2-y2*y2-r1*r1+r2*r2);
		if(Math.abs(x1-x2)>Math.abs(y1-y2)){
			double p1x=(R-(y1-y2)*maxBox.getMinY())/(x1-x2);
			double p2x=(R-(y1-y2)*maxBox.getMaxY())/(x1-x2);
			p1=new Point2D.Double(p1x, maxBox.getMinY());
			p2=new Point2D.Double(p2x, maxBox.getMaxY());
		}else{
			double p1y=(R-(x1-x2)*maxBox.getMinX())/(y1-y2);
			double p2y=(R-(x1-x2)*maxBox.getMaxX())/(y1-y2);
			p1=new Point2D.Double(maxBox.getMinX(), p1y);
			p2=new Point2D.Double(maxBox.getMaxX(), p2y);
		}
		Line2DE line=new Line2DE(p1, p2);
		Segment2D lineSeg=line.getSegment2D(0);
		CrossCurvePT[] crossP1s=Curve2DUtil.intersectionPtsOfLineAndArc(lineSeg, segment1);
		CrossCurvePT[] crossP2s=Curve2DUtil.intersectionPtsOfLineAndArc(lineSeg, segment2);
		String str="-- Curve2DUtil.intersectionPTOfCircles";
		str+=" lineSeg="+lineSeg.toString();
		if(debug>0) System.out.println(str);
		if(crossP1s==null||crossP2s==null){
			if(debug>0) System.out.println(" - crosspP1s==null or crosspP2s==null");
			return null;
		} else{
			for (int i = 0; i < crossP1s.length; i++) {
				if(debug>0) System.out.println(" - crosspP1s["+i+"]="+crossP1s[i].toString());
			}
			for (int i = 0; i < crossP1s.length; i++) {
				if(debug>0) System.out.println(" - crosspP2s["+i+"]="+crossP2s[i].toString());
			}
		}

		Vector vector=new Vector();
		for(int i=0;i<crossP1s.length;i++){
			if(crossP1s[i]==null) continue;
			for(int j=0;j<crossP2s.length;j++){
				if(crossP2s[j]==null) continue;
				double t1=crossP1s[i].getParameterT1();
				double t2=crossP1s[i].getParameterT1();
				if(Math.abs(t1-t2)<Curve2DUtil.eps4){
					CrossCurvePT crossPT=new CrossCurvePT(crossP1s[i].getParameterT2(), 
							crossP2s[i].getParameterT2(), crossP1s[i].getP1(), crossP2s[i].getP1());
					vector.add(crossPT);
				}
			}
		}
		int size=vector.size();
		if(size==0) return null;
		CrossCurvePT[] crossPTs=new CrossCurvePT[size];
        for(int i=0;i<size;i++) {
			 CrossCurvePT crossP=(CrossCurvePT)vector.get(i);
            crossPTs[i]=crossP;
            if(debug>0) System.out.println("-- Curve2DUtil.IntersectionPTOfCircles " +
                    "\n    curvePTs["+i+"]="+crossP.toString());
        }
        return crossPTs;
    }
//-++++------------------------//
// intersectionPTOfLineAndQuad
//------------------------------//   
    protected static CrossCurvePT[] intersectionPtsOfLineAndQuad(Segment2D segment1, Segment2D segment2){
		int debug=intersectionPTOfLineAndQuad_debug;
        Rectangle2D boundingBox1=segment1.getBoundingBox();
        Rectangle2D boundingBox2=segment2.getBoundingBox();
      //----------------------------------------------------------------// 
        if(!Curve2DUtil.boxCheck(boundingBox1, boundingBox2)) return null;
      //---------------------------------------------------------------//  
        Vector vector=new Vector();
        Line2D line=(Line2D)segment1.getAwtGeom();
        QuadCurve2D curve=(QuadCurve2D)segment2.getAwtGeom();
        Vector2D P0=new Vector2D(line.getP1());
        Vector2D P1=new Vector2D(line.getP2());
        Vector2D lineVec=Vector2D.sub(P1,P0);
        Vector2D unitLineVec=Vector2D.unitVector(lineVec);
        if(Vector2D.length(lineVec)<eps4) return null;
        Vector2D normal=Vector2D.normalVector(lineVec);
        Vector2D Q0=new Vector2D(curve.getP1());
        Vector2D Q1=new Vector2D(curve.getCtrlPt());
        Vector2D Q2=new Vector2D(curve.getP2());
        Vector2D a=new Vector2D(Q0.getX()-2*Q1.getX()+Q2.getX(), Q0.getY()-2*Q1.getY()+Q2.getY());
        Vector2D b=new Vector2D(-2*Q0.getX()+2*Q1.getX(), -2*Q0.getY()+2*Q1.getY());
        Vector2D c=new Vector2D(Q0.getX()-P0.getX(), Q0.getY()-P0.getY());
        double[] eqn=new double[3];
        eqn[2]=Vector2D.sproduct(a, normal);
        eqn[1]=Vector2D.sproduct(b, normal);
        eqn[0]=Vector2D.sproduct(c, normal);
        double[] roots=new double[2];
        int nRoots=QuadCurve2D.solveQuadratic(eqn, roots);
        for(int i=0;i<nRoots;i++){
            double t2=roots[i];
           //if(debug>=0) System.out.println("-- Curve2DUItil.IntersectionPTOfLineAndQuad " +
           //         ", roots["+i+"]="+roots[i]); 
            if(t2<-eps10||t2>1d+eps10) continue;
            Point2D PT2=segment2.getP(t2);
            Vector2D vec=Vector2D.sub(new Vector2D(PT2), P0);
            double t1=Vector2D.sproduct(vec, unitLineVec)/Vector2D.length(lineVec);
            if(t1<-eps10||t1>1d+eps10) continue;

            Point2D PT1=segment1.getP(t1);
            CrossCurvePT curvePT=new CrossCurvePT(t1, t2, PT1, PT2);
            vector.add(curvePT);
        }
        CrossCurvePT[] curvePTs=null;
        int size=vector.size();
        if(size==0) return null;
        curvePTs=new CrossCurvePT[size];
        for(int i=0;i<size;i++) {
            curvePTs[i]=(CrossCurvePT)vector.get(i);
            if(debug>0) System.out.println("-- Curve2DUItil.IntersectionPTOfLineAndQuad " +
                    "\n    curvePTs["+i+"]="+curvePTs[i].toString());
        }
        return curvePTs;
    }
//-++++------------------------//
// intersectionPTOfLineAndCubic
//------------------------------//   
    protected static CrossCurvePT[] intersectionPtsOfLineAndCubic(Segment2D segment1, Segment2D segment2){
		int debug=intersectionPTOfLineAndCubic_debug;
        Rectangle2D boundingBox1=segment1.getBoundingBox();
        Rectangle2D boundingBox2=segment2.getBoundingBox();
      //----------------------------------------------------------------// 
        if(!Curve2DUtil.boxCheck(boundingBox1, boundingBox2)) return null;
      //---------------------------------------------------------------//  
        Vector vector=new Vector();
        Line2D line=(Line2D)segment1.getAwtGeom();
        CubicCurve2D curve=(CubicCurve2D)segment2.getAwtGeom();
        Vector2D P0=new Vector2D(line.getP1());
        Vector2D P1=new Vector2D(line.getP2());
        Vector2D lineVec=Vector2D.sub(P1,P0);
        Vector2D unitLineVec=Vector2D.unitVector(lineVec);
        if(Vector2D.length(lineVec)<eps4) return null;
        Vector2D normal=Vector2D.normalVector(lineVec);
        Vector2D Q0=new Vector2D(curve.getP1());
        Vector2D Q1=new Vector2D(curve.getCtrlP1());
        Vector2D Q2=new Vector2D(curve.getCtrlP2());
        Vector2D Q3=new Vector2D(curve.getP2());
        Vector2D a=new Vector2D(-Q0.getX()+3*Q1.getX()-3*Q2.getX()+Q3.getX(), 
                -Q0.getY()+3*Q1.getY()-3*Q2.getY()+Q3.getY());
        Vector2D b=new Vector2D(3*Q0.getX()-6*Q1.getX()+3*Q2.getX(),
                3*Q0.getY()-6*Q1.getY()+3*Q2.getY());
        Vector2D c=new Vector2D(-3*Q0.getX()+3*Q1.getX(), 
                -3*Q0.getY()+3*Q1.getY());
        Vector2D d=new Vector2D(Q0.getX()-P0.getX(), Q0.getY()-P0.getY());
        double[] eqn=new double[4];
        eqn[3]=Vector2D.sproduct(a, normal);
        eqn[2]=Vector2D.sproduct(b, normal);
        eqn[1]=Vector2D.sproduct(c, normal);
        eqn[0]=Vector2D.sproduct(d, normal);
        double[] roots=new double[3];
        int nRoots=CubicCurve2D.solveCubic(eqn, roots);
        
        for(int i=0;i<nRoots;i++){
            double t2=roots[i];
           if(debug>0) {
               if(i==0) System.out.print("\n");
               System.out.println("-- Curve2DUItil.IntersectionPTOfLineAndQuad " +
                    ", roots["+i+"]="+roots[i]); 
           }
            if(t2<-eps10||t2>1d+eps10) continue;
            Point2D PT2=segment2.getP(t2);
            Vector2D vec=Vector2D.sub(new Vector2D(PT2), P0);
            double t1=Vector2D.sproduct(vec, unitLineVec)/Vector2D.length(lineVec);
            if(t1<-eps10||t1>1d+eps10) continue;
            Point2D PT1=segment1.getP(t1);
            CrossCurvePT curvePT=new CrossCurvePT(t1, t2, PT1, PT2);
            vector.add(curvePT);
        }
        CrossCurvePT[] curvePTs=null;
        int size=vector.size();
        if(size==0) return null;
        curvePTs=new CrossCurvePT[size];
        for(int i=0;i<size;i++) {
            curvePTs[i]=(CrossCurvePT)vector.get(i);
            if(debug>0) System.out.println("-- Curve2DUtil.IntersectionPTOfLineAndCubic " +
                    "\n    curvePTs["+i+"]="+curvePTs[i].toString());
        }
        return curvePTs;
    }
//-++++------------------------//
// ntersectionPTOfArbitraries
//------------------------------//   
    protected static CrossCurvePT[] intersectionPtsOfArbitraries(Segment2D segment1, 
            Segment2D segment2){
		int debug=intersectionPTOfArbitraries_debug;
        Vector subdivisionVector=new Vector();
        int numSubDiv=8;
        double delta=1d;
        long startTime = System.currentTimeMillis();
        int depth=0;
      //---------------------------------------------------------------//  
        Curve2DUtil.multisectionForInterSection(depth, numSubDiv, delta, 
                segment1, 0, 1, segment2, 0, 1, subdivisionVector);
      //---------------------------------------------------------------//  
        long endTime = System.currentTimeMillis();
        sectionTime+=endTime-startTime;
        if(debug>1) System.out.println("  -- IntersectionPTOfArbitraries bisection" +
                ",  used time="+(endTime-startTime)+" milisecond");
        Vector solutionVector=new Vector();
        int size=subdivisionVector.size();
        
        for(int i=0;i<size;i++){
            double[] interval=(double[])subdivisionVector.get(i);
            double t1Init=0.5*(interval[0]+interval[1]);
            double t2init=0.5*(interval[2]+interval[3]);
          //-----------------------------------------------------------------------------//  
            CrossCurvePT newtonPT=Curve2DUtil.NewtonRaphsonForInterSection(segment1, t1Init, 
                    segment2, t2init);
          //----------------------------------------------------------------------------//  
            if(newtonPT!=null) {
                double t1=newtonPT.getParameterT1();
                double t2=newtonPT.getParameterT2();
                int index=-1;
                //duplication check!
                for(int j=0;j<solutionVector.size();j++){
                    CrossCurvePT pt=(CrossCurvePT)solutionVector.get(j);
                    if( Math.abs(t1-pt.getParameterT1())+Math.abs(t2-pt.getParameterT2())<eps10){
                        index=j;
                        break;
                    }
                }
                if(index<0) solutionVector.add(newtonPT);
            }
       }
       endTime = System.currentTimeMillis();
       size=solutionVector.size();
       CrossCurvePT[] curvePTs=new CrossCurvePT[size];
       for(int i=0;i<solutionVector.size();i++){
           CrossCurvePT tsolution=(CrossCurvePT)solutionVector.get(i);
           curvePTs[i]=tsolution;
           if(debug>1)  System.out.println("-- Curve2DUtil.IntersectionPTOfArbitraries " +
                    "\n    curvePTs["+i+"]="+curvePTs[i].toString());
       }

       return curvePTs;
    }
//-++++------------------------//
// multisectionForInterSection
//------------------------------//  
    protected static void multisectionForInterSection(int depth, int numSubDiv, double delta, 
            Segment2D segment1, double t1s, double t1e, Segment2D segment2, double t2s, double t2e, 
            Vector vector){
		int debug=multisectionForInterSection_debug;
        Rectangle2D box1=segment1.getBoundingBox(t1s, t1e);
        Rectangle2D box2=segment2.getBoundingBox(t2s, t2e);
        double[] interval=new double[4];
      //--------------------------------------//  
        boolean crossed=boxCheck(box1,box2);
      //--------------------------------------//    
        double max1=Math.max(box1.getWidth(), box1.getHeight());
        double max2=Math.max(box2.getWidth(), box2.getHeight());
        int div1=(int)(max1/delta);
        int div2=(int)(max2/delta);
        if(debug>1) System.out.println("  ++ multisection depth=" +depth+",numSubDiv="+numSubDiv+
                ", t1s,t1e="+Util.Num(t1s)+","+Util.Num(t1e)+
                ", t2s,t2e="+Util.Num(t2s)+","+Util.Num(t2e)+
                ", t1W="+Util.Num(t1e-t1s)+", t2W="+Util.Num(t2e-t2s)+
                ", div1,div2="+Util.Num(div1)+","+Util.Num(div2)+
                ", boxWH1="+Util.Num(max1)+", boxWH2="+Util.Num(max2));
        if(crossed){
            if(div1==0&&div2==0){
                interval[0]=t1s;
                interval[1]=t1e;
                interval[2]=t2s;
                interval[3]=t2e;
                vector.add(interval);
                if(debug>1) System.out.println(" -- multisection result stored,  depth=" +depth+
                        ", t1s,t1e="+Util.Num(t1s)+","+Util.Num(t1e)+
                        ", t2s,t2e="+Util.Num(t2s)+","+Util.Num(t2e)+
                        ", boxWH1="+Util.Num(max1)+", boxWH2="+Util.Num(max2));
                return;
            } else{
                //depth++;  delete because of bug 2016.08.10
                div1++;
                div2++;
                if(div1>numSubDiv) div1=numSubDiv;
                if(div2>numSubDiv) div2=numSubDiv;
                double delt1=(t1e-t1s)/div1;
                double delt2=(t2e-t2s)/div2;
                for(int i=0;i<div1;i++){
                    double t1start=t1s+delt1*i;
                    double t1end=t1start+delt1;
                    for(int j=0;j<div2;j++){
                        double t2start=t2s+delt2*j;
                        double t2end=t2start+delt2;
                        multisectionForInterSection(depth+1, numSubDiv, delta, 
                            segment1, t1start, t1end, segment2, t2start, t2end, vector);
                    }
                }
            }
        } else return;
    }

    protected static boolean boxCheck(Rectangle2D box1, Rectangle2D box2){
        double x1=box1.getX(), y1=box1.getY(), w1=box1.getWidth(), h1=box1.getHeight();
        double x2=box2.getX(), y2=box2.getY(), w2=box2.getWidth(), h2=box2.getHeight();
        if(x1+w1<x2) return false;
        if(y1+h1<y2) return false;
        if(x2+w2<x1) return false;
        if(y2+h2<y1) return false;
        return true;
    }
//-++++------------------------//
// NewtonRaphsonForInterSection
//------------------------------//  
    protected static CrossCurvePT NewtonRaphsonForInterSection(Segment2D segment1, double t1s,
            Segment2D segment2, double t2s){
		int debug=NewtonRaphsonForInterSection_debug;
        if(t1s<0d||t1s>1d||t2s<0d||t2s>1d){
            System.out.println("*** Warning in Curve2DUtil.NewtonRaphsonForInterSection: " +
                    "t1s or t2s out of bound, t1s, tis="+t1s+","+t2s);
            if(t1s<0d) t1s=0d;
            if(t1s>1d) t1s=1d;
            if(t2s<0d) t1s=0d;
            if(t2s>1d) t1s=1d;
        }
        //double[] solution=null;
        double dt=Curve2D.largeNumber;
        double dDist=Curve2D.largeNumber;
        double t1=t1s; double t2=t2s;
        boolean parallel=false;
        boolean converged=false;
        int iter=0;
        while(iter<=10){
            Vector2D T1=segment1.getTangent(t1);
            Vector2D T2=segment2.getTangent(t2);
            Vector2D P1=new Vector2D(segment1.getP(t1));
            Vector2D P2=new Vector2D(segment2.getP(t2));
            double T1x=T1.getX(), T1y=T1.getY();
            double T2x=-T2.getX(), T2y=-T2.getY();
            double P1x=P1.getX(), P1y=P1.getY();
            double P2x=P2.getX(), P2y=P2.getY();
            double Qx=-P1x+P2x, Qy=-P1y+P2y;
            double det=T1x*T2y-T1y*T2x;
            if(Math.abs(det)<Curve2DUtil.eps4) {
                parallel=true;
                break;
            }
            double dt1=(Qx*T2y-Qy*T2x)/det;
            double dt2=(T1x*Qy-T1y*Qx)/det;
            
            t1=t1+dt1; t2=t2+dt2;
            P1=new Vector2D(segment1.getP(t1));
            P2=new Vector2D(segment2.getP(t2));
            dDist=Vector2D.dist(P1, P2);
            dt=Math.max(Math.abs(dt1), Math.abs(dt2));
            if(dt<eps12){
                converged=true;
                break;
            }
            iter++;
        }
        if(parallel&&dDist>Curve2DUtil.eps4){
            if(debug>1) System.out.println(" --  NewtonRaphson  parallel="+parallel+
                    "iter="+iter+", t1,t2="+t1+","+t2+", dist="+dDist);
            return null;
        }
        if(t1<0d||t1>1d||t2<0d||t2>1d){
            if(debug>1) System.out.println("*** Warning in Curve2DUtil.NewtonRaphsonForInterSection:" +
                    " t1 or t2 out of bound, t1,t2="+t1+","+t2);
            return null;
        }
        CrossCurvePT pt=new CrossCurvePT(t1,t2,segment1.getP(t1), segment2.getP(t2));
        if(debug>1) System.out.println(" --  NewtonRaphson iter="+iter+
                ", t1,t2="+Util.Num(t1)+","+Util.Num(t2));
        return pt;
    }
    
//****++++----------//
//  getProjectionLine
//------------------//
    public static CurvePT[] getProjectionLines(Point2D point, Vector2D dir, Curve2D curve){
		int debug=getProjectionLine_debug;
        int numSegments=curve.getNumOfSegments();
        CurvePT[] segmentPoints=new CurvePT[0];
        Vector vector=new Vector();
        for(int i=0;i<numSegments;i++){
            Segment2D segment=curve.getSegment2D(i);
            if(debug>1) System.out.println("-- getNormalPT point="+point.toString()+
                    ", segment no="+i+", segment="+segment.toString());
          //------------------------------------------------------------//    
            segmentPoints=Curve2DUtil.getProjectionLinesOnSegment(point, dir, segment);
          //------------------------------------------------------------//    
            if(segmentPoints!=null) {
                for(int j=0;j<segmentPoints.length;j++) {
                    segmentPoints[j].t=segmentPoints[j].t+i;
                    vector.add(segmentPoints[j]);
                }
            }
        }
        int size=vector.size();
        CurvePT[] curvePoints=new CurvePT[size];
        for(int i=0;i<size;i++) curvePoints[i]=(CurvePT)vector.get(i);
        CurvePT[] newCurvePTs=curvePoints;
      //-------------------------------------------------------------------// 
        if(size>=2) newCurvePTs
                =Curve2DUtil.eliminateDuplicationAndSort(curvePoints, 1e-8);
      //-------------------------------------------------------------------//  
        for(int i=0;i<newCurvePTs.length;i++) newCurvePTs[i].setCurve(curve);
        return newCurvePTs;

    }
    
    protected static CurvePT[] eliminateDuplicationAndSort(CurvePT[] PTs, double tolerance){
        int size=PTs.length;
        double[] tTemp=new double[size];
        for(int i=0;i<size;i++) tTemp[i]=PTs[i].getParameter();
        Curve2DUtil util=new Curve2DUtil();
        int[] indices=Util.indexedSimpleSort(tTemp);
        Vector vector=new Vector();
        vector.add(indices[0]);
		int index=0;
        for(int i=1;i<size;i++){
            if(Math.abs(tTemp[indices[index]]-tTemp[indices[i]])>tolerance) {
				vector.add(indices[i]);
				index=i;
			}
        }
        size=vector.size();
        CurvePT[] newPTs=new CurvePT[size];
        for(int i=0;i<size;i++){
            index=((Integer)vector.get(i)).intValue();
            newPTs[i]=PTs[index];
        }
        return newPTs;
    }
    
    protected static CurvePT[] getProjectionLinesOnSegment(Point2D point, Vector2D dir, 
            Segment2D segment){
        CurvePT[] curvePTs=new CurvePT[0];
        int type=3;
        int segmentType=segment.getType();
        boolean affine=segment.isAffineTransform();
        if(segmentType==Segment2D.MOVETO) return curvePTs;
        if(segmentType==Segment2D.LINE) type=1;
        //if(segmentType==Segment2D.ARC&&!affine) type=2;
        if(segmentType==Segment2D.ARC) type=2;
        
        
        switch(type){
            case 1: {
                //-----------------------------------------------------------------//  
                CurvePT curvePT=Curve2DUtil.ProjectionToLine(point, dir, segment);
                //----------------------------------------------------------------//    
                if(curvePT!=null) {
                    curvePTs= new CurvePT[1];
                    curvePTs[0]=curvePT;
                    
                }
                break;
            }
            case 2: {
              //-------------------------------------------------------------------//    
                curvePTs=Curve2DUtil.ProjectionToCircularArc(point, dir, segment);
              //-------------------------------------------------------------------//    
                break;
            }
            case 3: {
               //---------------------------------------------------------------//    
                curvePTs=Curve2DUtil.ProjectionToArbitrary(point, dir, segment);
               //---------------------------------------------------------------// 
                break;
            }
        }
        return curvePTs;
    }
    
    protected static CurvePT ProjectionToLine(Point2D point, Vector2D dir, Segment2D segment){
        CurvePT curvePT=null;
        Rectangle2D box=segment.getBoundingBox();
      //----------------------------------------------------------// 
        if(!Curve2DUtil.boxCheck(point, dir, box)) return null;
      //----------------------------------------------------------//  
        Vector2D tangentVec1=dir;
        Vector2D tangentVec2=segment.getTangent(0);
        tangentVec2=Vector2D.multiply(-1d, tangentVec2);
        Vector2D p1=new Vector2D(point);
        Vector2D p2=new Vector2D(segment.getP(0));
        Vector2D subVec=Vector2D.sub(p2,p1);
        double det=tangentVec1.getX()*tangentVec2.getY()-tangentVec1.getY()*tangentVec2.getX();
        if(Math.abs(det)<Curve2DUtil.eps10) return null;
        double t1=(subVec.getX()*tangentVec2.getY()-subVec.getY()*tangentVec2.getX())/det;
        double t2=(tangentVec1.getX()*subVec.getY()-tangentVec1.getY()*subVec.getX())/det;
        if(t2<-eps4||t2>1d+eps4) return null;
        curvePT=new CurvePT(t2, segment.getP(t2));
        return curvePT;
    }
    
    protected static CurvePT[] ProjectionToCircularArc(Point2D point, Vector2D dir, 
            Segment2D segment){
		int debug=projectionToCircularArc_debug;
        CurvePT[] curvePTs=new CurvePT[0];
        //System.out.println("Curve2D.ProjectionToCircularArc  dir="+dir.toString());
        Rectangle2D box=segment.getBoundingBox();
      //---------------------------------------------------------------//  
        if(!Curve2DUtil.boxCheck(point, dir, box)) return curvePTs;
      //---------------------------------------------------------------//  
        Vector vector=new Vector();
        //Point2D endP=new Point2D.Double(point.getX()+dir.getX(), point.getY()+dir.getY());
        Arc2D arc=(Arc2D)segment.getAwtGeom();
        double width=arc.getWidth();
        double height=arc.getHeight();
        double angleStart=arc.getAngleStart();
        double angleExtent=arc.getAngleExtent();
        Vector2D T=dir;
        Vector2D startP=new Vector2D(point);
        
        AffineTransform affine=segment.getAffineTransform();
        AffineTransform inverseAffine=null;
        if(affine!=null){
            try{
                inverseAffine=affine.createInverse();
                Point2D PT=inverseAffine.transform(point, null);
                Point2D TDir=inverseAffine.transform(new Point2D.Double(dir.getX(), dir.getY()), null);
                startP=new Vector2D(PT);
                T=new Vector2D(TDir);
            } catch(NoninvertibleTransformException e){
                System.out.println("Curve2DUtil.ProjectionToCircularArc"
                        + "  NoninvertibleTransformException");
                e.printStackTrace();
            }
        }

        Vector2D Q=new Vector2D(arc.getX()+0.5*width, arc.getY()+0.5*height);
        Vector2D P=Vector2D.sub(startP, Q);
        double Px=P.getX(), Py=P.getY();
        double Tx=T.getX(), Ty=T.getY();
        double a=0.5*width, b=0.5*height;
        double a2=a*a, b2=b*b;
        double coeff0=Tx*Tx/a2+Ty*Ty/b2;
        double coeff1=2*Tx*Px/a2+2*Ty*Py/b2;
        double coeff2=Px*Px/a2+Py*Py/b2-1;
        double X=coeff1*coeff1-4*coeff0*coeff2;
        if(X<0) return null;
            double t1=0;
            for(int i=0;i<2;i++){
                if(i==0) t1=(-coeff1+Math.sqrt(X))/(2*coeff0);
                else t1=(-coeff1-Math.sqrt(X))/(2*coeff0);
                Vector2D PT=Vector2D.add(startP, Vector2D.multiply(t1, T));
                Point2D PT1=new Point2D.Double(PT.getX(),PT.getY());
                double theta=Math.atan2(-(PT1.getY()-Q.getY())/b, (PT1.getX()-Q.getX())/a);
                for(int j=-1;j<=1;j++){
                    double thetaShift=theta+2*pai*j;
                    double t2=(thetaShift*180/pai-angleStart)/angleExtent;
                    if(t2<-eps10||t2>1d+eps10) continue;
                        Point2D PT2=segment.getP(t2);
                        CurvePT curvePT=new CurvePT(t2, PT2);
                        vector.add(curvePT);
                } // for j
            } // for i

        int size=vector.size();
        if(size==0) return null;
        curvePTs=new CurvePT[size];
        for(int i=0;i<size;i++) {
            curvePTs[i]=(CurvePT)vector.get(i);
            if(debug>0) System.out.println("-- Curve2D.ProjectionToCircularArc " +
                    "\n    curvePTs["+i+"]="+curvePTs[i].toString());
        }
        return curvePTs;
    }
    
    protected static CurvePT[] ProjectionToArbitrary(Point2D point, Vector2D dir, 
            Segment2D segment){
		int debug=projectionToArbitrary_debug;
        Vector subdivisionVector=new Vector();
       if(debug>1) System.out.println("  -- ProjectionToArbitrary start point="+
                point.toString()+", segment="+segment.toString());
       int div=180;
       double delta=1.0d/div;
       long startTime = System.currentTimeMillis();
       for(int i=0;i<div;i++){
           double ts=delta*i;
           double te=delta*(i+1);
         //------------------------------------------------------------//  
           Curve2DUtil.bisectionForProjectionLines(point,dir,  segment, 
                   ts, te, subdivisionVector);
         //------------------------------------------------------------//  
       }
       long endTime = System.currentTimeMillis();
       if(debug>1) System.out.println("  -- ProjectionToArbitrary Bisection check,  used time="+
                (endTime-startTime)+" milisecond");
       int size=subdivisionVector.size();
       Vector solutionVector=new Vector();
       for(int i=0;i<size;i++){
           double[] interval=(double[])subdivisionVector.get(i);
           //System.out.println(" -- result["+i+"]="+result.toString());
           double ts=interval[0];
           double te=interval[1];
         //-----------------------------------------------------------------------//
           CurvePT newtonPT
               =Curve2DUtil.NewtonRaphsonForProjectionLines(point, dir, segment, ts, te);
         //------------------------------------------------------------------------//  
           if(newtonPT!=null) {
               double t=newtonPT.getParameter();
               int index=-1;
             //duplication check!
               for(int j=0;j<solutionVector.size();j++){
                   CurvePT saved=(CurvePT)solutionVector.get(j);
                   if( Math.abs(t-saved.getParameter())<eps10){
                       index=j;
                       break;
                   }
               }
               if(index<0) solutionVector.add(newtonPT);
           }
       }
       size=solutionVector.size();
       CurvePT[] curvePTs=new CurvePT[size];
       for(int i=0;i<solutionVector.size();i++){
           CurvePT tsolution=(CurvePT)solutionVector.get(i);
           curvePTs[i]=tsolution;
           if(debug>1)  System.out.println("  -- Curve2D.ProjectionToArbitrary " +
                    ", curvePTs["+i+"]="+curvePTs[i].toString());
       }
       return curvePTs;
    }
    
    protected static boolean boxCheck(Point2D point, Vector2D dir, Rectangle2D box){
        double x=box.getX(), y=box.getY(), w=box.getWidth(), h=box.getHeight();
        Vector2D P=new Vector2D(point);
        Vector2D[] points=new Vector2D[4];
        double ext=1.0d;
        points[0]=new Vector2D(x-ext,y-ext);
        points[1]=new Vector2D(x+w+ext,y-ext);
        points[2]=new Vector2D(x+w+ext,y+h+ext);
        points[3]=new Vector2D(x-ext,y+h+ext);
        double signSave=0d;
        boolean crossed=false;
        for(int i=0;i<4;i++){
            Vector2D vec=Vector2D.sub(points[i],P);
            double vprod=Vector2D.vproduct(dir, vec);
            double sign=Math.signum(vprod);
            if(i==0) signSave=sign;
            if(signSave*sign<=0d) {
                crossed=true;
                break;
            }
        }
        return crossed;
    }
    
    protected static void bisectionForProjectionLines(Point2D point, Vector2D dir,
            Segment2D segment, double ts, double te, Vector vector){
		int debug=bisectionForProjectionLine_debug;
        double delta=2d;
        double[] interval=new double[2];
        Vector2D Pt=new Vector2D(point);
        Vector2D Xs=new Vector2D(segment.getP(ts));
        Vector2D Xe=new Vector2D(segment.getP(te));
        Vector2D PtToXs=Vector2D.unitVector(Vector2D.sub(Xs, Pt));
        Vector2D PtToXe=Vector2D.unitVector(Vector2D.sub(Xe, Pt));
        Vector2D unitDir=Vector2D.unitVector(dir);
        double vprod1=Vector2D.vproduct(unitDir, PtToXs);
        double vprod2=Vector2D.vproduct(unitDir, PtToXe);
        boolean found=false;
        if(vprod1*vprod2<=0) {
            interval[0]=ts;
            interval[1]=te;
            found=true;
        }
        if(found){
            double arcLength=Vector2D.dist(Xs, Xe);   
            if(debug>1) System.out.println(" ++ bisection result stored, "+
                        ", ts,te="+Util.Num(ts)+","+Util.Num(te)+", te-ts="+Util.Num((te-ts))+
                        ", sprod1, sprod2="+Util.Num(vprod1)+","+Util.Num(vprod2)+
                        ", arclength="+Util.Num(arcLength));
            if(arcLength<delta||(te-ts)<eps10){
                vector.add(interval);
                return;
            } else {
                int divide=2;
                double deltaT=(te-ts)/divide;
                for(int i=0;i<divide;i++) {
                    double dts=deltaT*i+ts;
                    double dte=deltaT*(i+1)+ts;
                  //-----------------------------------------------------------//  
                    Curve2DUtil.bisectionForProjectionLines(point, dir, segment, 
                            dts, dte, vector);
                  //-----------------------------------------------------------//  
                }    
            }
        } else {
            return;
        }
    }
//++++----------------------------//
//  NewtonRaphsonForProjectionLine
//--------------------------------//
    protected static CurvePT NewtonRaphsonForProjectionLines(Point2D point, Vector2D dir,
            Segment2D segment, double ts, double te){
		int debug=NewtonRaphsonForProjectionLine_debug;
        if(debug>1) System.out.println("  -- Newton=raphson start  ts,te="+ts+","+te);
        //double[] solution=null;
        Vector2D PT=new Vector2D(point);
        double t=0.5d*(ts+te); 
        int iter=0;
        double sinAngle=0;
        double dt=Curve2D.largeNumber;
        boolean error=false;
        boolean  converged=false;
        while(iter<10){
            Vector2D X=new Vector2D(segment.getP(t));
            Vector2D T=segment.getTangent(t);
            Vector2D ptToX=Vector2D.sub(X,PT);
            double F=Vector2D.vproduct(ptToX, dir);
            double DF=Vector2D.vproduct(T,dir);
            sinAngle=F/(Vector2D.length(ptToX)*Vector2D.length(T));
            sinAngle=Math.abs(sinAngle);
            if(Math.abs(DF)<eps4) {
                error=true;
                break;
            }
            dt=-F/DF;
            t=t+dt;
            if(t<-eps10||t>1d+eps10) {
                if(debug>1) System.out.println("*** Warning in NewtonRaphsonForProjectionLine; " +
                        "t out of bound, iter="+iter+", t="+t+", dt="+dt);
                return null;
            }
            if(Math.abs(dt)<eps12){
                converged=true;
                break;
            }
            iter++;
        }
        if(error||!converged) {
            if(debug>1) System.out.println("*** Warning in NewtonRaphsonForNormalPoint failed; " +
                    ", error="+error+", converged="+converged+
                    "iter="+iter+", t="+t+", dt="+dt);
            return null;
        }
        CurvePT pt=new CurvePT(t, segment.getP(t));
        if(debug>0) System.out.println("  -- Newton=raphson iter="+iter+", CurvePT="+pt.toString());
        return pt;
    }
    
    
//****++++----------//
//  getNormalLines
//------------------//
    public static CurvePT[] getNormalLines(Point2D point, Curve2D curve){
		int debug=getNormalLines_debug;
        int numSegments=curve.getNumOfSegments();
        CurvePT[] segmentPoints=new CurvePT[0];
        Vector vector=new Vector();
        for(int i=0;i<numSegments;i++){
            Segment2D segment=curve.getSegment2D(i);
            if(debug>1) System.out.println("-- getNormalLines point="+point.toString()+
                    ", segment no="+i+", segment="+segment.toString());
          //------------------------------------------------------------//    
            segmentPoints=Curve2DUtil.getNormalLinesOnSegment(point, segment);
          //------------------------------------------------------------//    
            if(segmentPoints!=null) {
                for(int j=0;j<segmentPoints.length;j++) {
                    segmentPoints[j].t=segmentPoints[j].t+i;
                    vector.add(segmentPoints[j]);
                }
            }
        }
        int size=vector.size();
        CurvePT[] curvePoints=new CurvePT[size];
        for(int i=0;i<size;i++) curvePoints[i]=(CurvePT)vector.get(i);
        CurvePT[] newCurvePTs=curvePoints;
      //-------------------------------------------------------------------// 
        if(size>=2) newCurvePTs
                =Curve2DUtil.eliminateDuplicationAndSort(curvePoints, 1e-8);
      //-------------------------------------------------------------------//  
        for(int i=0;i<newCurvePTs.length;i++) newCurvePTs[i].setCurve(curve);
        return newCurvePTs;

    }
    
    protected static CurvePT[] getNormalLinesOnSegment(Point2D point, Segment2D segment){
        int type=3;
        CurvePT[] curvePTs=new CurvePT[0];
        int segmentType=segment.getType();
        if(segmentType==Segment2D.MOVETO) return curvePTs;
        boolean affine=segment.isAffineTransform();
        if(segmentType==Segment2D.LINE) type=1;
        if(segmentType==Segment2D.ARC&&!affine) {
            Arc2D arc=(Arc2D)segment.getAwtGeom();
            double width=arc.getWidth();
            double height=arc.getHeight();
            if(Math.abs(width-height)<Curve2DUtil.eps4) type=2;
        }

        switch(type){
            case 1: {
                //----------------------------------------------------//  
                CurvePT curvePT=Curve2DUtil.NormalToLine(point, segment);
                //----------------------------------------------------//    
                if(curvePT!=null) {
                    curvePTs= new CurvePT[1];
                    curvePTs[0]=curvePT;
                }
                break;
            }
            case 2: {
              //-------------------------------------------------------//    
                curvePTs=Curve2DUtil.NormalToCircularArc(point, segment);
              //-------------------------------------------------------//    
                break;
            }
            case 3: {
               //-------------------------------------------------------//    
                curvePTs=Curve2DUtil.NormalToArbitrary(point, segment);
               //-------------------------------------------------------// 
                break;
            }
        }
        return curvePTs;
    }

    protected static CurvePT NormalToLine(Point2D point, Segment2D segment){
        CurvePT curvePT=null;
        Vector2D pt=new Vector2D(point);
        Vector2D pt1=new Vector2D(segment.getP(0));
        Vector2D pt2=new Vector2D(segment.getP(1));
        Vector2D unitVec=Vector2D.unitVector(Vector2D.sub(pt2,pt1));
        double dist=Vector2D.dist(pt1, pt2);
        double sprod=Vector2D.sproduct(Vector2D.sub(pt,pt1),unitVec);
        double t=sprod/dist;
        Vector2D normalPt=Vector2D.add(pt1,Vector2D.multiply(sprod, unitVec));
        if(t<0||t>1) return null;
        curvePT=new CurvePT(t, new Point2D.Double(normalPt.getX(), normalPt.getY()));
        return curvePT;
    }
    
    protected static CurvePT[] NormalToCircularArc(Point2D point, Segment2D segment){
        CurvePT curvePT=null;
        Vector vector=new Vector();
        Arc2D arc=(Arc2D)segment.getAwtGeom();
        double x=arc.getX();
        double y=arc.getY();
        double width=arc.getWidth();
        double height=arc.getHeight();
        double angleStart=arc.getAngleStart();
        double angleExtent=arc.getAngleExtent();
        if(Math.abs(width-height)>Curve2DUtil.eps4) return null;
        Vector2D pt=new Vector2D(point);
        Vector2D center=new Vector2D(x+0.5*width, y+0.5*height);
        Vector2D chord=Vector2D.sub(pt, center);
        double theta=Math.atan2(-chord.getY(), chord.getX());
        for(int i=-2;i<=2;i++){
            double thetaShift=theta+pai*i;
            double t=(thetaShift*180/pai-angleStart)/angleExtent;
            if(t>=0&&t<=1) {
                Point2D normalPt=segment.getP(t);
                curvePT=new CurvePT(t, normalPt);
                vector.add(curvePT);
             }
         }
        int size=vector.size();
        CurvePT[] curvePoints=new CurvePT[size];
        for(int i=0;i<size;i++) curvePoints[i]=(CurvePT)vector.get(i);
        return curvePoints;
    }
    
    protected static CurvePT[] NormalToArbitrary(Point2D point, Segment2D segment){
		int debug=normalToArbitrary_debug;
        Vector subdivisionVector=new Vector();
       if(debug>1) System.out.println("  -- NormalToArbitrary start point="+
                point.toString()+", segment="+segment.toString());
       int div=180;
       double delta=1.0d/div;
       long startTime = System.currentTimeMillis();
       for(int i=0;i<div;i++){
           double ts=delta*i;
           double te=delta*(i+1);
         //-----------------------------------------------------------------------------//  
           Curve2DUtil.bisectionForNormalLines(point, segment, ts, te, subdivisionVector);
         //-----------------------------------------------------------------------------//  
       }
       long endTime = System.currentTimeMillis();
       if(debug>1) System.out.println("  -- NormalToArbitrary Bisection check,  used time="+
                (endTime-startTime)+" milisecond");
       int size=subdivisionVector.size();
       Vector solutionVector=new Vector();
       for(int i=0;i<size;i++){
           double[] interval=(double[])subdivisionVector.get(i);
           //System.out.println(" -- result["+i+"]="+result.toString());
           double ts=interval[0];
           double te=interval[1];
         //-----------------------------------------------------------------------//
           CurvePT newtonPT
                   =Curve2DUtil.NewtonRaphsonForNormalLines(point, segment, ts, te);
         //------------------------------------------------------------------------//  
           if(newtonPT!=null) {
               double t=newtonPT.getParameter();
               int index=-1;
             //duplication check!
               for(int j=0;j<solutionVector.size();j++){
                   CurvePT saved=(CurvePT)solutionVector.get(j);
                   if( Math.abs(t-saved.getParameter())<eps10){
                       index=j;
                       break;
                   }
               }
               if(index<0) solutionVector.add(newtonPT);
           }
       }
       size=solutionVector.size();
       CurvePT[] curvePTs=new CurvePT[size];
       for(int i=0;i<solutionVector.size();i++){
           CurvePT tsolution=(CurvePT)solutionVector.get(i);
           curvePTs[i]=tsolution;
           if(debug>1)  System.out.println("  -- Curve2D.NormalToArbitrary " +
                    ", curvePTs["+i+"]="+curvePTs[i].toString());
       }
       return curvePTs;
    }
    
    protected static void bisectionForNormalLines(Point2D point,
            Segment2D segment, double ts, double te, Vector vector){
		int debug=bisectionForNormalLines_debug;
        double delta=2d;
        double[] interval=new double[2];
        Vector2D Pt=new Vector2D(point);
        Vector2D Xs=new Vector2D(segment.getP(ts));
        Vector2D Xe=new Vector2D(segment.getP(te));
        Vector2D PtToXs=Vector2D.sub(Xs, Pt);
        Vector2D PtToXe=Vector2D.sub(Xe, Pt);
        Vector2D tangent1=segment.getTangent(ts);
        Vector2D tangent2=segment.getTangent(te);
        double sprod1=Vector2D.sproduct(tangent1,PtToXs);
        double sprod2=Vector2D.sproduct(tangent2,PtToXe);
        boolean found=false;
        if(sprod1*sprod2<=0) {
            interval[0]=ts;
            interval[1]=te;
            found=true;
        }
        if(found){
            double arcLength=Vector2D.dist(Xs, Xe);   
            if(debug>1) System.out.println(" ++ bisection result stored, "+
                        ", ts,te="+Util.Num(ts)+","+Util.Num(te)+", te-ts="+Util.Num((te-ts))+
                        ", sprod1, sprod2="+Util.Num(sprod1)+","+Util.Num(sprod2)+
                        ", arclength="+Util.Num(arcLength));
            if(arcLength<delta||(te-ts)<eps10){
                vector.add(interval);
                return;
            } else {
                int divide=2;
                double deltaT=(te-ts)/divide;
                for(int i=0;i<divide;i++) {
                    double dts=deltaT*i+ts;
                    double dte=deltaT*(i+1)+ts;
                  //---------------------------------------------------------------------//  
                    Curve2DUtil.bisectionForNormalLines(point, segment, dts, dte, vector);
                  //---------------------------------------------------------------------//  
                }    
            }
        } else {
            return;
        }
    }
    
    protected static CurvePT NewtonRaphsonForNormalLines(Point2D point, 
            Segment2D segment, double ts, double te){
		int debug=NewtonRaphsonForNormalLines_debug;
        if(debug>1) System.out.println("  -- Newton=raphson start  ts,te="+ts+","+te);
        double[] solution=null;
        Vector2D PT=new Vector2D(point);
        double t=0.5d*(ts+te); 
        int iter=0;
        double cosAngle=0;
        double dt=Curve2D.largeNumber;
        boolean error=false;
        boolean  converged=false;
        while(iter<10){
            Vector2D X=new Vector2D(segment.getP(t));
            Vector2D T=segment.getTangent(t);
            Vector2D DT=segment.getTangentDerivative(t);
            Vector2D ptToX=Vector2D.sub(X,PT);
            double F=Vector2D.sproduct(ptToX, T);
            double DF=Vector2D.sproduct(T,T)+Vector2D.sproduct(ptToX,DT);
            cosAngle=F/(Vector2D.length(ptToX)*Vector2D.length(T));
            cosAngle=Math.abs(cosAngle);
            if(Math.abs(DF)<eps4) {
                error=true;
                break;
            }
            dt=-F/DF;
            t=t+dt;
            if(t<-eps10||t>1d+eps10) {
                if(debug>1) System.out.println("*** Warning in NewtonRaphsonForNormalLines; " +
                        "t out of bound, iter="+iter+", t="+t+", dt="+dt);
                return null;
            }
            if(Math.abs(dt)<eps10){
                converged=true;
                break;
            }
            iter++;
        }
        if(error||!converged) {
            if(debug>1) System.out.println("*** Warning in NewtonRaphsonForNormalLines failed; " +
                    ", error="+error+", converged="+converged+
                    "iter="+iter+", t="+t+", dt="+dt);
            return null;
        }
        //solution=new double[2];
        //solution[0]=t;
        //solution[1]=cosAngle;
        CurvePT pt=new CurvePT(t, segment.getP(t));
        if(debug>1) System.out.println("  -- Newton=raphson iter="+iter+", CurvePT="+pt.toString());
        return pt;
    }
    
//****++++-------------//
//  getShortestNormalLine
//---------------------//
    public static CurvePT getShortestNormalLine(Point2D point, Curve2D curve){
		//-----------------------------------------------------------//
        CurvePT[] normalPTs=Curve2DUtil.getNormalLines(point, curve);
		//-----------------------------------------------------------//
        CurvePT nearestPT=null;
        double distMin=1e+5;
        if(normalPTs!=null||normalPTs.length==0) {
            for(int i=0;i<normalPTs.length;i++) {
                Point2D curvePT=normalPTs[i].getP();
                double dist=Vector2D.dist(point, curvePT);
                if(dist<distMin){
                    distMin=dist;
                    nearestPT=normalPTs[i];
                }
            }//for i
        }
        if(nearestPT!=null) nearestPT.setCurve(curve);
        return nearestPT;
    }
//****++++-------------//
//  getShortestLine
//---------------------//
    public static CurvePT getShortestLine(Point2D point, Curve2D curve){
		//----------------------------------------------------------------//
        CurvePT nearestPT=Curve2DUtil.getShortestNormalLine(point, curve);
		//----------------------------------------------------------------//
        double distMin=Curve2DUtil.largeNumber;
        if(nearestPT!=null) distMin=Vector2D.dist(point, nearestPT.getP());
        int numSegments=curve.getNumOfSegments();
        for(int i=0;i<=numSegments;i++){
            Point2D segmentPT=curve.getP((double)i);
            if(segmentPT==null) continue;
            double dist=Vector2D.dist(point, segmentPT);
            if(dist<distMin){
                distMin=dist;
                nearestPT=new CurvePT((double)i, segmentPT);
            }
        }//for i
        if(nearestPT==null){
            System.out.println("*** Error Curve2D.getShortestLine ShortestLine not found");
        } else{
            double dist=Vector2D.dist(point, nearestPT.getP());
            //if(debug>1) System.out.println("** Curve2D.getnearestPT dist="+dist+
             //       ", nearestPT"+nearestPT.toString());
        }
        nearestPT.setCurve(curve);
        return nearestPT;
    }
	
//****++++-------------------//
// getNormalLinesBetweenShapes
//---------------------------//
	public static Vector getNormalLinesBetweenShapes(Curve2D curve1, Curve2D curve2,
			String shapeId1, String shapeId2) {
		int debug=getNormalsBetweenShapes_debug;
		String methodName="Curve2DUtil.getNormalsBetweenShapes";
		Vector solutionVector=new Vector();
		Vector segSolutionVector=null;
		Vector vector=new Vector();
		int numSeg1 = curve1.getNumOfSegments();
		int numSeg2 = curve2.getNumOfSegments();
		//Vector normalsVector=new Vector();
		for(int j=0;j<numSeg2;j++){
			Segment2D segment2=curve2.getSegment2D(j);
			for (int i = 0; i < numSeg1; i++) {
				Segment2D segment1 = curve1.getSegment2D(i);
				if(debug>0) System.out.println("** "+ methodName
						+", (i.j)=("+i+","+j+")"
						+", segment1="+Segment2D.codeStr[segment1.getType()]
						+", segment2="+Segment2D.codeStr[segment2.getType()]);
				int type1 = segment1.getType();
				int type2 = segment2.getType();
				Rectangle2D box1=segment1.getBoundingBox();
				Rectangle2D box2=segment2.getBoundingBox();
				double w1=box1.getWidth();
				double h1=box1.getHeight();
				double w2=box2.getWidth();
				double h2=box2.getHeight();
				int type = 9;

				if (type1 == Segment2D.MOVETO || type2 == Segment2D.MOVETO) return vector;
				if (type1 == Segment2D.LINE && type2 == Segment2D.LINE) type = 1;

				if (type1 == Segment2D.ARC && type2 == Segment2D.ARC) {
					boolean affine1=segment1.isAffineTransform();
					boolean affine2=segment2.isAffineTransform();
					boolean affine=affine1||affine2;
					boolean circle=Math.abs(w1-h1)+Math.abs(w2-h2)<eps4;
					if(circle&&!affine) type = 4;
				}

				switch (type) {
					case 1: {
						//-------------------------------------------------------------------------//   
						segSolutionVector = Curve2DUtil.segmentsNormalLinesBetweenLines(segment1, segment2);
						//-------------------------------------------------------------------------//  
						break;
					}
					case 2: {
						//-----------------------------------------------------------------//   
						//segIntervalVector = Curve2DUtil.intersectionPTOfLineAndArc(segment1, segment2);
						//----------------------------------------------------------------//   
						break;
					}
					case 3: {
						//------------------------------------------------------------------// 
						//segIntervalVector = Curve2DUtil.intersectionPTOfLineAndArc(segment2, segment1);
						//------------------------------------------------------------------//    
						break;
					}
					case 4: {
						//---------------------------------------------------------------------------//   
						segSolutionVector  = Curve2DUtil.segmentsNormalLinesBetweenCircles(segment1, segment2);
						//---------------------------------------------------------------------------//   
						break;
					}
					case 5: {
						//------------------------------------------------------------------// 
						//segIntervalVector = Curve2DUtil.intersectionPTOfLineAndQuad(segment2, segment1);
						//------------------------------------------------------------------//    
						break;
					}
					case 6: {
						//-----------------------------------------------------------------//   
						//segIntervalVector = Curve2DUtil.intersectionPTOfLineAndCubic(segment1, segment2);
						//----------------------------------------------------------------//   
						break;
					}
					case 7: {
						//------------------------------------------------------------------// 
						//segIntervalVector = Curve2DUtil.intersectionPTOfLineAndCubic(segment2, segment1);
						//------------------------------------------------------------------//    
						break;
					}
					case 9: {
						//------------------------------------------------------------------//   
						segSolutionVector=segmentsNormalLinesBetweenArbitraries(segment1, segment2);
						//------------------------------------------------------------------//    
						break;
					}
				}
				//---------------------------------------------------------------------//   
				//segIntervalVector=segmentsNormalsToArbitraries(segment1, segment2);
				//----------------------------------------------------------------------//    
				int size=segSolutionVector.size();
				//NormalsInfo segSolution;
				//ShapesDistInfo segSolution;
				double[] T=new double[4];
				String str="\n* Curve2DUtil.getNormalsBetweenShapes-1 segSolutionVector size="+size+"\n";
				//System.out.println("\n* Curve2DUtil.getNormalsBetweenShapes-1 segSolutionVector size="+size);
				for (int k = 0; k < size; k++) {
					NormalsInfo segSolution = (NormalsInfo)segSolutionVector.get(k);
				        str+=" - Curve2DUtil.getNormalsBetweenShapes segSolution "
								+ "i,j,k="+i+","+j+","+k+segSolution.toString();

					
					if(segSolution.type==NormalsInfo.SegmentSolution){
						Curve2D[] curves=new Curve2D[2];
						curves[0]=curve1;
						curves[1]=curve2;
						double[] t=new double[2];
						t[0]=segSolution.t[0]+i;
						t[1]=segSolution.t[1]+j;
						NormalsInfo solution=new NormalsInfo(NormalsInfo.Solution, 
								shapeId1, shapeId2, curves[0], curves[1], t[0], t[1]);
						solutionVector.add(solution);
					}
					if(segSolution.type==NormalsInfo.SegmentIntervalSolution ){
						Curve2D[] curves=new Curve2D[2];
						curves[0]=curve1;
						curves[1]=curve2;
						double[] interval=new double[4];
						interval[0]=segSolution.interval[0]+i;
						interval[1]=segSolution.interval[1]+i;
						interval[2]=segSolution.interval[2]+j;
						interval[3]=segSolution.interval[3]+j;
						NormalsInfo solution=new NormalsInfo(NormalsInfo.IntervalSolution, 
								shapeId1, shapeId2, curves[0], curves[1], interval);
						solutionVector.add(solution);
					}
				} //for k
				if(debug>1) System.out.println(str);
			}//for i
		}//for j
		//Eliminate Duplication
		vector=eliminateNormalLinesDuplication(solutionVector);
		if(debug>1){
			int size=solutionVector.size();
			System.out.println("\n* Curve2DUtil.getNormalsBetweenShapes-2 (before eliminateDuplication) size="+size);
			for(int i=0;i<size;i++){
				String str="";
				NormalsInfo info=(NormalsInfo)solutionVector.get(i);
				str+="- i="+i+info.toString();
				System.out.println(str);
			}
		}
		if(debug>0){
			int size=vector.size();
			System.out.println("\n* Curve2DUtil.getNormalsBetweenShapes-3 (after eliminateDuplication) size="+size);
			for(int i=0;i<size;i++){
				String str="";
				NormalsInfo info=(NormalsInfo)vector.get(i);
				str+="- i="+i+info.toString();
				System.out.println(str);
			}
		}
		return vector;
	}
//+++-----------------------//
// eliminateNormalsDuplication
//---------------------------//
	protected static Vector eliminateNormalLinesDuplication(Vector distanceVector){
		Vector vector=new Vector();
		int size=distanceVector.size();
		for(int i=0;i<size;i++){
			NormalsInfo info=(NormalsInfo)distanceVector.get(i);
			boolean same=false;
			for(int j=0;j<vector.size();j++){
				NormalsInfo savedInfo=(NormalsInfo)vector.get(j);
				boolean type=(info.type==savedInfo.type);
				double diff=0;
				//Solution=0; SolutionInterval=1; SegmentSolution=2; SegmentSolutionInterval=3; 
				//CurveInterval=4; egmentInterval=5;
				switch(info.type){
					case NormalsInfo.Solution: {
						diff=Math.abs(info.t[0]-savedInfo.t[0])+Math.abs(info.t[1]-savedInfo.t[1]);
						break;
					}
					case NormalsInfo.IntervalSolution: {
						diff=Math.abs(info.interval[0]-savedInfo.interval[0])
								+Math.abs(info.interval[1]-savedInfo.interval[1])
								+Math.abs(info.interval[2]-savedInfo.interval[2])
								+Math.abs(info.interval[3]-savedInfo.interval[3]);
						break;
					}
					case NormalsInfo.SegmentSolution: {
						diff=Math.abs(info.t[0]-savedInfo.t[0])+Math.abs(info.t[1]-savedInfo.t[1]);
						break;
					}
					case NormalsInfo.SegmentIntervalSolution : {
						diff=Math.abs(info.interval[0]-savedInfo.interval[0])
								+Math.abs(info.interval[1]-savedInfo.interval[1])
								+Math.abs(info.interval[2]-savedInfo.interval[2])
								+Math.abs(info.interval[3]-savedInfo.interval[3]);
						break;
					}

					case NormalsInfo.SegmentHitInterval: {
						diff=Math.abs(info.interval[0]-savedInfo.interval[0])
								+Math.abs(info.interval[1]-savedInfo.interval[1])
								+Math.abs(info.interval[2]-savedInfo.interval[2])
								+Math.abs(info.interval[3]-savedInfo.interval[3]);
						break;
					}
				}
				if(type&&diff<eps4) same=true;
			}//for j
			if(!same) vector.add(info);
		} // for i
		return vector;
	}
//++++--------------------//
// segmentsNormalsToLines
//------------------------//
	protected static Vector segmentsNormalLinesBetweenLines(Segment2D segment1, Segment2D segment2){
		int debug=segmentsNormalsBetweenLines_debug;
		String methodName="Curve2DUtil.segmentsNormalsBetweenLines";
		Vector normalsVector=new Vector();
	// Get intersection pioints to the normalsVector(Vector)
		CrossCurvePT crossP=Curve2DUtil.intersectionPtOfLines(segment1, segment2);
		if(crossP!=null){
			NormalsInfo info=new NormalsInfo(NormalsInfo.SegmentSolution, 
							segment1, segment2, crossP.getParameterT1(), crossP.getParameterT2());
			normalsVector.add(info);
		}
	// Get intervals between tow line segments
		Vector2D tan1=segment1.getTangent(0.0);
		tan1=Vector2D.unitVector(tan1);
		Vector2D tan2=segment2.getTangent(0.0);
		tan2=Vector2D.unitVector(tan2);
		if(Math.abs(Vector2D.vproduct(tan1, tan2))>eps4) {
			return normalsVector;
		}
		CurvePT curvePT=null;
		Point2D p1=segment1.getP(0.0);
		Point2D p2=segment1.getP(1.0);
		Vector2D norm=Vector2D.unitNormalVector(tan1);
		double[] T1=new double[4];
		double[] T2=new double[4];
		int id=0;
		curvePT=Curve2DUtil.ProjectionToLine(p1, norm, segment2);
		if(curvePT!=null){
			T1[id]=0.0;
			T2[id]=curvePT.getParameter();
			++id;
		}
		curvePT=Curve2DUtil.ProjectionToLine(p2, norm, segment2);
		if(curvePT!=null){
			T1[id]=1.0;
			T2[id]=curvePT.getParameter();
			++id;
		}
		p1=segment2.getP(0.0);
		p2=segment2.getP(1.0);
		curvePT=Curve2DUtil.ProjectionToLine(p1, norm, segment1);
		if(curvePT!=null){
			T1[id]=curvePT.getParameter();
			T2[id]=0.0;
			++id;
		}
		curvePT=Curve2DUtil.ProjectionToLine(p2, norm, segment1);
		if(curvePT!=null){
			T1[id]=curvePT.getParameter();
			T2[id]=1.0;
			++id;
		}
		if(id==0) return normalsVector;
		
		double[] T=new double[id];
		for(int i=0;i<id;i++){
			T[i]=T1[i];
		}
		int[] index=Util.indexedSimpleSort(T);
		//debug=1;
		String str=" -- "+methodName+ " sorted T \n";
		if(debug>1) System.out.print(" -"+methodName+ " sorted T ");
		for(int i=0;i<id;i++){
			str+="  - index[i]="+index[i]+", T[index[i]]="+Util.Num4(T[index[i]])+"\n";
		}
		if(debug>1) System.out.println(str);
		double[] interval=new double[4];
		//for(int i=0;i<4;i++){
			interval[0]=T1[index[0]];
			interval[1]=T1[index[0]];
			interval[2]=T2[index[0]];
			interval[3]=T2[index[0]];
		//}
		for(int i=1;i<id;i++){
			if(T1[index[i]]>interval[1]) {
				interval[1]=T1[index[i]];
				interval[3]=T2[index[i]];
			}
		}
		Segment2D[] segments=new Segment2D[2];
		segments[0]=segment1;
		segments[1]=segment2;
		NormalsInfo segSolutionInterval
				=new NormalsInfo(NormalsInfo.SegmentIntervalSolution , segments, interval);
		normalsVector.add(segSolutionInterval);
		if(debug>0){
			NormalsInfo segSolution=null;
			System.out.println("** "+ methodName+ " SegmentSolution size="+normalsVector.size());
			for(int i=0; i<normalsVector.size();i++){
				str="";
				segSolution=(NormalsInfo)normalsVector.get(i);
				str +="--"+ segSolution.toString();
				System.out.println(str);
			}
		}
		return normalsVector;
	}
//++++--------------------//
// segmentsNormalsToCircles
//------------------------//
	protected static Vector segmentsNormalLinesBetweenCircles(Segment2D segment1, Segment2D segment2){
		int debug=segmentsNormalsBetweenCircles_debug;
		String methodName="Curve2DUtil.egmentsNormalsBetweenCircles";
		Vector normalsVector=new Vector();
	// Get intersection pioints to the normalsVector(Vector)
		CrossCurvePT[] crossPs=Curve2DUtil.intersectionPtsOfCircles(segment1, segment2);
		//CrossCurvePT[] crossPs=Curve2DUtil.intersectionPTOfArbitraries(segment1, segment2);
		if(debug>0) {
			if(crossPs==null){
				System.out.println(" -"+ methodName+ " crossPs=null");
			}else{
			if(debug>0) System.out.println(" - "+ methodName+ " crossPs.length="+crossPs.length);
			}
		}
		if(crossPs!=null){
			for(int i=0;i<crossPs.length;i++){
				NormalsInfo info=new NormalsInfo(NormalsInfo.SegmentSolution, 
							segment1, segment2, crossPs[i].getParameterT1(), crossPs[i].getParameterT2());
				normalsVector.add(info);
				String str="";
				str +="-- "+ methodName+ info.toString();
				if(debug>0) System.out.println(str);
			}
		}
	// Get normallines between tow line segments
		Arc2D arc1=(Arc2D)segment1.getShape();
		Arc2D arc2=(Arc2D)segment2.getShape();
		
		double w1=arc1.getWidth();
		double h1=arc1.getHeight();
		double w2=arc2.getWidth();
		double h2=arc2.getHeight();
		Point2D centerP1=new Point2D.Double(arc1.getCenterX(), arc1.getCenterY());
		Point2D centerP2=new Point2D.Double(arc2.getCenterX(), arc2.getCenterY());
		Vector2D centersV=Vector2D.sub(centerP2, centerP1);
		double distCenters=Vector2D.abs(centersV);
		if(distCenters<eps4){

		} else{
			Line2D line=new Line2D.Double(centerP1, centerP2);
			Segment2D lineSeg=new Segment2D(Segment2D.LINE, line);
			lineSeg=Curve2DUtil.extendSegment2D(lineSeg, w2);
			lineSeg=lineSeg.reverseSegment();
			lineSeg=Curve2DUtil.extendSegment2D(lineSeg, w1);
			lineSeg=lineSeg.reverseSegment();
			CrossCurvePT[] crossP1=Curve2DUtil.getIntersectionPtsOfSegments(segment1, lineSeg);
			CrossCurvePT[] crossP2=Curve2DUtil.getIntersectionPtsOfSegments(segment2, lineSeg);
			if(crossP1!=null&&crossP2!=null){
				for(int j=0;j<crossP2.length;j++){
					for(int i=0;i<crossP1.length;i++){
						//NormalsInfo(int type, Segment2D segment1, Segment2D segment2, double t1, double t2) 
						NormalsInfo info=new NormalsInfo(NormalsInfo.SegmentSolution, 
							segment1, segment2, crossP1[i].getParameterT1(), crossP2[j].getParameterT1());
						normalsVector.add(info);
					}
				}
				if(debug>0){
					NormalsInfo segSolution=null;
					System.out.println("** "+ methodName+ " SegmentSolution size="+normalsVector.size());
					for(int i=0; i<normalsVector.size();i++){
						String str="";
						segSolution=(NormalsInfo)normalsVector.get(i);
						str += segSolution.toString();
						System.out.println(str);
					}
				}
			}
		}
		return normalsVector;
	}
//++++--------------------------//
// segmentsNormalsToArbitraries
//------------------------------//
	protected static Vector segmentsNormalLinesBetweenArbitraries(Segment2D segment1, Segment2D segment2) {
		int debug=segmentsNormalsBetweenArbitraries_debug;
		String indent=" ";
	    String methodName="segmentsNormalsBetweenArbitraries";
		if(debug>1) System.out.println(indent+"** "+ methodName+ " start");
		//CrossCurvePT[] crossPTs=null;
		Vector normalsVector=new Vector();
		//int numDiv = 8;
		double stopSize = 4;
		int depth=0;
		Segment2D[] segments=new Segment2D[2];
		int[] numDiv=new int[2];
		double[] T=new double[4];
		segments[0]=segment1;
		segments[1]=segment2;
		for(int i=0;i<2;i++){
			if(segments[i].getType()==Segment2D.LINE) numDiv[i]=2;
			if(segments[i].getType()==Segment2D.ARC) numDiv[i]=8;
			if(segments[i].getType()==Segment2D.QUAD) numDiv[i]=2;
			if(segments[i].getType()==Segment2D.CUBIC) numDiv[i]=3;
		}
		T[0]=0d;
		T[1]=1d;
		T[2]=0d;
		T[3]=1d;
		//---------------------------------------------------------------//  
		roughCheck(depth, stopSize, numDiv, segments, T, normalsVector);
		//---------------------------------------------------------------//  
		int size=normalsVector.size();
		NormalsInfo segInterval;
		NormalsInfo segSolution;
		if(debug>0) {
			System.out.println(indent+"* "+ methodName+" List1(normalsVector SegmentHitInterval) size="+size);
			for (int i = 0; i < size; i++) {
				segInterval = (NormalsInfo)normalsVector.get(i);
				if(segInterval.type!=NormalsInfo.SegmentHitInterval) continue;
				T = segInterval.interval;
				String str =indent+"-- "+  methodName+ ", i="+i+" "+ segInterval.toString();
				System.out.println(str);
			}
		}

		//if(size>0&&debug>1) System.out.println(indent+"** "+  methodName+ "segSolutionVector size="+size);
		int id=0;
		for (int i = 0; i < size; i++) {
			segInterval = (NormalsInfo) normalsVector.get(i);
			if (segInterval.type != NormalsInfo.SegmentHitInterval) continue;
			T = segInterval.interval;
			double t1 = 0.5 * (T[0] + T[1]);
			double t2 = 0.5 * (T[2] + T[3]);
			//---------------------------------------------------------------------//
			segSolution=NewtonRaphsonForNormalLinesBetweenShapes(segInterval.segments[0], 
					segInterval.segments[1], t1, t2);
			//---------------------------------------------------------------------//
			if(segSolution!=null){
				normalsVector.add(segSolution);
				int vectorIndex=normalsVector.indexOf(segSolution);
				String str =indent+ "-- "+ methodName+ " segSolutions id=" + id
						+", vectorIndex="+vectorIndex;
				str += ", " + segSolution.toString();
				//if(debug>1) System.out.println(str);
				++id;
			}
		}
		
		if(debug>0) {
			System.out.println(indent+"** "+ methodName+" List2(normalsVector SegmentSolution) size="+size);
			size=normalsVector.size();
			for (int i = 0; i < size; i++) {
				segInterval = (NormalsInfo)normalsVector.get(i);
				if(segInterval.type!=NormalsInfo.SegmentSolution) continue;
				//T = segInterval.interval;
				String str =indent+"-- "+  methodName+ ", i="+i+" "+ segInterval.toString();
				System.out.println(str);
			}
		}
		return normalsVector;
	}

//++++---------//
// roughCheck
//--------------//
	protected static void roughCheck(int depth, double stopSize, int[] numDiv,
			Segment2D segments[], double[] T,
			Vector normalsVector) {
		int debug=roughCheck_debug ;
		String methodName="roughCheck";
		double d1=(T[1]-T[0])/(double)numDiv[0];
		double d2=(T[3]-T[2])/(double)numDiv[1];
		//Segment2D[] segments=new Segment2D[2];

		for (int i = 0; i < numDiv[0]; i++) {
			for (int j = 0; j < numDiv[1]; j++) {
				//Note: newT, divId, boxSize objects must be created here. 1016.08.10
				//If thesse objects are created outside i, j-loop, it will cause a bug
				double[] newT = new double[4];
				int[] divId = new int[2];
				double[] boxSize = new double[2];
				newT[0] = T[0]+d1*i;
				newT[1] = T[0]+d1*(i+1);
				newT[2] = T[2]+d2*j;
				newT[3] = T[2]+d2*(j+1);
				//--------------------------------------------------------------//  
				boolean segHit 
					= segmentHit(depth, segments[0], segments[1], newT);
				//--------------------------------------------------------------//   
				Rectangle2D box1 = segments[0].getBoundingBox(newT[0], newT[1]);
				Rectangle2D box2 = segments[1].getBoundingBox(newT[2], newT[3]);
				boxSize[0] = Math.max(box1.getWidth(), box1.getHeight());
				boxSize[1] = Math.max(box2.getWidth(), box2.getHeight());
				divId[0]=i;
				divId[1]=j;
				NormalsInfo segInterval
						=new NormalsInfo(NormalsInfo.SegmentHitInterval, 
							segments, depth, numDiv, divId, newT, boxSize);
				boolean boxSmall=segInterval.boxSize[0]<stopSize&&segInterval.boxSize[1]<stopSize;
				if (debug >1) {
				//if (debug >0&&segHit&&boxSmall) {
					String str="";
					str="** "+ methodName+segInterval.toString()+", segHit="+segHit;
					if (segHit&&boxSmall)str+="\n   save to Vector="+(segHit&&boxSmall);
					System.out.println(str);
				}
				if (segHit) {
					if(boxSmall){
						normalsVector.add(segInterval);
					} else {
						//Recursive call
						int[] nextNumDiv=new int[2];
						nextNumDiv[0] = 2;
						nextNumDiv[1] = 2;
						roughCheck(depth + 1, stopSize, nextNumDiv,
							segments, newT, normalsVector);
					}
				}
			}
		}
	}
//++++---------//
// segmentHit
//--------------//
	protected static boolean segmentHit(int depth, Segment2D segment1, Segment2D segment2, double[] newT) {
		int debug=segmentHit_debug;
		boolean segHit=false;
		Rectangle2D box2=segment2.getBoundingBox(newT[2], newT[3]);
		Point2D p1=segment1.getP(newT[0]);
		Point2D p2=segment1.getP(newT[1]);
		Vector2D e1=Vector2D.unitNormalVector(segment1.getTangent(newT[0]));
		Vector2D e2=Vector2D.unitNormalVector(segment1.getTangent(newT[1]));
		boolean rHit=rectHit(p1, p2, e1, e2, box2);
		if (debug > 1) {
			System.out.println(" -- segmentHit"
					+ " segment1=" + Segment2D.codeStr[segment1.getType()]
					+ ", segment2=" + Segment2D.codeStr[segment2.getType()]
					+ ", newT=(" + Util.Num4(newT[0]) + ", " + Util.Num4(newT[1])
					+ ", " + Util.Num4(newT[2])+ ", " + Util.Num4(newT[3])+")"+", segHit=" + segHit );
		}
		if(!rHit) return segHit;
		Rectangle2D box1=segment1.getBoundingBox(newT[0], newT[1]);
		p1 = segment2.getP(newT[2]);
		p2 = segment2.getP(newT[3]);
		e1 = Vector2D.unitNormalVector(segment2.getTangent(newT[2]));
		e2 = Vector2D.unitNormalVector(segment2.getTangent(newT[3]));
		rHit = rectHit(p1, p2, e1, e2, box1);
		if(rHit) segHit=true;
		if (debug > 1) {
			System.out.println(" -- segmentHit hit=" + segHit 
					+ ", segment1=" + Segment2D.codeStr[segment1.getType()]
					+ ", segment2=" + Segment2D.codeStr[segment2.getType()]
					+ ", newT=(" + Util.Num4(newT[0]) + ", " + Util.Num4(newT[1])
					+ ", " + Util.Num4(newT[2])+ ", " + Util.Num4(newT[3])+")");
		}
		return segHit;
	}
//++++---------//
// rectHit
//--------------//
	protected static boolean rectHit(Point2D p1, Point2D p2, Vector2D e1, Vector2D e2, Rectangle2D rect){
		int debug=rectHit_debug;
		Point2D[] cornerPts = new Point2D[4];
		double rX = rect.getX();
		double rY = rect.getY();
		double rW = rect.getWidth();
		double rH = rect.getHeight();
		cornerPts[0] = new Point2D.Double(rX, rY);
		cornerPts[1] = new Point2D.Double(rX + rW, rY);
		cornerPts[2] = new Point2D.Double(rX + rW, rY + rH);
		cornerPts[3] = new Point2D.Double(rX, rY + rH);
		boolean hit=false;
		boolean pos3=false;
		boolean pos4=false;
		for (int j = 0; j < 4; j++) {
			int pos = ptPosition(p1, p2, e1, e2, cornerPts[j]);
			if(pos==1||pos==2) hit=true;
			if(pos==3) pos3=true;
			if(pos==4) pos4=true;
		}
		if(pos3&&pos4) hit=true;
		if (debug > 1) {
			System.out.println(" -- rectHit hit="+hit + ", p1=" + Util.Pt(p1) + ", p2=" + Util.Pt(p2)
					+ ", e1=" + Util.Pt(e1) + ", e2=" + Util.Pt(e2) + ", p=" + Util.Rect(rect));
		}
		return hit;
	}
//++++---------//
// ptPosition
//--------------//
	public static int ptPosition(Point2D p1, Point2D p2, Vector2D e1, Vector2D e2, Point2D p){
		int debug=ptPosition_debug;
		if(debug>1) System.out.println("** ptPosition " + ", p1=" + Util.Pt(p1) + ", p2=" + Util.Pt(p2) 
				+ ", e1=" + Util.Pt(e1) + ", e2=" + Util.Pt(e2) + ", p=" + Util.Pt(p) );
		int region=0;
		Vector2D ex1=e1;
		Vector2D ex2=e2;
		Point2D px1=p1;
		Point2D px2=p2;
		Vector2D q =null;
		double vprod=Vector2D.vproduct(ex1, ex2);
		if (Math.abs(vprod) < eps4) {
			q = Vector2D.sub(px2, px1);
			Vector2D eNormal=Vector2D.normalVector(e1);
			double qsprod=Vector2D.sproduct(eNormal, q);
			if(qsprod<0) {
				eNormal=Vector2D.mult(-1.0, eNormal);
				qsprod=-qsprod;
			}
			Vector2D ep1=Vector2D.sub(p,p1);
			Vector2D ep2=Vector2D.sub(p,p2);
			double sprod1=Vector2D.sproduct(ep1, eNormal);
			double sprod2=Vector2D.sproduct(ep2, eNormal);
			if(sprod1>=0&&sprod1<=qsprod) region=1;
			if(sprod1<0) region=3;
			if(sprod1>qsprod) region=4;
			return region;
		}
		boolean exchanged=false;
		if (vprod < 0) {
			ex1 = e2;
			ex2 = e1;
			px1=p2;
			px2=p1;
			vprod = -vprod;
			exchanged=true;
			
		}
		q=Vector2D.sub(px2,px1);
		//vprod=-Vector2D.vproduct(ex1, ex2);
		double det=-vprod;
		double t1=-Vector2D.vproduct(q, ex2)/det;
		double t2=Vector2D.vproduct(ex1, q)/det;
		Vector2D crossVec1=Vector2D.add(new Vector2D(px1), Vector2D.multiply(t1, ex1));
		Vector2D crossVec2=Vector2D.add(new Vector2D(px2), Vector2D.multiply(t2, ex2));
		Point2D crossP1=new Point2D.Double(crossVec1.getX(), crossVec1.getY());
		Point2D crossP2=new Point2D.Double(crossVec2.getX(), crossVec2.getY());
		if(debug>0) System.out.println("* -- ptPosition exchanged=" + exchanged
					+ ", px1=" + Util.Pt(px1) + ", px2=" + Util.Pt(px2) + ", ex1=" + Util.Pt(ex1) + ", ex2=" + Util.Pt(ex2)
					+", vprod="+Util.Num2(vprod)
					+ ", crossP1=" + Util.Pt(crossP1) + ", crossP2=" + Util.Pt(crossP2)
					+ ", (t1,t2)=" + Util.Num2(t1) + "," + Util.Num2(t2));
		if(Vector2D.length(Vector2D.sub(crossP1, crossP2))>eps4){
			return region;
		}
		Point2D crossP=crossP1;
		Vector2D ep=Vector2D.unitVector(Vector2D.sub(p, crossP));
		double vprod1=Vector2D.vproduct(ex1, ep);
		double vprod2=Vector2D.vproduct(ep, ex2);
		
		if(vprod1>0&&vprod2>0) region=1;
		if(vprod1<0&&vprod2<0) region=2;
		if(vprod1>0&&vprod2<0) region=3;
		if(vprod1<0&&vprod2>0) region=4;
		return region;
	}
//++++------------------------------------//
// NewtonRaphsonForNormalsBetweenShapes
//----------------------------------------//
	protected static NormalsInfo NewtonRaphsonForNormalLinesBetweenShapes(Segment2D segment1, Segment2D segment2, 
			double t1s, double t2s) {
		//String methodName="NewtonRaphsonForNormalsBetweenShapes";
		int debug=NewtonRaphsonForNormalsBetweenShapes_debug;
		String indent="  ";
		//if(debug>0) System.out.println(indent+"-- NewtonRaphsonForNormalsBetweenShapes start");
		double dt = Curve2D.largeNumber;
		double df = Curve2D.largeNumber;
		double eps4=1.0e-4;
		double eps12=1.0e-12;
		double t1 = t1s;
		double t2 = t2s;
		boolean parallel = false;
		boolean converged = false;
        if(t1s<0d||t1s>1d||t2s<0d||t2s>1d){
            System.out.println(indent+"** Warning in Curve2DUtil.NewtonRaphsonForNormalsBetweenShapes:" 
					+ " t1s or t2s out of bound, t1s, tis="+Util.NumF3(t1s)+","+Util.NumF3(t2s));
            if(t1s<0d) t1s=0d;
            if(t1s>1d) t1s=1d;
            if(t2s<0d) t1s=0d;
            if(t2s>1d) t1s=1d;
        }
		if(debug>1) {
			System.out.println(indent+"-- NewtonRaphsonForNormalsBetweenShapes start"
					+" t1s="+Util.NumF3(t1s)+", t2s="+Util.NumF3(t2s));
		}
		int iter = 0;
		while (iter <= 10) {
			Vector2D P1 = new Vector2D(segment1.getP(t1));
			Vector2D P2 = new Vector2D(segment2.getP(t2));
			Vector2D T1 = segment1.getTangent(t1);
			Vector2D T2 = segment2.getTangent(t2);
			Vector2D TD1 = segment1.getTangentDerivative(t1);
			Vector2D TD2 = segment2.getTangentDerivative(t2);

			Vector2D Q=Vector2D.sub(P2, P1);
			double f1=-Vector2D.sproduct(Q, T1);
			double f2=Vector2D.sproduct(Q, T2);
			double m11=Vector2D.sproduct(T1, T1)-Vector2D.sproduct(Q, TD1);
			double m12=-Vector2D.sproduct(T1, T2);
			double m21=m12;
			double m22=Vector2D.sproduct(T2, T2)+Vector2D.sproduct(Q, TD2);
			double det = m11 * m22 - m12 * m21;
			
			double Qabs=Vector2D.abs(Q);
			double T1abs=Vector2D.abs(T1);
			double T2abs=Vector2D.abs(T2);

			if (Math.abs(det) < eps4) {
				parallel = true;
				break;
			}
			double dt1 = -(f1 * m22 - m12 * f2) / det;
			double dt2 = -(m11* f2 - f1 * m21) / det;

			t1 = t1 + dt1;
			t2 = t2 + dt2;
			dt = Math.max(Math.abs(dt1), Math.abs(dt2));
			df = Math.max( Math.abs(f1/(Qabs*T1abs)), Math.abs(f2/(Qabs*T2abs)) );
			double delt1=m11*dt1+m12*dt2+f1;
			double delt2=m21*dt1+m22*dt2+f2;
			if(debug>0) System.out.println(indent+"  - iter="+iter+", dt="+Util.NumF3(dt)
					+", dt1="+Util.NumF3(dt1)+", dt2="+Util.NumF3(dt2)
					+", delt1="+Util.NumF3(delt1)+", delt2="+Util.NumF3(delt2)+", df="+Util.NumF3(df));
			if (dt < eps12||df<eps4) {
				converged = true;
				break;
			}
			iter++;
		}
		if (parallel && df > eps4) {
			if (debug > 0) {
				System.out.println(indent+"-- NewtonRaphson iter="+ (iter+1)
						+ "Error parallel=" + parallel
						+ ", t1,t2=" + Util.NumF3(t1) + "," + Util.NumF3(t2) + ", dist=" + Util.NumF3(df));
			}
			return null;
		}
		if (t1 < 0d || t1 > 1d || t2 < 0d || t2 > 1d) {
			if (debug > 0) {
				System.out.println(indent+"-- NewtonRaphson iter="+ (iter+1)+ ":"
						+ "Error t1 or t2 out of bound, t1,t2=" + Util.NumF3(t1) + "," + Util.NumF3(t2));
			}
			return null;
		}
		if (!converged) {
			if (debug > 0) {
				System.out.println(indent+"-- NewtonRaphson iter="+ (iter+1)+ ":"
						+ "Error iteration over, converged="+converged
						+ ", t1,t2=" + Util.NumF3(t1) + "," + Util.NumF3(t2));
			}
			return null;
		}
        NormalsInfo info
				=new NormalsInfo(NormalsInfo.SegmentSolution, segment1, segment2, t1, t2);
		//NormalsInfo info=new NormalsInfo(segment1, segment2, t1, t2);
		if (debug >0) {
			System.out.println(indent+"-- NewtonRaphson iter=" + (iter+1)
					+ ", info="+info.toString());
		}
		return info;
	}
//****++++-------------------------//
// getShortestLineBetweenShapes
//---------------------------------//
	public static Vector getShortestLineBetweenShapes(Curve2D curve1, Curve2D curve2,
			String shapeId1, String shapeId2){
		int debug=getShortestLineBetweenShapes_debug;
		
		String methodName="GeometricTestLS.getShortestLinesBetweenShapes";
		String str="** "+ methodName+ "-0 start **";
		if(debug>0) System.out.println(str);

		//------------------------------------------------------------------------//
		Vector infos=Curve2DUtil.getNormalLinesBetweenShapes(curve1, curve2,
						shapeId1, shapeId2);
		//-------------------------------------------------------------------------//
		if(debug>0){
			int size=infos.size();
			str="** "+ methodName+ "-1 infos size="+size+"\n";
			for(int i=0;i<size;i++){
				Curve2DUtil.NormalsInfo info=(Curve2DUtil.NormalsInfo)infos.get(i);
				str+=" - i="+i+" "+info.toString()+"\n";
			}
			System.out.println(str);
		}
		
		double distMin = 1.0e+4;
		int id = -1;
		int index = -1;
		Point2D[] P1 = curve1.getNodePoints();
		Point2D[] P2 = curve2.getNodePoints();
		double t = -1;
		for (int i = 0; i < P1.length; i++) {
			//---------------------------------------------------------------//
			CurvePT curvePT = Curve2DUtil.getShortestLine(P1[i], curve2);
			//---------------------------------------------------------------//
			double dist = Vector2D.dist(P1[i], curvePT.getP());
			if (dist < distMin) {
				distMin = dist;
				id = 1;
				index = i;
				t = curvePT.getParameter();
			}
		}

		for (int i = 0; i < P2.length; i++) {
			//---------------------------------------------------------------//
			CurvePT curvePT = Curve2DUtil.getShortestLine(P2[i], curve1);
			//---------------------------------------------------------------//
			double dist = Vector2D.dist(P2[i], curvePT.getP());
			if (dist < distMin) {
				distMin = dist;
				id = 2;
				index = i;
				t = curvePT.getParameter();
			}
		}
		if (id == -1 || index == -1) {
			String errStr="*** Error getShortestLinesBetweenShapes "
					+"solution not found=>return. Bug: id=-1, index=-1";
			System.err.println(errStr);
			return null;
		}
		double t1 = -1;
		double t2 = -1;
		if (id == 1) {
			t1 = index;
			t2 = t;
		} else if (id == 2) {
			t1 = t;
			t2 = index;
		}
		Curve2DUtil.NormalsInfo solution
				= new Curve2DUtil.NormalsInfo(Curve2DUtil.NormalsInfo.SegmentPtSolution,
						shapeId1, shapeId2, curve1, curve2, t1, t2);
		infos.add(solution);

		int size=infos.size();
		if(debug>0){
			str="** "+ methodName+ "-2 infos size="+size+"\n";
			for(int i=0;i<size;i++){
				Curve2DUtil.NormalsInfo info=(Curve2DUtil.NormalsInfo)infos.get(i);
				str+=" - i="+i+" "+info.toString()+"\n";
			}
			System.out.println(str);
		}
		Vector output=new Vector();
		size=infos.size();
		index=-1;
		distMin = 1.0e+4;
		for(int i=0;i<infos.size();i++){
			Curve2DUtil.NormalsInfo info=(Curve2DUtil.NormalsInfo)infos.get(i);
			boolean type= info.type==Curve2DUtil.NormalsInfo.Solution
					||info.type==Curve2DUtil.NormalsInfo.IntervalSolution
					||info.type==Curve2DUtil.NormalsInfo.SegmentPtSolution;
			if(!type) continue;
			double dist=info.getDistance();
			if(dist<1.0e-4){
				output.add(info);
			} else if(dist<distMin){
				distMin=dist;
				index=i;
			}
		}
		Curve2DUtil.NormalsInfo info=null;
		if(index==-1){
			String errStr="*** Error getShortestLinesBetweenShapes "
					+"solution not found, Bug. index=-1";
			System.err.println(errStr);
		} else {
			info=(Curve2DUtil.NormalsInfo)infos.get(index);
			output.add(info);
		}

		if(debug>0){
			size=output.size();
			str="** "+ methodName+ "-3 output size="+size+"\n";
			for(int i=0;i<size;i++){
				info=(Curve2DUtil.NormalsInfo)output.get(i);
				str+=" - i="+i+" "+info.toString()+"\n";
			}
			System.out.println(str);
		}
		return output;
	}

//****----------------//
//  reverseCurve2D
//---------------------//
    public static Curve2D reverseCurve2D(Curve2D curve){
        int numseg=curve.getNumOfSegments();
        Segment2D[] newSegments=new Segment2D[numseg];
        for(int i=0;i<numseg;i++){
            Segment2D segment=(Segment2D)curve.getSegment2D(numseg-1-i).clone();
            newSegments[i]=segment.reverseSegment();
        }
        Curve2D newCurve=(Curve2D)curve.clone();
        newCurve.setData(newSegments);
        return newCurve;
    }
//****----------------//
//  trimCurve2D
//---------------------//
    public static Curve2D trimCurve2D(Curve2D curve, double t1, double t2){
        if(t1>t2&&!curve.isClosed()) {
            System.err.println("*** Error Curve2DUtil.getTrimmedCurve: t1>t2");
            return null;
        }
        boolean connect=false;
        if(t1>t2&&curve.isClosed()) connect=true;
        int it1=(int)t1;
        int it2=(int)t2;
        double t2save=t2;
        if(connect) {
            t2=curve.getNumOfSegments();
            it2=(int)t2;
        }
        Vector vector=new Vector();
        double ts=0; double te=0;
        for(int i=it1;i<=it2;i++){
            ts=0;
            te=1;
            if(i==it1) ts=t1-i;
            if(i==it2) te=t2-i;
            if(Math.abs(te-ts)>1e-4){
                Segment2D segment=curve.getSegment2D(i);
                Segment2D trimmedSeg=segment.trimSegment(ts, te);
                if(trimmedSeg!=null) vector.add(trimmedSeg);
            }
        }
        if(connect){
            t1=0;
            it1=0;
            t2=t2save;
            it2=(int)t2;
            for(int i=it1;i<=it2;i++){
                ts=0;
                te=1;
                if(i==it1) ts=t1-i;
                if(i==it2) te=t2-i;
                if(Math.abs(te-ts)>1e-4){
                    Segment2D segment=curve.getSegment2D(i);
                    Segment2D trimmedSeg=segment.trimSegment(ts, te);
                    if(trimmedSeg!=null) vector.add(trimmedSeg);
                }
            }
        }
        int size=vector.size();
        if(size==0) {
             System.err.println("*** Error Curve2DUtil.getTrimmedCurve: No Segment2D");
            return null;
        }
        Segment2D[] segments=new Segment2D[size];
        for(int i=0;i<size;i++) segments[i]=(Segment2D)vector.get(i);
        GeneralCurve2DE genCurve=new GeneralCurve2DE(segments);
        //GeneralCurve2DE newCurve=(GeneralCurve2DE)Curve2DUtil.getCompactCurve2D(generalCurve);
        Curve2D newCurve=genCurve.getSimpleCurve2D();
        if(connect) {
            newCurve=Curve2DUtil.arrangeCurveSegment(newCurve);
        }
        return newCurve;
    }
//****----------------//
//  getSimpleCurve2D
//---------------------//
    public static Curve2D getSimpleCurve2D(Curve2D curve){
        int debug=getSimpleCurve2D_debug;
        Curve2D ucurve=curve;
        int size=ucurve.getNumOfSegments();
        boolean line=false;
        boolean arc=false;
        boolean cubic=false;
        for(int i=0;i<size;i++) {
            int type=ucurve.getSegment2D(i).getType();
            if(type==Segment2D.LINE) line=true;
            if(type==Segment2D.ARC) arc=true;
            if(type==Segment2D.CUBIC) cubic=true;
        }

        Curve2D simpleCurve=(Curve2D)ucurve.clone();

        if(line&&!arc&&!cubic&&size==1){
            Segment2D lineSegment=ucurve.getSegment2D(0);
            lineSegment.getP(0);
            simpleCurve=new Line2DE(lineSegment.getP(0), lineSegment.getP(1));
        }

        if(line&&!arc&&!cubic&&size>1){
            Segment2D[] newSegments=new Segment2D[size];
            for(int i=0;i<size;i++) {
                newSegments[i]=(Segment2D)ucurve.getSegment2D(i).clone();
            }
            simpleCurve=new Polyline2DE(newSegments);
        }

        boolean smooth=true;
        if(cubic&&!line&&!arc){
            Segment2D[] newSegments=new Segment2D[size];
            for(int i=0;i<size;i++) {
                newSegments[i]=(Segment2D)ucurve.getSegment2D(i).clone();
                if(i>0){
                    Vector2D tout=newSegments[i-1].getTangent(1.0);
                    Vector2D tin=newSegments[i].getTangent(0.0);
                    double sprod=Vector2D.sproduct(tin, tout);
                    sprod=sprod/(Vector2D.length(tin)*Vector2D.length(tout));
                    if(smooth&&Math.abs(sprod)<1-1e-5) smooth=false;
                }
            }
            if(smooth) simpleCurve=new CubicCurve2DE(newSegments);
        }
        if(debug>0) System.out.println("Curve2DUtil.getSimpleCurve2D simpleCurve : "
                +simpleCurve.toString());
        return simpleCurve;
    }

    public static Curve2D arrangeCurveSegment(Curve2D curve){
		int debug=getSimpleCurve2D_debug;
        if(debug>0) System.out.println("\narrangeCurveSegment : "+curve.toString());
        int numseg = curve.getNumOfSegments();
        if(numseg==1){
            System.out.println("arrangeCurveSegment : Given curve has only one segment");
            return (Curve2D)curve.clone();
        }
        Vector vector=new Vector();
        Segment2D segment1=curve.getSegment2D(0);
        segment1=(Segment2D)segment1.clone();
        for(int i=1;i<numseg;i++){
            Segment2D segment2=(Segment2D)curve.getSegment2D(i).clone();
            Segment2D unitedSegment=Curve2DUtil.uniteSegment2Ds(segment1, segment2);
            if(unitedSegment==null){
                vector.add(segment1);
                segment1=segment2;
                if(i==numseg-1) vector.add(segment2);
            } else{
                segment1=unitedSegment;
                if(i==numseg-1) vector.add(unitedSegment);
            }
        }
        
        int size=vector.size();
        if(size==0) {
            System.err.println("*** Error in Curve2DUtil.arrangeCurveSegment : No segment in vector");
            return null;
        }

        Segment2D[] newSegments=new Segment2D[size];
        for(int i=0;i<size;i++){
            newSegments[i]=(Segment2D)vector.get(i);
        }
        Curve2D newCurve=(Curve2D)curve.clone();
        newCurve.setData(newSegments);
        if(debug>0) System.out.println("arrangeCurveSegment newCurve : "+newCurve.toString());
        return newCurve;
    }

    protected static Segment2D uniteSegment2Ds(Segment2D segment1, Segment2D segment2){
		int debug=uniteSegment2Ds_debug;
        if(debug>0) System.out.println("uniteSegment2Ds segment1 : "+segment1.toString());
        if(debug>0) System.out.println("uniteSegment2Ds segment2 : "+segment2.toString());
        int type=segment1.getType();
        if(type!=segment2.getType()) {
            if(debug>0) System.out.println(" Curve2DUtil.uniteSegment2Ds : Not united, different types");
            return null;
        }
        Point2D p1=segment1.getP(1);
        Point2D p2=segment2.getP(0);
        if(Vector2D.dist(p1, p2)>Curve2DUtil.eps3) {
            if(debug>0) System.out.println(" Curve2DUtil.uniteSegment2Ds : Not united, Illeagal connection");
            return null;
        }
        Vector2D tvec1=segment1.getTangent(1);
        Vector2D tvec2=segment2.getTangent(0);
        double vprod=Vector2D.vproduct(Vector2D.unitVector(tvec1), Vector2D.unitVector(tvec2));
        if(Math.abs(vprod)>Curve2DUtil.eps3) {
            if(debug>0)System.out.println(" Curve2DUtil.uniteSegment2Ds :"
                    + " Not united, Not smooth connection vprod="+vprod);
            return null;
        }
        Segment2D unitedSegment=null;

        if (type == Segment2D.LINE){
            Line2D line=new Line2D.Double(segment1.getP(0), segment2.getP(1));
            unitedSegment=new Segment2D(Segment2D.LINE, line);
        }
        if (type == Segment2D.ARC) {
            Arc2D arc1=(Arc2D)segment1.getAwtGeom();
            Arc2D arc2=(Arc2D)segment2.getAwtGeom();
            AffineTransform affine1=segment1.getAffineTransform();
            AffineTransform affine2=segment2.getAffineTransform();
            if(affine1==null) {
                affine1=(new Matrix2D()).getAffineTransform();
            }
            if(affine2==null) {
                affine2=(new Matrix2D()).getAffineTransform();
            }
            if(!Curve2DUtil.RotationEquals(affine1, affine2)) {
            //if(!affine1.equals(affine2)) {
                if(debug>0) System.out.println(" Curve2DUtil.uniteSegment2Ds :"
                    + " Not united, Different AffineTransform\n  -- affine1 : "+affine1.toString()+
                    "\n  -- affine2 : "+affine2.toString());
                return null;
            }

            double x1=arc1.getX();
            double y1=arc1.getY();
            double w1=arc1.getWidth();
            double h1=arc1.getHeight();
            double w2=arc2.getWidth();
            double h2=arc2.getHeight();
            double angleStart1=arc1.getAngleStart();
            double angleExtent1=arc1.getAngleExtent();
            double angleExtent2=arc2.getAngleExtent();
            if(Math.abs(w1-w2)>Curve2DUtil.eps3||Math.abs(h1-h2)>Curve2DUtil.eps3) {
                 if(debug>0) System.out.println(" Curve2DUtil.uniteSegment2Ds :"
                    + " Not united, Different widths or heights");
                return null;
            }
            double newStart=angleStart1;
            double newExtent=angleExtent1+angleExtent2;
            double newEnd=newStart+newExtent;
            if(newStart<-360||newEnd<-360) newStart=newStart+360;
            if(newStart>360||newEnd>360) newStart=newStart-360;
            Arc2D newArc=new Arc2D.Double(x1, y1, w1, h1, newStart,
                    newExtent, Arc2D.OPEN);
            unitedSegment=new Segment2D(Segment2D.ARC, newArc, affine1);
            if(debug>0) System.out.println("uniteSegment2Ds : "+unitedSegment.toString());
        }
        if (type == Segment2D.CUBIC) {
            unitedSegment=null;
        }

        if(debug>0){
            if(unitedSegment==null) {
                System.out.println("uniteSegment2Ds :  No united segment");
            }else{
                System.out.println("uniteSegment2Ds unitedSegment="+unitedSegment.toString());
            }
        }
        return unitedSegment;
    }

    protected static boolean RotationEquals(AffineTransform affine1, AffineTransform affine2){
        double[] flatmatrix1=new double[6];
        double[] flatmatrix2=new double[6];
        affine1.getMatrix(flatmatrix1);
        affine2.getMatrix(flatmatrix2);
        for(int i=0;i<4;i++){
            if(Math.abs(flatmatrix1[i]-flatmatrix2[i])>1.0e-12){
                return false;
            }
        }
        return true;
    }
//****----------------//
//  extendCurve2D
//---------------------//
    public static Curve2D extendCurve2D(Curve2D curve, double extension, int pos){
		int debug=extendCurve2D_debug;
        if(debug>0) System.out.println("extendCurve2D curve : "+curve.toString());
        if (curve.isClosed()) {
            return null;
        }
        //int type=curve.getType();
        int numseg = curve.getNumOfSegments();
        //System.out.println("getExtendedCurve2D pos="+pos);
        Curve2D workCurve=(Curve2D)curve.clone();
        if(pos==0){
            //workCurve.reverse();
            workCurve=Curve2DUtil.reverseCurve2D(workCurve);
        }
        //if(debug>0) System.out.println("-- Before extend  workCurve="+workCurve.toString());
        Segment2D segment=workCurve.getSegment2D(numseg-1);
        int type=segment.getType();
        //-------------------------------------------------------------------//
        Segment2D extSegment=Curve2DUtil.extendSegment2D(segment, extension);
        //-------------------------------------------------------------------//

        Segment2D[] newSegments=new Segment2D[numseg];
        if(type==Segment2D.CUBIC) newSegments=new Segment2D[numseg+1];
        for(int i=0;i<numseg;i++){
            newSegments[i]=(Segment2D)workCurve.getSegment2D(i).clone();
        }
        if(type==Segment2D.CUBIC){
            newSegments[numseg]=extSegment;
        } else {
            newSegments[numseg-1]=extSegment;
        }

        workCurve.setData(newSegments);
        //if(debug>0) System.out.println("-- After extend  workCurve="+workCurve.toString());
        Curve2D extCurve=workCurve;
        if(pos==0){
            //extCurve.reverse();
            extCurve=Curve2DUtil.reverseCurve2D(workCurve);
        }
        if(debug>0)  System.out.println("extendCurve2D  extCurve:"+extCurve.toString());

        return extCurve;
    }

    protected static Segment2D extendSegment2D(Segment2D segment, double extension){
		int debug=extendSegment2D_debug;
        int type=segment.getType();
        if(debug>0) System.out.println("extendSegment2D extension="+
                Util.Num(extension)+", segment : "+segment.toString());
        Segment2D extSegment=null;
        if (type == Segment2D.LINE) {
            Point2D p0=segment.getP(0);
            Point2D p1=segment.getP(1);
            Vector2D vec=segment.getTangent(0);
            double segLen=Vector2D.dist(p0, p1);
            Vector2D unitVec=Vector2D.unitVector(vec);
            Vector2D vec0=new Vector2D(p0);
            Vector2D vec1=Vector2D.add(vec0, Vector2D.multiply(extension+segLen, unitVec));
            Line2D line=new Line2D.Double(p0.getX(), p0.getY(), vec1.getX(), vec1.getY());
            extSegment=new Segment2D(Segment2D.LINE, line);
        }

        if (type == Segment2D.ARC) {
            if(debug>0) System.out.println("\nsegment : "+segment.toString());
            Arc2D arc=(Arc2D)segment.getAwtGeom();
            AffineTransform affineTransform=segment.getAffineTransform();
            double x = arc.getX();
            double y = arc.getY();
            double w = arc.getWidth();
            double h = arc.getHeight();
            double minR=0.5*Math.min(w, h);
            double angleStart=arc.getAngleStart();
            double angleExtent=arc.getAngleExtent();
            double addedExtent=(180.0/Curve2DUtil.pai)*(extension/minR);
            double newExtent=angleExtent+addedExtent;
            if(angleExtent<0) {
                newExtent=angleExtent-addedExtent;
            }
            if(newExtent>360.0) newExtent=360;
            if(newExtent<-360.0) newExtent=-360;
            //System.out.println(" angleStart="+angleStart+", angleExtent="+Util.Num(angleExtent)
            //        +", newExtent="+Util.Num(newExtent));
            Arc2D newArc=new Arc2D.Double(x, y, w, h, angleStart,
                    newExtent, Arc2D.OPEN);
            extSegment=new Segment2D(Segment2D.ARC, newArc, affineTransform);
            if(debug>0) System.out.println("ext Segment : "+extSegment.toString());
        }

        if (type == Segment2D.CUBIC) {
            Point2D p0=segment.getP(1);
            Vector2D tVec=segment.getTangent(1);
            Vector2D unitVec=Vector2D.unitVector(tVec);
            Vector2D vec0=new Vector2D(p0);
            Vector2D vec1=Vector2D.add(vec0, Vector2D.multiply(extension, unitVec));
            tVec=Vector2D.multiply(extension, unitVec);
            Point2D[] P=new Point2D[2];
            Vector2D[] Tin=new Vector2D[2];
            Vector2D[] Tout=new Vector2D[2];
            P[0]=p0;
            P[1]=new Point2D.Double(vec1.getX(), vec1.getY());
            Tin[0]=new Vector2D(0,0);
            Tin[1]=(Vector2D)tVec.clone();
            Tout[0]=(Vector2D)tVec.clone();
            Tout[1]=new Vector2D(0,0);
            FergusonCurve2D ferguson=new FergusonCurve2D(P, Tin, Tout);
            CubicCurve2D cubic=ferguson.getCubicCurve2D(0);
            extSegment=new Segment2D(Segment2D.CUBIC, cubic);
        }
        if(debug>0){
            System.out.println(" extSegment : "+extSegment.toString());
        }
        return extSegment;
    }

    public static Curve2D extendCurve2DByPT(Curve2D curve, Point2D PT){
		int debug=extendCurve2DByPT_debug;
        if(debug>0) System.out.println("extendCurve2DByPT curve : "+curve.toString());
        if (curve.isClosed()) {
            return null;
        }
        //int type=curve.getType();
        int numseg = curve.getNumOfSegments();
        Point2D P0=curve.getP(0);
        Point2D P1=curve.getP(numseg);
        int pos=0;
        if(Vector2D.dist(P0, PT)>Vector2D.dist(P1, PT)) {
            pos=1;
        }
        //System.out.println("getExtendedCurve2D pos="+pos);
        Curve2D workCurve=(Curve2D)curve.clone();
        if(pos==0){
            //workCurve.reverse();
            workCurve=Curve2DUtil.reverseCurve2D(workCurve);
        }
        if(debug>0) System.out.println("-- Before extend  workCurve="+workCurve.toString());
        Segment2D segment=workCurve.getSegment2D(numseg-1);
        int type=segment.getType();
        //-------------------------------------------------------------------//
        Segment2D extSegment=Curve2DUtil.extendSegment2DByPT(segment, PT);
        //-------------------------------------------------------------------//
        if(extSegment==null){
            return null;
        }
        Segment2D[] newSegments=new Segment2D[numseg];
        if(type==Segment2D.CUBIC&&extSegment!=null) {
            newSegments=new Segment2D[numseg+1];
        }
        for(int i=0;i<numseg;i++){
            newSegments[i]=(Segment2D)workCurve.getSegment2D(i).clone();
        }
        if(type==Segment2D.CUBIC&&extSegment!=null){
            newSegments[numseg]=extSegment;
        } else if(type!=Segment2D.CUBIC) {
            newSegments[numseg-1]=extSegment;
        }

        workCurve.setData(newSegments);
        if(debug>0) System.out.println("-- After extend  workCurve="+workCurve.toString());
        Curve2D extCurve=workCurve;
        if(pos==0){
            //extCurve.reverse();
            extCurve=Curve2DUtil.reverseCurve2D(workCurve);
        }
        if(debug>0)  System.out.println("extendCurve2DByPT  extCurve:"+extCurve.toString());

        return extCurve;
    }

    protected static Segment2D extendSegment2DByPT(Segment2D segment, Point2D PT){
		int debug=extendSegment2DByPT_debug;
        int type=segment.getType();
        if(debug>0) System.out.println("extendSegment2DByPT PT="+Util.Pt(PT)+", segment : "+segment.toString());
        Segment2D extSegment=null;
        if (type == Segment2D.LINE) {
            Point2D p0=segment.getP(0);
            Point2D p1=segment.getP(1);
            Vector2D vec=segment.getTangent(0);
            double segLen=Vector2D.dist(p0, p1);
            Vector2D unitVec=Vector2D.unitVector(vec);
            Vector2D subVec=Vector2D.sub(PT, p1);
            double len=Vector2D.sproduct(unitVec, subVec);
            if(len<0.0){
                extSegment=(Segment2D)segment.clone();
                return null;
            }
            Vector2D vec0=new Vector2D(p0);
            Vector2D vec1=Vector2D.add(vec0, Vector2D.multiply(len+segLen, unitVec));
            Line2D line=new Line2D.Double(p0.getX(), p0.getY(), vec1.getX(), vec1.getY());
            extSegment=new Segment2D(Segment2D.LINE, line);
        }

        if (type == Segment2D.ARC) {
            Point2D p1=segment.getP(1);
            Vector2D tVec1=segment.getTangent(1);
            double sprod=Vector2D.sproduct(tVec1, Vector2D.sub(PT, p1));
            if(sprod<0.0){
                extSegment=(Segment2D)segment.clone();
                return null;
            }
            Arc2D arc=(Arc2D)segment.getAwtGeom();
            AffineTransform affineTransform=segment.getAffineTransform();
            double x = arc.getX();
            double y = arc.getY();
            double w = arc.getWidth();
            double h = arc.getHeight();
            double angleStart=arc.getAngleStart();
            double angleExtent=arc.getAngleExtent();
            double newExtent=360.0-angleExtent;
            if(angleExtent<0) newExtent=-(360.0+angleExtent);
            Arc2D newArc=new Arc2D.Double(x, y, w, h, angleStart+angleExtent,
                    newExtent, Arc2D.OPEN);
            
            Segment2D testSegment=new Segment2D(Segment2D.ARC, newArc, affineTransform);
            
            //Segment2D testSegment=(Segment2D)segment.clone();
            //testSegment.setShape(newArc);
            
            CurvePT[] pts=Curve2DUtil.getNormalLinesOnSegment(PT, testSegment);
            if(pts.length==0){
                extSegment=(Segment2D)segment.clone();
                return null;
            }
            double tmin=10.0;
            for(int i=0;i<pts.length;i++){
                double t=pts[i].getParameter();
                if(t<tmin) tmin=t;
            }
            newArc=new Arc2D.Double(x, y, w, h, angleStart, angleExtent+newExtent*tmin, Arc2D.OPEN);
            extSegment=new Segment2D(Segment2D.ARC, newArc, affineTransform);
        }

        if (type == Segment2D.CUBIC) {
            Point2D p0=segment.getP(1);
            Vector2D tVec=segment.getTangent(1);
            Vector2D unitVec=Vector2D.unitVector(tVec);
            Vector2D subVec=Vector2D.sub(PT, p0);
            double len=Vector2D.sproduct(unitVec, subVec);
            if(len<0.0){
                System.err.println("extendSegment2DByPT CUBIC error");
                return null;
            }
            Vector2D vec0=new Vector2D(p0);
            Vector2D vec1=Vector2D.add(vec0, Vector2D.multiply(len, unitVec));
            tVec=Vector2D.multiply(len, unitVec);
            Point2D[] P=new Point2D[2];
            Vector2D[] Tin=new Vector2D[2];
            Vector2D[] Tout=new Vector2D[2];
            P[0]=p0;
            P[1]=new Point2D.Double(vec1.getX(), vec1.getY());
            Tin[0]=new Vector2D(0,0);
            Tin[1]=(Vector2D)tVec.clone();
            Tout[0]=(Vector2D)tVec.clone();
            Tout[1]=new Vector2D(0,0);
            FergusonCurve2D ferguson=new FergusonCurve2D(P, Tin, Tout);
            CubicCurve2D cubic=ferguson.getCubicCurve2D(0);
            extSegment=new Segment2D(Segment2D.CUBIC, cubic);
        }
        if(debug>0){
            System.out.println(" extSegment : "+extSegment.toString());
        }
        return extSegment;
    }
//****----------------//
//  createCircularArcs
//---------------------//
    public static Arc2D[] createCircularArcs(Point2D p1, Point2D p2, Point2D p3){
        Arc2D[] arcs=new Arc2D[0];
        double pai=Math.PI;
        Vector2D P1=new Vector2D(p1);
        Vector2D P2=new Vector2D(p2);
        Vector2D P3=new Vector2D(p3);
        Vector2D P12=Vector2D.multiply(0.5,Vector2D.add(P1, P2));
        Vector2D P23=Vector2D.multiply(0.5,Vector2D.add(P2, P3));
        Vector2D v12=Vector2D.sub(P2,P1);
        Vector2D v23=Vector2D.sub(P3,P2);
        Vector2D n1=Vector2D.unitNormalVector(v12);
        Vector2D n2=Vector2D.unitNormalVector(v23);
        Point2D centerP=Curve2DUtil.getCrossPoint(P12,n1,P23, n2);
        if(centerP==null) return arcs;
        Vector2D centerVec=new Vector2D(centerP);
        P1=Vector2D.sub(P1, centerVec);
        P2=Vector2D.sub(P2, centerVec);
        P3=Vector2D.sub(P3, centerVec);
        double r=(Vector2D.length(P1)+Vector2D.length(P2)+Vector2D.length(P3))/3d;
        double teta1=Math.atan2(-P1.getY(),P1.getX());
        double teta2=Math.atan2(-P2.getY(),P2.getX());
        double teta3=Math.atan2(-P3.getY(),P3.getX());
        boolean normalOrder=false;
        for(int i=-1;i<2;i++){
            double teta2Mod=teta2+i*2d*pai;
            for(int j=-1;j<2;j++){
                double teta3Mod=teta3+j*2d*pai;
                if((teta3Mod-teta2Mod)*(teta2Mod-teta1)<0) continue;
                if(Math.abs(teta3Mod-teta1)>=2d*pai) continue;
                teta2=teta2Mod;
                teta3=teta3Mod;
                normalOrder=true;
                break;
            }
        }
        if(!normalOrder){
            System.err.println("*** Error in FergusonCurve.createCircularArcs: " +
                    "Abnormal order of three points");
            return arcs;
        }
        double x=centerVec.getX()-r;
        double y=centerVec.getY()-r;
        arcs=new Arc2D[2];
        arcs[0]=new Arc2D.Double(x, y, 2d*r, 2d*r, teta1*180/pai, 
                (teta2-teta1)*180/pai, Arc2D.OPEN);
        arcs[1]=new Arc2D.Double(x, y, 2d*r, 2d*r, teta2*180/pai, 
                (teta3-teta2)*180/pai, Arc2D.OPEN);
        //System.out.println("FergusonCurve2D.createCircularArcs arc0="+arcs[0]+", arc1="+arcs[1]);
        return arcs;
    }
	
//****----------------//
//  getCrossPoint
//---------------------//
    protected static Point2D getCrossPoint(Vector2D p1, Vector2D n1, Vector2D p2, Vector2D n2){
        Point2D centerP=null;
        double det=-n1.getX()*n2.getY()+n1.getY()*n2.getX();
        Vector2D Q=Vector2D.sub(p2,p1);
        if(Math.abs(det)==0) return centerP;
        double t1=(-Q.getX()*n2.getY()+Q.getY()*n2.getX())/det;
        double t2=(n1.getX()*Q.getY()-n1.getY()*Q.getX())/det;
        Vector2D centerP1=Vector2D.add(p1,Vector2D.multiply(t1,n1));
        Vector2D centerP2=Vector2D.add(p2,Vector2D.multiply(t2,n2));
        Vector2D centerVec=Vector2D.multiply(0.5,Vector2D.add(centerP1,centerP2));
        centerP=new Point2D.Double(centerVec.getX(), centerVec.getY());
        return centerP;
    }
//****-----------------//
//  distanceBetweenBoxes
//---------------------//
public static double distanceBetweenBoxes(Rectangle2D box1, Rectangle2D box2) {
	int debug=distanceBetweenBoxes_debug;
		double distMin = 1.0e+5;
		double dist = 0.0;
		double x1 = box1.getX();
		double y1 = box1.getY();
		double w1 = box1.getWidth();
		double h1 = box1.getHeight();
		double x2 = box2.getX();
		double y2 = box2.getY();
		double w2 = box2.getWidth();
		double h2 = box2.getHeight();
		Vector2D[] p1 = new Vector2D[4];
		Vector2D[] p2 = new Vector2D[4];
		p1[0] = new Vector2D(x1, y1);
		p1[1] = new Vector2D(x1 + w1, y1);
		p1[2] = new Vector2D(x1, y1 + h1);
		p1[3] = new Vector2D(x1 + w1, y1 + h1);
		p2[0] = new Vector2D(x2, y2);
		p2[1] = new Vector2D(x2 + w2, y2);
		p2[2] = new Vector2D(x2, y2 + h2);
		p2[3] = new Vector2D(x2 + w2, y2 + h2);
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				dist = Vector2D.dist(p1[i], p2[j]);
				if (dist < distMin) {
					distMin = dist;
				}
			}
		}
		if (debug == 2) {
			System.out.println("step1 distMin=" + Util.Num(distMin));
		}
		boolean separateX = x2 + w2 < x1 || x2 > x1 + w1;
		boolean separateY = y2 + h2 < y1 || y2 > y1 + h1;
		if (debug ==2) {
			System.out.println("step2 separateX=" + separateX + ", separateY=" + separateY);
		}
		if (!separateX && !separateY) {
			dist = 0.0;
		}
		if (!separateX && separateY) {
			if (y2 + h2 < y1) {
				dist = y1 - (y2 + h2);
			}
			if (y2 > y1 + h1) {
				dist = y2 - (y1 + h1);
			}
			if (debug ==2) {
				System.out.println("step3 distMin=" + Util.Num(dist));
			}
		}
		if (separateX && !separateY) {
			if (x2 + w2 < x1) {
				dist = x1 - (x2 + w2);
			}
			if (x2 > x1 + w1) {
				dist = x2 - (x1 + w1);
			}
			if (debug ==2) {
				System.out.println("step4 distMin=" + Util.Num(dist));
			}
		}
		if (dist < distMin) {
			distMin = dist;
		}
		if (debug ==2) {
			System.out.println("result distMin=" + Util.Num(dist));
		}
		return distMin;
	}
//++++-----------------//
//  getMaxBoundingBox
//---------------------//
	public static Rectangle2D getMaxBox(Rectangle2D[] boxes) {
		double xmin = Curve2DUtil.largeNumber, ymin = xmin, xmax = -xmin, ymax = -xmin;
		for (int i = 0; i < boxes.length; i++) {
			double x = boxes[i].getX();
			double y = boxes[i].getY();
			double w = boxes[i].getWidth();
			double h = boxes[i].getHeight();
			if (x < xmin) {
				xmin = x;
			}
			if (y < ymin) {
				ymin = y;
			}
			if (x + w > xmax) {
				xmax = x + w;
			}
			if (y + h > ymax) {
				ymax = y + h;
			}
		}
		Rectangle2D maxBoundingBox
				= new Rectangle2D.Double(xmin, ymin, xmax - xmin, ymax - ymin);
		return maxBoundingBox;
	}
	
	public static Rectangle2D getMaxBox(Rectangle2D box1, Rectangle2D box2) {
		Rectangle2D[] boxes=new Rectangle2D[2];
		boxes[0]=box1;
		boxes[1]=box2;
		return getMaxBox(boxes);
	}
//****--------------------------//
// NormalsInfo
// Nested public static class
//------------------------------//
	public static class NormalsInfo {

		public int type = 0;
		public final static int Solution = 0;
		public final static int IntervalSolution = 1;
		public final static int SegmentPtSolution = 2;
		public final static int SegmentSolution = 3;
		public final static int SegmentIntervalSolution = 4;
		public final static int SegmentHitInterval = 5;
		public final String[] TypeString
				= {"Solution", "IntervalSolution","SegmentPtSolution","SegmentSolution", 
					"SegmentIntervalSolution ", "SegmentHitInterval"};
		public String callFrom="";
		public String[] shapeIds=new String[2];
		public Curve2D[] curves = new Curve2D[2];
		public double[] t = new double[2];
		public Segment2D[] segments = new Segment2D[2];
		public int depth;
		public int[] numDiv = new int[2];
		public int[] divId = new int[2];
		public double[] interval = new double[4];
		public double[] boxSize = new double[2];
		
//++++--------------------------//
// NormalsInfo Constructor
//------------------------------//
		public NormalsInfo(int type, String shapeId1, String shapeId2, 
				Curve2D curve1, Curve2D curve2, double t1, double t2) {
			if(type!=Solution&&type!=SegmentPtSolution ) {
				System.out.println("*** Error NormalsInfo Constructor Illeagal type, type="
						+this.getTypeString());
			}
			//this.callFrom=callFrom;
			this.type = type;
			this.shapeIds[0] = shapeId1;
			this.shapeIds[1] = shapeId2;
			this.curves[0] = curve1;
			this.curves[1] = curve2;
			this.t[0] = t1;
			this.t[1] = t2;
			this.boxSize = this.getBoxSize();
			this.boxSize = this.getBoxSize();
		}

		public NormalsInfo(int type, String shapeId1, String shapeId2, 
				Curve2D curve1, Curve2D curve2, double[] interval) {
			if(type!=IntervalSolution) {
				System.out.println("*** Error NormalsInfo Constructor Illeagal type, type="+TypeString[this.type]);
			}
			this.type = IntervalSolution;
			this.shapeIds[0] = shapeId1;
			this.shapeIds[1] = shapeId2;
			this.curves[0] = curve1;
			this.curves[1] = curve2;
			this.interval = interval;
			this.boxSize = this.getBoxSize();
		}

		public NormalsInfo(int type, Segment2D segment1, Segment2D segment2, double t1, double t2) {
			if(type!=SegmentSolution) {
				System.out.println("*** Error NormalsInfo Constructor Illeagal type, type="+TypeString[this.type]);
			}
			this.type = SegmentSolution;
			this.segments[0] = segment1;
			this.segments[1] = segment2;
			this.t[0] = t1;
			this.t[1] = t2;
			this.boxSize = this.getBoxSize();
		}
		
		public NormalsInfo(int type, Segment2D[] segments, double[] interval) {
			if(type!=SegmentIntervalSolution ) {
				System.out.println("*** Error NormalsInfo Constructor Illeagal type, type="+TypeString[this.type]);
			}
			this.type = SegmentIntervalSolution ;
			this.segments = segments;
			this.interval = interval;
		}
		
		public NormalsInfo(int type, Segment2D[] segments, int depth, int[] numDiv, int[] divId, 
				double[] interval, double[] boxSize) {
			if(type!=SegmentHitInterval) {
				System.out.println("*** Error NormalsInfo Constructor Illeagal type, type="+TypeString[this.type]);
			}
			this.type = SegmentHitInterval;
			this.segments = segments;
			this.depth = depth;
			this.numDiv = numDiv;
			this.divId = divId;
			this.interval = interval;
			this.boxSize = boxSize;
		}
		
		public String getTypeString(){
			return TypeString[type];
		}

		public double[] getBoxSize() {
			//double[] t=new double[4];
			double[] boxSize = new double[2];
			Rectangle2D box1 = null;
			Rectangle2D box2 = null;
			double t1 = this.t[0];
			double t2 = this.t[1];
			if (this.type == Solution || this.type == SegmentSolution
					||this.type == SegmentIntervalSolution ) {
				boxSize[0] = 0.0;
				boxSize[1] = 0.0;
			}

			if (this.type == SegmentHitInterval) {
				box1 = this.segments[0].getBoundingBox(this.interval[0], this.interval[1]);
				box2 = this.segments[1].getBoundingBox(this.interval[2], this.interval[3]);
				boxSize[0] = Math.max(box1.getWidth(), box1.getHeight());
				boxSize[1] = Math.max(box2.getWidth(), box2.getHeight());
			}
			return boxSize;
		}

		public double[] getAngle() {
			int debug=NormalsInfo_debug;
			double[] t = new double[4];
			Point2D p1 = null;
			Point2D p2 = null;
			Vector2D tan1 = null;
			Vector2D tan2 = null;
			double t1 = this.t[0];
			double t2 = this.t[1];
			if (this.type == Solution||this.type == SegmentPtSolution ) {
				p1 = this.curves[0].getP(t1);
				p2 = this.curves[1].getP(t2);
				tan1 = this.curves[0].getTangent(t1);
				tan2 = this.curves[1].getTangent(t2);
			}
			if (this.type == IntervalSolution) {
				t1 = 0.5 * (this.interval[0] + this.interval[1]);
				t2 = 0.5 * (this.interval[2] + this.interval[3]);
				p1 = this.curves[0].getP(t1);
				p2 = this.curves[1].getP(t2);
				tan1 = this.curves[0].getTangent(t1);
				tan2 = this.curves[1].getTangent(t2);
			}
			if (this.type == SegmentSolution) {
				p1 = this.segments[0].getP(t1);
				p2 = this.segments[1].getP(t2);
				tan1 = this.segments[0].getTangent(t1);
				tan2 = this.segments[1].getTangent(t2);
			}

			if (this.type == SegmentHitInterval||this.type == SegmentIntervalSolution ) {
				t1 = 0.5 * (this.interval[0] + this.interval[1]);
				t2 = 0.5 * (this.interval[2] + this.interval[3]);
				p1 = this.segments[0].getP(t1);
				p2 = this.segments[1].getP(t2);
				tan1 = this.segments[0].getTangent(t1);
				tan2 = this.segments[1].getTangent(t2);
			}
			Vector2D n = Vector2D.unitVector(Vector2D.sub(p2, p1));
			Vector2D e1 = Vector2D.unitVector(tan1);
			Vector2D e2 = Vector2D.unitVector(tan2);
			double sprod1 = Vector2D.sproduct(e1, n);
			double sprod2 = Vector2D.sproduct(e2, n);
			double[] angles = new double[2];
			angles[0] = Math.acos(Math.abs(sprod1)) * 180 / Math.PI;
			angles[1] = Math.acos(Math.abs(sprod2)) * 180 / Math.PI;
			return angles;
		}

		public double getDistance() {
			Point2D p1=null;
			Point2D p2=null;
			if (this.type == Solution||this.type == SegmentPtSolution) {
				p1 = this.curves[0].getP(t[0]);
				p2 = this.curves[1].getP(t[1]);
			}else if (this.type == IntervalSolution) {
				double t1 = 0.5 * (this.interval[0] + this.interval[1]);
				double t2 = 0.5 * (this.interval[2] + this.interval[3]);
				p1 = this.curves[0].getP(t1);
				p2 = this.curves[1].getP(t2);
			} else if (this.type == SegmentSolution) {
				p1 = this.segments[0].getP(t[0]);
				p2 = this.segments[1].getP(t[1]);
			} else if (this.type == SegmentIntervalSolution ) {
				p1 = this.segments[0].getP(t[0]);
				p2 = this.segments[1].getP(t[1]);
			} else if (this.type == SegmentHitInterval) {
				p1 = this.segments[0].getP(t[0]);
				p2 = this.segments[1].getP(t[1]);
			}
			double dist=Vector2D.dist(p1, p2);
			return dist;
		}

		public String toString() {
			String str = "";
			double[] angles = this.getAngle();
			if (this.type == Solution||this.type == SegmentPtSolution) {
				Point2D p1 = this.curves[0].getP(t[0]);
				Point2D p2 = this.curves[1].getP(t[1]);
				str += " type=" + this.getTypeString() 
						+ ", (t1, t2)=("+ Util.Num3(this.t[0]) + ", " + Util.Num3(this.t[1]) + ")"
						+ ", p1=" + Util.Pt(p1) + ", p2=" + Util.Pt(p2)
						+ ", p1-p2 dist="+Util.Num2(Vector2D.dist(p1, p2))
						+ ", angles=(" + Util.Num(angles[0]) + ", " + Util.Num(angles[1]) + ")"
						+", shape1="+this.shapeIds[0]+", shape2="+this.shapeIds[1];
			}else if (this.type == IntervalSolution) {
				double t1 = 0.5 * (this.interval[0] + this.interval[1]);
				double t2 = 0.5 * (this.interval[2] + this.interval[3]);
				Point2D p1 = this.curves[0].getP(t1);
				Point2D p2 = this.curves[1].getP(t2);
				str += " type=" + TypeString[this.type]
						+ ", interval=("+ Util.Num3(this.interval[0]) + ", " + Util.Num3(this.interval[1])
						+ ", " + Util.Num3(this.interval[2]) + ", " + Util.Num3(this.interval[3]) + ")"
						+ ", p1=" + Util.Pt(p1) + ", p2=" + Util.Pt(p2)
						+ ", p1-p2 dist="+Util.Num2(Vector2D.dist(p1, p2))
						+ ", angles=(" + Util.Num(angles[0]) + ", " + Util.Num(angles[1]) + ")"
						+", shape1="+this.shapeIds[0]+", shape2="+this.shapeIds[1];
			} else if (this.type == SegmentSolution) {
				Point2D p1 = this.segments[0].getP(t[0]);
				Point2D p2 = this.segments[1].getP(t[1]);
				str += " type=" + TypeString[this.type] + ", (t1, t2)=("
						+ Util.Num3(this.t[0]) + ", " + Util.Num3(this.t[1]) + ")"
						+ ", p1=" + Util.Pt(p1) + ", p2=" + Util.Pt(p2)
						+", p1-p2 dist="+Util.Num2(Vector2D.dist(p1, p2))
						+ ", angles=(" + Util.Num(angles[0]) + ", " + Util.Num(angles[1]) + ")";
			} else if (this.type == SegmentIntervalSolution ) {
				double t1 = 0.5 * (this.interval[0] + this.interval[1]);
				double t2 = 0.5 * (this.interval[2] + this.interval[3]);
				Point2D p1 = this.segments[0].getP(t1);
				Point2D p2 = this.segments[1].getP(t2);
				str += " type=" + TypeString[this.type]
						+ ", interval=(" + Util.Num3(this.interval[0]) + ", " + Util.Num3(this.interval[1])
						+ ", " + Util.Num3(this.interval[2]) + ", " + Util.Num3(this.interval[3]) + ")"
						+ ", p1=" + Util.Pt(p1) + ", p2=" + Util.Pt(p2)
						+", p1-p2 dist="+Util.Num2(Vector2D.dist(p1, p2))
						+ ", angles=(" + Util.Num(angles[0]) + ", " + Util.Num(angles[1]) + ")";
			} else if (this.type == SegmentHitInterval) {
				str += " type=" + TypeString[this.type] + ", depth=" + this.depth
						+ ", numDiv=(" + this.numDiv[0] + ", " + this.numDiv[1] + ")"
						+ ", divId=(" + this.divId[0] + ", " + this.divId[1] + ")"
						+ ", interval=(" + Util.Num3(this.interval[0]) + ", " + Util.Num3(this.interval[1])
						+ ", " + Util.Num3(this.interval[2]) + ", " + Util.Num3(this.interval[3]) + ")"
						+ ", boxSize=(" + Util.Num1(boxSize[0]) + ", " + Util.Num1(boxSize[1]) + ")"
						+ ", angles=(" + Util.Num(angles[0]) + ", " + Util.Num(angles[1]) + ")";
			}
			return str;
		}
	}
} // End of class

