I have my algorithm to find the closest pair of points. It works well and find the minimum delta. I want to make the points magenta when they show up in the panel. But I'm having issues with that.
This algorithm take n random points and put them into an array that will find the closest pair by the algorithm, but I want to show which points are the couple and then show them to the user.
This is my code:
public class FTCPAMethods {
static Sort s = new Sort();
static Point[] X,Y;
static Point[] P;
static double deltamin;
static Point[] cp = new Point[2];
static List<Point> bfList = new ArrayList<Point>();
static double deltaL, deltaR, delta;
public FTCPAMethods() {
}
public double presorting(Point[] P, int n) {
this.X = P.clone();
s.mergeSortX(X, X.length);
this.Y=P.clone();
s.mergeSortY(Y, Y.length);
return findClosest(X,Y,n);
}
public double findClosest(Point[] X, Point[] Y, int n) {
if(n<=3) {
deltamin = bruteForce(X,n);
System.out.println("BF: "+Arrays.toString(X));
return deltamin;
}else {
int mid = (int) (Math.ceil((double)n/2));
Point[] YL = Arrays.copyOfRange(Y, 0, mid);
Point[] YR = Arrays.copyOfRange(Y, mid, n);
System.out.println("Yl: "+Arrays.toString(YL));
System.out.println("Yr: "+Arrays.toString(YR));
double deltaL = findClosest(Arrays.copyOfRange(X, 0, mid),YL,mid);
double deltaR = findClosest(Arrays.copyOfRange(X, mid, n),YR, n-mid);
double delta = Math.min(deltaL, deltaR);
List<Point> Y1 = new ArrayList<Point>();
for(Point p:Y) {
if (Math.abs(p.x - line(X,mid)) < delta) {
Y1.add(p);
}
}
System.out.println("Y1: "+Y1);
System.out.println("line:"+line(X,mid));
System.out.println("delta: "+delta);
return closestY1(Y1.toArray(new Point[Y1.size()]), Y1.size(), delta);
}
}
public double closestY1(Point[] Y1arr, int dim, double delta) {
deltamin=delta;
for(int i=0;i<dim;i++) {
for(int j=i+1;j<dim && (Y1arr[j].y-Y1arr[i].y)<deltamin;j++) {
double distance = distance(Y1arr[i], Y1arr[j]);
if(distance<deltamin) {
deltamin=distance;
this.cp[0]=Y1arr[i];
this.cp[1]=Y1arr[j];
}
}
}
System.out.println("delta1: "+deltamin);
return deltamin;
}
public double distance(Point p1, Point p2) {
return Math.sqrt(Math.pow(p1.getX() - p2.getX(), 2) + Math.pow(p1.getY() - p2.getY(), 2));
}
public double line(Point[] X, int mid) {
int i = mid/2;
double line = (X[i].getX()+X[i+1].getX())/2;
return line;
}
public double bruteForce(Point[] P, int n) {
double delta1=Math.sqrt(Math.pow(FTCPPanel.WIDTH, 2)+Math.pow(FTCPPanel.HEIGHT, 2));
for(int i=0; i<n;i++) {
bfList.add(P[i]);
for(int j=i+1;j<n;j++) {
double deltam=distance(P[i],P[j]);
if(deltam<delta1) {
delta1=deltam;
}
}
}
return delta1;
}
public Point[] closestPointsArray(Point[] cp,List<Point> list, Point[] cp1) {
int size = list.size();
double dist = Double.MAX_VALUE;
double dist1 = Double.MAX_VALUE;
System.out.println("list"+list);
Point[] l= list.toArray(new Point[size]);
System.out.println("list"+Arrays.toString(l));
Point[] n3= new Point[2];
Point[] n6= new Point[2];
if(size==4) {
if(distance(l[0],l[1])<=distance(l[2],l[3])) {
cp1[0]=l[0];
cp1[1]=l[1];
}else {
cp1[0]=l[2];
cp1[1]=l[3];
}
}
else if(size==5) {
for(int i=0;i<2;i++) {
for(int j=i+1;j<3;i++) {
double distance=distance(l[i],l[j]);
if(distance<=dist) {
dist=distance;
n3[0]=l[i];
n3[1]=l[j];
}
}
}
if(distance(l[3],l[4])<=dist) {
cp1[0]=l[3];
cp1[1]=l[4];
}else {
cp1[0]=n3[0];
cp1[1]=n3[1];
}
}else if(size==6){
for(int i=0;i<2;i++) {
for(int j=i+1;j<3;i++) {
double distance=distance(l[i],l[j]);
if(distance<=dist) {
dist=distance;
n3[0]=l[i];
n3[1]=l[j];
}
}
}
for(int i=3;i<5;i++) {
for(int j=i+1;j<6;i++) {
double distance1=distance(l[i],l[j]);
if(distance1<=dist1) {
dist1=distance1;
n6[0]=l[i];
n6[1]=l[j];
}
}
}
if(dist<= dist1) {
cp1=n3.clone();
}else {
cp1=n6.clone();
}
}
System.out.println("cp1"+Arrays.toString(cp1));
double cp1d = distance(cp1[0], cp1[1]);
if(cp[0]!= null || cp[1]!=null) {
double cpd = distance(cp[0],cp[1]);
if(cpd<=cp1d) {
return cp;
}else {
return cp1;
}}else {
return cp1;
}
}
}
And this is the panel:
public class FTCPAPanel extends JPanel{
int WIDTH = 1000;
int HEIGHT = 600;
FTCPAMethods ftcpam = new FTCPAMethods();
int n;
static Point[] P;
Point[] closest = new Point[2];
Point[] cp1 =new Point[2];
public FTCPAPanel() {
super();
this.setVisible(true);
this.setPreferredSize(new Dimension(WIDTH, HEIGHT));
this.setBackground(new Color(153,153,255));
this.n= Integer.parseInt(FTCPPanel.pointfield.getText());
if(n<=1) {
System.out.println("The program does not run by entering negative\n numbers or a single point");
}else {
Random rand = new Random();
this.P = new Point[n];
for (int i=0; i<n; i++) {
P[i]= new Point(rand.nextInt(1000),rand.nextInt(600));
}
float StartTime = System.nanoTime();
ftcpam.presorting(P,n); //algorithm starts
float endTime = System.nanoTime();
float duration =(endTime - StartTime);
System.out.println("Lista: "+FTCPAMethods.bfList);
System.out.println("cp "+Arrays.toString(FTCPAMethods.cp));
this.closest=ftcpam.closestPointsArray(FTCPAMethods.cp, FTCPAMethods.bfList,cp1).clone();
System.out.println(duration/1000000);
System.out.println("P: "+Arrays.toString(P));
System.out.println("X: "+Arrays.toString(FTCPAMethods.X));
System.out.println("Y: "+Arrays.toString(FTCPAMethods.Y));
System.out.println("cp "+Arrays.toString(FTCPAMethods.cp));
}
}
@Override
public void paintComponent(Graphics g) {
super.paintComponent(g);
Graphics2D g1 = (Graphics2D)g;
g.setColor(Color.DARK_GRAY);
if(n>1) {
for(int i=0; i<P.length; i++) {
g.fillOval((int)P[i].getX(), (int) P[i].getY(), 4, 4);
}
g.setColor(Color.MAGENTA);
g.fillOval((int)closest[0].getX(), (int) closest[0].getY(), 4, 4);
g.fillOval((int)closest[1].getX(), (int) closest[1].getY(), 4, 4);
}
repaint();
}
}
But this is my output:
**Yl: [java.awt.Point[x=586,y=110], java.awt.Point[x=39,y=203], java.awt.Point[x=721,y=292], java.awt.Point[x=200,y=320], java.awt.Point[x=876,y=337]]
Yr: [java.awt.Point[x=517,y=371], java.awt.Point[x=785,y=446], java.awt.Point[x=936,y=472], java.awt.Point[x=454,y=536], java.awt.Point[x=403,y=596]]
Yl: [java.awt.Point[x=586,y=110], java.awt.Point[x=39,y=203], java.awt.Point[x=721,y=292]]
Yr: [java.awt.Point[x=200,y=320], java.awt.Point[x=876,y=337]]
BF: [java.awt.Point[x=39,y=203], java.awt.Point[x=200,y=320], java.awt.Point[x=403,y=596]]
BF: [java.awt.Point[x=454,y=536], java.awt.Point[x=517,y=371]]
Y1: [java.awt.Point[x=200,y=320]]
line:301.5
delta: 176.61823235442031
delta1: 176.61823235442031
Yl: [java.awt.Point[x=517,y=371], java.awt.Point[x=785,y=446], java.awt.Point[x=936,y=472]]
Yr: [java.awt.Point[x=454,y=536], java.awt.Point[x=403,y=596]]
BF: [java.awt.Point[x=586,y=110], java.awt.Point[x=721,y=292], java.awt.Point[x=785,y=446]]
BF: [java.awt.Point[x=876,y=337], java.awt.Point[x=936,y=472]]
Y1: [java.awt.Point[x=785,y=446]]
line:753.0
delta: 147.73286702694156
delta1: 147.73286702694156
Y1: [java.awt.Point[x=517,y=371], java.awt.Point[x=454,y=536], java.awt.Point[x=403,y=596]]
line:428.5
delta: 147.73286702694156
delta1: 78.74642849044012
Lista: [java.awt.Point[x=39,y=203], java.awt.Point[x=200,y=320], java.awt.Point[x=403,y=596], java.awt.Point[x=454,y=536], java.awt.Point[x=517,y=371], java.awt.Point[x=586,y=110], java.awt.Point[x=721,y=292], java.awt.Point[x=785,y=446], java.awt.Point[x=876,y=337], java.awt.Point[x=936,y=472]]
cp [java.awt.Point[x=454,y=536], java.awt.Point[x=403,y=596]]
list[java.awt.Point[x=39,y=203], java.awt.Point[x=200,y=320], java.awt.Point[x=403,y=596], java.awt.Point[x=454,y=536], java.awt.Point[x=517,y=371], java.awt.Point[x=586,y=110], java.awt.Point[x=721,y=292], java.awt.Point[x=785,y=446], java.awt.Point[x=876,y=337], java.awt.Point[x=936,y=472]]
list[java.awt.Point[x=39,y=203], java.awt.Point[x=200,y=320], java.awt.Point[x=403,y=596], java.awt.Point[x=454,y=536], java.awt.Point[x=517,y=371], java.awt.Point[x=586,y=110], java.awt.Point[x=721,y=292], java.awt.Point[x=785,y=446], java.awt.Point[x=876,y=337], java.awt.Point[x=936,y=472]]
cp1[null, null]
Exception in thread "AWT-EventQueue-0" java.lang.NullPointerException: Cannot invoke "java.awt.Point.getX()" because "p1" is null
at FindTheClosestPoints/findclosestpoints.FTCPAMethods.distance(FTCPAMethods.java:108)
at FindTheClosestPoints/findclosestpoints.FTCPAMethods.closestPointsArray(FTCPAMethods.java:226)
at FindTheClosestPoints/findclosestpoints.FTCPAPanel.<init>(FTCPAPanel.java:65)
at FindTheClosestPoints/findclosestpoints.FTCPPanel$1.actionPerformed(FTCPPanel.java:82) **
The list is full of all the points, but it should be like 6 element max. I need to know why the list take all the point and not the points that are when the `bruteforce() run.
