package yi.iu.processor.clc;

import yi.iu.processor.*;

import yi.iu.processor.ort.*;
import yi.iu.ui.*;
import yi.util.io.*;
import yi.dp.Histogram;
import yi.iu.processor.filter.GaussianSmooth;

import java.util.*;
import java.awt.*;
import java.io.*;

/**
 * Line Cluster
 * @author Yi Li
 * @version 1.0
 * @deprecated it is replaced by LineClusterSet.  Aug 26, 2002.
 */
public class LineCluster implements java.io.Serializable
{
    public int color;      //mostly by color-index
    public int orientationLeft, orientationRight;   //the range of orientation

    static int MINTOLERANCE=50;
    public static double STANDARDLEN=15;
    public static double MAXWEIGHT=1.5;
    public static int MINCANNUM= 10;    //minum considered line


    public Vector lines= new Vector();

    public LineCluster() {}

    public LineCluster(int c, int ol, int or) {
        color=c;
        orientationLeft=ol;
        orientationRight=or;
    }

    public void insert(ORTLine l) {
        lines.addElement(l);
    }

    public boolean insertByCondition(ORTLine l, int c, int o) {
        //whether the color is the same?
        if (c!=color) return false;

        //whether the orienation is falling into the range
        if (orientationLeft<=orientationRight) {
            if (o>=orientationLeft&&o<=orientationRight) {
                lines.addElement(l);
                return true;
            }
        }
        else {
            if (o>=orientationLeft||o<=orientationRight) {
                lines.addElement(l);
                return true;
            }
        }
        return false;
    }

    public int getColor() {return color;}

    public int size() {return lines.size();}

    public double weightedSize(double standard, double maxW) {
        double sum=0;
        for (int i=0;i<lines.size();i++) {
            ORTLine l= (ORTLine)lines.elementAt(i);
            sum+=l.weightedLength(standard, maxW);
        }
        return sum;
    }

    public double weightedSize()
    {
        return weightedSize(STANDARDLEN,MAXWEIGHT);
    }

    public void removeAll()
    {
        lines.removeAllElements();
    }

    public ORTLine getLineAt(int i) {return (ORTLine)lines.elementAt(i);}

    public Vector refineByPerspectiveRelation()
    {
        int i;
        //combine the collinear lines
        //Vector combinedLines= combineCollinear(lines);

        //find the converge point
        //Vector convergedLines= getConverged(combinedLines);
        Vector convergedLines= getConverged(lines);
        lines=convergedLines;
        /*
        //show the virtualLine
        Dimension d= new Dimension(640,480);
        int[] lineImg= new int[d.width*d.height];
        for (i=0;i<lineImg.length;i++) lineImg[i]=0xff000000;
        for (i=0;i<convergedLines.size();i++) {
            ORTLine line= (ORTLine)convergedLines.elementAt(i);
            DrawUtil.ort2image(lineImg, d, line, 0xffffffff, 1);
        }
        (new DisplayFrame("line", lineImg, d)).show();
        */

        return convergedLines;
    }

    public Vector refinedBySpatialRelationRepeatly(double t)
    {
        int size1,size2,size3;
        do {
            size1= lines.size();
            refinedBySpatialRelation(lines,0.3);
            size2= lines.size();
            refinedBySpatialRelation_2(lines,0.6);
            size3= lines.size();
        } while (size1!=size3);
        return lines;
    }


    public Vector refinedBySpatialRelation(Vector lines, double t)
    {
        int i;

        if (lines.size()<=0) return lines;

        int[][] prjLines= projectLines(lines);


        if (_parallel!=null) {  //the lines are parallel lines
            //make a line perpendicular to the parallels
            ORTLine y= _parallel.makeNewLineByRotate90();
            y.MidPoint.Col=(y.Start.Col+y.End.Col)/2;
            y.MidPoint.Row=(y.Start.Row+y.End.Row)/2;

            //get all the intesectant points
            double[] pos= new double[lines.size()];
            ORTPoint intersect= new ORTPoint();
            for (i=0;i<lines.size();i++) {
                ORTLine l=(ORTLine)lines.elementAt(i);
                l.MidPoint.Col=(l.Start.Col+l.End.Col)/2;
                l.MidPoint.Row=(l.Start.Row+l.End.Row)/2;
                //not intersect
                double[] inter= GeometricUtil.PtLinePerpIntercept(l.MidPoint, y);
                intersect= new ORTPoint(inter[0],inter[1]);
                pos[i]= positionOnAxis(intersect, y);
            }

            //quantilize the position
            int[] qPos= new int[pos.length];
            for (i=0;i<pos.length;i++) qPos[i]= (int)Math.round(pos[i]);

            //get the range of the position
            int min=qPos[0], max=qPos[0];
            for (i=0;i<qPos.length;i++) {
                if (min>qPos[i]) min=qPos[i];
                if (max<qPos[i]) max=qPos[i];
            }

            //make the histogram [min,..,max]->[0,..max-min]
            int numBin=max-min+1;
            double[] h= new double[numBin];
            for (i=0;i<lines.size();i++) {
                ORTLine l=(ORTLine)lines.elementAt(i);
                int index= qPos[i]-min;
                //h[index]+= l.Length;
                h[index]+= l.weightedLength(STANDARDLEN, MAXWEIGHT)*STANDARDLEN;
            }

            //get the range
            int[] range= dominant(h, t);

            //int[] range= Histogram.findHighestPeak_discrete(h, 10, 1);
            int lr=range[0]+min, rr=range[1]+min;
            Vector newLines= new Vector();
            for (i=0;i<lines.size();i++) {
                if (qPos[i]<lr||qPos[i]>rr) continue;
                newLines.addElement(lines.elementAt(i));
            }
            this.lines=newLines;
            return newLines;
        }
        else if (_converge!=null){                  //the lines are converged lines
            ORTLine virtualLine= getVirtualLine(lines);

            //project the lines onto the vertical virtual line
            ORTLine y= virtualLine.makeNewLineByRotate90();

            //get all the intesectant points
            double[] pos= new double[lines.size()];
            ORTPoint intersect= new ORTPoint();
            for (i=0;i<lines.size();i++) {
                ORTLine l=(ORTLine)lines.elementAt(i);
                l.MidPoint.Col=(l.Start.Col+l.End.Col)/2;
                l.MidPoint.Row=(l.Start.Row+l.End.Row)/2;
                l= new ORTLine(l.MidPoint, _converge);
                //not intersect
                if (!GeometricUtil.getInterceptPoint(l, y, intersect)) {
                    lines.removeElementAt(i);
                    continue;
                }
                pos[i]= positionOnAxis(intersect, y);
            }

            //quantilize the position
            int[] qPos= new int[pos.length];
            for (i=0;i<pos.length;i++) qPos[i]= (int)Math.round(pos[i]);

            //get the range of the position
            int min=qPos[0], max=qPos[0];
            for (i=0;i<qPos.length;i++) {
                if (min>qPos[i]) min=qPos[i];
                if (max<qPos[i]) max=qPos[i];
            }

            //make the histogram [min,..,max]->[0,..max-min]
            int numBin=max-min+1;
            double[] h= new double[numBin];
            for (i=0;i<lines.size();i++) {
                ORTLine l=(ORTLine)lines.elementAt(i);
                int index= qPos[i]-min;
                h[index]+= l.Length;
            }

            //get the range
            int[] range= dominant(h, t);
            int lr=range[0]+min, rr=range[1]+min;
            Vector newLines= new Vector();
            for (i=0;i<lines.size();i++) {
                if (qPos[i]<lr||qPos[i]>rr) continue;
                newLines.addElement(lines.elementAt(i));
            }
            this.lines=newLines;
            return newLines;
        }
        return lines;
    }


    //split the line cluster according to vertical spatial relationship
    //change this one to the max line cluster after split
    //also return all the line clusters after split with this one at the index#0
    public LineCluster[] splitByVerSpatialRelation(double t)
    {
        int i,j;

        if (lines==null||lines.size()<=0) return null;

        int[][] prjLines= projectLines(lines);

        //get the y position
        int[] qPos= new int[prjLines.length];
        for (i=0;i<qPos.length;i++) qPos[i]= prjLines[i][2];

        //get the range of the position
        int min=qPos[0], max=qPos[0];
        for (i=0;i<qPos.length;i++) {
            if (min>qPos[i]) min=qPos[i];
            if (max<qPos[i]) max=qPos[i];
        }

        //make the histogram [min,..,max]->[0,..max-min]
        int numBin=max-min+1;
        double[] h= new double[numBin];
        for (i=0;i<lines.size();i++) {
            ORTLine l=(ORTLine)lines.elementAt(i);
            int index= qPos[i]-min;
            //h[index]+= l.Length;
            h[index]+= l.weightedLength(STANDARDLEN, MAXWEIGHT)*STANDARDLEN;
        }

        /*
        System.err.println("min="+min+", max="+max);
        double[] h1= new double[480];
        for (i=0;i<lines.size();i++) {
            ORTLine l=(ORTLine)lines.elementAt(i);
            int index= (qPos[i]-(-240));
            //h[index]+= l.Length;
            h1[index]+= l.weightedLength(STANDARDLEN, MAXWEIGHT);
        }
        OutputResult.outputResult("hist", h1, 1, h1.length);
        //*/

        //get the range, and don't remove any ranges
        Vector ranges=Histogram.suspensionBridgeClustering(h, t, 0);

        if (ranges == null || ranges.size()==0) {
            LineCluster[] newlcs={this};
            removeAll();
            return newlcs;
        }
        //assign the lines to the ranges
        LineCluster[] newlcs= new LineCluster[ranges.size()];
        for (i=0;i<newlcs.length;i++) {
            newlcs[i]= new LineCluster(color,orientationLeft,orientationRight);
        }

        //transform the ranges
        int[][] range= new int[ranges.size()][2];
        for (i=0;i<range.length;i++) {
            int[] r= (int[]) ranges.elementAt(i);
            range[i][0]=r[0]+min;
            range[i][1]=r[1]+min;
        }

        for (i=0;i<lines.size();i++) {
            for (j=0;j<range.length;j++) {
                if (qPos[i]>=range[j][0]&&qPos[i]<=range[j][1]) {
                    newlcs[j].insert((ORTLine)lines.elementAt(i));
                }
            }
        }
        /*
        int maxsize=0;
        int maxi=-1;
        for (i=0;i<newlcs.length;i++) {
            if (newlcs[i].size()>maxsize) {
                maxsize=newlcs[i].size();
                maxi=i;
            }
        }
        if (maxi>=0) {
            //get the max size line cluster
            lines= newlcs[maxi].lines;
            //move it the first one
            newlcs[maxi]= newlcs[0];
            newlcs[0]= this;
        }
        //no cluster at all
        else {
            removeAll();
            newlcs[0]= this;
        }
        */
        return newlcs;
    }

    public Vector refinedBySpatialRelation_2(Vector lines, double t)
    {
        int i;

        if (lines.size()<=0) return lines;

        if (_parallel==null &&_converge==null) return lines;

        ORTLine x;
        if (_parallel!=null) {  //the lines are parallel lines
            x= _parallel;
        }
        else {                  //the lines are converged lines
            x= getVirtualLine(lines);
        }


        //get all the projected points
        double[] pos1= new double[lines.size()];
        double[] pos2= new double[lines.size()];
        ORTPoint intersect= new ORTPoint();
        for (i=0;i<lines.size();i++) {
            ORTLine l=(ORTLine)lines.elementAt(i);

            double[] inter= GeometricUtil.PtLinePerpIntercept(l.Start, x);
            intersect= new ORTPoint(inter[0],inter[1]);
            double p1= positionOnAxis(intersect, x);

            inter= GeometricUtil.PtLinePerpIntercept(l.End, x);
            intersect= new ORTPoint(inter[0],inter[1]);
            double p2= positionOnAxis(intersect, x);

            if (p1<p2) {pos1[i]=p1;pos2[i]=p2;}
            else {pos1[i]=p2;pos2[i]=p1;}
        }

        //quantilize the position
        int[] qPos1= new int[pos1.length];
        int[] qPos2= new int[pos2.length];
        for (i=0;i<pos1.length;i++) {
            qPos1[i]= (int)Math.round(pos1[i]);
            qPos2[i]= (int)Math.round(pos2[i]);
        }

        //get the range of the position
        int min=qPos1[0], max=qPos2[0];
        for (i=0;i<qPos1.length;i++) {
            if (min>qPos1[i]) min=qPos1[i];
            if (max<qPos2[i]) max=qPos2[i];
        }

        //make the histogram [min,..,max]->[0,..max-min]
        int numBin=max-min+1;
        int[] h_begin= new int[numBin];
        int[] h_end= new int[numBin];
        for (i=0;i<lines.size();i++) {
            ORTLine l=(ORTLine)lines.elementAt(i);
            int index_begin= qPos1[i]-min;
            h_begin[index_begin]++;
            int index_end= qPos2[i]-min;
            h_end[index_end]++;
        }

        //get the range
        //tolerance uses the average length
        double lenSum=0;
        for (i=0;i<lines.size();i++) {
            ORTLine l=(ORTLine)lines.elementAt(i);
            lenSum+= l.Length;
        }
        double tolerance= lenSum/lines.size();
        tolerance= Math.max(tolerance, 12);
        tolerance= Math.min(tolerance, 100);
        //adjust the tolerance according to the angle of the virtual line
        double aa= x.Theta;
        if (aa<0) aa+= Math.PI;
        if (aa>Math.PI) aa-=Math.PI;
        if (aa>Math.PI/2) aa-= Math.PI/2;
        aa= Math.min(aa,Math.PI/2-aa);
        double ot=tolerance;
        tolerance/=Math.cos(aa);
        if (tolerance<MINTOLERANCE) tolerance=MINTOLERANCE;
        int[] range= dominant(h_begin, h_end, t, 2, tolerance);
        int lr=range[0]+min, rr=range[1]+min;
        Vector newLines= new Vector();
        for (i=0;i<lines.size();i++) {
            if ((qPos1[i]<lr||qPos1[i]>rr)&&(qPos2[i]<lr||qPos2[i]>rr)) continue;
            newLines.addElement(lines.elementAt(i));
        }
        this.lines=newLines;
        return newLines;
    }

    LineCluster[] splitByHorSpatialRelation(double t, double min_tolerance)
    {
        int i,j;

        if (lines==null||lines.size()<=0) return null;

        int[][] prjLines= projectLines(lines);

        int[] qPos1= new int[prjLines.length];
        int[] qPos2= new int[prjLines.length];
        for (i=0;i<qPos1.length;i++) {
            qPos1[i]= prjLines[i][0];
            qPos2[i]= prjLines[i][1];
        }

        //get the range of the position
        int min=qPos1[0], max=qPos2[0];
        for (i=0;i<qPos1.length;i++) {
            if (min>qPos1[i]) min=qPos1[i];
            if (max<qPos2[i]) max=qPos2[i];
        }

        //make the histogram [min,..,max]->[0,..max-min]
        int numBin=max-min+1;
        int[] h_begin= new int[numBin];
        int[] h_end= new int[numBin];
        for (i=0;i<lines.size();i++) {
            ORTLine l=(ORTLine)lines.elementAt(i);
            int index_begin= qPos1[i]-min;
            h_begin[index_begin]++;
            int index_end= qPos2[i]-min;
            h_end[index_end]++;
        }

        //get the range
        //tolerance uses the average length
        double lenSum=0;
        for (i=0;i<lines.size();i++) {
            ORTLine l=(ORTLine)lines.elementAt(i);
            lenSum+= l.Length;
        }
        double tolerance= lenSum/lines.size();
        tolerance= Math.max(tolerance, 12);
        tolerance= Math.min(tolerance, 100);
        //adjust the tolerance according to the angle of the virtual line
        ORTLine x;
        if (_parallel!=null) x= _parallel;
        else x= getVirtualLine(lines);

        double aa= x.Theta;
        if (aa<0) aa+= Math.PI;
        if (aa>Math.PI) aa-=Math.PI;
        if (aa>Math.PI/2) aa-= Math.PI/2;
        aa= Math.min(aa,Math.PI/2-aa);
        double ot=tolerance;
        tolerance/=Math.cos(aa);
        if (tolerance<min_tolerance) tolerance=min_tolerance;
        //int[] range= dominant(h_begin, h_end, t, 2, tolerance);
        //find the count of lines upon one position
        int[] density=new int[h_begin.length];
        int now=0;
        for (i=0;i<h_begin.length;i++) {
            now+=h_begin[i];
            if (i>0) now-=h_end[i-1];
            density[i]=now;
        }
/*
        int[] hh= new int[640];
        System.err.println("min="+min+",max="+max);
        for (i=0;i<density.length;i++) hh[i+min+220]=density[i];
        OutputResult.outputResult("hh", hh, 1, hh.length);
//*/
        //using tolerance of average length
        Vector ranges=Histogram.breakWithTolerance(density, tolerance, 0);
        if (ranges == null || ranges.size()==0) {
            LineCluster[] newlcs={this};
            removeAll();
            return newlcs;
        }
        //assign the lines to the ranges
        LineCluster[] newlcs= new LineCluster[ranges.size()];
        for (i=0;i<newlcs.length;i++) {
            newlcs[i]= new LineCluster(color,orientationLeft,orientationRight);
        }

        //transform the ranges
        int[][] range= new int[ranges.size()][2];
        for (i=0;i<range.length;i++) {
            int[] r= (int[]) ranges.elementAt(i);
            range[i][0]=r[0]+min;
            range[i][1]=r[1]+min;
        }

        for (i=0;i<lines.size();i++) {
            for (j=0;j<range.length;j++) {
                if ((qPos1[i]>=range[j][0]&&qPos1[i]<=range[j][1])||
                    (qPos2[i]>=range[j][0]&&qPos2[i]<=range[j][1])){
                    newlcs[j].insert((ORTLine)lines.elementAt(i));
                }
            }
        }
        /*
        int maxsize=0;
        int maxi=-1;
        for (i=0;i<newlcs.length;i++) {
            if (newlcs[i].size()>maxsize) {
                maxsize=newlcs[i].size();
                maxi=i;
            }
        }
        if (maxi>=0) {
            //get the max size line cluster
            lines= newlcs[maxi].lines;
            //move it the first one
            newlcs[maxi]= newlcs[0];
            newlcs[0]= this;
        }
        //no cluster at all
        else {
            removeAll();
            newlcs[0]= this;
        }
        */
        return newlcs;
    }

    LineCluster[] splitByHorSpatialRelation(double t,
        double min_tolerance, double Tbreak)
    {
        int i,j;

        if (lines==null||lines.size()<=0) return null;

        int[][] prjLines= projectLines(lines);

        int[] qPos1= new int[prjLines.length];
        int[] qPos2= new int[prjLines.length];
        for (i=0;i<qPos1.length;i++) {
            qPos1[i]= prjLines[i][0];
            qPos2[i]= prjLines[i][1];
        }

        //get the range of the position
        int min=qPos1[0], max=qPos2[0];
        for (i=0;i<qPos1.length;i++) {
            if (min>qPos1[i]) min=qPos1[i];
            if (max<qPos2[i]) max=qPos2[i];
        }

        //make the histogram [min,..,max]->[0,..max-min]
        int numBin=max-min+1;
        int[] h_begin= new int[numBin];
        int[] h_end= new int[numBin];
        for (i=0;i<lines.size();i++) {
            ORTLine l=(ORTLine)lines.elementAt(i);
            int index_begin= qPos1[i]-min;
            h_begin[index_begin]++;
            int index_end= qPos2[i]-min;
            h_end[index_end]++;
        }

        //get the range
        //tolerance uses the average length
        double lenSum=0;
        for (i=0;i<lines.size();i++) {
            ORTLine l=(ORTLine)lines.elementAt(i);
            lenSum+= l.Length;
        }
        double tolerance= lenSum/lines.size();
        tolerance= Math.max(tolerance, 12);
        tolerance= Math.min(tolerance, 100);
        //adjust the tolerance according to the angle of the virtual line
        ORTLine x;
        if (_parallel!=null) x= _parallel;
        else x= getVirtualLine(lines);

        double aa= x.Theta;
        if (aa<0) aa+= Math.PI;
        if (aa>Math.PI) aa-=Math.PI;
        if (aa>Math.PI/2) aa-= Math.PI/2;
        aa= Math.min(aa,Math.PI/2-aa);
        double ot=tolerance;
        tolerance/=Math.cos(aa);
        if (tolerance<min_tolerance) tolerance=min_tolerance;
        //int[] range= dominant(h_begin, h_end, t, 2, tolerance);
        //find the count of lines upon one position
        int[] density=new int[h_begin.length];
        int now=0;
        for (i=0;i<h_begin.length;i++) {
            now+=h_begin[i];
            if (i>0) now-=h_end[i-1];
            density[i]=now;
        }

        //using tolerance of average length
        //Vector ranges=Histogram.breakWithTolerance(density, tolerance, 0);
        Vector ranges=Histogram.breakWithTolerance(density, tolerance, 0, Tbreak);
        if (ranges == null || ranges.size()==0) {
            LineCluster[] newlcs={this};
            removeAll();
            return newlcs;
        }
        //assign the lines to the ranges
        LineCluster[] newlcs= new LineCluster[ranges.size()];
        for (i=0;i<newlcs.length;i++) {
            newlcs[i]= new LineCluster(color,orientationLeft,orientationRight);
        }

        //transform the ranges
        int[][] range= new int[ranges.size()][2];
        for (i=0;i<range.length;i++) {
            int[] r= (int[]) ranges.elementAt(i);
            range[i][0]=r[0]+min;
            range[i][1]=r[1]+min;
        }

        for (i=0;i<lines.size();i++) {
            for (j=0;j<range.length;j++) {
                if ((qPos1[i]>=range[j][0]&&qPos1[i]<=range[j][1])||
                    (qPos2[i]>=range[j][0]&&qPos2[i]<=range[j][1])){
                    newlcs[j].insert((ORTLine)lines.elementAt(i));
                }
            }
        }
        /*
        int maxsize=0;
        int maxi=-1;
        for (i=0;i<newlcs.length;i++) {
            if (newlcs[i].size()>maxsize) {
                maxsize=newlcs[i].size();
                maxi=i;
            }
        }
        if (maxi>=0) {
            //get the max size line cluster
            lines= newlcs[maxi].lines;
            //move it the first one
            newlcs[maxi]= newlcs[0];
            newlcs[0]= this;
        }
        //no cluster at all
        else {
            removeAll();
            newlcs[0]= this;
        }
        */
        return newlcs;
    }

    void verifyByHorOverlap(int Tonline)
    {
        int i,j;

        if (lines==null||lines.size()<=0) return;

        //get the average width of the length
        double average=0;
        for (i=0;i<lines.size();i++) average+= ((ORTLine)lines.elementAt(i)).Length;
        average/= lines.size();

        boolean[] verified= new boolean[lines.size()];
        //connect every two middle point
        for (i=0;i<lines.size()-1;i++) {
            ORTLine l1= (ORTLine)lines.elementAt(i);
            for (j=i+1;j<lines.size();j++) {
                ORTLine l2= (ORTLine)lines.elementAt(j);
                int count=0;
                for (int k=0;k<lines.size();k++) {
                    ORTLine l= (ORTLine)lines.elementAt(k);
                    double d= GeometricUtil.PtLinePerpDistance(l.MidPoint, l1.MidPoint, l2.MidPoint);
                    if (d<=l.Length/2) count++;
                }
                if (count>=Tonline) {
                    for (int k=0;k<lines.size();k++) {
                        ORTLine l= (ORTLine)lines.elementAt(k);
                        double d= GeometricUtil.PtLinePerpDistance(l.MidPoint, l1.MidPoint, l2.MidPoint);
                        if (d<=l.Length/2) verified[k]=true;
                    }
                }

            }
        }

        for (i=lines.size()-1;i>=0;i--) {
            if (!verified[i]) lines.removeElementAt(i);
        }

    }

    void verifyByHorOverlap_1(int Tonline)
    {
        int i,j;

        if (lines==null||lines.size()<=0) return;

        refineByPerspectiveRelation();
        int[][] prjLines= projectLines(lines);

        ORTPoint[] mid= new ORTPoint[prjLines.length];
        for (i=0;i<mid.length;i++)
            mid[i]=new ORTPoint((prjLines[i][0]+prjLines[i][1])/2.0, prjLines[i][2]);

        //get the average width of the length
        int _average=0;
        for (i=0;i<prjLines.length;i++) _average+= prjLines[i][1]-prjLines[i][0];
        double average= (double)_average/(prjLines.length);
        //if (average>10) average=10;

        //get the upper center and the bottom center
        int ux=0,uy=0,uc=0;
        int bx=0,by=0,bc=0;
        for (i=0;i<prjLines.length;i++) {
            if (prjLines[i][2]>0) {
                ux+=prjLines[i][0]+prjLines[i][1];
                uy+=prjLines[i][2];
                uc++;
            }
            else if (prjLines[i][2]<0) {
                bx+=prjLines[i][0]+prjLines[i][1];
                by+=prjLines[i][2];
                bc++;
            }
        }

        if (uc>0) {ux/=(2*uc);uy/=uc;}
        else {ux=0;uy=10;}
        if (bc>0) {bx/=(2*bc);by/=bc;}
        else {bx=0;by=-10;}

        double theta= ORTLine.LineSegTheta(ux, uy, bx, by);
        double Tdistance= average/2*Math.sin(theta);
        /*
        if (theta<Math.PI/6||theta>Math.PI*5/6) {
            lines.removeAllElements();
            return;
        }
        */
/*
        Dimension dm= new Dimension(400,400);
        int[] img= new int[dm.width*dm.height];
        for (i=0;i<img.length;i++) img[i]=0xffffffff;
        DrawUtil.ort2image(img, dm,
                new ORTLine(-120,0,120,0),0xff00ff00, 1);
        DrawUtil.ort2image(img, dm,
                new ORTLine(0,-100,0,100),0xff00ff00, 1);

        for (i=0;i<prjLines.length;i++) {
            DrawUtil.ort2image(img, dm,
                new ORTLine(prjLines[i][0], prjLines[i][2], prjLines[i][1], prjLines[i][2]),
                0xff000000, 1);
        }
        DrawUtil.ort2image(img, dm,
                new ORTLine(ux, uy, bx, by),
                0xff0000ff, 1);
        DrawUtil.drawMark(img, dm, ux, uy, 4, 0xffff0000);
        DrawUtil.drawMark(img, dm, bx, by, 4, 0xffff0000);
        (new DisplayFrame("theta", img, dm)).show();
//*/
        boolean[] verified= new boolean[lines.size()];
        int verfiedc=0;
        //connect every two middle point
        for (i=0;i<prjLines.length;i++) {
            int count=0;
            int length= prjLines[i][1]-prjLines[i][0];
            for (j=0;j<prjLines.length;j++) {
                double d= GeometricUtil.PtLinePerpDistance(
                            mid[j], mid[i], theta);
                int length2=prjLines[j][1]-prjLines[j][0];
                //if (d<=Tdistance) count++;
                //if (d<=(length2+1)/2*Math.sin(theta))
                //if (d<=(length2+1)/2*Math.sin(theta)
                //    && (Math.abs(length2-length)<3))
                if (d<=(length2+1)/2*Math.sin(theta)&&consistentLength(length,length2))
                    count++;
            }
            if (count>=Tonline) {
                verified[i]=true;
                verfiedc++;
            }
        }
        if (false) System.err.println("verified "+verfiedc+ "/"+verified.length);
        for (i=lines.size()-1;i>=0;i--) {
            if (!verified[i]) lines.removeElementAt(i);
        }
/*        if (verfiedc<verified.length/2) lines.removeAllElements();
        else {
        }
//*/
    }
    boolean consistentLength(int l1, int l2) {
        return (l2>=l1*3/4&&l2<=l1*4/3);
    }
    public Vector splitBySpatialRelation(double t1, double t2, double min_tolerance,
        double Tbreak)
    {
        LineCluster[] newlcs= splitByVerSpatialRelation(t1);
        if (newlcs==null) return new Vector();
        Vector newlcs2= new Vector();
        for (int i=0;i<newlcs.length;i++) {
            LineCluster nlc= (LineCluster) newlcs[i];
            LineCluster[] rst= nlc.splitByHorSpatialRelation(t2, min_tolerance, Tbreak);
            for (int j=0;j<rst.length;j++) newlcs2.addElement(rst[j]);
        }
        return newlcs2;
    }

    public Vector splitBySpatialRelation(double t1, double t2, double min_tolerance)
    {
        LineCluster[] newlcs= splitByVerSpatialRelation(t1);
        //ConsistentLineCluster.drawLineClusters("vertical", new Dimension(640,428), newlcs, -1);

        if (newlcs==null) return new Vector();
        Vector newlcs2= new Vector();
        for (int i=0;i<newlcs.length;i++) {
            LineCluster nlc= (LineCluster) newlcs[i];
            LineCluster[] rst= nlc.splitByHorSpatialRelation(t2, min_tolerance);
            for (int j=0;j<rst.length;j++) newlcs2.addElement(rst[j]);
        }
        return newlcs2;
    }

    public Vector splitBySpatialRelation(double t1, double t2)
    {
        return splitBySpatialRelation(t1, t2, MINTOLERANCE);
    }
    ORTLine _parallel=null;
    ORTPoint _converge=null;

    boolean in(ORTPoint p, double x1, double y1, double x2, double y2) {
        if (p.Col<x1||p.Col>x2) return false;
        if (p.Row<y1||p.Row>y2) return false;
        return true;
    }
    /*
    //find the dominant part of a histogram
    int[] dominant(double[] h, double Tbreak, double Tdensity)
    {
        int i;

        //the length must no less than 3, so that use break algorithm
        if (h.length<3) {
            int[] r={0,h.length};
            return r;
        }

        //find the bins with bigger values
        double sumV=0;
        int Count=0;
        for (i=0;i<h.length;i++) {
            if (h[i]>0) {
                sumV+= h[i];
                Count++;
            }
        }
        double ThresholdV= sumV/Count*Tdensity;

        int leftB=0; while (h[leftB]<ThresholdV) leftB++;
        int rightB=h.length-1; while (h[rightB]<ThresholdV) rightB--;


        //average value of the bins
        double sum=0;
        for (i=0;i<h.length;i++) sum+= h[i];
        double average=sum/h.length;

        //find the possible break
        Vector breaks= new Vector();
        for (int l=1;l<h.length-1;l++) { //left max:length-2
            if (l>=leftB&&l<=rightB) {
                l=rightB+1; continue;
            }
            if (h[l]>0) continue;       //find a break - left
            int r=l;
            while (r<h.length-2&&h[r+1]==0) r++;    //max:length-2
            //now find a break from l..r

            //find the sum of the bridge of the break;
            double bridgeSum= h[l-1]+h[r+1];

            //if the average in the break is too small, break the h
            if (bridgeSum / (r-l+1) < average*Tbreak) {
                System.err.println(" break#"+ breaks.size()+
                    ": "+ bridgeSum / (r-l+1) / average);
                int[] b= {l,r};
                breaks.addElement(b);
            }
            l=r;
        }

        //find the domiant
        if (breaks.size()==0) {
            int[] r={0,h.length};
            return r;
        }

        //get the ranges
        int[][] ranges= new int[breaks.size()+1][];
        int l=0;
        for (i=0;i<breaks.size();i++) {
            int[] b= (int[]) breaks.elementAt(i);
            int[] range= {l,b[0]-1};
            ranges[i]= range;
            l=b[1]+1;
        }
        int[] range= {l,h.length-1};
        ranges[breaks.size()]= range;

        //calculate the sum of the ranges
        double[] sumRange= new double[ranges.length];
        for (i=0;i<ranges.length;i++) {
            range= ranges[i];
            for (int j=range[0];j<=range[1];j++) {
                sumRange[i]+=h[j];
            }
        }

        //find the range with the max sum
        double max=sumRange[0];
        int max_i=0;
        for (i=1;i<sumRange.length;i++) {
            if (sumRange[i]>max) {
                max=sumRange[i];
                max_i=i;
            }
        }
        return ranges[max_i];

    }
    */
    //find the dominant part of a histogram
    int[] dominant(double[] h, double Tbreak)
    {
        int i;

        Vector test=Histogram.suspensionBridgeClustering(h, Tbreak, 0.5);
        if (test.size()>0)
            return (int[]) test.elementAt(0);
        else {
            int[] r={1,0};
            return r;
        }
/*
        //the length must no less than 3, so that use break algorithm
        if (h.length<3) {
            int[] r={0,h.length};
            return r;
        }

        //average value of the bins
        double sum=0;
        int count=0;
        for (i=0;i<h.length;i++) {
            sum+= h[i];
            if (h[i]>0) count++;
        }
        double average1=sum/h.length;
        double average2= sum/count;

        //find the optimal Threshold
        //double threshold= average1*Tbreak;
        double threshold= average1*Tbreak;

        //distribute the bins
        int[] begin= new int[h.length];
        int[] end= new int[h.length];

        for (i=0;i<h.length;i++) {
            if (h[i]>0) {
                int distributeLen=(int)Math.ceil(h[i]/threshold);
                int left_arm= (distributeLen-1)/2;
                int right_arm= distributeLen-1-left_arm;
                int left=Math.max(0,i-left_arm);
                int right=Math.min(h.length-1,i+right_arm);
                begin[left]++;
                end[right]++;
            }
        }

        //re-calculate the distributed histogram
        int now=0;
        int[] dh= new int[h.length];
        for (i=0;i<h.length;i++) {
            now+=begin[i];
            if (i>0) now-=end[i-1];
            dh[i]=now;
        }

        System.err.println("average="+average1);
        OutputResult.outputResult("bridge_column", h);
        OutputResult.outputResult("bridge_shape", dh);

        //find the possible break
        Vector breaks= new Vector();
        for (int l=1;l<h.length-1;l++) { //left max:length-2
            if (dh[l]>0) continue;       //find a break - left
            int r=l;
            while (r<dh.length-2&&dh[r+1]==0) r++;    //max:length-2
            //now find a break from l..r

            int[] b= {l,r};
            breaks.addElement(b);
            l=r;
        }

        //find the domiant
        if (breaks.size()==0) {
            int[] r={0,h.length};
            return r;
        }

        //get the ranges
        int[][] ranges= new int[breaks.size()+1][];
        int l=0;
        for (i=0;i<breaks.size();i++) {
            int[] b= (int[]) breaks.elementAt(i);
            int[] range= {l,b[0]-1};
            ranges[i]= range;
            l=b[1]+1;
        }
        int[] range= {l,h.length-1};
        ranges[breaks.size()]= range;

        //calculate the sum of the ranges
        double[] sumRange= new double[ranges.length];
        for (i=0;i<ranges.length;i++) {
            range= ranges[i];
            for (int j=range[0];j<=range[1];j++) {
                sumRange[i]+=h[j];
            }
        }

        //find the range with the max sum
        double max=sumRange[0];
        int max_i=0;
        for (i=1;i<sumRange.length;i++) {
            if (sumRange[i]>max) {
                max=sumRange[i];
                max_i=i;
            }
        }
        return ranges[max_i];
*/
    }

    int[] dominant(int[] begin, int[] end, double Tboundary, double Tdensity, double tolerance)
    {
        //find the count of lines upon one position
        int[] density=new int[begin.length];
        int now=0;
        for (int i=0;i<begin.length;i++) {
            now+=begin[i];
            if (i>0) now-=end[i-1];
            density[i]=now;
        }

        //using tolerance of average length

        Vector test=Histogram.breakWithTolerance(density, tolerance, 0.5);
        if (test.size()>0)
            return (int[]) test.elementAt(0);
        else {
            int[] r={1,0};
            return r;
        }
/*
        //find the average
        int sum=0;
        int count=0;
        for (int i=0;i<begin.length;i++) {
            if (density[i]>0) {
                sum+=density[i];
                count++;
            }
        }
        double average= (double)sum/(double)count;
        if (average<Tdensity) {
            int[] range={1,-1};    //make the range empty
            return range;
        }

        //get the positions which satisfy the requirement
        boolean[] satisfied= new boolean[begin.length];
        for (int i=0;i<begin.length;i++) {
            if (density[i]>average*Tboundary) satisfied[i]=true;
            else satisfied[i]=false;
        }

        //get the left and rigth boundary
        int left=0;
        while (!satisfied[left]) left++;

        int right= begin.length-1;
        while (!satisfied[right]) right--;

        int[] range={left,right};
        return range;
*/
    }

    Vector getConverged(Vector lines)
    {
        int i;
        //sort the lines according to the length
        for (i=0;i<lines.size();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 if the length less than the standard
            if (element1.Length<STANDARDLEN&&i>=MINCANNUM) break;
            if (i>=2*MINCANNUM) break;
        }

        int useNum=i;   //only use the first i, the i-th is not usable

        //get all the possible converged points (candidates)
        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
        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;
            }
        }

        if (bestparaQual==0&&bestConvQual==0) return (new Vector());
        if (bestparaQual>bestConvQual) {
            _parallel= (ORTLine)lines.elementAt(bestparaIndex);
            return paralleledLines((ORTLine)lines.elementAt(bestparaIndex),lines);
        }
        _converge= convergedPts[bestConvIndex];
        return convergedLines(convergedPts[bestConvIndex],lines);
    }

    boolean isConverge(ORTLine l, ORTPoint p)
    {
        double d1= distance(p,l.Start);
        double d2= 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;}
        double d = GeometricUtil.PtLinePerpDistance(nearp, p, farp);
        //if (d<l.LengthPerpVar/2) q+=l.weightedLength(STANDLEN, MAXWEIGHT);
        if (d<=1) return true;
        return false;
        /*
        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 total length of those lines acrossing the p
    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+=l.weightedLength(STANDARDLEN, MAXWEIGHT);
        }
        return q;
    }

    Vector convergedLines(ORTPoint p, Vector lines)
    {
        if (p==null||lines==null) return null;

        Vector convL= new Vector();
        for (int i=0;i<lines.size();i++) {
            ORTLine l = (ORTLine)lines.elementAt(i);
            if (isConverge(l,p))  convL.addElement(l);
        }

        return convL;
    }

    boolean isParallel(ORTLine l, ORTLine standard) {
        double d = GeometricUtil.PtLinePerpDistance(l.Start, l.End, standard.Theta);
        //if (d<l.LengthPerpVar/2) q+=l.Length;
        if (d<=1) return true;
        else return false;
        /*
        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;
        */
    }

    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+=l.weightedLength(STANDARDLEN, MAXWEIGHT);
        }
        return q;
    }

    Vector paralleledLines(ORTLine line, Vector lines)
    {
        if (line==null||lines==null) return null;

        Vector paraL= new Vector();

        for (int i=0;i<lines.size();i++) {
            ORTLine l = (ORTLine)lines.elementAt(i);
            if (isParallel(l,line)) paraL.addElement(l);
        }
        return paraL;
    }

    Vector combineCollinear(Vector lines)
    {
        int i;
        ORTLine l;
        //get the virtual line
        ORTLine virtualLine= getVirtualLine(lines);

        //project the lines onto the vertical virtual line
        ORTLine verticalVL= virtualLine.makeNewLineByRotate90();

        //show the virtualLine
        Dimension d= new Dimension(640,480);
        int[] lineImg= new int[d.width*d.height];
        for (i=0;i<lineImg.length;i++) lineImg[i]=0xff000000;
        for (i=0;i<lines.size();i++) {
            ORTLine line= (ORTLine)lines.elementAt(i);
            DrawUtil.ort2image(lineImg, d, line, 0xffffffff, 1);
        }
        DrawUtil.ort2image(lineImg, d, virtualLine, 0xffff0000, 2);
        DrawUtil.ort2image(lineImg, d, verticalVL, 0xff00ff00, 2);
        (new DisplayFrame("line", lineImg, d)).show();

        double[] pos= new double[lines.size()];
        ORTPoint intersect= new ORTPoint();
        for (i=0;i<lines.size();i++) {
            l=(ORTLine)lines.elementAt(i);
            //not intersect
            if (!GeometricUtil.getInterceptPoint(l, verticalVL, intersect)) {
                lines.removeElementAt(i);
                continue;
            }
            pos[i]= positionOnYAxis(intersect.Col, intersect.Row,
                verticalVL.MidPoint.Col, verticalVL.MidPoint.Row, verticalVL.Theta);

        }

        //sort the lines according the insectant point with y axis
        for (i=0;i<lines.size()-1;i++) {
            ORTLine element1 = (ORTLine)lines.elementAt(i);
            for (int j=i+1;j<lines.size();j++) {
                if (pos[i] > pos[j]) {
                    ORTLine element2 = (ORTLine)lines.elementAt(j);
                    lines.setElementAt(element1, j);
                    element1=element2;
                    double tmp= pos[j];
                    pos[j]=pos[i];
                    pos[i]=tmp;
                }
            }
            lines.setElementAt(element1, i);
        }

        //make the collinears
        double Tpos = Math.sqrt(2.0);

        Vector collinears= new Vector();
        for (i=0;i<lines.size();i++) {
            ORTLine element1 = (ORTLine)lines.elementAt(i);
            for (int j=i+1;j<lines.size();j++) {
                ORTLine element2 = (ORTLine)lines.elementAt(j);
                //the position and the theta must be close
                /*
                if (Math.abs(pos[j]-pos[i])>Tpos) {
                    i=j-1; break;
                }
                double Ttheta= 2*Tpos/element1.Length+2*Tpos/element2.Length;
                if (Math.abs(element1.Theta-element2.Theta)>Ttheta) {
                    i=j-1; break;
                }
                */
                //make collinear
                ORTLine cl=getCollinearLine(element1, element2);
                if (cl==null) {
                    i=j-1;break;
                }
                cl.Length= element1.Length+element2.Length; //the length should be strange
                element1= cl;
            }
            collinears.addElement(element1);
        }

        //show the collinear lines
        int[] clineImg= new int[d.width*d.height];
        for (i=0;i<clineImg.length;i++) clineImg[i]=0xff000000;
        for (i=0;i<collinears.size();i++) {
            ORTLine line= (ORTLine)collinears.elementAt(i);
            DrawUtil.ort2image(clineImg, d, line, 0xffffffff, 1);
        }
        DrawUtil.ort2image(clineImg, d, virtualLine, 0xffff0000, 2);
        DrawUtil.ort2image(clineImg, d, verticalVL, 0xff00ff00, 2);
        (new DisplayFrame("line", clineImg, d)).show();


        return collinears;

    }

    ORTPoint getOrigin(Vector ls) {
                int i, j;
        ORTLine l;

        int num=ls.size();

        //the sum of the length
        double sumLength= 0;
        for (i=0;i<num;i++) {
            l= (ORTLine) ls.elementAt(i);
            sumLength+= l.Length;
        }
        double weightedSum=weightedSize();

        //the mid point of the virtual line
        double vlPtCol = 0, vlPtRow = 0;
        for (i=0;i<num;i++) {
            l = (ORTLine) ls.elementAt(i);
            //vlPtCol += (l.Start.Col+l.End.Col)/2 * l.Length;
            //vlPtRow += (l.Start.Row+l.End.Row)/2 * l.Length;
            vlPtCol += (l.Start.Col+l.End.Col)/2 * l.weightedLength(STANDARDLEN, MAXWEIGHT);
            vlPtRow += (l.Start.Row+l.End.Row)/2 * l.weightedLength(STANDARDLEN, MAXWEIGHT);
        }
        //vlPtCol /= sumLength;
        //vlPtRow /= sumLength;
        vlPtCol /= weightedSum;
        vlPtRow /= weightedSum;

        return new ORTPoint(vlPtCol,vlPtRow);

    }


    ORTLine getVirtualLine(Vector ls)
    {
        int i, j;
        ORTLine l;

        int num=ls.size();

        //the sum of the length
        double sumLength= 0;
        for (i=0;i<num;i++) {
            l= (ORTLine) ls.elementAt(i);
            sumLength+= l.Length;
        }
        double weightedSum=weightedSize();

        //the mid point of the virtual line
        double vlPtCol = 0, vlPtRow = 0;
        for (i=0;i<num;i++) {
            l = (ORTLine) ls.elementAt(i);
            //vlPtCol += (l.Start.Col+l.End.Col)/2 * l.Length;
            //vlPtRow += (l.Start.Row+l.End.Row)/2 * l.Length;
            vlPtCol += (l.Start.Col+l.End.Col)/2 * l.weightedLength(STANDARDLEN, MAXWEIGHT);
            vlPtRow += (l.Start.Row+l.End.Row)/2 * l.weightedLength(STANDARDLEN, MAXWEIGHT);
        }
        //vlPtCol /= sumLength;
        //vlPtRow /= sumLength;
        vlPtCol /= weightedSum;
        vlPtRow /= weightedSum;

        //Find the mean orientation of the virtual line weighted by the
        //  line lengths, (could also inversely weight by the theta variances)
        //First make sure that there are no such situation: some lines are around 0 radian
        //  and some are around PI radian. (in this case, the mean should be  0, but will be
        //  PI/2 if not deal with well)
        double vlTheta=0;
        if (orientationLeft<orientationRight) {     //nothing to worry about
            for (i = 0; i < num; i++) {
                l = (ORTLine) ls.elementAt(i);
                //vlTheta += l.Theta* l.Length;
                vlTheta += l.Theta* l.weightedLength(STANDARDLEN, MAXWEIGHT);
            }
        }
        else {
            for (i = 0; i < num; i++) {
                l = (ORTLine) ls.elementAt(i);
                double tempTheta = l.Theta;
                if (tempTheta >= (orientationRight)*Math.PI/180) tempTheta -= Math.PI; //make it to the negative
                vlTheta += tempTheta* l.weightedLength(STANDARDLEN, MAXWEIGHT);
            }
        }
        vlTheta /= weightedSum;
        //vlTheta /= sumLength;
        if (vlTheta < 0) vlTheta += Math.PI;
        if (vlTheta==Math.PI) vlTheta=0;

        // Find other parameters associated with the virtual line
        double vlRowIntercept = 0, vlColIntercept = 0;
        if (vlTheta < 0.001) { 		/* If vl is horizontal */
            vlRowIntercept = vlPtRow;
        }

        if (GeometricUtil.MACCompareWithPIBY2(vlTheta))		/* If vl is vertical */
            vlColIntercept = vlPtCol;

        /* So we have to work things out */
        if ( !GeometricUtil.MACCompareWithPIBY2(vlTheta) && (vlTheta) >= 0.001) {
            double Grad = Math.tan(vlTheta);
            vlRowIntercept = vlPtRow -  ( Grad * vlPtCol );
            vlColIntercept = -vlRowIntercept/Grad;

        }


        //Find intercept point between perp. dropped from the end points of the
        //lines onto the virtual line
        double interceptCol, interceptRow;
        double position;
        double minIntercept = 1000, maxIntercept = -1000;       //find the end points of the virtual line
        double vlStartCol=0, vlStartRow=0, vlEndCol=0, vlEndRow=0;
        for (i = 0; i < num; i++) {
            l = (ORTLine) ls.elementAt(i);
            double[] interceptTmp= GeometricUtil.PtLinePerpIntercept(
                l.Start.Col, l.Start.Row, vlColIntercept, vlRowIntercept, vlTheta);
            interceptCol = interceptTmp[0];
            interceptRow = interceptTmp[1];

            //find out the position of the projected point on the virtual line
            position = positionOnXAxis (
                interceptCol, interceptRow, vlPtCol, vlPtRow, vlTheta);
            if (position > maxIntercept ) {
                maxIntercept = position;
                vlEndCol = interceptCol;
                vlEndRow = interceptRow;
            }
            if (position < minIntercept ) {
                minIntercept = position;
                vlStartCol = interceptCol;
                vlStartRow = interceptRow;
            }

            interceptTmp= GeometricUtil.PtLinePerpIntercept(
                l.End.Col, l.End.Row, vlColIntercept, vlRowIntercept, vlTheta);
            interceptCol = interceptTmp[0];
            interceptRow = interceptTmp[1];

            //find out the position of the projected point on the virtual line
            position = positionOnXAxis (
                interceptCol, interceptRow, vlPtCol, vlPtRow, vlTheta);
            if (position > maxIntercept ) {
                maxIntercept = position;
                vlEndCol = interceptCol;
                vlEndRow = interceptRow;
            }
            if (position < minIntercept ) {
                minIntercept = position;
                vlStartCol = interceptCol;
                vlStartRow = interceptRow;
            }
        }

        ORTLine virtualLine= new ORTLine();
        virtualLine.Start.Col = vlStartCol;
        virtualLine.Start.Row = vlStartRow;
        virtualLine.End.Col = vlEndCol;
        virtualLine.End.Row = vlEndRow;
        virtualLine.MidPoint.Col = vlPtCol;
        virtualLine.MidPoint.Row = vlPtRow;
            double dx = vlStartCol-vlEndCol, dy = vlStartRow-vlEndRow;
            virtualLine.Length = Math.sqrt(dx*dx+dy*dy);
            virtualLine.Theta = vlTheta;
            virtualLine.LengthParlVar = 2.0*ORTLine._LengthParlVar;
            virtualLine.LengthPerpVar  = ORTLine._LengthPerpVar;


            return virtualLine;
    }


    ORTLine getCollinearLine(ORTLine l1, ORTLine l2)
    {
        Vector vcl= new Vector(2);
        vcl.addElement(l1);
        vcl.addElement(l2);
        ORTLine vl= getVirtualLine(vcl);

        double vlLength= distance(vl.Start.Col, vl.Start.Row,
                            vl.End.Col, vl.End.Row);
        double l1Length= distance(l1.Start.Col, l1.Start.Row,
                            l1.End.Col, l1.End.Row);
        double l2Length= distance(l2.Start.Col, l2.Start.Row,
                            l2.End.Col, l2.End.Row);

        //Significant overlap
        if ( vlLength <=
            l1Length + l2Length - (l1.LengthParlVar + l2.LengthParlVar))
            return null;
        /*
        So now we check if the lines are collinear or non-overlapping parallel
        based on how far the VL Col and Row are from the line segments. We first
        compute some required parameters, and then we check the VLPtCol etc..

        */

        double l1ColIntercept=GeometricUtil.LineSegColIntercept(
                    l1.Start.Col, l1.Start.Row, l1.End.Col, l1.End.Row);

        double l2ColIntercept=GeometricUtil.LineSegColIntercept(
                    l2.Start.Col, l2.Start.Row, l2.End.Col, l2.End.Row);

        double l1RowIntercept=GeometricUtil.LineSegRowIntercept(
                    l1.Start.Col, l1.Start.Row, l1.End.Col, l1.End.Row);

        double l2RowIntercept=GeometricUtil.LineSegRowIntercept(
                    l2.Start.Col, l2.Start.Row, l2.End.Col, l2.End.Row);

        double vlMidCol= vl.MidPoint.Col;
        double vlMidRow= vl.MidPoint.Row;

        double d1 = GeometricUtil.PtLinePerpDistance(
                vlMidCol, vlMidRow, l1ColIntercept, l1RowIntercept, l1.Theta);

        double d2 = GeometricUtil.PtLinePerpDistance(
                vlMidCol, vlMidRow, l2ColIntercept, l2RowIntercept, l2.Theta);

            if (d1 > l1.LengthPerpVar || d2 > l2.LengthPerpVar) return null;

        return vl;
    }

    //The original point of the axis is at (axisCol, axisRow) and the orientation of axis
    //axisTheta [0,180).
    //Given a point (col,row) on the axis, return the x-coordinate on the axis
    double positionOnXAxis (double col, double row,
        double axisCol, double axisRow, double axisTheta)
    {
        if (axisTheta<0||axisTheta>=Math.PI) {
            System.err.println("wrong argument in positionOnXAxis: "+axisTheta);
            return 0.0;
        }
        double pos = distance(col,row,axisCol,axisRow);

        //if the point is on the negative direction
        if (axisRow>row) pos=-pos;
        else if (axisRow==row && axisCol>col) pos=-pos;
        return pos;
    }

    //The original point of the axis is at (axisCol, axisRow) and the orientation of axis
    //axisTheta [90,270).
    //Given a point (col,row) on the axis, return the y-coordinate on the axis
    double positionOnYAxis (double col, double row,
        double axisCol, double axisRow, double axisTheta)
    {
        if (axisTheta<Math.PI/2) axisTheta+=Math.PI;
        if (axisTheta<Math.PI/2||axisTheta>=Math.PI*3/2) {
            System.err.println("wrong argument in positionOnYAxis: "+axisTheta);
            return 0.0;
        }

        double pos = distance(col,row,axisCol,axisRow);

        //if the point is on the negative direction
        if (axisCol<col) pos=-pos;
        else if (axisCol==col && axisRow>row) pos=-pos;
        return pos;
    }

    //make the axis from the start to end
    //!!the midpoint must has been set
    double positionOnAxis (ORTPoint p, ORTLine l)
    {
        double d= distance (p, l.MidPoint);
        if (l.Start.Col!=l.MidPoint.Col) {  //not vertical
            if (l.Start.Col>l.MidPoint.Col) {
                if (p.Col>l.MidPoint.Col) return -d;
                else return d;
            }
            else {
                if (p.Col>l.MidPoint.Col) return d;
                else return -d;
            }
        }
        else {                               //vertical
            if (l.Start.Row>l.MidPoint.Row) {
                if (p.Row>l.MidPoint.Row) return -d;
                else return d;
            }
            else {
                if (p.Row>l.MidPoint.Row) return d;
                else return -d;
            }
        }

    }

    double distance(double x1, double y1, double x2, double y2) {
        double dx=x1-x2, dy=y1-y2;
        return Math.sqrt(dx*dx+dy*dy);
    }

    double distance(ORTPoint p1, ORTPoint p2) {
        double dx=p1.Col-p2.Col, dy=p1.Row-p2.Row;
        return Math.sqrt(dx*dx+dy*dy);
    }


    //project the lines to a better coordinate according to its feature
    //if parallel
    //else converge
    //return the coordinates of the new lines [x1,x2,y], in other words, from (x1,y)->(x2,y)
    int[][] projectLines(Vector lines)
    {

        int i;
        if (lines==null||lines.size()<=0) return null;

        int[][] prjLines= new int[lines.size()][3];

        double[] pos= new double[lines.size()];
        ORTLine y= null;
        if (_parallel!=null) {  //the lines are parallel lines
            ORTPoint p= getOrigin(lines);
            double t= _parallel.Theta;
            _parallel= new ORTLine(p.Col+100*Math.cos(t) , p.Col+100*Math.sin(t),
                p.Col-100*Math.cos(t) , p.Col-100*Math.sin(t));


            //make a line perpendicular to the parallels
            y= _parallel.makeNewLineByRotate90();
            y.MidPoint.Col=(y.Start.Col+y.End.Col)/2;
            y.MidPoint.Row=(y.Start.Row+y.End.Row)/2;

            //get all the intesectant points
            ORTPoint intersect= new ORTPoint();
            for (i=0;i<lines.size();i++) {
                ORTLine l=(ORTLine)lines.elementAt(i);
                l.MidPoint.Col=(l.Start.Col+l.End.Col)/2;
                l.MidPoint.Row=(l.Start.Row+l.End.Row)/2;
                //not intersect
                double[] inter= GeometricUtil.PtLinePerpIntercept(l.MidPoint, y);
                intersect= new ORTPoint(inter[0],inter[1]);
                pos[i]= positionOnAxis(intersect, y);
            }
        }

        else if (_converge!=null){                  //the lines are converged lines
            ORTLine virtualLine= getVirtualLine(lines);

            //project the lines onto the vertical virtual line
            y= virtualLine.makeNewLineByRotate90();

            //get all the intesectant points
            ORTPoint intersect= new ORTPoint();
            for (i=0;i<lines.size();i++) {
                ORTLine l=(ORTLine)lines.elementAt(i);
                l.MidPoint.Col=(l.Start.Col+l.End.Col)/2;
                l.MidPoint.Row=(l.Start.Row+l.End.Row)/2;
                l= new ORTLine(l.MidPoint, _converge);
                //not intersect
                if (!GeometricUtil.getInterceptPoint(l, y, intersect)) {
                    System.err.println("the converged line not intersect with y");
                    pos[i]=0;
                    continue;
                }
                pos[i]= positionOnAxis(intersect, y);
            }
        }

        //quantilize the position
        for (i=0;i<pos.length;i++) prjLines[i][2]= (int)Math.round(pos[i]);

        ORTLine x;
        if (_parallel!=null) {  //the lines are parallel lines
            x= _parallel;
        }
        else {                  //the lines are converged lines
            x= getVirtualLine(lines);
        }

        //get all the projected points
        double[] pos1= new double[lines.size()];
        double[] pos2= new double[lines.size()];
        ORTPoint intersect= new ORTPoint();
        for (i=0;i<lines.size();i++) {
            ORTLine l=(ORTLine)lines.elementAt(i);

            double[] inter= GeometricUtil.PtLinePerpIntercept(l.Start, x);
            intersect= new ORTPoint(inter[0],inter[1]);
            double p1= positionOnAxis(intersect, x);

            inter= GeometricUtil.PtLinePerpIntercept(l.End, x);
            intersect= new ORTPoint(inter[0],inter[1]);
            double p2= positionOnAxis(intersect, x);

            if (p1<p2) {pos1[i]=p1;pos2[i]=p2;}
            else {pos1[i]=p2;pos2[i]=p1;}
        }

        //quantilize the position
        for (i=0;i<pos1.length;i++) {
            prjLines[i][0]= (int)Math.round(pos1[i]);
            prjLines[i][1]= (int)Math.round(pos2[i]);
        }



        return prjLines;
    }

    public Vector refinedBySpatialRelation_test(Vector lines)
    {
        int i;

        if (lines==null||lines.size()<=0) return lines;

        int[][] prjLines= projectLines(lines);
        Vector newLines= new Vector();

        for (i=0;i<prjLines.length;i++) {
            ORTLine l= new ORTLine(prjLines[i][0], prjLines[i][2], prjLines[i][1], prjLines[i][2]);
            newLines.addElement(l);
        }

        //find the weighted center point
        int sumx=0, sumy=0, suml=0;
        for (i=0;i<prjLines.length;i++) {
            int length= prjLines[i][1]-prjLines[i][0];
            sumx+= (prjLines[i][0]+prjLines[i][1])*length;
            sumy+= prjLines[i][2]*length;
            suml+= length;
        }
        sumx/=2;

        int centerX= sumx/suml;
        int centerY= sumy/suml;

        //find the farest distance from a point to the center
        int maxD=0;
        for (i=0;i<prjLines.length;i++) {
            int d= distanceOnCircle(centerX, centerY, prjLines[i][0], prjLines[i][2]);
            if (d>maxD) maxD=d;
            d= distanceOnCircle(centerX, centerY, prjLines[i][1], prjLines[i][2]);
            if (d>maxD) maxD=d;
        }

        //make a histogram for the distance
        int[] h= new int[maxD+1];
        for (i=0;i<prjLines.length;i++) {
            int d= distanceOnCircle(centerX, centerY, (prjLines[i][0]+prjLines[i][1])/2, prjLines[i][2]);
            if (d>maxD) {
                System.err.println("d is greater than maxD");
                d=0;
            }
            h[d]+= prjLines[i][1]-prjLines[i][0];
        }

        return newLines;
    }

    int distanceOnCircle(int x1, int y1, int x2, int y2)
    {
        return (int)(Math.max(Math.abs(x1-x2), Math.abs(y1-y2)));
    }

    public boolean closeToVertical() {
        ORTLine virtualLine= getVirtualLine(lines);
        double Theta= virtualLine.Theta;
        if (Theta < 0.0 )
            Theta = Theta + Math.PI;

        if (Theta > Math.PI)
            Theta = Theta - Math.PI;

        if (Theta > Math.PI/4 && Theta < Math.PI*3/4) return true;
        return false;
    }
    static int outputCount=0;
    public void output()
    {
        //output a line cluster
        try {
            FileWriter out= new FileWriter("rst\\line_cluster"+outputCount+".eg");
            String s=("LineCluster lc"+outputCount+"= new LineCluster("+color+","
                +orientationLeft+","+orientationRight+");");
            out.write(s);
            out.write("\n");

            for (int i=0;i<size();i++) {
                ORTLine line= getLineAt(i);
                s=("lc"+outputCount+".insert(new ORTLine("+line.Start.Col+","+line.Start.Row+","
                +line.End.Col+","+line.End.Row+"));");
                out.write(s);
                out.write("\n");
            }
            out.close();
        }
        catch (IOException e) {
            System.err.println("io error: "+e);
        }
        outputCount++;

    }

    public double[] getBoundary()
    {
        double[] rst= new double[4];
        if (lines==null||lines.size()==0) return rst;

        ORTLine line= getLineAt(0);
        double minx=line.Start.Col, miny=line.Start.Row,
        maxx=line.Start.Col, maxy=line.Start.Row;
        for (int j=0;j<size();j++) {
            line= getLineAt(j);
            if (line.Start.Col<minx) minx=line.Start.Col;
            if (line.Start.Col>maxx) maxx=line.Start.Col;
            if (line.End.Col<minx) minx=line.End.Col;
            if (line.End.Col>maxx) maxx=line.End.Col;
            if (line.Start.Row<miny) miny=line.Start.Row;
            if (line.Start.Row>maxy) maxy=line.Start.Row;
            if (line.End.Row<miny) miny=line.End.Row;
            if (line.End.Row>maxy) maxy=line.End.Row;
        }
        rst[0]=minx;rst[1]=miny;rst[2]=maxx;rst[3]=maxy;
        return rst;
    }

    public double getAverageLength() {
        if (lines==null||lines.size()==0) return 0;
        double sum=0;
        for (int i=0;i<lines.size();i++) {
            ORTLine l= (ORTLine)lines.elementAt(i);
            sum+= l.Length;
        }
        return sum/lines.size();
    }

    public double getLineLenVariance() {
        if (lines==null||lines.size()<=1) return 0;
        double mean= getAverageLength();
        double sum=0;
        for (int i=0;i<lines.size();i++) {
            ORTLine l= (ORTLine)lines.elementAt(i);
            double deviation= l.Length/mean-1;
            sum+= deviation*deviation;
        }
        return sum/(lines.size()-1);
    }

    public double getLineMeanDeviation() {
        if (lines==null||lines.size()<=1) return 0;
        double mean= getAverageLength();
        double sum=0;
        for (int i=0;i<lines.size();i++) {
            ORTLine l= (ORTLine)lines.elementAt(i);
            double deviation= l.Length/mean-1;
            sum+= Math.abs(deviation);
        }
        return sum/(lines.size());
    }

    public LineCluster copy() {
        LineCluster newlc= new LineCluster(color, orientationLeft, orientationRight);
        newlc.lines= (Vector)lines.clone();
        return newlc;
    }

    public Vector clusterByLength()
    {
        int i,j;

        if (lines==null||lines.size()<=0) return new Vector();

        refineByPerspectiveRelation();
        int[][] prjLines= projectLines(lines);

        int[] lengths= new int[prjLines.length];
        int max_length=0;
        for (i=0;i<lengths.length;i++) {
            lengths[i]=prjLines[i][1]-prjLines[i][0];
            if (lengths[i]>max_length) max_length=lengths[i];
        }
        if (max_length==0) return new Vector();

        //make the histogram
        double[] len_h= new double[max_length+1];
        for (i=0;i<lengths.length;i++) {
            len_h[lengths[i]]++;
        }

        double sigma=2;
        double[] smooth= (new GaussianSmooth(sigma)).smoothing(len_h);
        //OutputResult.outputResult("smooth_length_histogram",smooth);
        int[][] peaks= Histogram.findFatPeaks_no_period(smooth,0);
        int[][] ranges= Histogram.peaks2Ranges(peaks);    //convert the peaks to the range of peaks

        //make the ranges as [small.. big]
        //because it can be [big..small] the ranges are gotten as periodical histogram
        for (i=0;i<ranges.length;i++) {
            if (ranges[i][1]<ranges[i][0]) ranges[i][1]=max_length;
        }

        //make the result line clusters
        Vector clusters= new Vector();
        for (i=0;i<ranges.length;i++) clusters.addElement(new LineCluster());
        for (i=0;i<lines.size();i++) {
            for (j=0;j<ranges.length;j++) {
                if (lengths[i]>=ranges[j][0]&&lengths[i]<=ranges[j][1]) {
                    LineCluster lc= (LineCluster)clusters.elementAt(j);
                    lc.insert((ORTLine)lines.elementAt(i));
                }
            }
        }
        return clusters;
    }

    public static void main(String[] args)
    {

LineCluster lc= new LineCluster(0,147,16);
lc.insert(new ORTLine(316.0,16.0,251.0,20.0));
lc.insert(new ORTLine(255.0,23.0,315.0,20.0));
lc.insert(new ORTLine(108.0,-128.0,83.0,-124.0));
lc.insert(new ORTLine(268.0,60.0,243.0,61.0));
lc.insert(new ORTLine(82.0,-134.0,105.0,-139.0));
lc.insert(new ORTLine(81.0,-178.0,104.0,-183.0));
lc.insert(new ORTLine(47.0,-128.0,70.0,-132.0));
lc.insert(new ORTLine(68.0,-218.0,46.0,-211.0));
lc.insert(new ORTLine(104.0,-215.0,82.0,-209.0));
lc.insert(new ORTLine(48.0,-84.0,70.0,-88.0));
lc.insert(new ORTLine(15.0,-79.0,37.0,-83.0));
lc.insert(new ORTLine(107.0,-93.0,85.0,-90.0));
lc.insert(new ORTLine(68.0,-206.0,47.0,-199.0));
lc.insert(new ORTLine(45.0,-201.0,66.0,-207.0));
lc.insert(new ORTLine(68.0,-122.0,47.0,-117.0));
lc.insert(new ORTLine(3.0,-160.0,-17.0,-154.0));
lc.insert(new ORTLine(94.0,-168.0,89.0,-167.0));
lc.insert(new ORTLine(55.0,-159.0,48.0,-157.0));
lc.insert(new ORTLine(59.0,-160.0,69.0,-162.0));
lc.insert(new ORTLine(-10.0,-195.0,0.0,-198.0));
lc.insert(new ORTLine(-4.0,-117.0,-10.0,-116.0));
lc.insert(new ORTLine(60.0,-199.0,46.0,-195.0));
lc.insert(new ORTLine(95.0,-215.0,80.0,-211.0));
lc.insert(new ORTLine(102.0,-125.0,106.0,-126.0));
lc.insert(new ORTLine(68.0,-165.0,51.0,-161.0));
lc.insert(new ORTLine(97.0,-124.0,90.0,-123.0));
lc.insert(new ORTLine(103.0,-120.0,108.0,-120.0));
lc.insert(new ORTLine(32.0,-198.0,15.0,-193.0));
lc.insert(new ORTLine(-6.0,-107.0,-18.0,-105.0));
lc.insert(new ORTLine(26.0,-111.0,33.0,-112.0));
lc.insert(new ORTLine(32.0,-115.0,15.0,-111.0));
lc.insert(new ORTLine(2.0,-190.0,-15.0,-185.0));
lc.insert(new ORTLine(31.0,-207.0,13.0,-202.0));
lc.insert(new ORTLine(107.0,-41.0,98.0,-40.0));
lc.insert(new ORTLine(50.0,-37.0,44.0,-37.0));
lc.insert(new ORTLine(32.0,-167.0,14.0,-162.0));
lc.insert(new ORTLine(84.0,3.0,73.0,4.0));
lc.insert(new ORTLine(99.0,-172.0,80.0,-168.0));
lc.insert(new ORTLine(99.0,-226.0,80.0,-221.0));
lc.insert(new ORTLine(-170.0,12.0,-174.0,12.0));
lc.insert(new ORTLine(250.0,13.0,256.0,13.0));
lc.insert(new ORTLine(66.0,-175.0,47.0,-170.0));
lc.insert(new ORTLine(308.0,24.0,316.0,24.0));
lc.insert(new ORTLine(221.0,25.0,216.0,26.0));
lc.insert(new ORTLine(299.0,25.0,303.0,25.0));
lc.insert(new ORTLine(306.0,27.0,310.0,27.0));
lc.insert(new ORTLine(253.0,27.0,260.0,27.0));
lc.insert(new ORTLine(15.0,-121.0,35.0,-125.0));
lc.insert(new ORTLine(316.0,32.0,300.0,33.0));
lc.insert(new ORTLine(2.0,-150.0,-18.0,-145.0));
lc.insert(new ORTLine(316.0,36.0,302.0,36.0));
lc.insert(new ORTLine(112.0,44.0,108.0,45.0));
lc.insert(new ORTLine(248.0,42.0,267.0,42.0));
lc.insert(new ORTLine(200.0,49.0,193.0,50.0));
lc.insert(new ORTLine(227.0,55.0,232.0,55.0));
lc.insert(new ORTLine(34.0,-157.0,14.0,-152.0));
lc.insert(new ORTLine(297.0,64.0,312.0,64.0));
lc.insert(new ORTLine(308.0,67.0,316.0,67.0));
lc.insert(new ORTLine(-156.0,68.0,-152.0,68.0));
lc.insert(new ORTLine(275.0,67.0,265.0,68.0));
lc.insert(new ORTLine(266.0,76.0,284.0,75.0));
lc.insert(new ORTLine(286.0,73.0,275.0,73.0));
lc.insert(new ORTLine(-46.0,84.0,-33.0,85.0));
lc.insert(new ORTLine(249.0,111.0,253.0,112.0));



        Dimension d= new Dimension(640,480);
        int[] demo= new int[d.width*d.height];
        for (int i=0;i<demo.length;i++) demo[i]=0xffffffff;
        for (int i=0;i<lc.size();i++) {
            ORTLine line= lc.getLineAt(i);
            DrawUtil.ort2image(demo, d, line, 0xff000000, 1);
        }
        System.err.println("size before perspective: "+lc.size());
        lc.refineByPerspectiveRelation();

        ORTLine virtualLine= lc.getVirtualLine(lc.lines);
        ORTLine y= virtualLine.makeNewLineByRotate90();
        DrawUtil.ort2image(demo, d, virtualLine, 0xffff0000, 1);
        DrawUtil.ort2image(demo, d, y, 0xffff0000, 1);

        for (int i=0;i<lc.size();i++) {
            ORTLine line= lc.getLineAt(i);
            DrawUtil.ort2image(demo, d, line, 0xff000000, 1);
        }


        //lc.refinedBySpatialRelationRepeatly(0.27);
        //lc.lines= lc.refinedBySpatialRelation_test(lc.lines);

        (new DisplayFrame("demo", demo, d)).show();

        int[] demo2= new int[d.width*d.height];
        for (int i=0;i<demo2.length;i++) demo2[i]=0xffffffff;

        ORTLine x= new ORTLine(-300,0,300,0);
        DrawUtil.ort2image(demo2, d, x, 0xffff0000, 1);
        x= new ORTLine(0,-200,0,200);
        DrawUtil.ort2image(demo2, d, x, 0xffff0000, 1);

        int[][] prjLines= lc.projectLines(lc.lines);
        for (int i=0;i<prjLines.length;i++) {
            ORTLine line= new ORTLine(
                -prjLines[i][0], -prjLines[i][2], -prjLines[i][1], -prjLines[i][2]);
            DrawUtil.ort2image(demo2, d, line, 0xff000000, 1);
        }
        (new DisplayFrame("demo2", demo2, d)).show();
//*/

        Vector newlcs2=lc.splitBySpatialRelation(0.18, 0.6);

        LineCluster[] rst2= new LineCluster[newlcs2.size()];
        for (int i=0;i<newlcs2.size();i++) rst2[i]=(LineCluster)newlcs2.elementAt(i);
        ConsistentLineCluster.drawLineClusters("split-vh", d, rst2, -1);


    }

}