किसी बिंदु के निर्देशांक को देखते हुए, मैं यह निर्धारित कैसे कर सकता हूं कि यह मनमाने ढंग से आकार में है या नहीं?निर्धारित करता है कि कोई बिंदु एक मनमाना आकार के भीतर बैठता है या नहीं?
आकार को अंक की एक सरणी द्वारा परिभाषित किया गया है, मुझे नहीं पता कि आकार कहां है 'बंद', जिस भाग को वास्तव में मदद की ज़रूरत है वह यह है कि आकार कहां बंद हो जाए।
सबसे आसान तरीका यह है कि बिंदु से एक किरण डाली है क्या करना है और गिनती कितनी बार यह सीमा को पार करने के लिए:
यहाँ वर्णन करने के लिए मैं एक छोटे से बेहतर क्या मतलब है एक छवि है। यदि यह विषम है, तो बिंदु अंदर है, यहां तक कि बिंदु बाहर है।
विकी: http://en.wikipedia.org/wiki/Point_in_polygon
ध्यान दें कि यह केवल कई गुना आकार के लिए काम करता है। - वे अपने आकार की सीमा के कुछ खंड फार्म
पर विचार करें P[i] अंक और P[i+1] के जोड़े सरणी में दिए गए:
शानदार। मुझे याद दिलाने के लिए धन्यवाद! – ambrus
वास्तव में, यदि आप अंक की एक सरणी दिया जाता है, तो आप आकार की निकटता के रूप में इस जाँच कर सकते हैं । आपको जांचने की आवश्यकता है कि क्या ऐसे दो खंड हैं जो छेड़छाड़ करते हैं, जिन्हें O(N^2) समय में चेक किया जा सकता है (केवल ऐसे सेगमेंट के सभी संभावित जोड़े को चेक करके)। यदि कोई छेड़छाड़ मौजूद है, तो इसका मतलब है कि आपका आकार बंद है।
नोट: आपको P[0],P[n-1] सेगमेंट को जांचना न भूलें (यानी सरणी में पहले और अंतिम बिंदु)।
कब पी [i], पी [i + 1] और पी [जे], पी [जे + 1] छेड़छाड़ करेंगे? मुझे लगता है कि यह बताएगा कि आकार एक साधारण बहुभुज या जटिल बहुभुज है या नहीं। इसके अलावा, आपने मूल प्रश्न का उत्तर नहीं दिया कि पॉलीगॉन में बिंदु क्या है या नहीं। –
@logic_max: ठीक है, मैंने इस सवाल के जवाब का जवाब दिया कि आकार कैसे बंद है या नहीं, और समस्या कथन के अनुसार, यह एक बहुभुज होना जरूरी नहीं है, यह एक मनमानी पॉलीलाइन हो सकता है। किसी भी पी की उपस्थिति [i], पी [i + 1] और पी [जे], पी [जे + 1] चौराहे केवल हमें बताएगी कि आकार का एक बंद हिस्सा है। अंदर बिंदु के बारे में क्या - मिकोला का जवाब इसके बारे में सही है। –
यह काम नहीं करता है। क्या होगा यदि आप एक बंद बहुभुज लेते हैं, तो इसके लिए एक लटकते किनारे जोड़ें? असल में, मुझे यकीन नहीं है कि आप वास्तव में क्या परीक्षण कर रहे हैं, और यह सवाल से कैसे संबंधित है? – Mikola
यदि आप यह निर्धारित करना चाहते हैं कि कोई बिंदु पी मनमाने ढंग से आकार में है या नहीं, तो मैं बस पी से शुरू होने वाली बाढ़ भरने को चलाऊंगा। यदि आपकी बाढ़ भरने से पूर्व निर्धारित बाउंडिंग बॉक्स छोड़ देता है, तो आप आकार के बाहर हैं। अन्यथा यदि आपका बाढ़ भरना समाप्त हो जाता है, तो आप आकार के भीतर हैं :)
मुझे विश्वास है कि यह एल्गोरिदम ओ (एन^2) है जहां एन अंक की संख्या है, क्योंकि अधिकतम क्षेत्र एन^2 के आनुपातिक है।
विकिपीडिया: Flood Fill
आकार मैं बस जहां यह बंद कर दिया है पता नहीं है खुला नहीं है ...। – gibo
आपको यह बताना होगा कि आकृति को अंक की एक सरणी द्वारा कैसे परिभाषित किया गया है। यदि आप का मतलब है कि अंक की सरणी आकार के भीतर बिंदुओं का सेट है, तो सवाल मामूली है। – sawa
मेरी पोस्ट में छवि इसे थोड़ा बेहतर समझा सकती है .. मुझे नीली रेखा के साथ बिंदु पता है, लेकिन यह नहीं पता कि क्रॉस – gibo