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