किनारे के मामलों के साथ पूर्णांक घुमावदार संख्या एल्गोरिदम

Question

मुझे एक बिंदु के बारे में एक बंद, टुकड़े-रेखा रेखा (उदाहरण के लिए एक बहुभुज) के winding number चाहिए, लेकिन इसके अलावा, मैं यह जानना चाहता हूं कि पथ बिंदु के माध्यम से कब गुज़रता है। इस कारण से, मैं मानक घुमावदार संख्या दोगुना करता हूं। सीसीडब्ल्यू उन्मुखीकरण के साथ एक को न काटने बहुभुज के लिए, मान होगा:

• 0 अगर बिंदु बहुभुज के बाहर
• 1 है अगर बिंदु बढ़त या बहुभुज के शीर्ष पर है
• 2 अगर बिंदु पॉलीगॉन

और इसी तरह अन्य मामलों में भी है। (संपादित करें: image of a few examples)

जब मैं बिंदु किनारे या कशेरुक पर होता हूं तो मुझे मिली प्रत्येक एल्गोरिदम विफल हो जाती है।

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

मैं को लगातार दो संयोग बिंदुओं या 180 डिग्री की बारी वाले अपरिवर्तनीय पथों को संभालने की आवश्यकता है।

वैसे भी, मुझे लगता है कि मेरे पास समाधान है। हालांकि, यह थोड़ा सा सुरुचिपूर्ण लगता है, और मुझे विश्वास नहीं है कि यह सही है। (। मैं वास्तव में अपने आप को क्या होता है जब बिंदु एक शीर्ष पर है के बारे में उलझन में) यहाँ यह अजगर में है:

def orient((x,y), (a0,b0), (a1,b1)): 
    return cmp((a1-a0)*y + (b0-b1)*x + a0*b1-a1*b0, 0) 
def windingnumber(p0, ps): 
    w, h = 0, [cmp(p, p0) for p in ps] 
    for j in range(len(ps)): 
     i, k = (j-1)%len(ps), (j+1)%len(ps) 
     if h[j] * h[k] == -1: 
      w += orient(p0, ps[j], ps[k]) 
     elif h[j] == 0 and h[i] == h[k]: 
      w += orient(ps[k], ps[i], ps[j]) 
    return w 

Link to a version with comments and unit tests.

मैं एक सही एल्गोरिथ्म के लिए एक लिंक, या कुछ पुष्टि है कि चाहते हैं मेरे एल्गोरिदम सही है, या एक परीक्षण केस जहां मेरा एल्गोरिदम विफल रहता है। धन्यवाद!

Answer 1

समस्या यह है कि आपकी धारणा गलत है।

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

यदि आप दो बार एक ही पथ का पालन करते हैं तो आपको दो बार घुमावदार संख्या मिलती है। तो अगर आपकी धारणा है कि संख्या 1 होगी यदि काउंटर पर बिंदु सही था, तो यह वास्तव में इंगित करेगा कि यदि आप एक बार जाते हैं तो घुमावदार संख्या 1/2 है, लेकिन यह स्पष्ट रूप से गलत है, क्योंकि घुमावदार संख्या हमेशा होती है पूर्णांक।