java - 在 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

我已经在你的代码中发现了几个错误(我不确定没有其他错误):

1. 如果多个点具有相同的 y 坐标怎么办？ TreeMap 只能为每个 y 值保存一个点。这是你想要的吗？

2. 当您查看当前点下方和上方的点时，您计算到 iterHi.next() 的距离:double tmp = p.distanceTo(tree.get (iterHi.next()));，然后将 qClosest 赋值给 q。不正确(很明显，iterHi.next()和q不是同一个点)。

3. 在第二个内部循环中，计算从 q 到集合元素的距离:double tmp = q.distanceTo(tree.get(iterLo.next( )));。它应该是 p。

我还建议维护 Point 的 TreeSet 而不是使用 TreeMap(当然，它们应该通过 y 坐标进行比较) .