CODEWITHSUNDEEP
javagraph
code_fish
code_fish

Reputation: 3426

Connect collection of points by finding neighborhood points

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.

Upvotes: 1

Views: 1849

Answers (1)

Daren
Daren

Reputation: 3427

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());
        }
    }

Upvotes: 1

Related Questions