दो सर्किलों के लिए सामान्य सभी बिंदुओं को ढूंढना

Question

पायथन में, एक को दो सर्किलों के लिए सामान्य सभी पूर्णांक बिंदु कैसे मिलेगा?

उदाहरण के लिए, दो हलकों (समान रूप से आकार) के एक वेन आरेख की तरह चौराहे, केंद्र-अंक (x1,y1) और (x2,y2) साथ कल्पना और r1=r2 radii। इसके अतिरिक्त, हम पहले से ही जानते हैं कि सर्कल के चौराहे के दो बिंदु (xi1,yi1) और (xi2,yi2) हैं।

एक सर्कल में दोनों सर्किलों में निहित (x,y) सभी बिंदुओं की सूची कैसे उत्पन्न करेगा? यही है, घुमाव वाले बॉक्स को खींचना और उसके माध्यम से पुनरावृत्ति करना आसान होगा, यह जांचना कि क्या दिया गया बिंदु दोनों मंडलियों के भीतर है, लेकिन क्या कोई बेहतर तरीका है?

Answer 1

तो तुम जाली अंक है कि दोनों हलकों के अंदर ढूंढना चाहते हैं?

बॉक्स में सभी बिंदुओं के माध्यम से बॉक्स को चित्रित करने और पुनरावृत्ति करने का सुझाव आपने मेरे लिए सबसे सरल लगता है। यह संभवतः कुशल होगा, जब तक कि बॉक्स में बिंदुओं की संख्या चौराहे में बिंदुओं की संख्या के बराबर है।

और यदि यह यथासंभव कुशल नहीं है, तो आपको इसे तब तक अनुकूलित करने की कोशिश नहीं करनी चाहिए जब तक कि आपके पास यह विश्वास करने का कोई अच्छा कारण न हो कि यह वास्तविक बाधा है।

Answer 2

ध्यान रखें कि यहां चार मामले हैं।

1. न तो सर्कल छेड़छाड़ करता है, जिसका अर्थ है "सामान्य क्षेत्र" खाली है।
2. एक सर्कल पूरी तरह से दूसरे के भीतर रहता है, जिसका अर्थ है "सामान्य क्षेत्र" छोटा/आंतरिक सर्कल है। यह भी ध्यान रखें कि इसका एक अपमानजनक मामला यह है कि यदि वे समान केंद्रित चक्र हैं, जो मानदंड दिए गए हैं कि वे आपके द्वारा निर्दिष्ट व्यास-व्यास मंडल हैं।
3. दो सर्किल एक चौराहे बिंदु पर स्पर्श करते हैं।
4. "सामान्य" मामला जहां दो चौराहे बिंदु होने जा रहे हैं। वहां से, आपके पास दो आर्क हैं जो संलग्न क्षेत्र को परिभाषित करते हैं। उस स्थिति में, बॉक्स-ड्राइंग विधि अब के लिए काम कर सकती है, मुझे यकीन नहीं है कि चौराहे से क्या है यह निर्धारित करने के लिए एक और अधिक कुशल विधि है। ध्यान दें, हालांकि, यदि आप क्षेत्र में रुचि रखते हैं, तो इसके लिए a formula है।

Answer 3

आप ग्राफिक्स विकास में उपयोग किए जाने वाले विभिन्न क्लिपिंग एल्गोरिदम भी देखना चाहते हैं। मैंने क्लिपिंग एल्गोरिदम का उपयोग किया है जो आप यहां पूछ रहे हैं जैसी समस्याओं का समाधान करने के लिए करते हैं।

Answer 4

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

आप अंक आप उचित रूप से खोज क्षेत्र को परिभाषित करते हुए जाँच की संख्या को कम कर सकते हैं। यह एक चौड़ाई चौराहे के अंक के बीच की दूरी के बराबर है, और

r1 + r2 - D

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

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

Answer 5

मैं द्वारा "सभी बिंदुओं" आप "सभी पिक्सल" मतलब मान। मान लीजिए कि आपका प्रदर्शन NY पिक्सेल द्वारा एनएक्स है। दो एरे

int x0[NY], x1[NY]; initially full of -1. 

चौराहे दो घटता के बीच, lozenge-shaped है। प्रत्येक वक्र के साथ इटरेट एक्स, वाई मान। प्रत्येक वाई मान पर (यानी, जहां वक्र y + 0.5 को पार करता है), सरणी में x मान संग्रहीत करें। यदि x0 [y] -1 है, तो इसे x0 में संग्रहीत करें, अन्यथा इसे x1 में संग्रहीत करें।

इसके अलावा y के निम्नतम और उच्चतम मूल्यों पर नज़र रखें।

जब आप पूरा कर लें, तो y मानों पर पुनरावृत्त करें, और प्रत्येक y पर, x0 और x1 के बीच x मानों पर पुनरावृत्त करें, यानी for (ix = x0[iy]; ix < x1[iy]; ix++) (या विपरीत)।

यह समझना महत्वपूर्ण है कि पिक्सल अंक जहां x और y पूर्णांक हैं नहीं कर रहे हैं महत्वपूर्ण है। इसके बजाय पिक्सल ग्रिड लाइनों के बीच छोटे वर्ग होते हैं। इससे आपको एज-केस समस्याएं होने से रोका जा सकता है।

Answer 6

आप बहुत करीब हैं। बॉक्स में बिंदुओं पर इटरेट करना काफी अच्छा होना चाहिए, लेकिन यदि आप दूसरी समन्वय के लिए सीमाओं के बीच सीधे पुनरावृत्ति करते हैं तो आप बेहतर कर सकते हैं।

आप साथ पुनरावृति कहो एक्स अक्ष पहले, तो y अक्ष के लिए, सीमांकन बॉक्स coords के बीच पुनरावृत्ति के बजाय यह पता लगाने जहां प्रत्येक चक्र एक्स लाइन काटती है, और अधिक विशेष आप y में चौराहों की समन्वय रुचि रखते हैं, और उन लोगों के बीच फिर से शुरू करें (गोल करने पर ध्यान दें)

जब आप ऐसा करते हैं, क्योंकि आप पहले ही जानते हैं कि आप मंडलियों के अंदर हैं, तो आप चेक को पूरी तरह से छोड़ सकते हैं। यदि आपके पास बहुत सारे अंक हैं तो आप बहुत सारे चेक छोड़ देते हैं और आपको कुछ प्रदर्शन सुधार मिल सकते हैं।

अतिरिक्त सुधार के रूप में आप एक्स अक्ष या वाई धुरी को छेड़छाड़ बिंदुओं की गणना करने के लिए आवश्यक समय को कम करने के लिए चुन सकते हैं।