math - एक सर्कल के भीतर एक यादृच्छिक बिंदु उत्पन्न करें(समान रूप से)




random geometry (12)

1) -1 और 1 के बीच एक यादृच्छिक एक्स चुनें।

var X:Number = Math.random() * 2 - 1;

2) सर्कल फॉर्मूला का उपयोग करके, वाई के अधिकतम और न्यूनतम मानों की गणना करें कि एक्स और 1 का त्रिज्या:

var YMin:Number = -Math.sqrt(1 - X * X);
var YMax:Number = Math.sqrt(1 - X * X);

3) उन चरम सीमाओं के बीच एक यादृच्छिक वाई चुनें:

var Y:Number = Math.random() * (YMax - YMin) + YMin;

4) अंतिम स्थान में अपने स्थान और त्रिज्या मूल्य शामिल करें:

var finalX:Number = X * radius + pos.x;
var finalY:Number = Y * radois + pos.y;

मुझे त्रिज्या आर के एक सर्कल के भीतर एक समान यादृच्छिक बिंदु उत्पन्न करने की आवश्यकता है।

मुझे एहसास है कि अंतराल में एक समान यादृच्छिक कोण चुनकर [0 ... 2π), और अंतराल में समान रूप से यादृच्छिक त्रिज्या (0 ... आर ) मैं केंद्र के प्रति अधिक अंक के साथ समाप्त होता हूं, क्योंकि दो दिए गए त्रिज्या, छोटे त्रिज्या में अंक बड़े त्रिज्या के बिंदुओं के मुकाबले एक-दूसरे के करीब होंगे।

मुझे इस पर एक ब्लॉग प्रविष्टि मिली लेकिन मुझे उनकी तर्क समझ में नहीं आया। मुझे लगता है कि यह सही है, लेकिन मैं वास्तव में समझना चाहूंगा कि वह कहां से मिलता है (2 / आर 2 ) × आर और वह अंतिम समाधान कैसे प्राप्त करता है।

अस्वीकृति नमूनाकरण के संबंध में: मैं आर × आर वर्ग के भीतर एक यादृच्छिक बिंदु उत्पन्न कर सकता हूं जब तक कि मुझे सर्कल में कोई नहीं मिलता। इस दृष्टिकोण में स्पष्ट ड्रॉ-बैक है कि यह समाप्ति की गारंटी प्रदान नहीं करता है (भले ही यह बहुत अधिक संभावना है कि यह लंबे समय तक चल रहा है)।


आइए आर्किमिडीज की तरह इस तरह से संपर्क करें।

हम त्रिभुज एबीसी में समान रूप से एक बिंदु कैसे उत्पन्न कर सकते हैं, जहां | एबी | = | बीसी | आइए एक समांतरोग्राम एबीसीडी तक विस्तार करके इसे आसान बनाएं। एबीसीडी में समान रूप से अंक उत्पन्न करना आसान है। हम समान रूप से बीसी पर एबी और वाई पर एक यादृच्छिक बिंदु एक्स चुनते हैं और जेड चुनते हैं कि एक्सबीवाईजेड समानांतर है। मूल त्रिकोण में एक समान रूप से चुना गया बिंदु प्राप्त करने के लिए हम एसीसी में एसी के साथ एबीसी में दिखाई देने वाले किसी भी बिंदु को बस फोल्ड करते हैं।

अब एक सर्कल पर विचार करें। सीमा में हम इसके बारे में सोच सकते हैं क्योंकि अनगिनत कई आइसोसेल त्रिशंकु एबीसी मूल के साथ बी और परिधि पर ए और सी एक दूसरे के करीब गायब हो जाते हैं। हम एक कोण थेटा चुनकर बस इन त्रिकोणों में से एक चुन सकते हैं। तो अब हमें स्लीवर एबीसी में एक बिंदु चुन कर केंद्र से दूरी उत्पन्न करने की जरूरत है। फिर, एबीसीडी तक बढ़ाएं, जहां डी अब सर्कल सेंटर से त्रिज्या से दोगुना है।

एबीसीडी में एक यादृच्छिक बिंदु चुनना उपर्युक्त विधि का उपयोग करना आसान है। एबी पर एक यादृच्छिक बिंदु उठाओ। समान रूप से बीसी पर एक यादृच्छिक बिंदु उठाओ। अर्थात। यादृच्छिक संख्या x और y की एक जोड़ी को समान रूप से [0, आर] पर केंद्र से दूरी प्रदान करें। हमारा त्रिकोण एक पतला sliver है इसलिए एबी और बीसी अनिवार्य रूप से समानांतर हैं। तो बिंदु जेड मूल से दूरी x + y दूरी है। यदि एक्स + वाई> आर हम वापस फोल्ड करते हैं।

R = 1 के लिए पूर्ण एल्गोरिदम यहां दिया गया है। मुझे उम्मीद है कि आप सहमत हैं कि यह बहुत आसान है। यह ट्रिग का उपयोग करता है, लेकिन आप इस बात पर गारंटी दे सकते हैं कि कितना समय लगेगा, और अस्वीकृति नमूनाकरण के विपरीत, कितनी random() कॉल की आवश्यकता है।

t = 2*pi*random()
u = random()+random()
r = if u>1 then 2-u else u
[r*cos(t), r*sin(t)]

यहां यह गणित में है।

f[] := Block[{u, t, r},
  u = Random[] + Random[];
  t = Random[] 2 Pi;
  r = If[u > 1, 2 - u, u];
  {r Cos[t], r Sin[t]}
]

ListPlot[Table[f[], {10000}], AspectRatio -> Automatic]


एक प्रोग्रामर समाधान:

  • थोड़ा नक्शा बनाएं (बूलियन मानों का एक मैट्रिक्स)। यह जितना बड़ा हो उतना बड़ा हो सकता है।
  • उस बिट मैप में एक सर्कल बनाएं।
  • सर्कल के बिंदुओं की एक लुकअप टेबल बनाएं।
  • इस लुकअप टेबल में एक यादृच्छिक अनुक्रमणिका चुनें।
const int RADIUS = 64;
const int MATRIX_SIZE = RADIUS * 2;

bool matrix[MATRIX_SIZE][MATRIX_SIZE] = {0};

struct Point { int x; int y; };

Point lookupTable[MATRIX_SIZE * MATRIX_SIZE];

void init()
{
  int numberOfOnBits = 0;

  for (int x = 0 ; x < MATRIX_SIZE ; ++x)
  {
    for (int y = 0 ; y < MATRIX_SIZE ; ++y)
    {
      if (x * x + y * y < RADIUS * RADIUS) 
      {
        matrix[x][y] = true;

        loopUpTable[numberOfOnBits].x = x;
        loopUpTable[numberOfOnBits].y = y;

        ++numberOfOnBits;

      } // if
    } // for
  } // for
} // ()

Point choose()
{
  int randomIndex = randomInt(numberOfBits);

  return loopUpTable[randomIndex];
} // ()

बिटमैप तर्क के स्पष्टीकरण के लिए केवल जरूरी है। यह बिटमैप के बिना कोड है:

const int RADIUS = 64;
const int MATRIX_SIZE = RADIUS * 2;

struct Point { int x; int y; };

Point lookupTable[MATRIX_SIZE * MATRIX_SIZE];

void init()
{
  int numberOfOnBits = 0;

  for (int x = 0 ; x < MATRIX_SIZE ; ++x)
  {
    for (int y = 0 ; y < MATRIX_SIZE ; ++y)
    {
      if (x * x + y * y < RADIUS * RADIUS) 
      {
        loopUpTable[numberOfOnBits].x = x;
        loopUpTable[numberOfOnBits].y = y;

        ++numberOfOnBits;
      } // if
    } // for
  } // for
} // ()

Point choose()
{
  int randomIndex = randomInt(numberOfBits);

  return loopUpTable[randomIndex];
} // ()

एक सर्कल में क्षेत्र तत्व डीए = आरडीआर * डीएफआई है। उस अतिरिक्त कारक ने आपके विचार को यादृच्छिक रूप से ar और phi चुनने के लिए नष्ट कर दिया। जबकि फाई को फ्लैट वितरित किया जाता है, आर नहीं है, लेकिन 1 / आर में फ्लैट (यानी आप "बैल की आंख" की तुलना में सीमा को मारने की अधिक संभावना रखते हैं)।

इसलिए सर्कल पर समान रूप से वितरित अंक उत्पन्न करने के लिए एक फ्लैट वितरण से 1 / आर वितरण से आरआई चुनें।

वैकल्पिक रूप से मेहरदद द्वारा प्रस्तावित मोंटे कार्लो विधि का उपयोग करें।

संपादित करें

1 / आर में एक यादृच्छिक आर फ्लैट लेने के लिए आप अंतराल [1 / आर, अनंतता] से एक यादृच्छिक एक्स चुन सकते हैं और आर = 1 / एक्स की गणना कर सकते हैं। फिर 1 / आर में फ्लैट वितरित किया जाता है।

यादृच्छिक फाई की गणना करने के लिए अंतराल से एक यादृच्छिक एक्स चुनें [0, 1] और phi = 2 * pi * x की गणना करें।


त्रिज्या rad एक सर्कल से अंक यादृच्छिक बिंदु उत्पन्न करने के लिए मेरा पायथन कोड यहां दिया गया है:

import matplotlib.pyplot as plt
import numpy as np
rad = 10
num = 1000

t = np.random.uniform(0.0, 2.0*np.pi, num)
r = rad * np.sqrt(np.random.uniform(0.0, 1.0, num))
x = r * np.cos(t)
y = r * np.sin(t)

plt.plot(x, y, "ro", ms=1)
plt.axis([-15, 15, -15, 15])
plt.show()

त्रिज्या के बीच एक रैखिक संबंध है और त्रिज्या के "बिंदु" के बिंदुओं की संख्या है, इसलिए उसे त्रिज्या वितरण का उपयोग करने की आवश्यकता है जो r अनुपात में त्रिज्या r पास डेटा बिंदुओं की संख्या भी बनाता है।


निष्क्रिय समाधान काम नहीं करने का कारण यह है कि यह सर्कल केंद्र के करीब बिंदुओं के लिए उच्च संभावना घनत्व देता है। दूसरे शब्दों में त्रिज्या आर / 2 में सर्कल में चयनित बिंदु प्राप्त करने की संभावना आर / 2 है, लेकिन इसमें क्षेत्र (अंक की संख्या) पीआई * आर ^ 2/4 है।

इसलिए हम एक त्रिज्या संभावना घनत्व चाहते हैं कि निम्नलिखित संपत्ति हो:

किसी दिए गए आर के लिए छोटे या बराबर त्रिज्या चुनने की संभावना त्रिज्या आर के साथ सर्कल के क्षेत्र के लिए आनुपातिक होना चाहिए। (क्योंकि हम अंक पर एक समान वितरण करना चाहते हैं और बड़े क्षेत्रों का मतलब अधिक अंक है)

दूसरे शब्दों में हम सर्कल के समग्र क्षेत्र के अपने हिस्से के बराबर होने के लिए [0, आर] के बीच त्रिज्या चुनने की संभावना चाहते हैं। कुल सर्कल क्षेत्र पीआई * आर ^ 2 है, और त्रिज्या आर के साथ सर्कल का क्षेत्र पीआई * आर ^ 2 है। इस प्रकार हम [0, आर] होना (पीआई * आर ^ 2) / (पीआई * आर ^ 2) = आर ^ 2 / आर ^ 2 के बीच त्रिज्या चुनने की संभावना चाहते हैं।

अब गणित आता है:

[0, आर] के बीच त्रिज्या चुनने की संभावना 0 से आर तक पी (आर) डॉ के अभिन्न अंग है (यह इसलिए है क्योंकि हम छोटी त्रिज्या की सभी संभावनाओं को जोड़ते हैं)। इस प्रकार हम अभिन्न (पी (आर) डॉ) चाहते हैं = आर ^ 2 / आर ^ 2। हम स्पष्ट रूप से देख सकते हैं कि आर ^ 2 स्थिर है, इसलिए हमें बस इतना करना है कि कौन सा पी (आर), एकीकृत होने पर हमें आर ^ 2 की तरह कुछ मिल जाएगा। जवाब स्पष्ट रूप से आर * निरंतर है। अभिन्न (आर * निरंतर डॉ) = आर ^ 2/2 * निरंतर। यह आर ^ 2 / आर ^ 2 के बराबर होना चाहिए, इसलिए निरंतर = 2 / आर ^ 2। इस प्रकार आपके पास संभाव्यता वितरण पी (आर) = आर * 2 / आर ^ 2 है

नोट: समस्या के बारे में सोचने का एक और अधिक सहज तरीका यह कल्पना करना है कि आप त्रिज्या आरए संभाव्यता घनत्व के प्रत्येक चक्र को इसके परिधि पर होने वाले अंकों की संख्या के अनुपात के बराबर देने की कोशिश कर रहे हैं। इस प्रकार त्रिज्या आर वाले एक सर्कल में इसकी परिधि पर 2 * पीआई * आर "अंक" होंगे। अंक की कुल संख्या पीआई * आर ^ 2 है। इस प्रकार आपको सर्कल आरए संभावना (2 * पीआई * आर) / (पीआई * आर ^ 2) = 2 * आर / आर ^ 2 के बराबर देना चाहिए। यह समझना और अधिक सहज ज्ञान युक्त है, लेकिन यह गणितीय ध्वनि के रूप में काफी नहीं है।


मुझे अभी भी सटीक '(2 / आर 2) × आर' के बारे में निश्चित नहीं है, लेकिन स्पष्ट है कि दिए गए यूनिट 'डॉ' में वितरित किए जाने वाले अंकों की संख्या यानी आर में वृद्धि आर 2 के अनुपात में नहीं होगी और आर नहीं।

इस तरह से जांचें ... कुछ कोण थेटा पर बिंदुओं की संख्या और आर (0.1r से 0.2r) के बीच यानी आर के अंश और आर (0.6r से 0.7r) के बीच बिंदुओं की संख्या बराबर होगी यदि आप मानक पीढ़ी का उपयोग करते हैं, चूंकि अंतर दो अंतराल के बीच केवल 0.1r है। लेकिन चूंकि अंक (0.6r से 0.7r) के बीच कवर क्षेत्र 0.1r से 0.2r के बीच कवर क्षेत्र से काफी बड़ा होगा, इसलिए बड़े क्षेत्र में अंकों की समान संख्या कम हो जाएगी, यह मुझे लगता है कि आप पहले से ही जानते हैं, तो फ़ंक्शन यादृच्छिक बिंदु उत्पन्न करने के लिए रैखिक लेकिन वर्गिक नहीं होना चाहिए, (क्योंकि दिए गए इकाई 'डॉ' में वितरित किए जाने वाले बिंदुओं की संख्या यानी आर में वृद्धि आर 2 के अनुपात में नहीं होगी और आर नहीं), इसलिए इस मामले में यह विपरीत होगा वर्गिक, क्योंकि हमारे अंतराल में डेल्टा (0.1r) है, कुछ फ़ंक्शन का वर्ग होना चाहिए ताकि यह अंक की रैखिक पीढ़ी के लिए बीज मूल्य के रूप में कार्य कर सके (बाद में, यह बीज पाप और कॉस फ़ंक्शन में रैखिक रूप से उपयोग किया जाता है), इसलिए हम पता है, डॉ वर्गवार मूल्य होना चाहिए और इस बीज को वर्गबद्ध बनाने के लिए, हमें इस मूल्य को आर के रूट रूट से उत्पन्न करने की आवश्यकता है, मुझे उम्मीद है कि इससे थोड़ा और स्पष्ट हो जाएगा।


मुझे लगता है कि इस मामले में ध्रुवीय निर्देशांक का उपयोग समस्या को जटिल करने का एक तरीका है, यदि आप 2 आर-पक्षीय वर्ग में यादृच्छिक बिंदु चुनते हैं तो यह बहुत आसान होगा और फिर अंक (x, y) का चयन करें जैसे x ^ 2 + y ^ 2 <= आर ^ 2।


मैंने एक बार इस विधि का उपयोग किया: यह पूरी तरह से अप्रचलित हो सकता है (यानी यह बिंदु की एक सरणी का उपयोग करता है ताकि बड़े सर्कल के लिए इसका उपयोग करने योग्य हो) लेकिन यादृच्छिक वितरण पर्याप्त प्रदान करता है। आप मैट्रिक्स के निर्माण को छोड़ सकते हैं और यदि आप चाहें तो सीधे आकर्षित कर सकते हैं। विधि सर्कल के अंदर आने वाले आयत में सभी बिंदुओं को यादृच्छिक बनाना है।

bool[,] getMatrix(System.Drawing.Rectangle r) {
    bool[,] matrix = new bool[r.Width, r.Height];
    return matrix;
}

void fillMatrix(ref bool[,] matrix, Vector center) {
    double radius = center.X;
    Random r = new Random();
    for (int y = 0; y < matrix.GetLength(0); y++) {
        for (int x = 0; x < matrix.GetLength(1); x++)
        {
            double distance = (center - new Vector(x, y)).Length;
            if (distance < radius) {
                matrix[x, y] = r.NextDouble() > 0.5;
            }
        }
    }

}

private void drawMatrix(Vector centerPoint, double radius, bool[,] matrix) {
    var g = this.CreateGraphics();

    Bitmap pixel = new Bitmap(1,1);
    pixel.SetPixel(0, 0, Color.Black);

    for (int y = 0; y < matrix.GetLength(0); y++)
    {
        for (int x = 0; x < matrix.GetLength(1); x++)
        {
            if (matrix[x, y]) {
                g.DrawImage(pixel, new PointF((float)(centerPoint.X - radius + x), (float)(centerPoint.Y - radius + y)));
            }
        }
    }

    g.Dispose();
}

private void button1_Click(object sender, EventArgs e)
{
    System.Drawing.Rectangle r = new System.Drawing.Rectangle(100,100,200,200);
    double radius = r.Width / 2;
    Vector center = new Vector(r.Left + radius, r.Top + radius);
    Vector normalizedCenter = new Vector(radius, radius);
    bool[,] matrix = getMatrix(r);
    fillMatrix(ref matrix, normalizedCenter);
    drawMatrix(center, radius, matrix);
}


यहां एक तेज़ और सरल समाधान है।

श्रेणी (0, 1), अर्थात् a और b में दो यादृच्छिक संख्याएं चुनें। यदि b < a , उन्हें स्वैप करें। आपका बिंदु है (b*R*cos(2*pi*a/b), b*R*sin(2*pi*a/b))

आप इस समाधान के बारे में निम्नानुसार सोच सकते हैं। यदि आप सर्कल लेते हैं, इसे काटते हैं, फिर इसे सीधे निकाल देते हैं, तो आपको एक दाएं कोण वाला त्रिकोण मिल जाएगा। स्केल जो त्रिकोण नीचे है, और आपके पास (0, 0) से (1, 0) से (1, 1) और फिर से (0, 0) तक त्रिकोण होगा। इन सभी परिवर्तनों में घनत्व समान रूप से बदल जाता है। आपने जो किया है वह समान रूप से त्रिकोण में एक यादृच्छिक बिंदु उठाया गया है और सर्कल में एक बिंदु प्राप्त करने के लिए प्रक्रिया को उलट दिया है।


सबसे पहले हम एक सीडीएफ उत्पन्न करते हैं [x] जो है

संभावना है कि एक बिंदु सर्कल के केंद्र से दूरी x से कम है। मान लें कि सर्कल में आर का त्रिज्या है।

जाहिर है कि एक्स शून्य है तो सीडीएफ [0] = 0

जाहिर है यदि एक्स आर है तो सीडीएफ [आर] = 1

जाहिर है अगर एक्स = आर तो सीडीएफ [आर] = (पीआई आर ^ 2) / (पीआई आर ^ 2)

ऐसा इसलिए है क्योंकि सर्कल पर प्रत्येक "छोटे क्षेत्र" को चुनने की समान संभावना होती है, इसलिए संभावना क्षेत्र के अनुपात में आनुपातिक रूप से होती है। और सर्कल के केंद्र से दूरी एक्स दिया गया क्षेत्र पीआई आर ^ 2 है

तो सीडीएफ [x] = x ^ 2 / आर ^ 2 क्योंकि पीआई एक-दूसरे को रद्द कर देते हैं

हमारे पास सीडीएफ है [x] = x ^ 2 / R ^ 2 जहां x 0 से आर तक जाता है

तो हम एक्स के लिए हल करते हैं

R^2 cdf[x] = x^2

x = R Sqrt[ cdf[x] ]

अब हम 0 से 1 तक यादृच्छिक संख्या के साथ सीडीएफ को प्रतिस्थापित कर सकते हैं

x = R Sqrt[ RandomReal[{0,1}] ]

आखिरकार

r = R Sqrt[  RandomReal[{0,1}] ];
theta = 360 deg * RandomReal[{0,1}];
{r,theta}

हम ध्रुवीय निर्देशांक प्राप्त करते हैं {0.601168 आर, 311.915 डिग्री}





probability