मौजूदा बिंदुओं के साथ टकराव के बिना निकटतम उपलब्ध स्थान ढूँढना

Question

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

इसके अलावा अंक (नीचे दिखाया गया) जहां बॉक्स तुरंत बात करने के लिए 4 अगले फिट नहीं कर सकते का एक अलग सेट को देखते हुए, मैं अभी भी (दिखाया गया है) निकटतम स्थान प्राप्त करने की उम्मीद कर रहा हूँ। मैं बिंदु 4 और लाल बॉक्स के केंद्र के बीच की दूरी से "निकटतम" का निर्धारण कर रहा हूं।

कोई मदद या विचारों को बहुत सराहना की जाएगी।

Answer 1

इस समस्या को हल करने की कुंजी इस बात पर विचार कर रही है कि प्रत्येक बिंदु चार (ओवरलैपिंग) सेमीप्लेन्स में अंतरिक्ष को विभाजित करता है: उत्तर, दक्षिण, पश्चिम या पूर्व।

संदर्भ बिंदु पर विचार करके प्रारंभ करें, आयताकार उत्तर में या उसके दक्षिण या आदि में या दूसरे शब्दों में, उपरोक्त परिभाषित अर्द्धपंथियों में से एक में होना चाहिए।

अर्ध-प्लेन के बजाय, उन पर अक्ष-संरेखित आयतों के रूप में सोचें जो अनंत में कुछ पक्ष हो सकते हैं।

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

तो, सारांश में:

1) आयतों संदर्भ बिंदु के लिए उनकी दूरी द्वारा आदेश दिया बाउंडिंग की एक कतार रहते हैं।

2) पहला तत्व प्राप्त करें, देखें कि संदर्भ बिंदु पर निकटतम स्थिति पर आप आयताकार फिट कर सकते हैं या नहीं। यदि आप कर सकते हैं, समस्या हल हो गई है।

3) अन्यथा, किसी भी टकराव बिंदु पर बाध्य आयताकार को विभाजित करें और परिणामी चार बाध्य आयतों को कतार में धक्का दें (उनको बहुत छोटा फ़िल्टर करें)।

4) दोहराना।