package yi.iu.processor.clc;

import java.util.*;
import yi.iu.processor.ort.*;
import java.awt.Dimension;
import yi.iu.processor.color.*;
import yi.iu.region.*;
import yi.ds.*;
import java.awt.*;
import yi.graph.polygon.*;

/**
 * Class LineClusterSet is to represent Line Clusters without duplicated lines.
 * The elements in the cluster are supposed to be the instances of
 * yi.iu.process.ort.ORTLine
 */
public class LineClusterSet extends java.util.HashSet{

  /**
   * When sorting the lines to construct the converging point of a line cluster,
   * if the length of a line is lower than STANDARD_LINE_LEN, it is considered
   * not that reliable.
   */
  public double STANDARD_LINE_LEN = 15;

  /**
   * When sorting the lines to construct the converging point of a line cluster,
   * if the length of a line is lower than STANDARD_LINE_LEN, but the number of
   * lines are still lower than MIN_LINE_NUM_4_FINDING_CONVERGING_POINT, it will
   * still be used althgouh it may be not that reliable.
   */
  public int MIN_LINE_NUM_4_FINDING_CONVERGING_POINT = 8;

  /**
   * When sorting the lines to construct the converging point of a line cluster,
   * only the longest MAX_LINE_NUM_4_FINDING_CONVERGING_POINT of lines will be
   * considered, others will be ignored.
   */
  public int MAX_LINE_NUM_4_FINDING_CONVERGING_POINT = 16;

  ColorPair m_colorPair = null;

  /**
   * The base line of the line cluser.  If the lines in the cluster are parallel
   * to each other, the line takes the parallel direction and passing the
   * weighted middle point of the lines.  If the lines are converging to a
   * point, the line passing the converging point and the weighted middle point
   * of the line cluster.  This information should be obtained on fly (be
   * calculated every time it will be used).  However since it costs a lot of
   * time to get it, the value is cached in this attribute.
   */
  ORTLine m_baseLine = null;

  /**
   * If the lines in the cluster are converging to a point, this filed is used
   * to cache the converging point.  It not, the value is "null".  This
   * information should be obtained on fly (be calculated every time it will be
   * used).  However since it costs a lot of time to get it, the value is cached
   * in this attribute.
   */
  ORTPoint m_convergingPoint = null;

  ORTLine m_overlappingLine = null;

  /**
   * The region of the line cluster.  This value should be generated "on fly",
   * but it takes long time to get it.  So cache it here.
   */
  Region m_region = null;


  int m_imgWidth, m_imgHeight;

  public LineClusterSet() {
    super();
  }

  public LineClusterSet(Collection lines) {
    super(lines);
  }

  public LineClusterSet(Collection lines, int width, int height) {
    super(lines);
    m_imgWidth = width;
    m_imgHeight = height;
  }

  public LineClusterSet(Object o) {
    super();
    if (o instanceof ColorPair) {
      m_colorPair = (ColorPair)o;
    }
  }

  public LineClusterSet(Object o, int width, int height) {
    this(o);
    m_imgWidth = width;
    m_imgHeight = height;
  }

 /**
   * Construct a line cluster using given line clusters.  All the lines in
   * each of those line clusters should be added to the resultant line cluster.
   * @param line_clusters
   */
  public LineClusterSet(LineClusterSets line_clusters) {
    Iterator i = line_clusters.values().iterator();
    while (i.hasNext()) {
      LineClusterSet line_cluster = (LineClusterSet)i.next();
      // only inherit image widht / height
      m_imgWidth = line_cluster.getImageWidth();
      m_imgHeight = line_cluster.getImageHeight();
      addAll(line_cluster);
    }
  }


  public void draw(int[] pixels, int width, int height, int color) {
    draw(pixels, width, height, color, 1, 0, 0);
  }

  /**
   * Draw the lines on the given image
   * @param pixels
   * @param width
   * @param height
   * @param color
   * @param bounds_color the color of the bounding box.  Passing in 0 if you
   * don't want the box to be draw
   */
  public void draw(int[] pixels, int width, int height, int color, int thickness, int bounds_color, int bounds_thickness) {
    Iterator i = iterator();
    if (bounds_color !=0 ) {
      ConvexPolygon poly = getPolygonBounds();
      GenericContour gpoly = new GenericContour(poly);
      gpoly.draw(pixels, width, height, bounds_color, bounds_thickness);
//              int delta_x = m_imgWidth / 2;
//      int delta_y = m_imgHeight / 2;
//      Vertexes vertexes = poly.getVertexes();
//      if (vertexes.size() > 0) {
//        LineClusterSet bound_lines = new LineClusterSet();
//        Point p1 = (Point) vertexes.elementAt(0);
//        for (int j = 1; j < vertexes.size(); j++) {
//          Point p2 = (Point) vertexes.elementAt(j);
//          bound_lines.add(new ORTLine(p1.x - delta_x, p1.y - delta_y,
//                                      p2.x - delta_x, p2.y - delta_y));
//          p1 = p2;
//        }
//        bound_lines.draw(pixels, width, height, bounds_color, bounds_thickness,
//                         0, 0);
//      }
    }
    while (i.hasNext()) {
      ORTLine l = (ORTLine)i.next();
      DrawUtil.ort2image(pixels, new Dimension(width, height), l, color, thickness);
    }
//    if (bounds_color !=0 ) {
//      Rectangle rect = getBounds();
//      int delta_x = m_imgWidth / 2;
//      int delta_y = m_imgHeight / 2;
//      double x1 = rect.getMinX() - delta_x, y1 = rect.getMinY() - delta_y,
//          x2 = rect.getMaxX() - delta_x, y2 = rect.getMaxY() - delta_y;
//      LineClusterSet bound_lines = new LineClusterSet();
//      bound_lines.add(new ORTLine(x1,y1,x2,y1));
//      bound_lines.add(new ORTLine(x2,y1,x2,y2));
//      bound_lines.add(new ORTLine(x2,y2,x1,y2));
//      bound_lines.add(new ORTLine(x1,y2,x1,y1));
//      bound_lines.draw(pixels, width, height, bounds_color, bounds_thickness, 0, 0);
//    }
  }


  /**
   * Return a demo image (new memory) of the line cluster
   * @param pixels the original image which will be used to construct
   *        background.  Pass in "null" to use black background
   * @param d
   * @param draw_lines whether draw lines
   * @param draw_boundingbox whether draw the bounding box
   * @param draw_axis whether draw the perspective coordinators
   * @param draw_cp whether draw the spectrum of color pair
   * @return the demo image
   */
  public int[] demo(int[] pixels, Dimension d, boolean draw_lines,
                    boolean draw_boundingbox, boolean draw_axis, boolean draw_cp) {

    // make the image with background
    int[] lineimg = (pixels != null) ?
        yi.util.ImageUtil.makeBackground(pixels) :
        yi.util.ImageUtil.makeBackground(d, 0xff000000);

    // draw the lines
    if (draw_lines) {
      draw(lineimg, d.width, d.height, 0xffffffff);
    }

    // recalculate base line and overlapping line so that we can lastest
    // bounding box and perspective coordinates
    getOverlappingLine(false);

    // bounding box
    if (draw_boundingbox) {
      LineClusterSet box = getPerspectiveBasedBoundingBox();
      box.draw(lineimg, d.width, d.height, 0xffff0000);
    }

    // the perspective coordinates
    if (draw_axis) {
      ORTLine base_line = getBaseLine();
      ORTLine overlapping_line = getOverlappingLine();
      DrawUtil.ort2image(lineimg, d, base_line, 0xff00ff00, 1);
      DrawUtil.ort2image(lineimg, d, overlapping_line, 0xff0000ff, 1);
    }

    // color spectrum
    if (draw_cp) {
      ColorPair cp = getColorPair();
      if (cp != null) {
        int[] colors = new int[] {
            cp.x, cp.y};
        int color_w = 40, color_h = 50;
        int[] spectrum = yi.iu.processor.color.ColorUtil.createSpectrum(
            colors, color_w, color_h);
        for (int y = 0; y < color_h; y++) {
          for (int x = 0; x < color_w * colors.length; x++) {
            lineimg[y * d.width + x] = spectrum[y * color_w * colors.length +
                x];
          }
        }
      }
    }
    return lineimg;

  }

  public int[] demoWithPolygonBound(int[] pixels, Dimension d, boolean draw_lines, boolean draw_cp) {

    // make the image with background
    int[] lineimg = (pixels != null) ?
        yi.util.ImageUtil.makeBackground(pixels) :
        yi.util.ImageUtil.makeBackground(d, 0xff000000);

    // draw bounds
    draw(lineimg, d.width, d.height, 0xff00ff00, 1, 0xffff0000, 2);

    // color spectrum
    if (draw_cp) {
      ColorPair cp = getColorPair();
      if (cp != null) {
        int[] colors = new int[] {
            cp.x, cp.y};
        int color_w = 40, color_h = 50;
        int[] spectrum = yi.iu.processor.color.ColorUtil.createSpectrum(
            colors, color_w, color_h);
        for (int y = 0; y < color_h; y++) {
          for (int x = 0; x < color_w * colors.length; x++) {
            lineimg[y * d.width + x] = spectrum[y * color_w * colors.length +
                x];
          }
        }
      }
    }
    return lineimg;

  }

  /**
   * Return a demo image to demonstrate the ellipse region of the lines
   * @param pixels the original image which will be used to construct
   *        background.  Pass in "null" to use black background
   * @param d
   * @return
   */
  int[] demoRegion(int[] pixels, Dimension d) {
    // make the image with background
    int[] lineimg = (pixels != null) ?
        yi.util.ImageUtil.makeBackground(pixels) :
        yi.util.ImageUtil.makeBackground(d, 0xff000000);
    Region r = getRegion();
    Region.drawRegions(lineimg, d, r, 0xffffffff);
    return lineimg;
  }

  /**
   * Filter the lines so that the remaining lines having the the specified
   * minimum length.
   * @param min_length the minimum length of the remaining lines
   * @return the total line number remained.
   */
  public int filter(double min_length) {
    Iterator i = iterator();
    while (i.hasNext()) {
      ORTLine l = (ORTLine) i.next();
      if (l.Length < min_length) i.remove();
    }
    return size();
  }

  public double getTotalLen() {
    double len = 0;
    Iterator i = iterator();
    while (i.hasNext()) {
      ORTLine l = (ORTLine) i.next();
      len += l.Length;
    }
    return len;
  }

  /**
   * for Castor only
   */
  public void setTotalLen() {
  }

  public double getMaxX() {
    double[] x1 = new double[size()];
    double[] x2 = new double[size()];
    Iterator i = iterator();
    int count = 0;
    while (i.hasNext()) {
      ORTLine l = (ORTLine) i.next();
      x1[count] = l.getX1();
      x2[count] = l.getX2();
      count++;
    }
    return Math.max(yi.stat.StatUtil.maximum(x1), yi.stat.StatUtil.maximum(x2));
  }

  public double getMinX() {
    double[] x1 = new double[size()];
    double[] x2 = new double[size()];
    Iterator i = iterator();
    int count = 0;
    while (i.hasNext()) {
      ORTLine l = (ORTLine) i.next();
      x1[count] = l.getX1();
      x2[count] = l.getX2();
      count++;
    }
    return Math.min(yi.stat.StatUtil.minimum(x1), yi.stat.StatUtil.minimum(x2));
  }

  public double getMaxY() {
    double[] y1 = new double[size()];
    double[] y2 = new double[size()];
    Iterator i = iterator();
    int count = 0;
    while (i.hasNext()) {
      ORTLine l = (ORTLine) i.next();
      y1[count] = l.getY1();
      y2[count] = l.getY2();
      count++;
    }
    return Math.max(yi.stat.StatUtil.maximum(y1), yi.stat.StatUtil.maximum(y2));
  }

  public double getMinY() {
    double[] y1 = new double[size()];
    double[] y2 = new double[size()];
    Iterator i = iterator();
    int count = 0;
    while (i.hasNext()) {
      ORTLine l = (ORTLine) i.next();
      y1[count] = l.getY1();
      y2[count] = l.getY2();
      count++;
    }
    return Math.min(yi.stat.StatUtil.minimum(y1), yi.stat.StatUtil.minimum(y2));
  }

  public HashSet getLineClusterSet() {
    return this;
  }

  public ColorPair getColorPair() {
    return m_colorPair;
  }

  public void setColorPair(ColorPair color_pair) {
    m_colorPair = color_pair;
  }

  /**
   * Return the base line.  Use cache if possible
   * @return
   */
  public ORTLine getBaseLine() {
    return getBaseLine(true);
  }

  public void setBaseLine(ORTLine l) {
    m_baseLine = l;
  }

  public ORTPoint getConvergingPoint() {
    return m_convergingPoint;
  }

  public void setConvergingPoint(ORTPoint p) {
    m_convergingPoint = p;
  }

  public int getImageWidth() {
    return m_imgWidth;
  }

  public void setImageWidth(int w) {
    m_imgWidth = w;
  }

  public int getImageHeight() {
    return m_imgHeight;
  }

  public void setImageHeight(int h) {
    m_imgHeight = h;
  }

  public Region getRegion(boolean useCache) {
    if (useCache && m_region != null) return m_region;
    int[] labels = new int[m_imgWidth * m_imgHeight]; // backgournd = 0
    Iterator i = iterator();
    while (i.hasNext()) {
      ORTLine l = (ORTLine)i.next();
      DrawUtil.ort2image(labels, new Dimension(m_imgWidth, m_imgHeight), l, 1, 1);
    }
    Region[] regions = yi.iu.region.Region.getRegions(labels, 1, new Dimension(m_imgWidth, m_imgHeight));
    m_region = regions[1];
    return m_region;
  }

  public Region getRegion() {
    return getRegion(true);
  }

  public void setRegion(Region r) {
    m_region = r;
  }

  public void setPolyonRegion(GenericPolygon r) {
  }

  public GenericPolygon getPolygonRegion() {
    ConvexPolygon poly = getPolygonBounds();
    GenericContour gcontour = new GenericContour(poly);
    GenericPolygon polygon_region = new GenericPolygon(gcontour);
    return polygon_region;
  }

  /**
   * Gets the bounding Rectangle of this cluster
   * @return
   */
  public Rectangle getBounds() {
    int delta_x = m_imgWidth / 2;
    int delta_y = m_imgHeight / 2;
    Rectangle rect = null;
    for (Iterator i=iterator(); i.hasNext();) {
      ORTLine l = (ORTLine)i.next();
      Point p1 = new Point((int)Math.round(l.getX1()) + delta_x, (int)Math.round(l.getY1()) + delta_y);
      Point p2 = new Point((int)Math.round(l.getX2()) + delta_x, (int)Math.round(l.getY2()) + delta_y);
      if (rect == null) {
        rect = new Rectangle(p1);
        rect.add(p2);
      } else {
        rect.add(p1);
        rect.add(p2);
      }
    }
    return rect;
  }

  public ConvexPolygon getPolygonBounds() {
    int delta_x = m_imgWidth / 2;
    int delta_y = m_imgHeight / 2;
    Vertexes vertexes =  new Vertexes();
    for (Iterator i=iterator(); i.hasNext();) {
      ORTLine l = (ORTLine) i.next();
      Point p1 = new Point( (int) Math.round(l.getX1()) + delta_x,
                           (int) Math.round(l.getY1()) + delta_y);
      Point p2 = new Point( (int) Math.round(l.getX2()) + delta_x,
                           (int) Math.round(l.getY2()) + delta_y);
      vertexes.add(p1);
      vertexes.add(p2);
    }
    ConvexPolygon poly = new ConvexPolygon(vertexes);
    return poly;
  }

  /**
   * When a LineClusterSets is obtained from clustering of a LineClusterSet, we
   * want to copy the properties of the parent to all the children (like the
   * color, oritentation and position information)
   * @param line_cluster
   */
  public void inheritProperties(LineClusterSet line_cluster) {
    if (m_colorPair == null) m_colorPair = line_cluster.m_colorPair;
    if (m_baseLine == null) m_baseLine = line_cluster.m_baseLine;
    if (m_convergingPoint == null) m_convergingPoint = line_cluster.m_convergingPoint;

    m_imgHeight = line_cluster.m_imgHeight;
    m_imgWidth = line_cluster.m_imgWidth;
  }

  /**
   * Create a new instance of LineClusterSet with the same properties but empty
   * lines
   * @return
   */
  public LineClusterSet newInstanceWithSameProperties() {
    LineClusterSet new_one = new LineClusterSet();
    new_one.inheritProperties(this);
    return new_one;
  }

  public String toString() {
    StringBuffer s = new StringBuffer(
      "line cluster :" +
      "(color = " + m_colorPair +
      " Dimension = (" + m_imgWidth + ", " + m_imgHeight + ")" +
      System.getProperty("line.separator"));
    Iterator i = iterator();
    while (i.hasNext()) {
      ORTLine line = (ORTLine)i.next();
      s.append(line.toString());
      s.append(System.getProperty("line.separator"));
    }
    return s.toString();
  }

  /**
   * Return the weighted length total of the lines in the cluster
   * @return
   */
  public double linesWeight() {
    double weight = 0;
    Iterator i = iterator();
    while (i.hasNext()) {
      ORTLine l = (ORTLine)i.next();
      weight += CLCUtil.lineWeight(l.Length);
    }
    return weight;
  }

  /**
   * Return the length total of the lines in the cluster
   * @return
   */
  public double linesLength() {
    double len = 0;
    Iterator i = iterator();
    while (i.hasNext()) {
      ORTLine l = (ORTLine)i.next();
      len += l.Length;
    }
    return len;
  }

  /**
   * Return the line with the maximum length
   * @return
   */
  public ORTLine getMaxLengthLine() {
    double len = 0;
    ORTLine max_l = null;
    Iterator i = iterator();
    while (i.hasNext()) {
      ORTLine l = (ORTLine)i.next();
      if (len < l.Length) {
        len = l.Length; max_l = l;
      }
    }
    return max_l;
  }

  /**
   * Return the weighted middle point of the lines
   * @return
   */
  public ORTPoint getWeightedMiddlePoint() {
    // the sum of weighted length
    double weightedSum = linesWeight();

    // find the weighted mid point
    double vlPtCol = 0, vlPtRow = 0;
    Iterator i = iterator();
    while (i.hasNext()) {
      ORTLine l = (ORTLine)i.next();
      vlPtCol += (l.Start.Col+l.End.Col)/2 * CLCUtil.lineWeight(l.Length);
      vlPtRow += (l.Start.Row+l.End.Row)/2 * CLCUtil.lineWeight(l.Length);
    }
    vlPtCol /= weightedSum;
    vlPtRow /= weightedSum;

    return new ORTPoint(vlPtCol, vlPtRow);
  }

  /**
   * Return the weighted length array of the lines
   * @return
   */
  public double[] getWeightedLength() {
    double[] weight_lenghth_array = new double[size()];
    Iterator i = iterator();
    int count = 0;
    while (i.hasNext()) {
      ORTLine l = (ORTLine)i.next();
      weight_lenghth_array[count++] = CLCUtil.lineWeight(l.Length);
    }
    return weight_lenghth_array;
  }

  public double getTotalWeightedLength() {
    double sum = 0;
    Iterator i = iterator();
    while (i.hasNext()) {
      ORTLine l = (ORTLine)i.next();
      sum += CLCUtil.lineWeight(l.Length);
    }
    return sum;
  }

  /**
   * Return the lines with the perspective effects removed.  Make a new
   * coordinate system and return the lines in the new system.  If the lines are
   * parallel to each other, make the parallel base line as the x axis; if the
   * lines are converging, make the converging base line as the x axis.  If the
   * lines are neither parallel nor converging, leave them untouched.
   * @param lines
   * @return
   */
  ORTLine[] getLinesWithoutPerspectiveEffects() {
    ORTLine[] new_lines = new ORTLine[size()];
    int count = 0;

    ORTLine base_line = getBaseLine();

    ORTLine y_axis = base_line.makeNewLineByRotate90();
    //ORTLine y_axis = getOverlappingLine();

    // y
    double y, x1, x2;

    // split the lines to upper part and the lower part
    Iterator i = iterator();
    while (i.hasNext()) {

      ORTLine l = (ORTLine)i.next();

      if (m_convergingPoint == null) {    // if the lines are parallel to each other

        // make a line perpendicular to the parallel base line (y axis)
        y = CLCUtil.coordinateToAxis(l.midPoint(), y_axis);
      }

      else { // lines are converging

        // modified line connecting its middle point and converging point
        ORTLine virtual_l= new ORTLine(l.midPoint(), m_convergingPoint);
        ORTPoint intersect = new ORTPoint();
        // intersectant point
        if (!GeometricUtil.getInterceptPoint(virtual_l, y_axis, intersect)) {
          System.err.println("the converged line not intersect with y");
          y = 0; // line is overlapped with y axis
        } else {
          y = CLCUtil.positionOnAxis(intersect, y_axis);
        }
      }

      // for x1, x2
      x1 = CLCUtil.coordinateToAxis(l.Start, base_line);
      x2 = CLCUtil.coordinateToAxis(l.End, base_line);

      // add the adjusted line
      new_lines[count++] = new ORTLine(x1, y, x2, y);
    }

//    // demo the lines before removing perspective effects
//    int[] demo_img = new int[m_imgHeight * m_imgWidth];
//    java.util.Arrays.fill(demo_img, 0xff000000);
//    draw(demo_img, m_imgWidth, m_imgHeight, 0xffffffff);
//    yi.util.io.OutputResult.outputGIFImage("a_perspective", demo_img, m_imgWidth, m_imgHeight, true);
//
//    // demo the lines after removing perspective effects
//    java.util.Arrays.fill(demo_img, 0xff000000);
//    LineClusterSet new_cluster = new LineClusterSet(java.util.Arrays.asList(new_lines));
//    new_cluster.draw(demo_img, m_imgWidth, m_imgHeight, 0xffffffff);
//    yi.util.io.OutputResult.outputGIFImage("b_perspective", demo_img, m_imgWidth, m_imgHeight, true);
    return new_lines;
  }

  ORTLine[] getLinesWRTBaseLine() {
    ORTLine[] new_lines = new ORTLine[size()];
    int count = 0;

    ORTLine base_line = getBaseLine();

    ORTLine y_axis = base_line.makeNewLineByRotate90();

    // y
    double y, x1, x2;

    // split the lines to upper part and the lower part
    Iterator i = iterator();
    while (i.hasNext()) {

      ORTLine l = (ORTLine)i.next();

      if (m_convergingPoint == null) {    // if the lines are parallel to each other

        // make a line perpendicular to the parallel base line (y axis)
        y = CLCUtil.coordinateToAxis(l.midPoint(), y_axis);
      }

      else { // lines are converging

        // intersectant point
        double[] intercept_p = GeometricUtil.PtLinePerpIntercept(l.midPoint(), y_axis);
        y = CLCUtil.positionOnAxis(new ORTPoint(intercept_p[0], intercept_p[1]), y_axis);
      }

      // for x1, x2
      x1 = CLCUtil.coordinateToAxis(l.Start, base_line);
      x2 = CLCUtil.coordinateToAxis(l.End, base_line);

      // add the adjusted line
      new_lines[count++] = new ORTLine(x1, y, x2, y);
    }

//    // demo the lines before removing perspective effects
//    int[] demo_img = new int[m_imgHeight * m_imgWidth];
//    java.util.Arrays.fill(demo_img, 0xff000000);
//    draw(demo_img, m_imgWidth, m_imgHeight, 0xffffffff);
//    yi.util.io.OutputResult.outputGIFImage("a_perspective", demo_img, m_imgWidth, m_imgHeight, true);
//
//    // demo the lines after removing perspective effects
//    java.util.Arrays.fill(demo_img, 0xff000000);
//    LineClusterSet new_cluster = new LineClusterSet(java.util.Arrays.asList(new_lines));
//    new_cluster.draw(demo_img, m_imgWidth, m_imgHeight, 0xffffffff);
//    yi.util.io.OutputResult.outputGIFImage("b_perspective", demo_img, m_imgWidth, m_imgHeight, true);
    return new_lines;
  }

  public int[] demo() {

    int[] lineimg = new int[m_imgHeight * m_imgWidth];
    java.util.Arrays.fill(lineimg, 0xff000000); // background to 0

    draw(lineimg, m_imgWidth, m_imgHeight, 0xffffffff);
    return lineimg;
  }

  public LineClusterSet getPerspectiveBasedBoundingBox() {
    // the perspective x-axis and y-axis
    ORTLine x_axis = getBaseLine();
    ORTLine y_axis = getOverlappingLine();

    // find the bounday of them
    ORTPoint min_x = x_axis.midPoint(), max_x = x_axis.midPoint(),
             min_y = x_axis.midPoint(), max_y = x_axis.midPoint();
    double dis_min_x = 0, dis_max_x = 0, dis_min_y = 0, dis_max_y = 0;

    Iterator i = iterator();
    while (i.hasNext()) {

      ORTLine l = (ORTLine)i.next();
      ORTPoint intersect = new ORTPoint();
      double x, y;
      ORTLine virtual_l;

      // virtual line pass the first end point of the line and parallel to
      // perspective x-axis
      virtual_l = new ORTLine (l.Start, x_axis.Theta, 1000);
      GeometricUtil.getInterceptPoint(virtual_l, y_axis, intersect);
      y = CLCUtil.positionOnAxis(intersect, y_axis);
      if (y > dis_max_y) {
        dis_max_y = y; max_y = new ORTPoint(intersect);
      }
      if (y < dis_min_y) {
        dis_min_y = y; min_y = new ORTPoint(intersect);
      }

      // virtual line pass the second end point of the line and parallel to
      // perspective x-axis
      virtual_l = new ORTLine (l.End, x_axis.Theta, 1000);
      GeometricUtil.getInterceptPoint(virtual_l, y_axis, intersect);
      y = CLCUtil.positionOnAxis(intersect, y_axis);
      if (y > dis_max_y) {
        dis_max_y = y; max_y = new ORTPoint(intersect);
      }
      if (y < dis_min_y) {
        dis_min_y = y; min_y = new ORTPoint(intersect);
      }

      // virtual line pass the first end point of the line and parallel to
      // perspective y-axis
      virtual_l = new ORTLine (l.Start, y_axis.Theta, 1000);
      GeometricUtil.getInterceptPoint(virtual_l, x_axis, intersect);
      x = CLCUtil.positionOnAxis(intersect, x_axis);
      if (x > dis_max_x) {
        dis_max_x = x; max_x = new ORTPoint(intersect);
      }
      if (x < dis_min_x) {
        dis_min_x = x; min_x = new ORTPoint(intersect);
      }

      // virtual line pass the second end point of the line and parallel to
      // perspective y-axis
      virtual_l = new ORTLine (l.End, y_axis.Theta, 1000);
      GeometricUtil.getInterceptPoint(virtual_l, x_axis, intersect);
      x = CLCUtil.positionOnAxis(intersect, x_axis);
      if (x > dis_max_x) {
        dis_max_x = x; max_x = new ORTPoint(intersect);
      }
      if (x < dis_min_x) {
        dis_min_x = x; min_x = new ORTPoint(intersect);
      }
    }

    // bounding lines (the length is not decided yet)
    ORTLine upper = new ORTLine(max_y, x_axis.Theta, 1000);
    ORTLine lower = new ORTLine(min_y, x_axis.Theta, 1000);
    ORTLine left = new ORTLine(min_x, y_axis.Theta, 1000);
    ORTLine right = new ORTLine(max_x, y_axis.Theta, 1000);

    // corners
    ORTPoint nw = new ORTPoint();
    ORTPoint ne = new ORTPoint();
    ORTPoint sw = new ORTPoint();
    ORTPoint se = new ORTPoint();

    GeometricUtil.getInterceptPoint(upper, left, nw);
    GeometricUtil.getInterceptPoint(upper, right, ne);
    GeometricUtil.getInterceptPoint(lower, left, sw);
    GeometricUtil.getInterceptPoint(lower, right, se);

    // boundary segment
    ORTLine upper_seg = new ORTLine(nw, ne);
    ORTLine lower_seg = new ORTLine(sw, se);
    ORTLine left_seg = new ORTLine(nw, sw);
    ORTLine right_seg = new ORTLine(ne, se);

    LineClusterSet bounding_box = new LineClusterSet();
    bounding_box.add(upper_seg);
    bounding_box.add(lower_seg);
    bounding_box.add(left_seg);
    bounding_box.add(right_seg);

    return bounding_box;

  }

  static double OVERLAPPING_BASELINE_LEN = 400;

  public void setOverlappingLine(ORTLine l) {
    m_overlappingLine = l;
  }

  /**
   * This method always use cached based line.  So if the cluster changed (some
   * lines are deleted), re-calculate the base line by calling
   * <code>
   * getBasedLine(false);
   * </code>
   * @return
   */
  public ORTLine getOverlappingLine() {
    return getOverlappingLine(true);
  }

  /**
   *
   * @param useCache
   * @return
   */
  public ORTLine getOverlappingLine(boolean useCache) {

    if (useCache && m_overlappingLine != null) return m_overlappingLine;

    ORTLine base_line = getBaseLine(useCache);
    LineClusterSet upper_lines = new LineClusterSet();
    LineClusterSet lower_lines = new LineClusterSet();

    ORTLine y_axis = base_line.makeNewLineByRotate90();

    // split the lines to upper part and the lower part
    Iterator i = iterator();
    while (i.hasNext()) {

      ORTLine l = (ORTLine)i.next();

      double y; // the y position will decide which group (upper or lower) the
                // line goes to

      if (m_convergingPoint == null) {    // if the lines are parallel to each other

        // make a line perpendicular to the parallel base line (y axis)
        y = CLCUtil.coordinateToAxis(l.midPoint(), y_axis);
      }

      else { // lines are converging

        // modified line connecting its middle point and converging point
        ORTLine virtual_l= new ORTLine(l.midPoint(), m_convergingPoint);
        ORTPoint intersect = new ORTPoint();
        // intersectant point
        if (!GeometricUtil.getInterceptPoint(virtual_l, y_axis, intersect)) {
          System.err.println("the converged line not intersect with y");
          y = 0; // line is overlapped with y axis
        } else {
          y = CLCUtil.positionOnAxis(intersect, y_axis);
        }
      }

      if (y > 0) upper_lines.add(l);
      else if (y < 0) lower_lines.add(l);
    }

    // if there are no obvious upper and lower part
    if (upper_lines.size() == 0 || lower_lines.size() == 0) {
      ORTPoint p = getWeightedMiddlePoint();
      double line_direction = y_axis.Theta;
      m_overlappingLine = new ORTLine(p, line_direction, 1);
      return m_overlappingLine;
    }

    // the line connecting the weighted middle point of the upper part and that
    // of the lower part is the direction of the overlapping (that line is not
    // necessarily passing the weighted middle point of all lines)
    ORTLine connected_line = new ORTLine(
      upper_lines.getWeightedMiddlePoint(),
      lower_lines.getWeightedMiddlePoint());

    // adjust it to passing the weighted middle point of all lines
    ORTPoint middle_p = getWeightedMiddlePoint();
    double line_direction = connected_line.Theta;
    m_overlappingLine  = new ORTLine(middle_p, line_direction, OVERLAPPING_BASELINE_LEN);
    return m_overlappingLine;

  }

  /**
   * Filter a line cluster using perspective information.  The remained lines
   * are either parallel to each other or are converged to a single point.  The
   * algorithm only use the longest lines in the line cluster to generate the
   * possilbe parallel directions and possible converging points.  It gives
   * scores for each possible parallel directions and possible converging
   * points and the lines will be filtered by the one with the highest score.
   * @param line_cluster the line cluster to be filtered.
   * @return the filtered line cluster
   */
  public ORTLine getBaseLine(boolean useCache)
  {
    if (useCache && m_baseLine != null) return m_baseLine;


    // if there is only one line, set the property to "parallel"
    if (size() < 1) return null;
    if (size() == 1) {
      m_baseLine = (ORTLine)iterator().next();
      m_convergingPoint = null;
      return m_baseLine;
    }

    // make a vector of lines for easy operations
    Vector lines = new Vector(this);

    // first sort the lines according to their length in the line cluster since
    // the longer a line, the more reliable perspective information it can
    // provide.  Only the longest MAX_LINE_NUM_4_FINDING_CONVERGING_POINT lines
    // are considered
    int i;
    for (i=0; i < lines.size() && i < MAX_LINE_NUM_4_FINDING_CONVERGING_POINT; i++) {
      //get the i-th longest
      ORTLine element1 = (ORTLine)lines.elementAt(i);
      for (int j=i+1; j<lines.size(); j++) {
        ORTLine element2 = (ORTLine)lines.elementAt(j);
        if (element1.Length < element2.Length) {
          lines.setElementAt(element1, j);
          element1=element2;
        }
      }
      lines.setElementAt(element1, i);
      // stop the sorting if the length of the line is less than the standard (
      // they are not that useful anymore).  This is to save the sorting time
      if (element1.Length < STANDARD_LINE_LEN &&
          i >= MIN_LINE_NUM_4_FINDING_CONVERGING_POINT) break;
    }

    int useNum = i;   //only use the first i, the lines[i] will not be used

    // get all the possible converged points (candidates)
    // if two lines are not converged, a "null" will be put there instead
    int candNum =useNum * (useNum - 1) / 2;
    ORTPoint[] convergedPts= new ORTPoint[candNum];
    int count=0;
    ORTPoint intersect=new ORTPoint();
    for (i=0; i<useNum-1; i++) {
      ORTLine element1 = (ORTLine)lines.elementAt(i);
      for (int j=i+1; j<useNum; j++) {
        ORTLine element2 = (ORTLine)lines.elementAt(j);
        boolean converge = GeometricUtil.getInterceptPoint
                  (element1, element2, intersect);
        if (converge) convergedPts[count++]= new ORTPoint(intersect.Col,intersect.Row);
        else convergedPts[count++]= null;
      }
    }

    //get the qualities for all the candidates of converging point
    double[] convQual= new double[candNum];
    for (i=0;i<candNum;i++) {
        convQual[i]= convergeQuality(convergedPts[i], lines);
    }

    //get the converged point with best quality
    double bestConvQual=0;
    int bestConvIndex=-1;
    for (i=0;i<candNum;i++) {
        if (convQual[i]>bestConvQual) {
            bestConvQual=convQual[i];
            bestConvIndex=i;
        }
    }

    //get the quality of parallel
    //get the qualities for all the candidates
    double[] paraQual= new double[useNum];
    for (i=0;i<useNum;i++) {
        ORTLine l= (ORTLine)lines.elementAt(i);
        paraQual[i]= parallelQuality(l, lines);
    }

    //get the paralleled point with best quality
    double bestparaQual=0;
    int bestparaIndex=-1;
    for (i=0;i<paraQual.length;i++) {
        if (paraQual[i]>bestparaQual) {
            bestparaQual=paraQual[i];
            bestparaIndex=i;
        }
    }

    // they are parallel
    if (bestparaQual >= bestConvQual) {
      double line_direction = ((ORTLine)lines.elementAt(bestparaIndex)).Theta;
      m_baseLine = makeParallelBaseLine(line_direction);
      m_convergingPoint = null;
    } else { // they are converging
      ORTPoint converging_point = convergedPts[bestConvIndex];
      m_convergingPoint = converging_point;
      m_baseLine = makeConvergingBaseLine(converging_point);
    }
    return m_baseLine;
  }

  static double PARALLEL_BASELINE_LEN = 100;

  /**
   * Return the parallel base line of the lines in the cluster.  The line
   * has the direction as specified in the argument and passes the weighted
   * middle line of the lines in the line cluster
   * @param line_direction
   * @return
   */
  ORTLine makeParallelBaseLine(double line_direction) {

    // weighted middle point as the middle point of the base line
    ORTPoint p = getWeightedMiddlePoint();

    return new ORTLine(p, line_direction, PARALLEL_BASELINE_LEN);
  }

  /**
   * Return the converging base line of the lines in the cluster.  The base line
   * passes the given converging point and its middle point is the weighted
   * middle point of all the liness in the cluster.
   * @param converging_point
   * @return
   */
  ORTLine makeConvergingBaseLine(ORTPoint converging_point) {

    // weighted middle point as the middle point of the base line
    ORTPoint weighted_middle = getWeightedMiddlePoint();

    double vlPtCol = weighted_middle.Col;
    double vlPtRow = weighted_middle.Row;

    // make the converging point as one end, and calculate the other end to
    // maintain the middle point position
    double other_col = vlPtCol + (vlPtCol - converging_point.Col);
    double other_row = vlPtRow + (vlPtRow - converging_point.Row);

    // return the base line
    return new ORTLine(converging_point, new ORTPoint(other_col, other_row));
  }

  /**
   * Decide whether a line is crossing a point.  Because the orientation of line
   * is not precise in the discrete coordinate system, so we can just examine
   * whether the point is on the line.   This algorithm tolerant one pixel shift
   * of one end point of the line.  It connects the point and the end point the
   * line far from the point to make a virtual line and examines whether the
   * other end point is less than 1-pixel away from the virtual line.
   * @param l
   * @param p
   * @return
   */
  boolean isConverge(ORTLine l, ORTPoint p)
  {
    // see which end point is far from the point p
    double d1 = GeometricUtil.distance(p,l.Start);
    double d2 = GeometricUtil.distance(p,l.End);
    ORTPoint farp = null, nearp = null;
    if (d1 > d2) {
      farp = l.Start; nearp = l.End;
    } else {
      farp = l.End; nearp = l.Start;
    }

    // the distance from the near end point of the line to the virtual line
    // which connects the point and the far end point of the line
    double d = GeometricUtil.PtLinePerpDistance(nearp, p, farp);

//    // another criterion: the shift of the point should be less 1/2 of the line
//    // variance on perpenticular direction
//    if (d < l.LengthPerpVar/2) return true;
    double threshold = 1 + l.getDistortionCompensate(Math.max(m_imgHeight, m_imgWidth));
    if (d <= threshold) return true;
    else return false;

//    // another criterion: connect the point and the middle point of the line to
//    // make a virtual line and see whether the end points are within 1-pixel
//    // away
//    ORTPoint mid= new ORTPoint((l.Start.Col+l.End.Col)/2,(l.Start.Row+l.End.Row)/2);
//    double d1 = GeometricUtil.PtLinePerpDistance(l.Start, p, mid);
//    double d2 = GeometricUtil.PtLinePerpDistance(l.End, p, mid);
//    if (d1 < 1 && d2 < 1) return true;
//    return false;
  }

  /**
   * Calcualte the quality for making p as the converged point of lines.  The
   * quality is simply the total length of those lines acrossing the p
   * @param p
   * @param lines
   * @return
   */
  double convergeQuality(ORTPoint p, Vector lines)
  {
      if (p==null || lines==null) return 0;
      double q=0;
      for (int i=0; i<lines.size(); i++) {
          ORTLine l = (ORTLine)lines.elementAt(i);
          if (isConverge(l,p)) q += CLCUtil.lineWeight(l.Length);
      }
      return q;
  }

  /**
   * Return the lines in the given "lines" which are converging to the point
   * @param p
   * @param lines
   * @return
   */
  LineClusterSet convergedLines(ORTPoint p, LineClusterSet lines) {
    return convergedLines(p, lines, -1);

  }

  /**
   * Return the lines in the given "lines" which are converging to the point.
   * The direction of the returned lines can be similar.  This is controlled
   * by the parameter dir_diff_threshold.  If the directin of a line is too
   * different from the mean of the direction (greater than dir_diff_threshold),
   * it will be not considered as "converged" to the point.  Pass negative
   * number for dir_diff_threshold if you don't care the direction of lines
   * @param p
   * @param lines
   * @param dir_diff_threshold
   * @return
   */
  LineClusterSet convergedLines(ORTPoint p, LineClusterSet lines, double dir_diff_threshold)
  {
      if (p == null || lines == null) return null;

      LineClusterSet convL = lines.newInstanceWithSameProperties();
      convL.m_convergingPoint = p;

      for (Iterator i = lines.iterator(); i.hasNext(); ) {
          ORTLine l = (ORTLine)i.next();
          if (isConverge(l,p))  convL.add(l);
      }

      if (dir_diff_threshold < 0) return convL;

      double direction_mean = convL.getDirectionMean();

      for (Iterator i = convL.iterator(); i.hasNext(); ) {
        ORTLine l = (ORTLine) i.next();
        double theta = l.getDirection();
        double diff = ORTLine.directionDifference(theta, direction_mean);
        if (diff >= dir_diff_threshold) {
          i.remove();
        }
      }

      // if no lines have similar direction, add only the first line
      if (convL.size() == 0 && lines.size() > 0) {

        for (Iterator i = lines.iterator(); i.hasNext(); ) {
            ORTLine l = (ORTLine)i.next();
            if (isConverge(l,p))  convL.add(l);
        }

        // find the longest line
        Iterator i = convL.iterator();
        ORTLine longest = (ORTLine) i.next();
        while (i.hasNext()) {
          ORTLine l = (ORTLine) i.next();
          if (longest.getLength() < l.getLength())
            longest = l;
        }

        // add those having similar direction to the longest in
        double the_direction = longest.getDirection();
        for (i = convL.iterator(); i.hasNext(); ) {
          ORTLine l = (ORTLine) i.next();
          double theta = l.getDirection();
          double diff = ORTLine.directionDifference(theta, the_direction);
          if (diff >= dir_diff_threshold) {
            i.remove();
          }
        }
      }

      return convL;
  }

  /**
   * Return the direction mean of the line cluster.  Since the direction is
   * cyclic, so it is difficult to define the mean sometimes.  For example,
   * what's the direction mean of a 0 degree line and a 178 degree line.  One
   * answer is (0 + 178)/2, and another is (180 + 178)/2.  This method will
   * calculate two means: one using I and II coordinates quarters; and another
   * using I and IIII.  The better one will be returned.
   * @return
   */
  public double getDirectionMean() {
    // see whether the lines are most horizontal lines or vertical
    // so that we know how to calculate the mean of the orientation
    double horizontal_mean = 0;
    double vertical_mean = 0;
    for (Iterator i = iterator(); i.hasNext(); ) {
      ORTLine l = (ORTLine) i.next();
      double theta = l.getDirection();
      if (theta >= Math.PI / 2) {
        horizontal_mean += (theta - Math.PI);
        vertical_mean += theta;
      }
      else {
        horizontal_mean += theta;
        vertical_mean += theta;
      }
    }
    horizontal_mean /= size();
    vertical_mean /= size();

    // see which mean is better
    double horizontal_diff = 0;
    double vertical_diff = 0;
    for (Iterator i = iterator(); i.hasNext(); ) {
      ORTLine l = (ORTLine) i.next();
      double theta = l.getDirection();
      horizontal_diff += ORTLine.directionDifference(theta, horizontal_mean);
      vertical_diff += ORTLine.directionDifference(theta, vertical_mean);
    }

    double mean = (horizontal_diff >= vertical_diff)? vertical_mean: horizontal_mean;

    return mean;
  }

  /**
   * Decide whether a line is parallel to a base line.  Because the orientation
   * of a line is not precise in the discrete coordinate system, so we can just
   * examine whether their orientations are the same.  This algorithm tolerant
   * one pixel shift of one end point of the line.  It makes a virtual line
   * passing one end point of the line and having the orientation as in the base
   * line and examines whether the other end point is less than 1-pixel away
   * from the virtual line.
   * @param l
   * @param standard
   * @return
   */
  boolean isParallel(ORTLine l, ORTLine standard) {
    double correct_theta_var = l.LineSegThetaVar(l.Length);
    double d = GeometricUtil.PtLinePerpDistance(l.Start, l.End, standard.Theta);

//    // another criterion: the shift of the point should be less 1/2 of the line
//    // variance on perpenticular direction
//    if (d < l.LengthPerpVar/2) return true;
    double threshold = 1 + l.getDistortionCompensate(Math.max(m_imgHeight, m_imgWidth));
    if (d <= threshold) return true;
    else return false;

//    // another criterion: make the virtual line pass the middle point of the
//    // and having the same orientation as the base line and see whether the
//    // end points are within 1-pixel away
//    ORTPoint mid= new ORTPoint((l.Start.Col+l.End.Col)/2,(l.Start.Row+l.End.Row)/2);
//    double d1 = GeometricUtil.PtLinePerpDistance(l.Start, mid, standard.Theta);
//    double d2 = GeometricUtil.PtLinePerpDistance(l.End, mid, standard.Theta);
//    if (d1 < 1 && d2 < 1) return true;
//    else return false;
  }

  /**
   * Calcualte the quality for making the lines parallel to the base line.  The
   * quality is simply the total length of those lines parallel to the base
   * line.
   * @param line
   * @param lines
   * @return
   */
  double parallelQuality(ORTLine line, Vector lines)
  {
    if (line == null || lines == null) return 0;

    double q=0;

    for (int i=0;i<lines.size();i++) {
      ORTLine l = (ORTLine)lines.elementAt(i);
      if (isParallel(l,line)) q += CLCUtil.lineWeight(l.Length);
    }
    return q;
  }

  /**
   * Return the lines in the given "lines" which are parallel to the base line
   * @param p
   * @param lines
   * @return
   */
  LineClusterSet paralleledLines(ORTLine line, LineClusterSet lines)
  {
      if (line==null || lines==null) return null;

      LineClusterSet paraL = lines.newInstanceWithSameProperties();
      paraL.m_baseLine = line;
      paraL.m_convergingPoint = null;

      Iterator i = lines.iterator ();
      while (i.hasNext()) {
          ORTLine l = (ORTLine)i.next();
          if (isParallel(l,line)) paraL.add(l);
      }
      return paraL;
  }

  /**
   * Filter a line cluster using perspective information.  The remained lines
   * are either parallel to each other or are converged to a single point.  The
   * algorithm only use the longest lines in the line cluster to generate the
   * possilbe parallel directions and possible converging points.  It gives
   * scores for each possible parallel directions and possible converging
   * points and the lines will be filtered by the one with the highest score.
   * @return the filtered line cluster
   */
  LineClusterSet perspectiveConsistentLines() {

    // construct the perspective x-axis and y-axis
    ORTLine base_line = getBaseLine(false);

    // construct the result
    // must after calling getBaseLine(false) so that the new cluster get the
    // base line and convergin point information copied.
    LineClusterSet result = newInstanceWithSameProperties();

    if (m_convergingPoint == null) {     // they are parallel
      result.addAll(paralleledLines(base_line, this));
    } else { // they are converging
      result.addAll(convergedLines(m_convergingPoint, this));
    }
    return result;
  }



}