दो उत्तल बहुभुजों का छेद

Question

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

Answer 1

For each edge V1-V2 in the first polygon, 
    Let H := Half-plane tangenting V1-V2, with the remaining 
     vertices on the "inside". 
    Let C := New empty polygon. 
    For each edge V3-V4 in the second polygon, 
     Let X := The intersection between V3-V4 and H. 
     If V3 inside H, and V4 is outside H then, 
      Add V3 to C. 
      Add X to C. 
     Else if both V3 and V4 lies outside H then, 
      Skip. 
     Else if V3 outside H, and V4 is inside H then, 
      Add X to C. 
     Else 
      Add V3 to C. 
    Replace the second polygon with C. 

यह सरल उपयोग के लिए पर्याप्त होना चाहिए; 10-20 शिखर और प्रत्येक फ्रेम का पुनर्मूल्यांकन नहीं।

• Computer Graphics I – Polygon Clipping and Filling (पीडीएफ)
• rosettacode.org – Sutherland-Hodgman polygon clipping

Answer 2

आप तथ्य यह है कि से फायदा हो सकता: — ओ (n)

---

यहाँ कुछ लिंक है दोनों बहुभुज उत्तल हैं। और इस ज्ञान के साथ आप फॉलोइन स्वीप लाइन एल्गोरिदम का उपयोग करके ओ (एन) समय प्राप्त कर सकते हैं:

दोनों बहुभुजों में शीर्षतम बिंदु खोजें। सादगी के लिए मान लीजिए कि आपके पास कोई क्षैतिज किनार नहीं है। बहुभुज की बाएं और दाएं सीमाओं में योगदान देने वाले किनारों की सूचियां बनाएं।

विमान को साफ़ करने के दौरान आप 4 किनारों को स्टोर करते हैं। left_edge_C1, right_edge_C1, left_edge_C2, right_edge_C2। किनारों पर घूमने के लिए आपको किसी भी जटिल की आवश्यकता नहीं है, क्योंकि उनमें से केवल चार ही हैं। आप सभी संभावित विकल्पों को फिर से शुरू करके अगले ईवेंट बिंदु पा सकते हैं।

प्रत्येक घटना पर कुछ किनारे उनके चौराहे की सीमा पर दिखाई देते हैं। असल में, प्रत्येक घटना बिंदु पर आप एक मुक्त मामलों में से एक हो सकते हैं (तस्वीर देखें।)।

Answer 3

इसके अलावा @ Yola के अच्छा विमान स्वीप विवरण, वहाँ एक रेखीय समय एल्गोरिथ्म Computational Geometry in C, अध्याय 7 और सी & जावा कोड में वर्णित है (एक ही लिंक पर) उपलब्ध है। कई मुश्किल अपमानजनक मामले हैं, उदाहरण के लिए, जब दो बहुभुज एक बिंदु पर छेड़छाड़ करते हैं, या चौराहे एक सेगमेंट होता है।