यह सप्ताह छोटा था, सोमवार और मंगलवार को मैंने 2 डी प्रकाश व्यवस्था पर काम करना जारी रखा। बाकी समय मैंने क्वाडट्री पेड़ों के कार्यान्वयन पर बिताया।

इस लेख में मैं अपने कार्यान्वयन और विचारों को साझा करूंगा जो इसके डिजाइन की प्रक्रिया में उत्पन्न हुए थे।

सबसे पहले, मुझे यह कहने की आवश्यकता है कि मैंने एक चतुर्भुज वृक्ष को लागू करने का निर्णय क्यों लिया।

क्वाडट्री एक अंतरिक्ष विभाजन डेटा संरचना है । अन्य डेटा संरचनाओं पर इसका मुख्य लाभ इसकी अनुकूलनशीलता है। यह डालने, हटाने और खोज करने पर अच्छा प्रदर्शन प्रदान करता है। यही है, हम इस पेड़ को एक गतिशील संदर्भ में उपयोग कर सकते हैं जहां डेटा अक्सर बदलता रहता है। इसके अलावा, यह संरचना समझने और लागू करने में काफी आसान है।

यदि अंतरिक्ष विभाजन आपके लिए एक नया विषय है, तो मैं रॉबर्ट निस्ट्रोम के इस लेख को पढ़ने की सलाह देता हूं। यदि आप चतुष्कोणीय पेड़ों के बारे में अधिक जानना चाहते हैं, तो इस या इस लेख को पढ़ें।

मेरे खेल में ऐसे क्षेत्र हैं जिनमें क्वाडट्री का उपयोग करना तुरंत भुगतान करता है:

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

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

लेख में दिखाए गए सभी कोड GitHub पर पाए जा सकते हैं।

प्रारंभिक तैयारी

क्वाडट्री कोड का विवरण देने से पहले, हमें ज्यामितीय आदिम के लिए छोटे वर्गों की आवश्यकता है: आयतों को परिभाषित करने के लिए Vector2 अंक और परिभाषित करने के लिए Box वर्ग। दोनों बॉयलरप्लेट होंगे।

Vector2

Vector2 वर्ग अतिसूक्ष्म है। इसमें केवल कंस्ट्रक्टर होते हैं, साथ ही + और / ऑपरेटर्स होते हैं। बस इतना ही चाहिए:

 template<typename T> class Vector2 { public: T x; T y; constexpr Vector2<T>(TX = 0, TY = 0) noexcept : x(X), y(Y) { } constexpr Vector2<T>& operator+=(const Vector2<T>& other) noexcept { x += other.x; y += other.y; return *this; } constexpr Vector2<T>& operator/=(T t) noexcept { x /= t; y /= t; return *this; } }; template<typename T> constexpr Vector2<T> operator+(Vector2<T> lhs, const Vector2<T>& rhs) noexcept { lhs += rhs; return lhs; } template<typename T> constexpr Vector2<T> operator/(Vector2<T> vec, T t) noexcept { vec /= t; return vec; }

डिब्बा

Box क्लास बहुत अधिक जटिल नहीं है:

 template<typename T> class Box { public: T left; T top; T width; // Must be positive T height; // Must be positive constexpr Box(T Left = 0, T Top = 0, T Width = 0, T Height = 0) noexcept : left(Left), top(Top), width(Width), height(Height) { } constexpr Box(const Vector2<T>& position, const Vector2<T>& size) noexcept : left(position.x), top(position.y), width(size.x), height(size.y) { } constexpr T getRight() const noexcept { return left + width; } constexpr T getBottom() const noexcept { return top + height; } constexpr Vector2<T> getTopLeft() const noexcept { return Vector2<T>(left, top); } constexpr Vector2<T> getCenter() const noexcept { return Vector2<T>(left + width / 2, top + height / 2); } constexpr Vector2<T> getSize() const noexcept { return Vector2<T>(width, height); } constexpr bool contains(const Box<T>& box) const noexcept { return left <= box.left && box.getRight() <= getRight() && top <= box.top && box.getBottom() <= getBottom(); } constexpr bool intersects(const Box<T>& box) const noexcept { return !(left >= box.getRight() || getRight() <= box.left || top >= box.getBottom() || getBottom() <= box.top); } };

इसमें कुछ उपयोगी गेटर्स शामिल हैं।

जो अधिक दिलचस्प है वह यह है कि इसमें विधि शामिल है, जो यह जाँचता है कि क्या आयत दूसरे के अंदर है, और intersects विधि, जो यह जाँचती है कि आयत दूसरे के साथ प्रतिच्छेद करती है या नहीं।

हम सम्मिलित करते समय और हटाते समय और intersects को पहचानते समय intersects उपयोग करेंगे।

Quadtree

यहाँ Quadtree वर्ग Quadtree :

 template<typename T, typename GetBox, typename Equal = std::equal_to<T>, typename Float = float> class Quadtree { static_assert(std::is_convertible_v<std::invoke_result_t<GetBox, const T&>, Box<Float>>, "GetBox must be a callable of signature Box<Float>(const T&)"); static_assert(std::is_convertible_v<std::invoke_result_t<Equal, const T&, const T&>, bool>, "Equal must be a callable of signature bool(const T&, const T&)"); static_assert(std::is_arithmetic_v<Float>); public: Quadtree(const Box<Float>& box, const GetBox& getBox = GetBox(), const Equal& equal = Equal()) : mBox(box), mRoot(std::make_unique<Node>()), mGetBox(getBox), mEqual(equal) { } private: static constexpr auto Threshold = std::size_t(16); static constexpr auto MaxDepth = std::size_t(8); struct Node { std::array<std::unique_ptr<Node>, 4> children; std::vector<T> values; }; Box<Float> mBox; std::unique_ptr<Node> mRoot; GetBox mGetBox; Equal mEqual; bool isLeaf(const Node* node) const { return !static_cast<bool>(node->children[0]); } };

जैसा कि आप देख सकते हैं, Quadtree एक टेम्पलेट क्लास है। यह हमें विभिन्न उद्देश्यों के लिए कक्षा का उपयोग करने की अनुमति देगा, जिसके बारे में मैंने शुरुआत में बात की थी।

टेम्पलेट विकल्प:

T : मानों का प्रकार जो चतुष्कोण में समाहित होगा। T एक आसान वर्ग होना चाहिए, क्योंकि यह एक क्वाडट्री के अंदर संग्रहीत किया जाएगा। आदर्श रूप से, यह एक सूचक या एक छोटा सा सरल डेटा स्ट्रक्चर (POD) होना चाहिए।
GetBox : उस तथाकथित ऑब्जेक्ट का प्रकार जो इनपुट पर मूल्य प्राप्त करेगा और एक आयत लौटाएगा।
Equal : दो मान समान होने पर जाँचने के लिए तथाकथित वस्तु का प्रकार। डिफ़ॉल्ट रूप से, हम मानक समानता ऑपरेटर का उपयोग करते हैं।
Float : गणना में प्रयुक्त अंकगणित प्रकार। डिफ़ॉल्ट रूप से, हम float उपयोग करते हैं।

कक्षा की परिभाषा की शुरुआत में, टेम्पलेट मापदंडों की वैधता की जांच के लिए तीन स्थिर दावे हैं।

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

मैंने दोनों दृष्टिकोणों के बेंचमार्क का संचालन किया (एक आयत को गहराई से और बिना बचत के संरक्षण के साथ) और उन्हें मक्खी पर गणना करते समय कोई प्रदर्शन गिरावट नहीं मिली। इसके अलावा, यह थोड़ी मेमोरी बचाता है।

एक शीट से एक आंतरिक नोड को भेद करने में सक्षम होने के लिए, isLeaf विधि isLeaf । यह सिर्फ यह जाँचता है कि पहला बच्चा अशक्त नहीं है। चूंकि अशक्त या तो सभी बच्चे नोड्स हैं, या उनमें से कोई भी नहीं है, यह केवल पहले एक की जांच करने के लिए पर्याप्त है।

अब हम Quadtree सदस्य Quadtree देख सकते हैं:

mBox एक ग्लोबल बाउंडिंग बॉक्स है। क्वाडट्री में डाले गए सभी मूल्यों को इसके भीतर समाहित किया जाना चाहिए।
mRoot quadtree का मूल है।
mGetBox को ऑब्जेक्ट कहा जाता है, जिसका उपयोग हम आयत को मान से प्राप्त करने के लिए करेंगे।
mEqual उस वस्तु को कहते हैं, जिसका उपयोग हम दो मूल्यों की समानता को सत्यापित करने के लिए करेंगे।

कंस्ट्रक्टर बस mGetBox , mGetBox और mEqual सेट करता है, और एक रूट नोड भी बनाता है।

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

अब हम और दिलचस्प ऑपरेशन शुरू करने के लिए तैयार हैं।

डालें और हटाएँ

इससे पहले कि मैं सम्मिलित कोड दिखाऊं, हमें चर्चा करने की आवश्यकता है कि किन नोड्स में मान शामिल होंगे। दो रणनीतियाँ हैं:

मूल्यों को केवल पत्तियों में संग्रहीत किया जाता है। चूंकि एक मान का बाउंडिंग बॉक्स कई पत्तियों के साथ बातचीत कर सकता है, इसलिए इन सभी पत्तियों में मूल्य संग्रहीत किया जाएगा।
मान सभी नोड्स में संग्रहीत किए जा सकते हैं। हम मूल्य को सबसे छोटे नोड में संग्रहीत करते हैं जिसमें पूरी तरह से इसका बाउंडिंग बॉक्स होता है।

यदि बाउंडिंग आयत छोटे और लगभग समान आकार के हैं, तो चौराहों की तलाश करते समय पहली रणनीति अधिक प्रभावी होती है। हालांकि, यदि बड़ी आयतें मौजूद हैं, तो पतित मामले हो सकते हैं जिसमें प्रदर्शन बहुत खराब होगा। उदाहरण के लिए, यदि हम एक मान डालें जिसका आयत वैश्विक बाउंडिंग बॉक्स में है, तो इसे सभी पत्तियों में जोड़ा जाएगा। और अगर हम ऐसे मूल्यों के लिए Threshold सम्मिलित करते हैं, तो सभी नोड्स को विभाजित किया जाएगा जब तक कि MaxDepth नहीं पहुंच जाता है और मान सभी पत्तियों में नहीं होते हैं। इसलिए, चतुर्भुज सम्‍मिलित होगा

t e x t t t थ ् र े श ो ल ् ड_{4}^{t e x t t t M a x D e p t h}

$\ texttt {थ्रेशोल्ड} \ _ 4 ^ {\ texttt {MaxDepth}}$ मान, और वह ... बहुत सारे हैं।

इसके अलावा, पहली रणनीति के साथ, सम्मिलित करना और हटाना थोड़ा धीमा होगा, क्योंकि हमें मूल्य को प्रतिच्छेद करने वाले सभी नोड्स को सम्मिलित (या हटाना) करना है।

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

यह पता लगाने के लिए कि हम किस नोड में एक मान डालेंगे या हटाएंगे, हम दो सहायक कार्यों का उपयोग करेंगे।

पहला, computeBox , मूल नोड के आयत और उसके चतुर्भुज के सूचकांक द्वारा बच्चे के नोड की आयत की गणना करता है।

 Box<Float> computeBox(const Box<Float>& box, int i) const { auto origin = box.getTopLeft(); auto childSize = box.getSize() / static_cast<Float>(2); switch (i) { // North West case 0: return Box<Float>(origin, childSize); // Norst East case 1: return Box<Float>(Vector2<Float>(origin.x + childSize.x, origin.y), childSize); // South West case 2: return Box<Float>(Vector2<Float>(origin.x, origin.y + childSize.y), childSize); // South East case 3: return Box<Float>(origin + childSize, childSize); default: assert(false && "Invalid child index"); return Box<Float>(); } }

दूसरा, getQuadrant , वह क्वाड्रंट लौटाता है जिसमें मान स्थित है:

 int getQuadrant(const Box<Float>& nodeBox, const Box<Float>& valueBox) const { auto center = nodeBox.getCenter(); // West if (valueBox.getRight() < center.x) { // North West if (valueBox.getBottom() < center.y) return 0; // South West else if (valueBox.top >= center.y) return 2; // Not contained in any quadrant else return -1; } // East else if (valueBox.left >= center.x) { // North East if (valueBox.getBottom() < center.y) return 1; // South East else if (valueBox.top >= center.y) return 3; // Not contained in any quadrant else return -1; } // Not contained in any quadrant else return -1; }

यह -1 रिटर्न करता है अगर यह किसी भी क्वैडेंट में समाहित नहीं है

अब हम डालने और हटाने के तरीकों पर विचार करने के लिए तैयार हैं।

डालने

add विधि बस एक निजी सहायक विधि कहती है:

 void add(const T& value) { add(mRoot.get(), 0, mBox, value); }

यहाँ सहायक विधि कोड है:

 void add(Node* node, std::size_t depth, const Box<Float>& box, const T& value) { assert(node != nullptr); assert(box.contains(mGetBox(value))); if (isLeaf(node)) { // Insert the value in this node if possible if (depth >= MaxDepth || node->values.size() < Threshold) node->values.push_back(value); // Otherwise, we split and we try again else { split(node, box); add(node, depth, box, value); } } else { auto i = getQuadrant(box, mGetBox(value)); // Add the value in a child if the value is entirely contained in it if (i != -1) add(node->children[static_cast<std::size_t>(i)].get(), depth + 1, computeBox(box, i), value); // Otherwise, we add the value in the current node else node->values.push_back(value); } }

शुरुआत में कुछ धारणाएँ हैं जो यह प्रमाणित करती हैं कि हम कुछ भी अतार्किक नहीं कर रहे हैं, उदाहरण के लिए, हम एक ऐसे नोड में मान नहीं डाल रहे हैं जिसमें उसका बाउंडिंग बॉक्स न हो।

फिर, यदि नोड एक शीट है, और हम इसमें एक नया मान डाल सकते हैं, अर्थात्। हम MaxDepth या Threshold तक नहीं पहुंचे हैं, इंसर्ट करें। अन्यथा, हम इस नोड को साझा करते हैं और फिर से प्रयास करते हैं।

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

यहाँ जुदाई प्रक्रिया है:

 void split(Node* node, const Box<Float>& box) { assert(node != nullptr); assert(isLeaf(node) && "Only leaves can be split"); // Create children for (auto& child : node->children) child = std::make_unique<Node>(); // Assign values to children auto newValues = std::vector<T>(); // New values for this node for (const auto& value : node->values) { auto i = getQuadrant(box, mGetBox(value)); if (i != -1) node->children[static_cast<std::size_t>(i)]->values.push_back(value); else newValues.push_back(value); } node->values = std::move(newValues); }

हम चार बच्चे नोड बनाते हैं, और फिर मूल नोड के प्रत्येक मूल्य के लिए, हम तय करते हैं कि किस नोड (बच्चे या माता-पिता) में मूल्य संग्रहीत किया जाना चाहिए।

निष्कासन

remove तरीका भी बस एक सहायक विधि कहता है:

 void remove(const T& value) { remove(mRoot.get(), nullptr, mBox, value); }

यहाँ सहायक विधि कोड है, यह सम्मिलित कोड के समान है:

 void remove(Node* node, Node* parent, const Box<Float>& box, const T& value) { assert(node != nullptr); assert(box.contains(mGetBox(value))); if (isLeaf(node)) { // Remove the value from node removeValue(node, value); // Try to merge the parent if (parent != nullptr) tryMerge(parent); } else { // Remove the value in a child if the value is entirely contained in it auto i = getQuadrant(box, mGetBox(value)); if (i != -1) remove(node->children[static_cast<std::size_t>(i)].get(), node, computeBox(box, i), value); // Otherwise, we remove the value from the current node else removeValue(node, value); } }

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

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

 void removeValue(Node* node, const T& value) { // Find the value in node->values auto it = std::find_if(std::begin(node->values), std::end(node->values), [this, &value](const auto& rhs){ return mEqual(value, rhs); }); assert(it != std::end(node->values) && "Trying to remove a value that is not present in the node"); // Swap with the last element and pop back *it = std::move(node->values.back()); node->values.pop_back(); }

हमें tryMerge पर एक नज़र डालने की tryMerge :

 void tryMerge(Node* node) { assert(node != nullptr); assert(!isLeaf(node) && "Only interior nodes can be merged"); auto nbValues = node->values.size(); for (const auto& child : node->children) { if (!isLeaf(child.get())) return; nbValues += child->values.size(); } if (nbValues <= Threshold) { node->values.reserve(nbValues); // Merge the values of all the children for (const auto& child : node->children) { for (const auto& value : child->values) node->values.push_back(value); } // Remove the children for (auto& child : node->children) child.reset(); } }

tryMerge सत्यापित करता है कि सभी चाइल्ड नोड्स पत्तियां हैं और इसकी कुल संख्या और चाइल्ड नोड्स के मान थ्रेशोल्ड से कम हैं। यदि ऐसा है, तो हम बच्चे के नोड्स से वर्तमान नोड तक सभी मानों की प्रतिलिपि बनाते हैं और बच्चे के नोड्स को हटाते हैं।

अंतर्मुखी खोज

आयत के साथ अंतरविरोध

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

यह query जाएगा:

 std::vector<T> query(const Box<Float>& box) const { auto values = std::vector<T>(); query(mRoot.get(), mBox, box, values); return values; }

इस पद्धति में, हम बस std::vector चयन करते हैं, जिसमें मान शामिल होंगे जो बाउंडिंग बॉक्स को इंटरसेप्ट करते हैं, और हेल्पर को कॉल करते हैं:

 void query(Node* node, const Box<Float>& box, const Box<Float>& queryBox, std::vector<T>& values) const { assert(node != nullptr); assert(queryBox.intersects(box)); for (const auto& value : node->values) { if (queryBox.intersects(mGetBox(value))) values.push_back(value); } if (!isLeaf(node)) { for (auto i = std::size_t(0); i < node->children.size(); ++i) { auto childBox = computeBox(box, static_cast<int>(i)); if (queryBox.intersects(childBox)) query(node->children[i].get(), childBox, queryBox, values); } } }

सबसे पहले, हम वर्तमान नोड में संग्रहीत सभी मूल्यों को जोड़ते हैं जो अनुरोधित आयत के साथ प्रतिच्छेद करते हैं। फिर, यदि वर्तमान नोड आंतरिक है, तो हम प्रत्येक बच्चे के नोड के लिए एक पुनरावर्ती कॉल करते हैं जिसका बाउंड आयत अनुरोधित आयत के साथ प्रतिच्छेद करता है।

सभी जोड़ीदार चौराहों

दूसरा समर्थित उपयोग मामला उन सभी जोड़े के मानों को खोजना है, जो प्रतिच्छेदन पेड़ में संग्रहीत हैं। शारीरिक इंजन बनाते समय यह विशेष रूप से उपयोगी है। query विधि का उपयोग करके इस समस्या को हल किया जा सकता है। और वास्तव में, हम सभी मूल्यों के बाउंडिंग बॉक्स पर query कह सकते हैं। हालांकि, यह एक जोड़ी के लिए केवल एक चौराहे को जोड़कर अधिक कुशलता से किया जा सकता है ( query साथ हम उन्हें दो बार मिलेंगे)।

इसे महसूस करने के लिए, हमें यह विचार करने की आवश्यकता है कि चौराहा केवल हो सकता है

एक नोड में संग्रहीत दो मानों के बीच

या

नोड में संग्रहीत मूल्य और इस नोड के वंशज में संग्रहीत एक और मूल्य के बीच।

इस वजह से, हमें केवल बीच के चौराहे की जाँच करनी चाहिए:

मान और निम्न मान एक ही नोड में संग्रहीत हैं

और

मूल्य और मूल्य वंश में संग्रहीत।

इस प्रकार, हम निश्चित रूप से एक ही चौराहे को दो बार रिपोर्ट नहीं करेंगे।

यहाँ findAllIntersections code है:

 std::vector<std::pair<T, T>> findAllIntersections() const { auto intersections = std::vector<std::pair<T, T>>(); findAllIntersections(mRoot.get(), intersections); return intersections; }

फिर, हम बस std::vector आवंटित करते हैं std::vector चौराहों को संग्रहीत करने और सहायक फ़ंक्शन को कॉल करने के लिए std::vector :

 void findAllIntersections(Node* node, std::vector<std::pair<T, T>>& intersections) const { // Find intersections between values stored in this node // Make sure to not report the same intersection twice for (auto i = std::size_t(0); i < node->values.size(); ++i) { for (auto j = std::size_t(0); j < i; ++j) { if (mGetBox(node->values[i]).intersects(mGetBox(node->values[j]))) intersections.emplace_back(node->values[i], node->values[j]); } } if (!isLeaf(node)) { // Values in this node can intersect values in descendants for (const auto& child : node->children) { for (const auto& value : node->values) findIntersectionsInDescendants(child.get(), value, intersections); } // Find intersections in children for (const auto& child : node->children) findAllIntersections(child.get(), intersections); } }

पहले चरण में, वर्तमान नोड में संग्रहीत मानों के बीच के चौराहों की जांच की जाती है। फिर, यदि वर्तमान नोड आंतरिक है, तो इस नोड में संग्रहीत मानों और इसके वंशजों में संग्रहीत मानों के बीच चौराहों के लिए findIntersectionInDescendants जाँच करें। अंत में, हम पुनरावर्ती कॉल करते हैं।

findIntersectionsInDescendants आवर्ती रूप से दिए गए मान और सबट्री में संग्रहीत सभी मानों के बीच के अंतर को पाता है:

 void findIntersectionsInDescendants(Node* node, const T& value, std::vector<std::pair<T, T>>& intersections) const { // Test against the values stored in this node for (const auto& other : node->values) { if (mGetBox(value).intersects(mGetBox(other))) intersections.emplace_back(value, other); } // Test against values stored into descendants of this node if (!isLeaf(node)) { for (const auto& child : node->children) findIntersectionsInDescendants(child.get(), value, intersections); } }

वह सब है! मैं दोहराता हूं, सभी कोड GitHub पर पोस्ट किए गए हैं।

उपयोगी संसाधन

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

निष्कर्ष

यह टकराव की मान्यता के साथ काम पूरा करता है। हालाँकि, यह केवल आधा भौतिक इंजन है। दूसरी छमाही टक्करों का संकल्प है ।

चतुष्कोणीय पेड़ और टकराव की पहचान