👩🏾‍🎨 🚆 🤴🏼 नियमित नेटवर्क प्वाइंट क्लस्टरिंग 🥘 🥈 🎴

इस लेख में, मैं दो एल्गोरिदम पर विचार करूंगा, पहला - सीधे क्लस्टरिंग, दूसरा - एक उत्तल बहुभुज के रूप में क्लस्टर के समोच्च का निर्माण, परिणाम की बेहतर धारणा के लिए एक लागू कार्य।

क्लस्टरिंग

सामान्य तौर पर, इस क्षेत्र के साथ कानून काफी सतही है, इसलिए यह उम्मीद की जाती है कि इस तरह के एक एल्गोरिथ्म लंबे समय से अस्तित्व में है और किसी भी तरह नाम दिया गया है, अगर किसी को पता है, तो कृपया सूचित करें।

इनपुट डेटा

बिंदु निर्देशांक केवल दो-आयामी निर्देशांक की एक सरणी है
आर - एक क्लस्टर में बिंदुओं के बीच की अधिकतम दूरी - एक क्लस्टर के निर्माण के लिए मुख्य संकेतक
k - ग्रिड गुणांक - संख्या 2 के लिए डिग्री, जिसके द्वारा नेटवर्क सेल के पक्ष की गणना की जाती है: a = 2 = k

एल्गोरिथ्म को प्रभावी ढंग से काम करने के लिए, निम्नलिखित स्थिति को देखा जाना चाहिए:
R <2 ^ k, या एल्गोरिथ्म को संशोधित करें।

एल्गोरिथ्म

एक नियमित नेटवर्क की कोशिकाओं के साथ अंकों के निर्देशांक की तुलना।
एक्सआर = एक्स >> के
Yr = y >> k, जहाँ k ग्रिड गुणांक है, >> बिटवाइज़ ऑफ़सेट है। इस चरण में विभाजन के संचालन की अनुपस्थिति के कारण, गति में एक अच्छा लाभ प्राप्त होता है। इस चरण का परिणाम फ़ॉर्म का शब्दकोश होगा:
[नेटवर्क सेल निर्देशांक]: [इस सेल से संबंधित बिंदुओं के लिंक]
बिंदुओं पर एक पास में बिल्डिंग क्लस्टर:
- अगला बिंदु लिया जाता है, यदि यह क्लस्टर से जुड़ा नहीं है, तो एक नया क्लस्टर बनाया जाता है और इसमें एक बिंदु जोड़ा जाता है, बिंदु पर ही क्लस्टर का लिंक चिपका दिया जाता है।
- कोशिकाओं की एक सूची ली जाती है; इसमें शामिल हैं: एक बिंदु और पड़ोसी कोशिकाओं के साथ एक कोशिका।
- प्राप्त सूची से कोशिकाओं के सभी बिंदुओं का चयन किया जाता है।
- वर्तमान बिंदु और सूची में से एक के बीच की दूरी पाई जाती है, यदि दूरी <= R है तो दो मामले संभव हैं
  - परीक्षण किया गया बिंदु अभी क्लस्टर में शामिल नहीं है => बिंदु को वर्तमान बिंदु के समान क्लस्टर में दर्ज किया गया है
  - बिंदु की जाँच पहले से ही कुछ क्लस्टर से संबंधित है जो कि वर्तमान से भिन्न है => क्लस्टर के साथ बड़ी संख्या में क्लस्टर एक छोटे से एक क्लस्टर को अवशोषित करता है।

कार्य का परिणाम प्रत्येक समूह में एक समूह होगा, जिसमें अंकों के बीच की दूरी R से अधिक नहीं होनी चाहिए, कुछ इस प्रकार है:

या अधिक स्पष्ट रूप से इस तरह:

एक क्लस्टर के बिंदुओं को एक रंग में इंगित किया गया है।

समोच्च

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

public static int CrossLinePoint(ClusterPoint l1, ClusterPoint l2, ClusterPoint p) { return (pX - l2.X) * (l2.Y - l1.Y) - (pY - l2.Y) * (l2.X - l1.X); }

यदि फ़ंक्शन का परिणाम 0 से कम है, तो मध्य बिंदु पर मोड़ दक्षिणावर्त जाता है, यदि 0 से अधिक है, तो विरुद्ध है, यदि यह 0 है, तो कोई मोड़ नहीं है। अर्थ स्वयं महत्वपूर्ण नहीं है, केवल संकेत महत्वपूर्ण है।

एल्गोरिथ्म में केवल दो चरण होते हैं।

वर्णनात्मक रूपरेखा चयन

भार गुणांक को ध्यान में रखे बिना क्लस्टर के द्रव्यमान का केंद्र पाया जाता है। यानी वे बस सभी निर्देशांक जोड़ते हैं, अलग से x और y में, और क्लस्टर में बिंदुओं की संख्या से विभाजित होते हैं, प्राप्त निर्देशांक [Xc; Yc] क्लस्टर के द्रव्यमान का केंद्र होगा।
हम द्रव्यमान के केंद्र से तीन बिंदुओं की खोज करते हैं जो प्रारंभिक समोच्च बनाते हैं।
शेष बिंदुओं को क्रमबद्ध किया जाता है, और प्रारंभिक समोच्च में प्रत्येक प्रविष्टि के लिए जांच की जाती है, अगर बिंदु इसमें प्रवेश करता है, तो कुछ भी नहीं होता है, अगर बाहर होता है, तो यह समोच्च का हिस्सा बन जाता है।
समोच्च में एक बिंदु जोड़ते समय, समोच्च बिंदुओं के सरणी को क्रमबद्ध किया जाता है, बिंदु के ध्रुवीय निर्देशांक से कोण, जहां क्लस्टर के निर्देशांक का केंद्र निर्देशांक के केंद्र के रूप में कार्य करता है, को छंटाई के लिए मान के रूप में लिया जाता है।
परिणाम एक टूटी हुई समोच्च होगा जो कि क्लस्टर बनाने वाले बिंदुओं का वर्णन करता है, और समोच्च में बिंदु पहले से ही द्रव्यमान के केंद्र के सापेक्ष दक्षिणावर्त ऑर्डर किए जाते हैं।

ध्रुवीय निर्देशांक से कोण प्राप्त करने का कार्य:

 private float GetPolarAngle(ClusterPoint p) { float a = 0, x = pX - center.X, y = pY - center.Y; if (x > 0 && y >= 0) { a = (float)Math.Atan(y / x); } else if (x > 0 && y < 0) { a = (float)(Math.Atan(y / x) + 2 * Math.PI); } else if (x < 0) { a = (float)(Math.Atan(y / x) + Math.PI); } else if (x == 0 && y > 0) { a = (float)(Math.PI * .5); } else if (x == 0 && y < 0) { a = (float)(Math.PI * 1.5); } else if (x == 0 && y == 0) { a = 0; } return (float)(a * 180 / Math.PI); }

यहाँ केंद्र क्लस्टर के द्रव्यमान का केंद्र है।

समोच्च बिंदुओं को सही क्रम में खींचने के लिए कोणीय छंटाई की आवश्यकता है, और यह निर्धारित करने के लिए कि समोच्च का निर्माण करते समय एक बिंदु समोच्च में शामिल नहीं है / नहीं। यदि आप डॉट्स को यादृच्छिक क्रम में छोड़ते हैं, तो एल्गोरिथ्म काम नहीं करेगा।

काम का परिणाम:

हरे रंग का बिंदु द्रव्यमान का केंद्र है।
अभी भी बहुत अच्छा नहीं है, इसलिए अंतिम चरण पर जाएं।

उत्तल रूपरेखा

सबसे सरल कदम, जिसमें अंक पहले से ही दक्षिणावर्त दिए जाते हैं, बिंदुओं के माध्यम से गुजरते हुए बनाया जाता है और जिन लोगों में झुंड वामावर्त होता है उन्हें समोच्च से बाहर निकाल दिया जाता है। मोड़ को निर्धारित करने के लिए, ऊपर दिए गए क्रॉसलाइन फ़ंक्शन का उपयोग करें।
काम का परिणाम:

परीक्षण

एल्गोरिथ्म की गति के रेखांकन।

फ़ील्ड में एक स्थिर आकार होता है, बिंदुओं का घनत्व बढ़ता है:

क्षेत्र आकार में बढ़ता है, अंकों का घनत्व लगभग समान है:

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

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

आगे क्या है

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

कार्यान्वयन

यदि कोई एल्गोरिथम में रुचि रखता है, तो एक कार्यक्रम और स्रोत कोड है। जीत / सी #
विन x86
सूत्रों का कहना है

अंक के रूप में लेख में दिखाए गए समूहों के मैपिंग के अलावा और एक समोच्च लाइनों के साथ अंक के रूप में, कार्यक्रम भी बंद घटता, और बंद घटता के भरे हुए क्षेत्र के रूप में प्रदर्शित कर सकता है।

मानक GDI + टूल का उपयोग किया जाता है।

नियमित नेटवर्क प्वाइंट क्लस्टरिंग