在二维平面上,有一些点,请找出经过点数最多的那条线。
在二维平面上,有一些点,请找出经过点数最多的那条线。
一贱书生 发表于2年前
在二维平面上,有一些点,请找出经过点数最多的那条线。
  • 发表于 2年前
  • 阅读 8
  • 收藏 0
  • 点赞 0
  • 评论 0

移动开发云端新模式探索实践 >>>   

/**

 * 功能:在二维平面上,有一些点,请找出经过点数最多的那条线。[java] view plain copy

 

  1. /** 
  2.      * 思路:在任意两点之间画一条无线长的直线,用散列表追踪那条直线出现的次数最多。时间复杂度O(N*N) 
  3.      * 注意: 
  4.      *      1)用斜率和y轴截距来确定是否是同一条直线。 
  5.      *      2)浮点数不一定能用二进制数准确表示,因此检查两个浮点数的差值是否在某个极小值(epsilon)内。 
  6.      *      3)对于散列表而言,斜率相等,未必散列值相同。因此,将斜率减去一个极小值,并以得到的结果flooredSlope作为散列键。 
  7.      *      4)取得所有可能相等的直线,搜索三个位置:flooredSlope,flooredSlope-epsilon,flooredSlope+epsilon。 
  8.      * @param points 
  9.      * @return 
  10.      */  
  11.     public static MyLine1 findBestLine(GraphPoint[] points){  
  12.         MyLine1 bestLine=null;  
  13.         int bestCount=0;  
  14.           
  15.         HashMap<Double,ArrayList<MyLine1>> lineBySlope=new HashMap<Double, ArrayList<MyLine1>>();  
  16.           
  17.         for(int i=0;i<points.length-1;i++){  
  18.             for(int j=i+1;j<points.length;j++){  
  19.                 MyLine1 line=new MyLine1(points[i],points[j]);  
  20.                 insertLine(lineBySlope,line);  
  21.                 int count=countEquivalentLines(lineBySlope,line);  
  22.                 if(count>bestCount){  
  23.                     bestCount=count;  
  24.                     bestLine=line;  
  25.                 }  
  26.             }  
  27.         }  
  28.         return bestLine;  
  29.           
  30.     }  
  31.   
  32.     private static int countEquivalentLines(HashMap<Double, ArrayList<MyLine1>> lineBySlope, MyLine1 line) {  
  33.         double key=line.floorToNearestEpsilon(line.slope);  
  34.         double eps=line.epsilon;  
  35.         int count=countEquivalentLines(lineBySlope.get(key), line)+countEquivalentLines(lineBySlope.get(key-eps), line)+  
  36.                 countEquivalentLines(lineBySlope.get(key+eps), line);  
  37.           
  38.         return count;  
  39.     }  
  40.       
  41.     public static int countEquivalentLines(ArrayList<MyLine1> lines,MyLine1 line){  
  42.         if(lines==null)  
  43.             return 0;  
  44.         int count=0;  
  45.         for(MyLine1 paralleLine:lines){  
  46.             if(paralleLine==line)  
  47.                 count++;  
  48.         }  
  49.         return count;  
  50.     }  
  51.   
  52.     private static void insertLine(HashMap<Double, ArrayList<MyLine1>> lineBySlope, MyLine1 line) {  
  53.         ArrayList<MyLine1> lines=null;  
  54.         double key=line.floorToNearestEpsilon(line.slope);  
  55.         if(!lineBySlope.containsKey(key)){  
  56.             lines=new ArrayList<MyLine1>();  
  57.             lineBySlope.put(key, lines);  
  58.         }else{  
  59.             lines=lineBySlope.get(key);  
  60.         }  
  61.         lines.add(line);//注意此处添加的用法  
  62.     }  
  63.       
  64.       
  65.   
  66. class MyLine1{  
  67.     public static double epsilon=0.0001;  
  68.     public double slope,intercept;  
  69.     public boolean infiniteSlope=false;  
  70.       
  71.     public MyLine1(GraphPoint p,GraphPoint q){  
  72.         if(Math.abs(p.x-q.x)>epsilon){//两个点的x坐标不同  
  73.             slope=(p.y-q.y)/(p.x-q.x);//斜率  
  74.             intercept=p.y-slope*p.x;//y轴截距  
  75.         }else{  
  76.             infiniteSlope=true;  
  77.             intercept=p.x;//x轴截距  
  78.         }  
  79.     }  
  80.       
  81.     public double floorToNearestEpsilon(double d){  
  82.         int r=(int) (d/epsilon);//使原d保留小数位后的4位(epsilon=0.0001)  
  83.         return ((double)r)*epsilon;  
  84.     }  
  85.       
  86.     public boolean isEquivalent(MyLine1 line){  
  87.         if((slope==line.slope)&&(intercept==line.intercept)&&(infiniteSlope==line.infiniteSlope))  
  88.             return true;  
  89.         return false;  
  90.     }  
  91.       
  92.     public boolean isEquivalent(double a,double b){  
  93.         return Math.abs(a-b)<epsilon;  
  94.     }  
  95.       
  96.   
  97.       
  98. }  
  99.   
  100. class GraphPoint{  
  101.     int x;  
  102.     int y;  
  103.       
  104.     public GraphPoint(int x,int y){  
  105.         this.x=x;  
  106.         this.y=y;  
  107.     }  

 

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 19
博文 722
码字总数 600072
×
一贱书生
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: