给定2D平面上的n个点，求出同一直线上的最大点数 [英] Given n points on a 2D plane, find the maximum number of points that lie on the same straight line
问题描述
下面是我要实现的解决方案
/ **
*定义点。
*类Point {
* int x;
* int y;
* Point（）{x = 0; y = 0; }
* Point（int a，int b）{x = a; y = b; }
*}
* /
公共类解决方案{
public int maxPoints（Point [] points）{
int max = 0;
if（points.length == 1）
返回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 {
**在我遭受痛苦的情况下**
}
}
}
返回最大值；
}
public int get_collinear（int x1，int y1，int x2，int y2，Point [] points）
{
int c = 0;
for（int i = 0; i
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 ++;
}
返回c;
}
}
它运行在O（n ^ 3）处。我基本上在做的是运行两个循环，比较2d平面中的各个点。然后取2个点，我将这2个点发送到get_collinear方法，该方法用数组的所有元素击中这2个点形成的线，以检查3个点是否共线。我知道这是蛮力方法。但是，如果输入为[（0,0），（0,0）]，我的结果将失败。 else循环是我必须添加条件以找出此类情况的地方。有人可以帮我解决这个问题吗？在更好的运行时间上是否存在针对此问题的更好解决方案。
BTW 的确确实是 O（n ^ 3）降低所需的值：
-
以某种方式对点进行排序
按
x和或y升序或降序排列。极坐标的使用有时也会有帮助
-
在impera（除法和征服）算法上使用除法
通常用于平面几何算法是将区域分为象限和子象限的好主意，但是这些算法很难在矢量图形上进行编码
-
另外还有一种提速的可能性
检查所有可能的情况方向（例如，数量有限，例如到
360个角度）会导致O（n ^ 2）。然后计算结果仍为O（m ^ 3），其中m是每个测试方向的点的子集。
好，这是我用C ++编写的一些基本内容，例如：
void points_on_line（）
{
const int dirs = 360; //方向数量（精度）
double mdir = double（dirs）/ M_PI; //从角度转换为代码
double pacc = 0.01; //位置acc< 0,1>
double lmin = 0.05; //最小行尺寸acc< 0,1>
double lmax = 0.25; //最大行尺寸acc< 0,1>
double pacc2，lmin2，lmax2;
int n，ia，ib;
double x0，x1，y0，y1;
struct _lin
{
int dir; //目录代码< 0，dirs>
double ang; // dir [rad]< 0，M_PI>
double dx，dy; //目录单位向量
int i0，i1; //点的索引
} * lin;
glview2D :: _ pnt * a，* b;
glview2D :: _ lin q;
_lin l;
//准备缓冲区
n = view.pnt.num; // n =点数
n =（（n * n）-n）> 1; // n =最大行数
lin = new _lin [n]; n = 0;
if（lin == NULL）返回;
//预计算区域大小并更新精度常数〜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]；
}
如果（x0> a-> p [0]）x0 = a-> p [0];
如果（x1 a-p [0]）x1 = a-p [0]；
如果（y0> a-> p [1]）y0 = a-> p [1];
如果（y1 a-p [1]）y1 = a-p [1]；
}
x1- = x0; y1- = y0;如果（x1> y1）x1 = y1;
pacc * = x1; pacc2 = pacc * pacc;
lmin * = x1; lmin2 = lmin * lmin;
lmax * = x1; lmax2 = lmax * lmax;
//预计算行〜O（（N ^ 2）/ 2）
for（a = view.pnt.dat，ia = 0; ia< view.pnt.num; ia ++，a ++）$ （b = a + 1，ib = ia + 1; ib< view.pnt.num; ib ++，b ++）的b
$ 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）;
如果（x1 <= lmin2）继续; //如果（x1> = lmax2）继续，则忽略太小的行
; //忽略太大的行
l.ang = atanxy（x0，y0）;
if（l.ang> M_PI）l.ang- = M_PI; // 180度足以使线双向移动...
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）; //只显示用于测试的行
}
//测试方向
int cnt，cntmax = 0;
double t; （ia = 0; ia
{
cnt = 1; （ib = ia + 1; ib
{
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）//如果在单行上找到更多点
{
cntmax = cnt; //更新点数
q.p0 = view.pnt [lin [ia] .i0]; //复制起点/终点
q.p1 = q.p0;
q.p0.p [0]-= 500.0 * lin [ia] .dx; //并将结果行设置为非常大（无限）的行
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;
//标题= n; //只是看看实际上有多少行可以通过过滤
}
这是我的几何引擎提供的，所以这里解释了一些东西：
glview2D :: _ pnt
view.pnt [] 被输入 2D 点（我在随机线周围输入随机点+随机噪声点）
view.pnt.num 是点数
glview2D :: _ lin
view.lin [] 是输出行（仅使用一行）
准确性
玩 pacc，lmin，lmax 常数可更改行为和计算速度。更改 dirs 以更改方向精度和计算速度
由于对输入数据的依赖性很大，因此无法进行复杂度估计
但对于我的随机测试点，是这样的运行时：
[0.056 ms]生成100个随机2D点
[151.839 ms]计算第1行的100点（未优化的蛮力O（N ^ 3））
[4.385 ms]计算第2行的100点（优化方向检查）
[0.096 ms]类型200随机2D点
[1041.676 ms]计算第1行200点
[39.561 ms]计算第2行200点
[0.440 ms]生成1000个随机2D点
[29061.54毫秒]在第2行
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.
BTW complexity is indeed O(n^3) to lower that you need to:
sort the points somehow
by
xand oryin ascending or descending order. Also use of polar coordinates can help sometimesuse divide at impera (divide and conquer) algorithms
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
Also there is one other speedup possibility
check against all possible directions (limited number of them for example to
360angles only) which leads toO(n^2). Then compute results which is stillO(m^3)wheremis the subset of points per the tested direction.
Ok here is something basic I coded in C++ for example:
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
view.pnt[] are input 2D points (I feed random points around random line + random noise points)
view.pnt.num is number of points
glview2D::_lin
view.lin[] are output lines (just one line is used)
accuracy
Play with pacc,lmin,lmax constants to change the behavior and computation speed. Change dirs to change direction accuracy and computation speed
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
这篇关于给定2D平面上的n个点，求出同一直线上的最大点数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
