Given a two dimensional graph with points on it, fin a line which passes the most number of points
Page 1 of 1
Given a two dimensional graph with points on it, fin a line which passes the most number of points
public static Line findBestLine(GraphPoint[] points){
HashTable<Line,Integer> hash=new HashTable<Line,Integer>();
int len=points.length();
for(int i=0;i<len;i++){
for(int j=i+1;j<len;j++){
int slope=(point[i].gety()-point[j].gety())/(point[i].getx()-point[j].getx());
int y=***;
Line line=new Line(slope,y);
int numpoints=2;
for(int z=0;z<len;z++){
if(point[z]!=point[i]&&point[z]!=point[j]){
if(line.include(point[z])){
numpoints++;
}
}
hash.put(line.new Integer(count));
}
}
}
Iterator pointer=hash.iterator();
int max=0;
Line final;
while(pointer.hasNext()){
if(pointer.getvalue().intValue()>max)
final=pointer.getKey();
max=pointer.getValue().intValue();
}
}
return final;
class Line{
double slope;
double y;
public Line(){};
public Line(double s, double yy){
slope=s;
y=yy;
}
public double getslope(){
return slope;
}
public double gety(){
return y;
}
public boolean include(point a){
if(a.gety()==this.slope*a.getx()+this.y)
return true;
return false;
}
}
class GraphPoint{
double x;
double y;
public GraphPoint(double a,double b){
x=a;
y=b;
}
}
HashTable<Line,Integer> hash=new HashTable<Line,Integer>();
int len=points.length();
for(int i=0;i<len;i++){
for(int j=i+1;j<len;j++){
int slope=(point[i].gety()-point[j].gety())/(point[i].getx()-point[j].getx());
int y=***;
Line line=new Line(slope,y);
int numpoints=2;
for(int z=0;z<len;z++){
if(point[z]!=point[i]&&point[z]!=point[j]){
if(line.include(point[z])){
numpoints++;
}
}
hash.put(line.new Integer(count));
}
}
}
Iterator pointer=hash.iterator();
int max=0;
Line final;
while(pointer.hasNext()){
if(pointer.getvalue().intValue()>max)
final=pointer.getKey();
max=pointer.getValue().intValue();
}
}
return final;
class Line{
double slope;
double y;
public Line(){};
public Line(double s, double yy){
slope=s;
y=yy;
}
public double getslope(){
return slope;
}
public double gety(){
return y;
}
public boolean include(point a){
if(a.gety()==this.slope*a.getx()+this.y)
return true;
return false;
}
}
class GraphPoint{
double x;
double y;
public GraphPoint(double a,double b){
x=a;
y=b;
}
}
Similar topics
» Given a magic number sum, to find if there are two numbers whose sum equals to the number
» Given a directed graph, design an algorithm to find out whether there is a route be- tween two nodes.
» Design an algorithm and write code to serialize and deserialize a binary tree/graph
» Judge whether a number is power of 2
» Count number of 1's in Java
» Given a directed graph, design an algorithm to find out whether there is a route be- tween two nodes.
» Design an algorithm and write code to serialize and deserialize a binary tree/graph
» Judge whether a number is power of 2
» Count number of 1's in Java
Page 1 of 1
Permissions in this forum:
You cannot reply to topics in this forum
|
|