1

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

我已经使用 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。

4

1 回答 1

2

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

  1. 如果几个点具有相同的 y 坐标怎么办？对于每个 y 值， ATreeMap只能保留一个点。那是你要的吗？

  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。

我还建议维护 a TreeSetofPoint而不是使用 a TreeMap（当然，它们应该通过它们的 y 坐标进行比较）。

于 2015-01-09T11:51:24.800 回答