c# - 如何在针对任意区域加权的正方形中选择随机 float ？

Question

我有一个正方形，它在 x 和 y 中从 -1 到 1。

在这个正方形中选择一个随机点非常简单:

Random r = new Random();
float x = (float)Math.Round(r.NextDouble() * 2 - 1, 4);
float y = (float)Math.Round(r.NextDouble() * 2 - 1, 4);

这会以相同的概率在我的方 block 中给出任何点。

从可能性中删除正方形的一部分也很容易

Random r = new Random();
float x = (float)Math.Round(r.NextDouble() * 1.5 - 1, 4);
float y = (float)Math.Round(r.NextDouble() * 2 - 1, 4);

但我真正努力去做的是将随机权重分配给某个区域。具体来说，我希望此处突出显示的部分更有可能，其他所有内容(红色部分除外，它仍然是禁区)的概率应该较低，具体取决于与突出显示线的距离。最远的点应该有 0 的机会，其余的是现有的机会，当靠近线时更高，点正好在我的线上(因为我将它们四舍五入到特定的小数，线上有点)有最佳赔率。

对不起，丑陋的图片。这是我在绘画中所能做的最好的表达我的想法。

“最有可能”的区域是一个空心菱形(就是顶点为 (-1, 0)、(0, -0.5)、(1, 0)、(0, 0.5) 的区域，当然还有红色区域覆盖权重，因为它超出了限制。红色区域是任何 x > 0.5

有人知道怎么做吗？我在 C# 工作，但老实说，任何非深奥语言的算法都可以解决问题。我完全不知道如何继续。

一位评论者指出，将禁区添加到算法中会增加难度，但没有实际用处。

你可以假设我会在运行加权算法后自己处理禁区。因为它只有 25% 的面积，所以大多数时候，如果我只是这样做，它甚至不会对性能产生影响:

while (x > 0.5)
{
    runAlgorithmAgain();
}

因此您可以安全地忽略该部分以获得答案。

Answer 1

好的，这是我对这件事的看法。我想提出一些算法，如果有一些拒绝，可能会解决您的问题。请注意，由于需要接受-拒绝，它可能比您预期的要慢。

我们在单个象限(比如左下角)中采样，然后使用反射将点放入任何其他象限，然后拒绝红色区域点。

基本上，象限抽样是一个两步过程。首先，我们对边界线上的第一个位置进行采样。一旦我们在线上找到位置，我们就从钟形分布(例如高斯分布或拉普拉斯分布)中采样，并在与边界线方向正交的方向上移动点。

代码编译，但完全未经测试，所以请检查所有以数字开头的内容

using System;

namespace diamond
{
    class Program
    {
        public const double SQRT_5 = 2.2360679774997896964091736687313;

        public static double gaussian((double mu, double sigma) N, Random rng) {
            var phi = 2.0 * Math.PI * rng.NextDouble();
            var r   = Math.Sqrt( -2.0 * Math.Log(1.0 - rng.NextDouble()) );
            return N.mu + N.sigma * r * Math.Sin(phi);
        }

        public static double laplace((double mu, double sigma) L, Random rng) {
            var v = - L.sigma * Math.Log(1.0 - rng.NextDouble());
            return L.mu + ((rng.NextDouble() < 0.5) ? v : -v );
        }

        public static double sample_length(double lmax, Random rng) {
            return lmax * rng.NextDouble();
        }

        public static (double, double) move_point((double x, double y) pos, (double wx, double wy) dir, double l) {
            return (pos.x + dir.wx * l, pos.y + dir.wy * l);
        }

        public static (double, double) sample_in_quadrant((double x0, double y0) pos, (double wx, double wy) dir, double lmax, double sigma, Random rng) {
            while (true) {
                var l = sample_length(lmax, rng);
                (double x, double y) = move_point(pos, dir, l);

                var dort = (dir.wy, -dir.wx); // orthogonal to the line direction

                var s = gaussian((0.0, sigma), rng); // could be laplace instead of gaussian

                (x, y) = move_point((x, y), dort, s);
                if (x >= -1.0 && x <= 0.0 && y >= 0.0 && y <= 1.0) // acceptance/rejection
                    return (x, y);
            }
        }

        public static (double, double) sample_in_plane((double x, double y) pos, (double wx, double wy) dir, double lmax, double sigma, Random rng) {
            (double x, double y) = sample_in_quadrant(pos, dir, lmax, sigma, rng);

            if (rng.NextDouble() < 0.25)
                return (x, y);

            if (rng.NextDouble() < 0.5) // reflection over X
                return (x, -y);

            if (rng.NextDouble() < 0.75) // reflection over Y
                return (-x, y);

            return (-x, -y); // reflection over X&Y
        }

        static void Main(string[] args) {
            var rng = new Random(32345);

            var L = 0.5 * SQRT_5 + 0.5 / SQRT_5; // sampling length, BIGGER THAN JUST A SEGMENT IN THE QUADRANT
            (double x0, double y0) pos = (-1.0, 0.0); // initial position
            (double wx, double wy) dir = (2.0 / SQRT_5, 1.0 / SQRT_5); // directional cosines, wx*wx + wy*wy = 1
            double sigma = 0.2; // that's a value to play with

            // last rejection stage
            (double x, double y) pt;
            while(true) {
                pt = sample_in_plane(pos, dir, L, sigma, rng);

                if (pt.x < 0.5) // reject points in the red area, accept otherwise
                    break;
            }
            Console.WriteLine(String.Format("{0} {1}", pt.x, pt.y));
        }
    }
}