CODEWITHSUNDEEP
javaalgorithmclosest-points
Cethy
Cethy

Reputation: 551

Closest pair of points using sweep line algorithm in Java

First off; I'm doing this as an assignment for school, and that's why I'm using the sweep line algorithm. I'm basing it off of the pseudocode given by my teacher.

I've done an implementation of my own using TreeMap instead of a balanced binary search tree, which I was told would provide the same functionality. (Don't know if this is true, though?)

However I don't get the proper end result, and I really have no idea why. I've been staring myself blind.

Below is the part of my code that performs the actual computation. I've omitted the creation of the points-list, and other unimportant stuff.

            count = 0;

            TreeMap<Double, Point> tree = new TreeMap<Double, Point>();

            double dist = Double.POSITIVE_INFINITY;

            // Sorts points on x-axis
            Collections.sort(points); 

            // Gets left-most point
            Point q = points.get(count++);

            for (Point p : points) {

                while (q.getX() < p.getX() - dist) {
                    tree.remove(q.getY());
                    q = points.get(count++);
                }

                NavigableSet<Double> keys = tree.navigableKeySet();

                // Look at the 4 points above 'p'
                int i = 1;
                Iterator<Double> iterHi = keys.tailSet(p.getY()).iterator();

                while (i <= 4 && iterHi.hasNext()) {
                    double tmp = p.distanceTo(tree.get(iterHi.next()));
                    if (tmp < dist) {
                        dist = tmp;
                        pClosest = p;
                        qClosest = q;
                    }
                    i++;
                }

                // Look at the 4 points below 'p'
                i = 1;
                Iterator<Double> iterLo = keys.headSet(p.getY()).iterator();

                while (i <= 4 && iterLo.hasNext()) {
                    double tmp = q.distanceTo(tree.get(iterLo.next()));
                    if (tmp < dist) {
                        dist = tmp;
                        pClosest = p;
                        qClosest = q;
                    }
                    i++;
                }

                tree.put(p.getY(), p);
            }

            double finalDist = pClosest.distanceTo(qClosest);

Edit: The pseudocode can be found here: http://pastebin.com/i0XbPp1a . It's based on notes taken from what my teacher wrote on the whiteboard.

Regarding results: Using the following points (X, Y): (0, 2) - (6, 67) - (43, 71) - (39, 107) - (189, 140)

I should get ~36, but I'm getting ~65.

Upvotes: 1

Views: 1065

Answers (1)

kraskevich
kraskevich

Reputation: 18556

I have already found several bugs in your code(I'm not sure that there are no others):

  1. What if several points have the same y coordinate? A TreeMap can hold only one point for each y value. Is that what you want?

  2. When you look at points below and above the current one, you compute a distance to the iterHi.next(): double tmp = p.distanceTo(tree.get(iterHi.next()));, but then assign qClosest to q. It is not correct(obviously, iterHi.next() and q is not the same point).

  3. In the second inner loop, you compute the distance from q to the element of the set: double tmp = q.distanceTo(tree.get(iterLo.next()));. It should be p instead.

I would also recommend maintaining a TreeSet of Point instead of using a TreeMap(they should compared by their y coordinate, of course).

Upvotes: 2

Related Questions