Connect collection of points by finding neighborhood points

Question

I have a swing application in which I have a ArrayList of some points on the image. Now I want to connect those points such that each point is connected to its nearest neighbors.

Like this:

enter image description here

So i started like this:

Minuatiae.java

public class Minutiae {
  private int x;

  private int y;

  public Minutiae(int x, int y){
      this.x = x;
      this.y = y;
  }

 public int getX() {
     return x;
 }

 public void setX(int x) {
     this.x = x;
 }

 public int getY() {
     return y;
 }

 public void setY(int y) {
     this.y = y;
 }
}

Manager.java

List<Minutiae> minuatiaePoints = new ArrayList<Minutiae>(minutiae);

        for(int i = 0; i<minuatiaePoints.size(); i++){
            Minutiae mPoint = minuatiaePoints.get(i);
            Minutiae minPoint = minuatiaePoints.get((i+1) % minuatiaePoints.size());
            int minXDistance = minPoint.getX()-mPoint.getX();
            int minYDistance = minPoint.getY()-mPoint.getY();
            double minDist = Math.hypot(minXDistance, minYDistance);

            for(int j = 0; j < minuatiaePoints.size(); j++)  // <- you had i++ here!
            {
                if (i == j) {
                    continue;
                }

                Minutiae testPt = minuatiaePoints.get(j);
                double dist = Math.hypot(mPoint.getX() - testPt.getX(), mPoint.getY() - testPt.getY());
                if (dist < minDist)
                {
                    minDist = dist;
                    minPoint = testPt;
                }
            }
            g2D.drawLine(mPoint.getX(), mPoint.getY(), minPoint.getX(), minPoint.getY());
        }

But it connects to only one nearest point.

Could anyone help me with this? Any link or example code will be very grateful.

Can you elaborate on how you define the nearest neighbours? Why aren't 6 and 5 connected for example? Or 4 and 2? — Bernhard Barker, Aug 26 '13 at 13:55
@Gerret minutiae points are the some points on the image having x,y coordinates. — code_fish, Aug 26 '13 at 13:58
@Dukeling The point is that graph should be connected in such a way that there is no need to connect each point to every other point but it should be connected to its neighbours. — code_fish, Aug 26 '13 at 14:00
i'm guessing this not really a graph, where distance is measured in number edges needed to reach a node, but the spacial representation of a graph where it is geometric distance which measures distance between nodes as can be deduced by the code shown. — Daren, Aug 26 '13 at 14:20

Daren · Accepted Answer · 2013-08-26T14:05:32.820

You have two options:

Once you have the minimum distance, have another go at your list and connect all whose minimum distance = your min distance (therefore you only need to find the min. distance). And on the second run if dist=min distance, then you draw the line every time you have the equality.

The second option is to keep a list of minimum distance points and then go through the list to draw the lines.

EDIT: updated to add code for the second algortihm:

List<Minutiae> minuatiaePoints = new ArrayList<Minutiae>(minutiae);

    for(int i = 0; i<minuatiaePoints.size(); i++){
        Minutiae mPoint = minuatiaePoints.get(i);
        Minutiae minPoint = minuatiaePoints.get((i+1) % minuatiaePoints.size());
        int minXDistance = minPoint.getX()-mPoint.getX();
        int minYDistance = minPoint.getY()-mPoint.getY();
        double minDist = Math.hypot(minXDistance, minYDistance);

        List<Minutiae> minDistPoints = new ArrayList<Minutiae>();

        for(int j = 0; j < minuatiaePoints.size(); j++)  // <- you had i++ here!
        {
            if (i == j) {
                continue;
            }

            Minutiae testPt = minuatiaePoints.get(j);
            double dist = Math.hypot(mPoint.getX() - testPt.getX(), mPoint.getY() - testPt.getY());
            if (dist < minDist)
            {
                minDist = dist;
                minDistPoints  = new ArrayList<Minutiae>();
                minDistPoints.add(testPt);
            } else if (dist = minDist) {
                minDistPoints.add(testPt);
            }
        }

        for(Minutae p: minDistPoints){
            g2D.drawLine(mPoint.getX(), mPoint.getY(), p.getX(), p.getY());
        }
    }

sorry for the late reply. yeah.. it worked but my requirement got changed and I had to put that on hold for some time. I will contact you as soon I ready to work on same with the requirements. Thanks — code_fish, Sep 12 '13 at 11:06

Connect collection of points by finding neighborhood points

1 Answers1

Linked