在二维平面上给定n点，找出在同一直线上的最大点数。

Below is the solution I am trying to implement

下面是我正在尝试实现的解决方案。

/**
 * 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;
}
}

It runs at O(n^3). What I am basically doing is running two loops comparing various points in the 2d plane. And then taking 2 points I send these 2 points to the get_collinear method which hits the line formed by these 2 points with all the elements of the array to check if the 3 points are collinear. I know this is a brute force method. However in case where the input is[(0,0),(0,0)] my result fails. The else loop is where I have to add a condition to figure out such cases. Can someone help me with the solution to that. And does there exist a better solution to this problem at better run time. I can't think of any.

它运行在O(n ^ 3)。我所做的就是运行两个循环来比较二维平面中的不同点。然后取两点，我将这两个点发送到get_collinear方法中，这两个点到达了由这两个点组成的直线，并通过数组的所有元素来检查这3个点是否共线。我知道这是一种蛮力法。但是，如果输入是[(0,0)，(0,0)]我的结果失败。else循环是我需要添加一个条件来计算出这样的情况。有人能帮我解决这个问题吗?在更好的运行时间内，是否存在更好的解决方案。我想不出来。

1 个解决方案

#1

BTW complexity is indeed O(n^3) to lower that you need to:

顺便说一句复杂性确实是O(n ^ 3)降低,您需要:

1. sort the points somehow

   对点以某种方式排序

   by x and or y in ascending or descending order. Also use of polar coordinates can help sometimes

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

2. use divide at impera (divide and conquer) algorithms

   在impera(分和治)算法中使用划分。

   usually for planar geometry algorithms is good idea to divide area to quadrants and sub-quadrants but these algorithms are hard to code on vector graphics

   通常对于平面几何算法来说，将面积划分为象限和子象限是一个好主意，但是这些算法很难在矢量图形上编码。

3. Also there is one other speedup possibility

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

   check against all possible directions (limited number of them for example to 360 angles only) which leads to O(n^2). Then compute results which is still O(m^3) where m is the subset of points per the tested direction.

   检查所有可能的方向(例如有限数量的360只角)导致O(n ^ 2)。然后计算结果仍然是O(m ^ 3),m是分测试方向的子集。

Ok here is something basic I coded in C++ for example:

这是我用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
    }

It is from my geometry engine so here is some stuff explained:

它来自于我的几何引擎这里有一些解释

glview2D::_pnt

glview2D:_pnt

view.pnt[] are input 2D points (I feed random points around random line + random noise points)
view.pnt.num is number of points

视图。pnt[]是输入的2D点(我在随机的线+随机噪声点周围随机点)。num是点的个数。

glview2D::_lin

glview2D:_lin

view.lin[] are output lines (just one line is used)

视图。lin[]是输出线(只使用一行)

accuracy

精度

Play with pacc,lmin,lmax constants to change the behavior and computation speed. Change dirs to change direction accuracy and computation speed

使用pacc、lmin、lmax等常量来改变行为和计算速度。改变方向精度和计算速度。

Complexity estimation is not possible due to big dependency on input data
But for my random test points are the runtimes like this:

由于对输入数据有很大的依赖性，因此不可能进行复杂性估计，但对于我的随机测试点是这样的运行时间:

[   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