import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
import javax.swing.event.*;
import java.util.*;

public class Nurbs extends JFrame implements ActionListener, ChangeListener
{
   private JButton resetB, tenPlus, tenMinus; // top buttons
   public static JLabel message;
   private JPanel controlPanel, statusPanel;  // aux panels for interface
   private NURBSTest drawPanel;               // Java2 panel for drawing
   private JSlider js;

   public static void main(String[] args)
  {
    Nurbs application = new Nurbs();
    application.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
  }

// this method is for building the GUI
   public Nurbs()
   {
     Toolkit toolkit = Toolkit.getDefaultToolkit();  // opening the Java
     Dimension screenSize = toolkit.getScreenSize(); // application window
     int screenWidth = screenSize.width;             // with a specific size,
     int screenHeight = screenSize.height;           // title, and position
     setSize(3*screenWidth/4, 3*screenHeight/4);     // on the screen
     setLocation(screenWidth/8, screenHeight/8);
     setTitle("Nurbs test");

     resetB = new JButton("Reset");      // the polygon entering button (the left one)

     js = new JSlider(SwingConstants.HORIZONTAL, 0, 100, 100);
     js.setBackground(new Color(0xcccc99));           // the slider stuff
     js.setValue(50);

     controlPanel = new JPanel();             // the top panel containing the buttons
     controlPanel.setLayout(new FlowLayout(FlowLayout.CENTER, 50, 0));
     controlPanel.setBackground(Color.orange);
     controlPanel.add(resetB);                // adding the GUI components
     controlPanel.add(js);
     
     statusPanel = new JPanel();              // the bottom panel (the status panel)
     statusPanel.setLayout(new FlowLayout()); // it is for displaying the messages only
     statusPanel.setBackground(Color.orange);
     message = new JLabel("Enter a point with the left mouse button, close the polygon with the right one",
            SwingConstants.CENTER);           // the bottom message
     statusPanel.add(message);

     drawPanel = new NURBSTest();              // the main panel for drawing 
     drawPanel.poly = new LinkedList<NURBVertex>();
     drawPanel.polyClosed = false;            // indicator of closing the polygon
     drawPanel.setBackground(new Color(255, 255, 204));

     Container pane = getContentPane();       // add all panels to the layout manager
     pane.setLayout(new BorderLayout());
     pane.add(controlPanel, BorderLayout.NORTH);
     pane.add(drawPanel, BorderLayout.CENTER);
     pane.add(statusPanel, BorderLayout.SOUTH);

     addMouseMotionListener(drawPanel);       // add necessary listeners for the mouse events
     addMouseListener(drawPanel);             // and for the button clicking events
     resetB.addActionListener(this);
     js.addChangeListener(this);

     drawPanel.proximity = 10;                
     drawPanel.tension = 1.1;

     setVisible(true);
     drawPanel.repaint();
   }

// here we figure out the width/height of the panel for drawing and the height of the top panel
   public void start()
   {
     drawPanel.shift = controlPanel.getHeight();      // height of the top panel
   }

// this method will be called if a button on the top panel is pressed
   public void actionPerformed(ActionEvent e)
   {
     if (e.getSource() == resetB)             // the start over (left) applet button is pressed
     {
       drawPanel.polyClosed = false;          // start a new (not yet ready) polygon
       drawPanel.poly.clear();                // clear storave containers for the original
       drawPanel.poly2.clear();               // and extended polygons
       drawPanel.repaint();                   // incorporate the changes (redisplay the drawing panel)
     }
   }

   public void stateChanged(ChangeEvent e)  // slider event handler
   {
     drawPanel.tension = js.getValue()/50.0 + 0.2;     // get tension from slider
     if (drawPanel.tension == 1.0) drawPanel.tension = 1.1;
     drawPanel.constructCurve();
     drawPanel.repaint();                   // and redisplay the curve
   }
}

// auxilary class containg the method for label placement
class NURBSTest extends JPanel implements MouseListener, MouseMotionListener
{
   private int mouseX, mouseY, mouseXold, mouseYold;  // current and previous mouse coordinates
   public boolean polyClosed;    // indicator of the polygon closeness
   public LinkedList<NURBVertex> poly = new LinkedList<NURBVertex>();      // storage for polygon nodes
   public LinkedList<NURBVertex> poly2 = new LinkedList<NURBVertex>();
   public int shift;                          // height of the top panel (for Java API)
   private double[] knots;                    // array of B-spline knot points
   private int m, p=3;                        // B-spline parameters
   public double proximity;                   // max distance of curve points from the nodes
   public double tension;

// this method is called whenever the mouse is dragged
   public void mouseDragged(MouseEvent e) { }

// this method is called whenever a mouse button is pressed
   public void mousePressed(MouseEvent e)
   {
     int s = poly.size() - 1;
     if (e.getButton() == MouseEvent.BUTTON1) // do this if the left mouse button is pressed
     {
       mouseX = e.getX();                     // get the coords of the a polygon node
       mouseY = e.getY() - shift;             // adjust mouse coords to the drawing window
       if (!polyClosed)                       // polygon line processing
       {
         if (s >= 0 && Math.abs(poly.get(s).x - mouseX) <= 3 && // ignore too closed points
                       Math.abs(poly.get(s).y - mouseY) <= 3) return;
         insertPoint(mouseX, mouseY, poly.size()-1); // insert new points into the extended polygon
         poly.add(new NURBVertex(mouseX, mouseY)); // store the new node in a vector of nodes
         repaint();                           // display the new line segment (and the old ones)
       }
     }
     else if (e.getButton() == MouseEvent.BUTTON3) // do this if the right mouse button is pressed
     {
       if (!polyClosed && s >= 3)             // do nothing after closing the polygon
       {
         polyClosed = true;                   // the polygon is closed now
         insertPoint(poly2.get(0).x, poly2.get(0).y, poly.size()-1);
         poly.add(new NURBVertex(poly.get(0).x, poly.get(0).y));
//         insertPoint(poly2.get(1).x, poly2.get(1).y);
         insertPoint(poly.get(1).x, poly.get(1).y, poly.size()-1); // temporary insert the first node 
         poly2.removeLast();                           // the very last node is not needed now
         poly2.get(0).x = poly2.get(poly2.size()-1).x; // make sure that the (old) origin matches 
         poly2.get(0).y = poly2.get(poly2.size()-1).y; // possibly modified new one
         poly2.get(0).w = poly2.get(poly2.size()-1).w;
         for (int i=1; i<p; i++)                       // add the remaining p-1 nodes to close the curve
           poly2.add(new NURBVertex(poly2.get(i).x, poly2.get(i).y, poly2.get(i).w));  
         repaint();
       }
     }
   }

// this method will be called whenever the mouse is moved and no mouse button is pressed
   public void mouseMoved(MouseEvent e) { }
   public void mouseReleased(MouseEvent e) { }    
   public void mouseClicked(MouseEvent e) { }    
   public void mouseEntered(MouseEvent e) { }
   public void mouseExited(MouseEvent e) { }

// this method will be called by repaint()
   public void paintComponent(Graphics g)
   {
     super.paintComponent(g);
     NURBVertex p1 = null;
     NURBVertex p2 = null;

     g.setColor(Color.lightGray);
     if (poly == null) return;
     int n = poly.size();                     // # of polygon nodes
     for (int i=0; i<n-1; i++)                // display the polygon segments
     {
       p1 = poly.get(i);
       p2 = poly.get(i+1);
       g.drawLine(p1.x, p1.y, p2.x, p2.y);
       g.fillRect(p1.x-1, p1.y-1, 3, 3);
       g.drawString(i+"", p1.x-6, p1.y-6);    // display the point index i
     }
     if ((!polyClosed) && n > 0)              // display the last point of an open poly line
     {
       p1 = poly.get(n-1);
       g.fillRect(p1.x-1, p1.y-1, 3, 3);
       g.drawString((n-1)+"", p1.x-6, p1.y-6);
     }

/*
     g.setColor(Color.green);
     for (int i=0; i<poly2.size()-1; i++)     // display the auxilary polygon segments
     {
       p1 = poly2.get(i);
       p2 = poly2.get(i+1);
       g.drawLine(p1.x, p1.y, p2.x, p2.y);
       g.fillRect(p1.x-1, p1.y-1, 3, 3);
       g.drawString(i+":"+(Math.round(p1.w*10)/10.0)+"w", p1.x-6, p1.y-6);
//       g.drawString(i+"", p1.x-6, p1.y-6);
     }
     if (p2 != null)
       g.drawString((Math.round(p2.w*10)/10.0)+"w", p2.x-6, p2.y-6);
*/

     if (poly2.size() >= 4)                   // draw B-spline
     {
       int N = 1000;                          // # of points on B-spline curve
       double uStep = computeKnots();
       g.setColor(Color.red);
       if (!polyClosed)
       {
         p1 = getCurvePoint(0);
         double step = 1.0 / N;
         for (int i=1; i<N; i++)              // it is principal that we only apply
         {                                    // the loop for 0 <= u < 1
           p2 = getCurvePoint(i*step);
           g.drawLine(p1.x, p1.y, p2.x, p2.y);
//           g.fillRect(p1.x-1, p1.y-1, 3, 3); 
           p1 = p2;
         }
         p2 = poly.get(poly.size()-1);        // hence, the lst piece of the curve
         g.drawLine(p1.x, p1.y, p2.x, p2.y);  // should be drawn separately
       }
       else                                   // closed curve processing
       {
         p1 = getCurvePoint(knots[p]);
         double step = (knots[m-p] - knots[p])*1.0 / N;
         for (int i=1; i<N; i++)              // it is principal that we only apply
         {                                    // the loop for 0 <= u < 1
           double u = knots[p] + i*step;
           p2 = getCurvePoint(u);
           g.drawLine(p1.x, p1.y, p2.x, p2.y);
           p1 = p2;
         }
         p2 = getCurvePoint(knots[p]);
         g.drawLine(p1.x, p1.y, p2.x, p2.y);  
       }


       g.setColor(Color.blue);                // drawing the spline points corresponding
       int ub = m-p;                          // to the knots
       if (!polyClosed) ub = poly2.size();
 System.out.println();
       for (int i=p; i<ub; i++)
       {
         NURBVertex pp = getCurvePoint(knots[i]);
         g.fillRect(pp.x-1, pp.y-1, 3, 3);
         g.drawString(i+"", pp.x-6, pp.y-6);
         double ww = (poly2.get(i-3).w + 4*poly2.get(i-2).w + poly2.get(i-1).w)/6.0;
         int xx = (int)Math.round((poly2.get(i-3).x*poly2.get(i-3).w + 
                                   4*poly2.get(i-2).x*poly2.get(i-2).w + 
                                   poly2.get(i-1).x*poly2.get(i-1).w)/(6.0*ww));
         int yy = (int)Math.round((poly2.get(i-3).y*poly2.get(i-3).w + 
                                   4*poly2.get(i-2).y*poly2.get(i-2).w + 
                                   poly2.get(i-1).y*poly2.get(i-1).w)/(6.0*ww));
         System.out.println(i+":  ("+pp.x+","+pp.y+")   (" +xx+","+yy+")");
       }

     } 
   } // of paint()

   public void constructCurve()
   {
     poly2.clear();
     proximity = 40 - tension*15;
     for (int i=0; i<poly.size(); i++)
     {
       NURBVertex p = poly.get(i);
       insertPoint(p.x, p.y, i-1);
     }
     if (polyClosed)
     {
       insertPoint(poly.get(1).x, poly.get(1).y, poly.size()-1); // temporary insert the first node
       poly2.removeLast();                           // the very last node is not needed now
       poly2.get(0).x = poly2.get(poly2.size()-1).x; // make sure that the (old) origin matches
       poly2.get(0).y = poly2.get(poly2.size()-1).y; // possibly modified new one
       poly2.get(0).w = poly2.get(poly2.size()-1).w;
       for (int i=1; i<p; i++)                       // add the remaining p-1 nodes to close the curve
         poly2.add(new NURBVertex(poly2.get(i).x, poly2.get(i).y, poly2.get(i).w));
     }
   }

   public void insertPoint(int x, int y, int s)// insert new point (x,y) into the extended poly
   {
     int s2 = poly2.size()-1;
     if (! clockwise(x, y, s+1))              // do this only if the angle between the last
     {                                        // (original) polygon side and (x,y) is accute
       int x1 = poly.get(s).x;                // compute the distance from the last poly point
       int y1 = poly.get(s).y;                // and (x,y)
       double len1 = Math.sqrt((x1-x)*(x1-x) + (y1-y)*(y1-y));

       int x2 = poly.get(s-1).x;              // compute the length of the last poly segment
       int y2 = poly.get(s-1).y;
       double len2 = Math.sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1));

       double ll = Math.min(proximity, len2/2); // distance adjustment (see text)
       NURBVertex p1 = new NURBVertex((int)Math.round(x1 + (x1 - x)*ll/len1),   // first new node
                              (int)Math.round(y1 + (y1 - y)*ll/len1));
       ll = Math.min(proximity, len1/2);      // distance adjustment (see text)
       NURBVertex p2 = new NURBVertex((int)Math.round(x1 + (x1 - x2)*ll/len2),  // second new node
                              (int)Math.round(y1 + (y1 - y2)*ll/len2)); 
       poly2.removeLast();                    // replace the previous poly node with 3 new ones  
       poly2.add(p1);
       NURBVertex p3 = new NURBVertex((p1.x+p2.x)/2, (p1.y+p2.y)/2); // midpoint of the new segment
       poly2.add(p3);                         // insert the midpoint
       poly2.add(p2);
     }
     else if (s2 >= 1)
     {
       NURBVertex p1 = poly2.get(s2-1);
       NURBVertex p2 = poly2.get(s2);
       NURBVertex p3 = new NURBVertex((p1.x+p2.x)/2, (p1.y+p2.y)/2); // midpoint of the new segment
       poly2.add(s2, p3);
     }
     poly2.add(new NURBVertex(x, y, tension));  // insert the new node
   }

   public double computeKnots()                 // compute the uniform partition of [0,1)
   {
     int n = poly2.size()-1;                  // # of polygon nodes
     m = n + p + 1;                           // B-spline principal equation
     knots = new double[m+1];                 // storage for knots
     double step = 0;
     if (!polyClosed)                         // compute knots for the clamped B-spline
     {
       for (int i=0; i<=p; i++)               // make the first knot of multiplicity p 
         knots[i] = 0;
       step = 1.0 / (m - 2*p);
       for (int i=1; i<=m-2*(p+1)+1; i++)
         knots[p+i] = i*step;                 // distribute the other knots uniformly
       for (int i=0; i<=p; i++)               // make the last knot of multiplicity p
         knots[m-i] = 1.0;                     
     }
     else                                     // computing knots for the closed B-spline
     {
       step = 1.0 / m;
       for (int i=0; i<=m; i++)               // distribute knots uniformly
         knots[i] = i*step; 
     }
//     System.out.println("\nn=0" + n);
//     for (int i=0; i<knots.length; i++)
//       System.out.println(i + ": " + knots[i] + " ");
     return(step);
   }

   public NURBVertex getCurvePoint(double u)  // implementation of the de-Boor algorithm
   {                                          // that computes a B-spline point for u in [0,1)
     int k = p+ (int)Math.floor(u*(m - 2*p)); // compute k s.t. u is in [u_k, u_{k+1})
     if (polyClosed)
       k = (int)Math.floor(u*m);              // for closed polygons the formula is different
     int s = 0;
     if (u == knots[k]) s = 1;                // s=1 iff u is a knot so s is the multiplicity
     if (u == knots[k+1]) {k++; s=1;}         // fix for rounding errors
     int h = p - s;                           // auxilary parameter

     double[] pts = new double[3*(h+1)];      // get the involved poly points
     for (int i=0; i<=h; i++)                 // and store their coordinates in array pts
     {
       double w = poly2.get(k-p+i).w;
       pts[3*i] = poly2.get(k-p+i).x*w;       // the x-coords are on even positions
       pts[3*i+1] = poly2.get(k-p+i).y*w;     // converting the Cartesian point coordinates
       pts[3*i+2] = w;                        // into homogenious coordinates
     }

     for (int r=1; r<=h; r++)                 // main loop of the de-Boor algorithm
       for (int i=0; i<=h-r; i++)
       {
         double a = (u - knots[k-p+r+i]) / (knots[k+i+1] - knots[k-p+r+i]);
         pts[3*i] = (1.0 - a)*pts[3*i] + a*pts[3*i+3];
         pts[3*i+1] = (1.0 - a)*pts[3*i+1] + a*pts[3*i+4];         
         pts[3*i+2] = (1.0 - a)*pts[3*i+2] + a*pts[3*i+5];
       }
     return new NURBVertex((int)Math.round(pts[0] / pts[2]), (int)Math.round(pts[1] / pts[2]), pts[2]);
   }

   public boolean clockwise(int x, int y, int s)     // check if the turm from the last poly segment
   {                                          // to (x,y) is clockwise
     if (s < 2) return(true);
     NURBVertex p0 = poly.get(s-2);
     NURBVertex p1 = poly.get(s-1);
     int area = (p1.x - p0.x)*(y - p0.y) - (x - p0.x)*(p1.y - p0.y);
     return(area > 0);
   }

   // auxilary function for printing the polygon nodes (just for debugging)
   public void printPoly(LinkedList<NURBVertex> l)
   {
     for (int i=0; i<l.size(); i++)
       System.out.println(i + ":  (" + l.get(i).x + "," + l.get(i).y + ") ");
     System.out.println();
   } 
}

// auxilary class for representing the polygon nodes
class NURBVertex
{
  public int x, y;              // node coordinates
  public double w;
  public NURBVertex(int x, int y, double w)   // node constructor
  {
    this.x = x;
    this.y = y;
    this.w = w;
  }
  public NURBVertex(int x, int y)
  {
    this(x, y, 1.0);
  }

  public NURBVertex clone()         // copy constructor
  {
    return(new NURBVertex(this.x, this.y, this.w)); 
  }
}