ग्राफ स्पेसिंग एल्गोरिदम

Question

मैं एक एल्गोरिदम खोज रहा हूं जो स्क्रीन पर प्रदर्शित करने के लिए कई ऑब्जेक्ट्स के लिए x y निर्देशांक निर्धारित करने के लिए उपयोगी होगा। प्रत्येक वस्तु किसी अन्य वस्तु से संबंधित हो सकती है और वहां कई रिश्ते हो सकते हैं और इन वस्तुओं में से कोई भी संख्या हो सकती है।

इस ऑब्जेक्ट को प्रदर्शित करने के लिए क्षेत्र के समग्र आकार पर कोई प्रतिबंध नहीं है।

मैं इसे php में लिख रहा हूं और निर्देशांक को सरणी में संग्रहीत करना चाहता हूं।

Answer 1

ऐसा करने का एक तरीका एक छद्म भौतिकी मॉडल का उपयोग करना है। यदि आपके संलग्न होते हैं तो आपके ऑब्जेक्ट्स में एक प्रतिकूल बल और एक आकर्षक बल होता है।

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

छद्म कोड में, एक यात्रा होगा:

for each object o1 
    force[o1] = 0 
    for each object o2 
     if o1 and o2 are linked 
     force[o1] += attraction_force(o1, o2) 
     else 
     force[o1] += repulsion_force(o1, o2) 

for each object o1 
    move(o1, force[o1]) 

और जब वस्तुओं एक स्थिर स्थिति में पहुँच गए हैं पुनरावृत्तियों बंद करो।

आपको शायद विभिन्न बल कानूनों के साथ प्रयोग करने की आवश्यकता होगी। विशेष रूप से, आप वस्तुओं को आसन्न संतुलन तक पहुंचने के लिए आसन्न करना चाहते हैं। मैं दूरी के एक शक्ति तीव्रता रैखिक (एक स्प्रिंग की तरह) या द्विघात (gravition/बिजली आकर्षण)

इसके अलावा, आप शायद शेष से ग्राफ के कुछ हिस्सों को रोकने के लिए वस्तुओं को बेतरतीब ढंग से ले जाने के लिए की आवश्यकता होगी के साथ प्रयोग stucked होगा। यादृच्छिक कदम की मात्रा पहले पुनरावृत्तियों के लिए बड़ी होनी चाहिए और समय के साथ घटाना चाहिए।

Answer 2

कि आप क्या करना चाहते हैं के लिए परंपरागत नाम ग्राफ लेआउट और graph drawing हैं। यह सामान्य रूप से एक आसान समस्या नहीं है। आरेख केवल अच्छे दिखने जा रहे हैं यदि वे planar या लगभग प्लानर हैं।