Java 中使用扫描线算法的最近点对

Question

首先；我这样做是为了学校的作业，这就是我使用扫描线算法的原因。我基于我老师给出的伪代码。

我已经使用 TreeMap 而不是平衡二叉搜索树完成了自己的实现，有人告诉我它可以提供相同的功能。（虽然不知道这是不是真的？）

但是我没有得到正确的最终结果，我真的不知道为什么。我一直在盯着自己看。

下面是我执行实际计算的代码部分。我省略了点列表的创建和其他不重要的东西。

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

编辑：伪代码可以在这里找到：http://pastebin.com/i0XbPp1a。它基于我的老师在白板上写的笔记。

关于结果：使用以下点 (X, Y)： (0, 2) - (6, 67) - (43, 71) - (39, 107) - (189, 140)

我应该得到 ~36，但我得到了 ~65。

Answer 1

我已经在你的代码中发现了几个错误（我不确定没有其他错误）：

如果几个点的y坐标相同怎么办？ TreeMap 每个 y 值只能保存一个点。这就是你想要的吗？
当您查看当前点下方和上方的点时，您计算到 iterHi.next() 的距离：double tmp = p.distanceTo(tree.get(iterHi.next()));，然后将 qClosest 分配给 q。这是不正确的（很明显，iterHi.next()和q不是同一个点）。
在第二个内部循环中，计算从 q 到集合元素 double tmp = q.distanceTo(tree.get(iterLo.next())); 的距离。应该是p。

我还建议保持 Point 的 TreeSet 而不是使用 TreeMap（当然，它们应该通过 y 坐标进行比较）。

Java 中使用扫描线算法的最近点对

Closest pair of points using sweep line algorithm in Java

java

algorithm

closest-points