algorithm ओवरलैपिंग सर्किल के संयुक्त क्षेत्र




geometry area (11)

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

उदाहरण छवि:

दो सर्किलों के लिए यह काफी आसान है,

मैं केवल प्रत्येक मंडल क्षेत्र के अंश की गणना कर सकता हूं जो त्रिकोण के भीतर नहीं है और फिर त्रिकोण के क्षेत्र की गणना करता है।

लेकिन क्या एक चालाक एल्गोरिदम है जिसका उपयोग मैं दो से अधिक मंडलियों में कर सकता हूं?


हम्म, बहुत रोचक समस्या है। मेरा दृष्टिकोण शायद निम्न की तरह कुछ होगा:

  • सर्किलों की मनमानी संख्या के बीच छेड़छाड़ के क्षेत्र क्या काम करते हैं, यानी यदि मेरे पास 3 मंडल हैं, तो मुझे यह जानने में सक्षम होना चाहिए कि मुझे उन मंडलियों के बीच छेड़छाड़ करने में सक्षम होना चाहिए। "मोंटे-कार्लो" विधि इस अनुमान का एक अच्छा तरीका होगा ( http://local.wasp.uwa.edu.au/~pbourke/geometry/circlearea/ )।
  • पूरी तरह से किसी अन्य सर्कल में निहित किसी भी मंडल को हटाएं (त्रिज्या को देखें और दो मंडलियों के केंद्र के बीच की दूरी के मॉड्यूलस) मुझे लगता है कि अनिवार्य नहीं है।
  • 2 मंडलियां चुनें (उन्हें ए और बी कॉल करें) और इस सूत्र का उपयोग करके कुल क्षेत्र का कार्य करें:

(यह किसी भी आकार के लिए सच है, चाहे वह सर्कल हो या अन्यथा)

area(A∪B) = area(A) + area(B) - area(A∩B)

जहां A ∪ B मतलब है एक संघ बी और A ∩ B अर्थ है एक अंतरण बी (आप इसे पहले चरण से बाहर कर सकते हैं।

  • अब मंडलियों को जोड़ना जारी रखें और मंडलियों के बीच चौराहे के क्षेत्रों और क्षेत्रों के क्षेत्रों के योग / घटाव के रूप में जोड़े गए क्षेत्र को काम करना जारी रखें। उदाहरण के लिए 3 सर्किलों के लिए (अतिरिक्त सर्कल सी को कॉल करें) हम इस सूत्र का उपयोग करके क्षेत्र को बाहर करते हैं:

(यह उपरोक्त जैसा ही है जहां A को A∪B साथ बदल दिया गया है)

area((A∪B)∪C) = area(A∪B) + area(C) - area((A∪B)∩C)

जहां area(A∪B) हमने अभी काम किया है, और area((A∪B)∩C) पाया जा सकता है:

area((A∪B)nC) = area((A∩C)∪(B∩C)) = area(A∩C) + area(A∩B) - area((A∩C)∩(B∩C)) = area(A∩C) + area(A∩B) - area(A∩B∩C)

फिर से आप उपरोक्त से क्षेत्र (एबीबीएसी) पा सकते हैं।

मुश्किल बिट आखिरी कदम है - अधिक सर्किल जितना जटिल हो जाता है उतना जटिल हो जाता है। मेरा मानना ​​है कि एक सीमित संघ के साथ छेड़छाड़ के क्षेत्र को काम करने के लिए एक विस्तार है, या वैकल्पिक रूप से आप इसे फिर से काम करने में सक्षम हो सकते हैं।

इसके अलावा, मोंटे-कार्लो का उपयोग इस क्षेत्र के अनुमान के अनुमान के लिए करने के संबंध में, मेरा मानना ​​है कि उन सर्किलों में से 4 के चौराहे के लिए एक मनमानी संख्या के सर्कल के चौराहे को कम करना संभव है, जिसे बिल्कुल गणना की जा सकती है (यह नहीं पता कि यह कैसे करें तथापि)।

शायद इस बीटीडब्ल्यू करने का एक बेहतर तरीका है - प्रत्येक अतिरिक्त सर्कल के लिए जटिलता काफी बढ़ जाती है (संभावित रूप से घातीय रूप से, लेकिन मुझे यकीन नहीं है)।


पिक्सेल-पेंटिंग दृष्टिकोण (जैसा कि @ लोडमास्टर द्वारा सुझाया गया है) विभिन्न तरीकों से गणितीय समाधान से बेहतर है:

  1. कार्यान्वयन बहुत आसान है। उपरोक्त समस्या को कोड की 100 से कम पंक्तियों में हल किया जा सकता है, क्योंकि यह जेएसफ़िल्ड समाधान प्रदर्शित करता है (अधिकांशतः क्योंकि यह अवधारणात्मक रूप से बहुत सरल है, और इसमें कोई बढ़िया मामला या अपवाद नहीं है)।
  2. यह अधिक सामान्य समस्याओं के लिए आसानी से अनुकूल है। यह मोर्फोलॉजी के बावजूद किसी भी आकार के साथ काम करता है, जब तक कि यह 2 डी ड्राइंग पुस्तकालयों (यानी, "उन सभी को!") के साथ प्रस्तुत करने योग्य है - मंडल, अंडाकार, splines, बहुभुज, आप इसे नाम दें। बिल्ली, यहां तक ​​कि बिटमैप छवियों।
  3. पिक्सेल-पेंटिंग समाधान की जटिलता ~ ओ [एन] है, गणितीय समाधान के लिए ~ ओ [एन * एन] की तुलना में। इसका मतलब है कि यह बेहतर प्रदर्शन करेगा क्योंकि आकृतियों की संख्या बढ़ जाती है।
  4. और प्रदर्शन की बात करते हुए, आपको अक्सर हार्डवेयर त्वरण मिल जाएगा, क्योंकि अधिकांश आधुनिक 2 डी पुस्तकालय (जैसे HTML5 के कैनवास, मुझे विश्वास है) ग्राफिक्स त्वरक को प्रतिपादन कार्य को ऑफ़लोड कर देगा।

पिक्सेल-पेंटिंग के लिए एक डाउनसाइड समाधान की सीमित सटीकता है। लेकिन यह स्थिति की मांग के रूप में बड़े या छोटे कैनवास को प्रतिपादित करके ट्यून करने योग्य है। ध्यान दें, 2 डी प्रतिपादन कोड (अक्सर डिफ़ॉल्ट रूप से चालू) में anti-aliasing बेहतर-से-पिक्सेल-स्तर सटीकता उत्पन्न करेगा। इसलिए, उदाहरण के लिए, एक ही आयाम के कैनवास में 100x100 आकृति को प्रस्तुत करना चाहिए, मुझे लगता है, 1 / (100 x 100 x 255) = .000039% के क्रम पर सटीकता उत्पन्न करना चाहिए ... जो शायद "पर्याप्त पर्याप्त" है सबसे अधिक मांग करने वाली समस्याओं के लिए सभी के लिए।

<p>Area computation of arbitrary figures as done thru pixel-painting, in which a complex shape is drawn into an HTML5 canvas and the area determined by comparing the number of white pixels found in the resulting bitmap.  See javascript source for details.</p>

<canvas id="canvas" width="80" height="100"></canvas>

<p>Area = <span id="result"></span></p>
// Get HTML canvas element (and context) to draw into
var canvas = document.getElementById('canvas');
var ctx = canvas.getContext('2d');

// Lil' circle drawing utility
function circle(x,y,r) {
  ctx.beginPath();
  ctx.arc(x, y, r, 0, Math.PI*2);
  ctx.fill();
}

// Clear canvas (to black)
ctx.fillStyle = 'black';
ctx.fillRect(0, 0, canvas.width, canvas.height);

// Fill shape (in white)
ctx.fillStyle = 'white';
circle(40, 50, 40);
circle(40, 10, 10);
circle(25, 15, 12);
circle(35, 90, 10);

// Get bitmap data
var id = ctx.getImageData(0, 0, canvas.width, canvas.height);
var pixels = id.data; // Flat array of RGBA bytes

// Determine area by counting the white pixels
for (var i = 0, area = 0; i < pixels.length; i += 4) {
  area += pixels[i]; // Red channel (same as green and blue channels)
}

// Normalize by the max white value of 255
area /= 255;

// Output result
document.getElementById('result').innerHTML = area.toFixed(2);


बाहरी परिधि (जैसे बी, डी, एफ, एच निम्नलिखित आरेख पर) पर सभी सर्कल चौराहे खोजें। बहुभुज बनाने के लिए उन्हें संबंधित मंडलियों के केंद्रों के साथ एक साथ कनेक्ट करें। मंडलियों के संघ का क्षेत्र बहुभुज का क्षेत्र है + सर्कल स्लाइस का क्षेत्र लगातार चौराहे बिंदुओं और उनके बीच सर्कल केंद्र द्वारा परिभाषित किया गया है। आपको किसी भी छेद के लिए भी खाते की आवश्यकता होगी।


आप जिस समस्या को हल करने की कोशिश कर रहे हैं उसके आधार पर ऊपरी और निचले बाउंड को पाने के लिए पर्याप्त हो सकता है। ऊपरी बाउंड आसान है, बस सभी मंडलियों का योग। निचले बाउंड के लिए आप एक त्रिज्या चुन सकते हैं जैसे कि कोई भी मंडल ओवरलैप नहीं होता है। प्रत्येक सर्कल के लिए सबसे बड़ा त्रिज्या (वास्तविक त्रिज्या तक) को बेहतर बनाने के लिए ताकि यह ओवरलैप न हो। किसी भी पूरी तरह से ओवरलैप्ड सर्कल को हटाने के लिए यह बहुत छोटा होना चाहिए (ऐसी सभी मंडलियां संतुष्ट होती हैं | पी_ए - पी_बी | <= आर_ए) जहां पी_ए सर्कल ए का केंद्र है, पी_बी सर्कल बी का केंद्र है, और आर_ए ए का त्रिज्या है ) और यह ऊपरी और निचले बाउंड दोनों betters। यदि आप अपने मंडल सूत्र का उपयोग केवल सभी मंडलियों के योग के बजाय मनमानी जोड़े पर अपने ऊपरी फॉर्मूला का उपयोग करते हैं तो आप बेहतर ऊपरी बाउंड भी प्राप्त कर सकते हैं। "सर्वश्रेष्ठ" जोड़े चुनने का एक अच्छा तरीका हो सकता है (जोड़े जो कम से कम कुल क्षेत्र में परिणामस्वरूप होते हैं।

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


यहां एक एल्गोरिदम है जो अभ्यास में लागू करना आसान होना चाहिए, और मनमाने ढंग से छोटी त्रुटि उत्पन्न करने के लिए समायोजित किया जा सकता है:

  1. एक ही बिंदु पर केंद्रित नियमित बहुभुज द्वारा प्रत्येक सर्कल को लगभग
  2. बहुभुज की गणना करें जो अनुमानित सर्कल का संघ है
  3. मर्ज किए गए बहुभुज के क्षेत्र की गणना करें

चरण 2 और 3 को कम्प्यूटेशनल ज्यामिति से मानक, आसानी से खोजने वाले एल्गोरिदम का उपयोग करके किया जा सकता है।

जाहिर है, आप प्रत्येक अनुमानित बहुभुज के लिए जितनी अधिक पक्षों का उपयोग करते हैं, उतना सटीक आपके उत्तर के करीब होगा। सटीक उत्तर पर सीमा प्राप्त करने के लिए आप अंकित और परिपत्रित बहुभुज का उपयोग करके अनुमान लगा सकते हैं।


यदि आप एक अलग (एक निरंतर के विपरीत) जवाब चाहते हैं, तो आप कुछ पिक्सेल पेंटिंग एल्गोरिदम के समान कुछ कर सकते हैं।

सर्कल को ग्रिड पर खींचे, और फिर ग्रिड के प्रत्येक सेल को रंग दें यदि यह ज्यादातर सर्कल के भीतर होता है (यानी, इसके क्षेत्र का कम से कम 50% सर्किलों में से एक है)। पूरे ग्रिड के लिए ऐसा करें (जहां ग्रिड मंडलियों द्वारा कवर किए गए सभी क्षेत्र को फैलाता है), फिर ग्रिड में रंगीन कोशिकाओं की संख्या गिनें।


मुझे यकीन है कि एक चालाक एल्गोरिदम है, लेकिन इसे देखने के लिए यहां एक गूंगा व्यक्ति है;

  • सर्कल के चारों ओर एक बाध्यकारी बॉक्स रखो;
  • बाध्यकारी बॉक्स के भीतर यादृच्छिक अंक उत्पन्न करें;
  • पता लगाएं कि यादृच्छिक बिंदु मंडलियों में से एक के अंदर है या नहीं;
  • कुछ साधारण जोड़ और विभाजन (proportion_of_points_inside * area_of_bounding_box) द्वारा क्षेत्र की गणना करें।

यकीन है कि यह गूंगा है, लेकिन:

  • आप जितना चाहें सटीक उत्तर प्राप्त कर सकते हैं, बस अधिक अंक उत्पन्न करें;
  • यह किसी भी आकार के लिए काम करेगा जिसके लिए आप अंदर / बाहरी भेद की गणना कर सकते हैं;
  • यह खूबसूरती से समानांतर होगा ताकि आप अपने सभी कोर का उपयोग कर सकें।

मुझे 2 छेड़छाड़ करने वाले सर्कल के मामले में दृष्टिकोण पसंद है - यहां मैं अधिक जटिल उदाहरण के लिए एक ही दृष्टिकोण की थोड़ी भिन्नता का उपयोग कैसे करूंगा।

यह बड़ी संख्या में सेमी-ओवरलैपिंग सर्कल के लिए एल्गोरिदम को सामान्य करने में बेहतर अंतर्दृष्टि दे सकता है।

यहां अंतर यह है कि मैं केंद्रों को जोड़कर शुरू करता हूं (इसलिए सर्कल के केंद्र के बीच एक ऊर्ध्वाधर है, जहां सर्किलों को घेरने वाले स्थानों के बीच) मुझे लगता है कि इससे इसे बेहतर सामान्यीकृत करने दिया जा सकता है।

(अभ्यास में, शायद मोंटे-कार्लो विधि सार्थक है)

alt text http://secretGeek.net/image/triangles_1667310.png


मैं घने खेतों में वास्तविक डिस्क क्षेत्रों से सच्चे स्टार की गणना करने का प्रयास करने के प्रयास में ओवरलैपिंग स्टार फ़ील्ड को अनुकरण करने की समस्या पर काम कर रहा हूं, जहां बड़े उज्ज्वल सितारे फेंटर वाले लोगों को मुखौटा कर सकते हैं। मैं भी कठोर औपचारिक विश्लेषण द्वारा ऐसा करने में सक्षम होने की उम्मीद कर रहा था, लेकिन कार्य के लिए एल्गोरिदम खोजने में असमर्थ था। मैंने नीले रंग की पृष्ठभूमि पर स्टार फ़ील्ड को हरे रंग की डिस्क के रूप में उत्पन्न करके हल किया, जिसका व्यास एक संभाव्यता एल्गोरिदम द्वारा निर्धारित किया गया था। एक साधारण दिनचर्या उन्हें यह देखने के लिए जोड़ सकती है कि क्या ओवरलैप है (स्टार जोड़ी पीला मोड़ रहा है); फिर रंगों की एक पिक्सेल गिनती सैद्धांतिक क्षेत्र की तुलना करने के लिए मनाए गए क्षेत्र को उत्पन्न करती है। यह फिर सही मायने रखता है के लिए एक संभावना वक्र उत्पन्न करता है। ब्रूट फोर्स शायद, लेकिन ऐसा लगता है कि ठीक है।
http://www.2from.com/images/simulated_star_field.gif


पिछले एक से अलग समाधान के लिए आप एक क्वाड्री का उपयोग करके मनमाना परिशुद्धता के साथ अनुमान लगा सकते हैं।

यह किसी भी आकार संघ के लिए भी काम करता है यदि आप बता सकते हैं कि कोई वर्ग अंदर या बाहर है या आकार को छेड़छाड़ करता है या नहीं।

प्रत्येक कोशिका में राज्यों में से एक है: खाली, पूर्ण, आंशिक

एल्गोरिदम में निम्न रिज़ॉल्यूशन (उदाहरण के लिए 4 कोशिकाओं को खाली के रूप में चिह्नित) के साथ शुरू होने वाले क्वाड्री में मंडलियों को "ड्राइंग" करना होता है। प्रत्येक सेल या तो है:

  • कम से कम एक सर्कल के अंदर, फिर सेल को पूर्ण रूप से चिह्नित करें,
  • सभी सर्कल के बाहर, सेल को खाली के रूप में चिह्नित करें,
  • अन्यथा सेल को आंशिक रूप से चिह्नित करें।

जब यह हो जाता है, तो आप क्षेत्र के अनुमान की गणना कर सकते हैं: पूर्ण कोशिकाएं निम्न बाध्य होती हैं, खाली कोशिकाएं उच्च बाध्य होती हैं, आंशिक कोशिकाएं अधिकतम क्षेत्र त्रुटि प्रदान करती हैं।

यदि त्रुटि आपके लिए बहुत बड़ी है, तो आप आंशिक कोशिकाओं को परिशोधित करते हैं जब तक कि आपको सही परिशुद्धता न मिल जाए।

मुझे लगता है कि ज्यामितीय विधि से लागू करना आसान होगा जिसे कई विशेष मामलों को संभालने की आवश्यकता हो सकती है।





area