改进米切尔最佳候选算法

Question

我已成功实现了Mitchell的最佳候选算法。Mitchell的最佳候选算法通过创建k个候选样本并选择最佳的k个样本来生成新的随机样本。这里“最佳”样本的定义是与之前样本最远的样本。该算法近似于泊松盘采样，产生比均匀随机采样更自然的外观（更好的蓝噪声光谱特性）。

我正在尝试改进它，特别是在速度方面。因此，我想到的第一个想法是将候选样本仅与最后添加的元素进行比较，而不是将它们与整个以前的样本进行比较。这会偏向泊松盘采样，但可能会产生一些有趣的结果。

以下是我的实现的主要部分。

public class MitchellBestCandidateII extends JFrame {

    private List<Point> mitchellPoints = new ArrayList<Point>();
    private Point currentPoint;
    private int currentPointIndex =0;
    private boolean isBeginning = true;
    private Point[] candidatesBunch = new Point[MAX_CANDIDATES_AT_TIME];

    public MitchellBestCandidateII() {      
        computeBestPoints();
        initComponents();
    }

computeBestPoints方法在计算点时与Mitchell算法不同，它仅将候选点与上一个添加的点进行比较，而不是将其与整个样本进行比较。

    private void computeBestPoints() {

        do {
            if (isBeginning) {
                currentPoint = getRandomPoint();
                mitchellPoints.add(currentPoint);
                isBeginning = false;
                currentPointIndex = 0;              
            } 

            setCandidates();
            Point bestCandidate = pickUpCandidateFor(currentPoint);
            mitchellPoints.add(bestCandidate);
            currentPoint = bestCandidate;
            currentPointIndex++;    
        } while (currentPointIndex <MAX_NUMBER_OF_POINTS);

    }

    private Point pickUpCandidateFor(Point p) {
        double biggestDistance = 0.0D;
        Point  result = null;
        for (int i = 0; i < MAX_CANDIDATES_AT_TIME; i++) {

            double d = distanceBetween(p, candidatesBunch[i]);
            if (biggestDistance < d) {
                biggestDistance = d;
                result = candidatesBunch[i];

            }
        }

        return result;
    }

setCandidates方法会生成随机的候选项，只有其中一个会成为样本的一部分，其余的将被舍弃。

    private void setCandidates() {
        for (int i = 0; i < MAX_CANDIDATES_AT_TIME; i++) {
            candidatesBunch[i] = getRandomPoint();
        }
    }


    private Point getRandomPoint() {
        return new Point(Randomizer.getHelper().nextInt(SCREEN_WIDTH),     Randomizer.getHelper().nextInt(SCREEN_HEIGHT));

    }

initComponents是设置JFrame和JPanel的方法，并将要绘制的点列表传递给JPanel。

    private void initComponents() {
        this.setSize(SCREEN_WIDTH,SCREEN_HEIGHT);
        PaintPanel panel = new PaintPanel(mitchellPoints);
        panel.setPreferredSize(new Dimension(SCREEN_WIDTH,SCREEN_HEIGHT));
        this.setContentPane(panel);
        this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

    }

distanceBetween方法计算两点之间的距离，应用了数学公式。

    public double distanceBetween(Point p1, Point p2) {

        double deltaX = p1.getX() - p2.getX();
        double deltaY = p1.getY() - p2.getY();
        double deltaXSquare = Math.pow(deltaX, 2);
        double deltaYSquare = Math.pow(deltaY, 2);

        return Math.sqrt(deltaXSquare + deltaYSquare);

    }

}

下面是执行的示意图：

每次运行似乎都会产生相同类型的点分布，正如您在上面的图片中所看到的，这些点似乎会避开中心区域。我不明白为什么会出现这种情况。有人能帮我理解这种行为吗？是否有其他方法（或已知算法）可以显着改进Mitchell的最佳候选算法？我的Mitchell最佳候选算法实现（不是上面的代码）正在Code Review上进行审查。

感谢您的帮助。

- alainlompo

---

一个相当好的解决方案是构建一个K-D Tree，而不是使用当前的列表，其中K在这种情况下为2，因为您正在使用2D点。 K-D树允许O(log n)插入和搜索树中最近的点。如果我有时间，明天我会添加一个答案，其中包括应用于此最佳候选算法的示例实现。 - Alex

Answer 1

每次运行似乎都会产生相同类型的点分布，如上图所示，点似乎避开了中心区域。我不明白为什么会出现这种情况。有人能帮我理解这种行为吗？

正如 @pens-fan-69 answer 中已经指出的那样，如果您基于新添加的点与前一个点的距离来选择要添加的新点，则最终会在空间的边缘之间振荡（完全相反的点的确切相反是它本身）。

有没有其他方法（或已知算法）可以显着改进米切尔最佳候选算法？

对于您描述的问题，我认为一种专门用于模拟K维空间数据并允许快速搜索占用空间以查找给定新坐标的最近邻居的数据结构是有意义的。K-D树就是这样的结构：K-D Tree。

在计算机科学中，k-d树（k维树）是一种用于组织k维空间中的点的空间划分数据结构。 k-d树是几个应用程序的有用数据结构，例如涉及多维搜索键（例如范围搜索和最近邻搜索）的搜索。 k-d树是二叉空间划分树的特殊情况。 通常，在构建K-D树时，使用一组（排序）数据点，并沿着其中一个维度轴使用该轴上其余点的中位数值递归地划分（分区）搜索空间。 我添加了一个非常简单且天真的实现，其中仅包含在您的问题中使用的操作，并且不执行插入的任何树重新平衡。 由于插入的点的特定性质（与现有点的最大距离），因此这似乎运行得相当不错，请参见下图（评估500、每轮10个候选项，总共5000、1000个点分别用于左侧和右侧图像）。

这段代码是用C#编写的，因为我已经有了一些可用的部分，但将其翻译成Java应该非常简单。我省略了Points类的代码。

// A very naive partial K-D Tree implementation with K = 2 for Points.
public class TwoDTree
{
    private Node _root;

    public void Insert(Point coordinate)
    {
        _root = Node.Insert(coordinate, _root, 0);
    }

    public Point FindNearest(Point to, out double bestDistance)
    {
        bestDistance = double.MaxValue;
        var best = Node.FindNearest(to, _root, 0, null, ref bestDistance);
        return best != null ? best.Coordinate : null;
    }

    public IEnumerable<Point> GetPoints()
    {
        if (_root != null)
            return _root.GetPoints();
        return Enumerable.Empty<Point>();
    }

    private class Node
    {
        private Node _left;
        private Node _right;

        public Node(Point coord)
        {
            Coordinate = coord;
        }

        public readonly Point Coordinate;

        public IEnumerable<Point> GetPoints()
        {
            if (_left != null)
            {
                foreach (var pt in _left.GetPoints())
                    yield return pt;
            }
            yield return Coordinate;

            if (_right != null)
            {
                foreach (var pt in _right.GetPoints())
                    yield return pt;
            }
        }

        // recursive insert (non-balanced).
        public static Node Insert(Point coord, Node root, int level)
        {
            if (root == null)
                return new Node(coord);

            var compareResult = ((level % 2) == 0)
                ? coord.X.CompareTo(root.Coordinate.X)
                : coord.Y.CompareTo(root.Coordinate.Y);

            if (compareResult > 0)
                root._right = Insert(coord, root._right, level + 1);
            else
                root._left = Insert(coord, root._left, level + 1);
            return root;
        }

        public static Node FindNearest(Point coord, Node root, int level, Node best, ref double bestDistance)
        {
            if (root == null)
                return best;

            var axis_dif = ((level % 2) == 0)
                ? coord.X - root.Coordinate.X
                : coord.Y - root.Coordinate.Y;

            // recurse near & maybe far as well
            var near = axis_dif <= 0.0d ? root._left : root._right;
            best = Node.FindNearest(coord, near, level + 1, best, ref bestDistance);
            if (axis_dif * axis_dif < bestDistance)
            {
                var far = axis_dif <= 0.0d ? root._right : root._left;
                best = Node.FindNearest(coord, far, level + 1, best, ref bestDistance);
            }

            // do we beat the old best.
            var dist = root.Coordinate.DistanceTo(coord);
            if (dist < bestDistance)
            {
                bestDistance = dist;
                return root;
            }
            return best;
        }
    }
}

// Mitchell Best Candidate algorithm, using the K-D Tree.
public class MitchellBestCandidate
{
    private const int MaxX = 420;
    private const int MaxY = 320;
    private readonly int _maxCandidates;
    private readonly int _maxPoints;
    private readonly Random _rnd;
    private readonly TwoDTree _tree = new TwoDTree();

    public MitchellBestCandidate(int maxPoints, int maxCandidatesPerRound)
    {
        _maxPoints = maxPoints;
        _maxCandidates = maxCandidatesPerRound;
        _rnd = new Random();
    }

    public IEnumerable<Point> CurrentPoints
    {
        get { return _tree.GetPoints(); }
    }

    public void Generate()
    {
        _tree.Insert(GetRandomPoint(_rnd, MaxX, MaxY));
        for (var i = 1; i < _maxPoints; i++)
        {
            var bestDistance = double.MinValue;
            var bestCandidate = default(Point);
            for (var ci = 0; ci < _maxCandidates; ci++)
            {
                var distance = default(double);
                var candidate = GetRandomPoint(_rnd, MaxX, MaxY);
                var nearest = _tree.FindNearest(candidate, out distance);
                if (distance > bestDistance)
                {
                    bestDistance = distance;
                    bestCandidate = candidate;
                }
            }
            _tree.Insert(bestCandidate);
        }
    }

    private static Point GetRandomPoint(Random rnd, int maxX, int maxY)
    {
        return new Point(rnd.Next(maxX), rnd.Next(maxY));
    }
}

- Alex

---

优秀的回答，Alex！ - pens-fan-69

Answer 2

我认为它避开中心区域的原因是因为你只考虑了最近选择的点。因此，在第一个点被选择后，"最远距离"候选点将是最靠近区域最远边缘的候选点。如果你不想让分布在边缘周围避开中心，请考虑之前选择的点。也许只考虑一组有限的先前选择的点？

- pens-fan-69

---

我想到了一个问题，如果你使用一组有限的预先选定的点，最好的选择可能是随机选择。 - pens-fan-69

谢谢，这听起来很棒。你的意思是，一方面我可以将候选人与不止一个点（但有限的集合）进行比较，另一方面我不应该仅选择最后添加的点，而应随机选择几个：这值得一试。 - alainlompo

Answer 3

我建议看一下Bridson在Siggraph 2007上发表的“任意维度快速泊松盘采样”论文。我认为它更快且产生的采样效果更好。

- Gab