Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> Python

Python में दिए गए पॉइंट को पॉलीगोन के अंदर या बाउंड्री पर है या नहीं, इसकी जांच करने का प्रोग्राम


मान लीजिए हमारे पास कार्टेशियन पॉइंट्स की एक सूची [(x1, y1), (x2, y2), ..., (xn, yn)] है, जो एक पॉलीगोन को दर्शाती है, और हमारे पास दो मान x और y भी हैं, हमें जांचना है कि (x, y) इस पॉलीगोन के अंदर है या बाउंड्री पर।

इसलिए, यदि इनपुट इस तरह है points = [(0, 0), (1, 3), (4, 4), (6, 2), (4, 0)] pt = (3, 1)

Python में दिए गए पॉइंट को पॉलीगोन के अंदर या बाउंड्री पर है या नहीं, इसकी जांच करने का प्रोग्राम

तो आउटपुट True होगा

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

  • ans := False
  • i के लिए 0 से पॉलीगोन के आकार - 1 तक रेंज में, करें
    • (x0, y0) := पॉलीगोन[i]
    • (x1, y1) := पॉलीगोन[(i + 1) mod पॉलीगोन का आकार]
    • यदि pt[1] y0, y1 के न्यूनतम और अधिकतम की रेंज में नहीं है, तो
      • अगले इटरेशन के लिए जाएं
    • यदि pt[0] x0 और x1 के न्यूनतम से कम है, तो
      • अगले इटरेशन के लिए जाएं
    • cur_x := x0 यदि x0, x1 के समान है अन्यथा x0 + (pt[1] - y0) *(x1 - x0) /(y1 - y0)
    • ans := ans XOR (1 जब pt[0] > cur_x सत्य है, अन्यथा 0)
  • ans लौटाएं

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

class Solution:
    def solve(self, polygon, pt):
        ans = False
        for i in range(len(polygon)):
            x0, y0 = polygon[i]
            x1, y1 = polygon[(i + 1) % len(polygon)]
            if not min(y0, y1) < pt[1] <= max(y0, y1):
                continue
            if pt[0] < min(x0, x1):
                continue
            cur_x = x0 if x0 == x1 else x0 + (pt[1] - y0) * (x1 - x0) / (y1 - y0)
            ans ^= pt[0] > cur_x
        return ans
ob = Solution()
points = [(0, 0), (1, 3), (4, 4), (6, 2), (4, 0)]
pt = (3, 1)
print(ob.solve(points, pt))

इनपुट

[(0, 0), (1, 3), (4, 4), (6, 2), (4, 0)], (3, 1)

आउटपुट

True
  1. Python में दिया गया ट्री सममित ट्री है या नहीं, इसकी जांच करने का प्रोग्राम Python में दिया गया ट्री सममित ट्री है या नहीं, इसकी जांच करने का प्रोग्राम

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

  1. पायथन में जांचें कि दिया गया ग्राफ द्विभाजित है या नहीं पायथन में जांचें कि दिया गया ग्राफ द्विभाजित है या नहीं

    मान लीजिए हमारे पास एक अविकल्पित ग्राफ है, हमें जांचना है कि ग्राफ द्विभाजित है या नहीं। जैसा कि हम जानते हैं, एक ग्राफ द्विभाजित होता है जब हम ग्राफ के नोड्स को दो सेट A और B में विभाजित कर सकते हैं ताकि ग्राफ में प्रत्येक किनारा {u,v} का एक नोड u A में और दूसरा नोड v B में हो। उदाहरण के लिए, यदि

  1. पायथन प्रोग्राम: जांचें कि दी गई स्ट्रिंग कीवर्ड है या नहीं पायथन प्रोग्राम: जांचें कि दी गई स्ट्रिंग कीवर्ड है या नहीं

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