java - 改进 Mitchell 的最佳候选算法

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

感谢您的帮助。

Answer 1

Every run seems to produce the same type of points distribution and as you can see in the pictures above the points seems to be avoiding the central area. I can't understand why it is behaving this way. Can someone help me to understand this behavior?

正如在@pens-fan-69 answer 中指出的那样，基本上，如果您根据新点的选择来添加它与前一个点的距离(一个点的完全相反的恰好相反的是它本身)，您最终会在空间的边缘之间振荡。

Is there any other approach (or known algorithm) that significantly improve Mitchell's best candidate algorithm?

对于您描述的问题，我认为专门用于在 K 维空间数据建模并允许在占用空间中快速搜索给定新坐标的最近邻居的数据结构是有意义的。 <强> K-D Tree 是这样的结构:

In computer science, a k-d tree (short for k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space. k-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key (e.g. range searches and nearest neighbor searches). k-d trees are a special case of binary space partitioning trees.

通常，在构造 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));
    }
}