最近点对算法

6

我正在尝试实现一个比二次算法更好的简化版本。我的想法基本上是仅按x坐标对点进行排序并从那里解决它。一旦我按x坐标对点数组进行排序，我想遍历数组并跳过距离大于我取出的前两个点的点。

例如，我的当前最小距离= x;如果我正在查看的两个点对的距离>x（仅通过其x coord dist），我会忽略该点并在数组中向后移动。我已经有了想法，但我在如何实际实现它方面有些困惑（特别是条件部分）。我有一个函数，根据它们的x坐标返回两个点之间的距离。由于我希望忽略距离太远的点并仍然填充包含每个i（即我正在查看的当前点）的最近点答案的数组，因此对我的循环实际编写条件感到困惑。任何提示或指导都将不胜感激。我对编码算法的知识不是很了解，因此这非常令人沮丧。

这是我的代码的一部分：

for (i = 0; i < numofmypoints; i++)
        {
            for (int j = i + 1; (j < numpofmypoints) && ((inputpoints[j].x - inputpoints[i].x) < currbest); j++ )
            {
                currdist = Auxilary.distbyX(inputpoints[i],inputpoints[j]);

                if (currdist < bestdist) 
                {
                 closest[i] = j;
                 bestdist = currdist;

                }
            }
        }

distbyX是我的函数，它只返回两个点之间的距离。

谢谢！

- Paul

@Paul：你经常需要这样做吗？把你的点存储在“四叉树”中不是更有帮助吗？http://en.wikipedia.org/wiki/Quadtree - TacticalCoder

2

请注意，使用这种算法可能会比朴素算法获得更好的性能，但时间复杂度仍然是O(n^2)。 - ARRG

你的代码中为什么有 currbest 和 bestdist？它们之间有什么区别？ - Ishtar

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- tom · Accepted Answer

使用KD-Tree的快速算法
该算法创建一个kd-tree，然后为每个点找到最近的对应点。创建kd-tree的时间复杂度是O(n log²n)，查找点的最近邻居的时间复杂度是O(logn)。值得一提的是，维基百科在一篇文章中详细介绍了如何创建kd-tree以及如何使用它们来查找最近的邻居。

import java.util.*;

public class Program
{
    public static void main(String[] args)
    {
        List<Point> points = generatePoints();
        Point[] closest = new Point[points.size()];

        KDTree tree = new KDTree(points, 0); // WILL MODIFY 'points'

        for (int i = 0; i < points.size(); i++)
        {
            closest[i] = tree.findClosest(points.get(i));
        }

        for (int i = 0; i < points.size(); i++)
        {
            System.out.println(points.get(i) + " is closest to " + closest[i]);
        }
    }

    private static List<Point> generatePoints()
    {
        ArrayList<Point> points = new ArrayList<Point>();
        Random r = new Random();

        for (int i = 0; i < 1000; i++)
        {
            points.add(new Point(r.nextInt() % 1000, r.nextInt() % 1000));
        }

        return points;
    }
}

class Point
{
    public static final Point INFINITY
        = new Point(Double.POSITIVE_INFINITY,
                    Double.POSITIVE_INFINITY);

    public double[] coord; // coord[0] = x, coord[1] = y

    public Point(double x, double y)
    {
        coord = new double[] { x, y };
    }

    public double getX() { return coord[0]; }
    public double getY() { return coord[1]; }

    public double distance(Point p)
    {
        double dX = getX() - p.getX();
        double dY = getY() - p.getY();
        return Math.sqrt(dX * dX + dY * dY);
    }

    public boolean equals(Point p)
    {
        return (getX() == p.getX()) && (getY() == p.getY());
    }

    public String toString()
    {
        return "(" + getX() + ", " + getY() + ")";
    }

    public static class PointComp implements Comparator<Point>
    {
        int d; // the dimension to compare in (0 => x, 1 => y)

        public PointComp(int dimension)
        {
            d = dimension;
        }

        public int compare(Point a, Point b)
        {
            return (int) (a.coord[d] - b.coord[d]);
        }
    }
}

class KDTree
{
    // 2D k-d tree
    private KDTree childA, childB;
    private Point point; // defines the boundary
    private int d; // dimension: 0 => left/right split, 1 => up/down split

    public KDTree(List<Point> points, int depth)
    {
        childA = null;
        childB = null;
        d = depth % 2;

        // find median by sorting in dimension 'd' (either x or y)
        Comparator<Point> comp = new Point.PointComp(d);
        Collections.sort(points, comp);

        int median = (points.size() - 1) / 2;
        point = points.get(median);

        // Create childA and childB recursively.
        // WARNING: subList() does not create a true copy,
        // so the original will get modified.
        if (median > 0)
        {
            childA = new KDTree(
                points.subList(0, median),
                depth + 1);
        }
        if (median + 1 < points.size())
        {
            childB = new KDTree(
                points.subList(median + 1, points.size()),
                depth + 1);
        }
    }

    public Point findClosest(Point target)
    {
        Point closest = point.equals(target) ? Point.INFINITY : point;
        double bestDist = closest.distance(target);
        double spacing = target.coord[d] - point.coord[d];
        KDTree rightSide = (spacing < 0) ? childA : childB;
        KDTree otherSide = (spacing < 0) ? childB : childA;

        /*
         * The 'rightSide' is the side on which 'target' lies
         * and the 'otherSide' is the other one. It is possible
         * that 'otherSide' will not have to be searched.
         */

        if (rightSide != null)
        {
            Point candidate = rightSide.findClosest(target);
            if (candidate.distance(target) < bestDist)
            {
                closest = candidate;
                bestDist = closest.distance(target);
            }
        }

        if (otherSide != null && (Math.abs(spacing) < bestDist))
        {
            Point candidate = otherSide.findClosest(target);
            if (candidate.distance(target) < bestDist)
            {
                closest = candidate;
                bestDist = closest.distance(target);
            }
        }

        return closest;
    }
}

问题代码修复
如果你真的不担心复杂度，那么你的代码唯一的问题就是你只向前查找而没有往后查找。只需复制内部循环并使 j 从 (i - 1) 到 0 即可：

Point[] points = sort(input());
int[] closest = new int[points.length];

for (int i = 0; i < points.length; i++)
{
    double bestdist = Double.POSITIVE_INFINITY;

    for (int j = i + 1; (j < points.length) && ((points[j].x - points[i].x) < bestdist); j++ )
    {
        double currdist = dist(points[i], points[j]);

        if (currdist < bestdist)
        {
            closest[i] = j;
            bestdist = currdist;
        }
    }
    for (int j = i - 1; (j >= 0) && ((points[i].x - points[j].x) < bestdist); j-- )
    {
        double currdist = dist(points[i], points[j]);

        if (currdist < bestdist)
        {
            closest[i] = j;
            bestdist = currdist;
        }
    }
}