给定2D平面上的n个点，找出位于同一直线上的最大点数

以下是我正在尝试实施的解决scheme

/** * Definition for a point. * class Point { * int x; * int y; * Point() { x = 0; y = 0; } * Point(int a, int b) { x = a; y = b; } * } */ public class Solution { public int maxPoints(Point[] points) { int max=0; if(points.length==1) return 1; for(int i=0;i<points.length;i++){ for(int j=0;j<points.length;j++){ if((points[i].x!=points[j].x)||(points[i].y!=points[j].y)){ int coll=get_collinear(points[i].x,points[i].y,points[j].x,points[j].y,points); if(coll>max) max=coll; } else{ **Case where I am suffering** } } } return max; } public int get_collinear(int x1,int y1,int x2, int y2,Point[] points) { int c=0; for(int i=0;i<points.length;i++){ int k1=x1-points[i].x; int l1=y1-points[i].y; int k2=x2-points[i].x; int l2=y2-points[i].y; if((k1*l2-k2*l1)==0) c++; } return c; } } 

它运行在O（n ^ 3）。 我基本上做的是运行两个循环比较2D平面中的各个点。 然后把2个点发送给get_collinear方法，这个方法用数组中的所有元素点击这2个点形成的线来检查3个点是否共线。 我知道这是一个蛮力的方法。 但是，如果input是[（0,0），（0,0）]，我的结果失败。 else循环是我必须添加一个条件来找出这种情况。 有人可以帮我解决这个问题。 在更好的运行时间里，是否存在更好的解决scheme？ 我想不出来。

Answer 1

BTW的复杂性实际上是O(n^3)降低，你需要：

1. 以某种方式对点进行sorting

   由x和或y按升序或降序排列。 极坐标的使用有时可以帮助

2. 使用分割（divide and conquer）algorithm

   通常对于平面几何algorithm来说，将区域划分为象限和子象限是一个好主意，但是这些algorithm很难在vectorgraphics上编码

3. 另外还有一个加速的可能性

   检查所有可能的方向（有限的数量，例如只有360angular度），导致O(n^2) 。 然后计算仍然是O(m^3)结果，其中m是每个testing方向的点的子集。

好的，这里是我用C ++编写的一些基本的东西：

 void points_on_line() { const int dirs =360; // num of directions (accuracy) double mdir=double(dirs)/M_PI; // conversion from angle to code double pacc=0.01; // position acc <0,1> double lmin=0.05; // min line size acc <0,1> double lmax=0.25; // max line size acc <0,1> double pacc2,lmin2,lmax2; int n,ia,ib; double x0,x1,y0,y1; struct _lin { int dir; // dir code <0,dirs> double ang; // dir [rad] <0,M_PI> double dx,dy; // dir unit vector int i0,i1; // index of points } *lin; glview2D::_pnt *a,*b; glview2D::_lin q; _lin l; // prepare buffers n=view.pnt.num; // n=number of points n=((n*n)-n)>>1; // n=max number of lines lin=new _lin[n]; n=0; if (lin==NULL) return; // precompute size of area and update accuracy constants ~O(N) for (a=view.pnt.dat,ia=0;ia<view.pnt.num;ia++,a++) { if (!ia) { x0=a->p[0]; y0=a->p[1]; x1=a->p[0]; y1=a->p[1]; } if (x0>a->p[0]) x0=a->p[0]; if (x1<a->p[0]) x1=a->p[0]; if (y0>a->p[1]) y0=a->p[1]; if (y1<a->p[1]) y1=a->p[1]; } x1-=x0; y1-=y0; if (x1>y1) x1=y1; pacc*=x1; pacc2=pacc*pacc; lmin*=x1; lmin2=lmin*lmin; lmax*=x1; lmax2=lmax*lmax; // precompute lines ~O((N^2)/2) for (a=view.pnt.dat,ia=0;ia<view.pnt.num;ia++,a++) for (b=a+1,ib=ia+1;ib<view.pnt.num;ib++,b++) { l.i0=ia; l.i1=ib; x0=b->p[0]-a->p[0]; y0=b->p[1]-a->p[1]; x1=(x0*x0)+(y0*y0); if (x1<=lmin2) continue; // ignore too small lines if (x1>=lmax2) continue; // ignore too big lines l.ang=atanxy(x0,y0); if (l.ang>M_PI) l.ang-=M_PI; // 180 deg is enough lines goes both ways ... l.dx=cos(l.ang); l.dy=sin(l.ang); l.dir=double(l.ang*mdir); lin[n]=l; n++; // q.p0=*a; q.p1=*b; view.lin.add(q); // just visualise used lines for testing } // test directions int cnt,cntmax=0; double t; for (ia=0;ia<n;ia++) { cnt=1; for (ib=ia+1;ib<n;ib++) if (lin[ia].dir==lin[ib].dir) { a=&view.pnt[lin[ia].i0]; if (lin[ia].i0!=lin[ib].i0) b=&view.pnt[lin[ib].i0]; else b=&view.pnt[lin[ib].i1]; x0=b->p[0]-a->p[0]; x0*=x0; y0=b->p[1]-a->p[1]; y0*=y0; t=sqrt(x0+y0); x0=a->p[0]+(t*lin[ia].dx)-b->p[0]; x0*=x0; y0=a->p[1]+(t*lin[ia].dy)-b->p[1]; y0*=y0; t=x0+y0; if (fabs(t)<=pacc2) cnt++; } if (cntmax<cnt) // if more points on single line found { cntmax=cnt; // update point count q.p0=view.pnt[lin[ia].i0]; // copy start/end point q.p1=q.p0; q.p0.p[0]-=500.0*lin[ia].dx; // and set result line as very big (infinite) line q.p0.p[1]-=500.0*lin[ia].dy; q.p1.p[0]+=500.0*lin[ia].dx; q.p1.p[1]+=500.0*lin[ia].dy; } } if (cntmax) view.lin.add(q); view.redraw=true; delete lin; // Caption=n; // just to see how many lines actualy survive the filtering } 

这是从我的几何引擎，所以这里有一些东西解释：

glview2D::_pnt

view.pnt[]是input的2D点（我随机点周围随机点+随机噪声点）
view.pnt.num是点数

glview2D::_lin

view.lin[]是输出行（只使用一行）

准确性

使用pacc,lmin,lmax常量来改变行为和计算速度。 更改dirs以改变方向精度和计算速度

由于对input数据的依赖性很大，复杂度估计是不可能的
但是对于我的随机testing点是这样的运行时间：

 [ 0.056 ms]Genere 100 random 2D points [ 151.839 ms]Compute 100 points on line1 (unoptimized brute force O(N^3)) [ 4.385 ms]Compute 100 points on line2 (optimized direction check) [ 0.096 ms] Genere 200 random 2D points [1041.676 ms] Compute 200 points on line1 [ 39.561 ms] Compute 200 points on line2 [ 0.440 ms] Genere 1000 random 2D points [29061.54 ms] Compute 1000 points on line2