पता लगाएं कि किसी जटिल बहुभुज के शिखर वाले सरणी में बिंदुओं का एक सेट दक्षिणावर्त या घुमावदार क्रम में परिभाषित किया गया था?

Question

संपादित करें: मैंने उत्तर के साथ program अपडेट किया है और यह बहुत अच्छा काम करता है!

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

यहाँ कैसे अंक निर्धारित किए जाते हैं:

:

यहाँ एक वामावर्त बहुभुज की एक छवि है:

function Point(x, y) { 
    this.x = x; 
    this.y = y; 
} 

var vertices = []; 

// Called on click 
function addPoint(mouseX, mouseY) { 
    vertices.push(new Point(mouseX, mouseY)); 
} 

यहाँ एक घड़ी की बहुभुज की एक छवि है

यदि आप मुझे पता लगाने में मदद कर सकते हैं कि अंक के "घड़ी की दिशा" को कैसे निर्धारित किया जाए, तो मैं बहुत आभारी रहूंगा!

Answer 1

shoelace formula का उपयोग करके बहुभुज क्षेत्र की गणना करें, लेकिन पूर्ण मूल्य चिह्न के बिना। यदि परिणाम सकारात्मक है, तो अंक को विपरीत दिशा में आदेश दिया जाता है, और यदि ऋणात्मक - घड़ी की दिशा में।

function polygonArea() { 
    var area = 0; 
    for (var i = 0; i < vertices.length; i++) { 
     j = (i + 1) % vertices.length; 
     area += vertices[i].x * vertices[j].y; 
     area -= vertices[j].x * vertices[i].y; 
    } 
    return area/2; 
} 
var clockwise = polygonArea() > 0; 

Answer 2

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

तो:

• अन्य सभी अंक इस लाइन के एक तरफ हैं कि तो अपने polygones के दो अंक हैं।
• यदि सभी बिंदु बाईं ओर हैं (बस अंक में से एक की जांच करें), यह विपरीत है। यदि वे दाईं ओर हैं, तो यह घड़ी की दिशा में है।

उदाहरण:

शीर्ष आंकड़ा पर: 4-5 दाईं तरफ आंकड़ा है, 5-11 सही पर आंकड़ा है, ... नीचे आंकड़ा पर: 6- बाईं तरफ आंकड़ा जाने 7, 7-14 बाईं तरफ आंकड़ा है, ...

चेतावनी जाने: एक ओर जहां अपने बहुभुज पर "चल", संख्यान को पुनः आरंभ नहीं है, अन्यथा यह गलत होगा। शीर्ष आंकड़े पर, 4- (एन -1) बाईं ओर आकृति को चलो!

Answer 3

घड़ी की अंतर्दृष्टि की आपकी अंतर्ज्ञानी परिभाषा अच्छी तरह से परिभाषित नहीं है। उदाहरण के लिए, अगर मैं एक घोड़े की नाल आकर्षित:

/---a-b--\ 
/ _d_c_ \ 
//  \ \ 
| |  | | 
| |  | | 
    \ \  // 
    \ \ // 
    --  -- 

तो 0 = a < b < b < d और मैं a और b देखो मैं अपने विवरण है कि आकार दक्षिणावर्त तैयार किया गया है से निष्कर्ष निकालना होगा, लेकिन अगर 0 = c < d < a < b मैं निष्कर्ष निकालना होगा कि आकार दिया गया है anticlockwise खींचा।चूंकि इन दोनों परिदृश्यों में एक ही दिशा शामिल है जिसमें अंक तैयार किए गए थे, केवल अलग-अलग शुरुआती बिंदुओं से, मैं केवल यह निष्कर्ष निकाल सकता हूं कि आपकी परिभाषा में कमी है।

घोड़े की नाल मैंने खींचा सबसे अच्छा नहीं है; विचार यह है कि यह दूसरी तरफ विपरीत दिशा में खींचा जाने के लिए, नीचे एक छोटा छेद वाला लगभग एक सर्कल है।

आप और अधिक सख्ती से बातें परिभाषित करने में रुचि रखते हैं, तो मैं निम्नलिखित लाइनों के साथ कुछ सुझाव देते हैं:

किसी भी परिमित सरल दो अलग-अलग क्षेत्रों में विमान को अलग करने के रूप में बहुभुज को ध्यान में रखते (एक परिमित और एक अनंत), हम हमेशा परिमित क्षेत्र को बहुभुज के आंतरिक होने पर विचार कर सकते हैं। इस तरह के परिदृश्य में हम एक चरम क्रम को घड़ी की दिशा में परिभाषित करते हैं यदि अंक का क्रम बाहरी के साथ बाहरी के साथ चलता है। इसे curve orientation कहा जाता है।

एक बार आपके पास यह और अधिक ठोस परिभाषा हो जाने के बाद, कार्यान्वयन घुमावदार संख्या की गणना के रूप में सरल हो सकता है। किसी भी आदेशित जोड़ी का मध्यबिंदु लें, 0 और 1 कहें, आदेशित जोड़ी के दाईं ओर एक लाइन सेगमेंट लें (किसी भी कोण पर, लंबवत कहें), और गिनती करें कि अन्य लाइन सेगमेंट के साथ कितने अंतर हैं: वक्र घड़ी की दिशा में है iff संख्या विषम है।

यह लागू करने के लिए आसान है, समय O(n) में रैखिक, और स्थिर स्थान O(1) जोड़ता है।

Answer 4

यह एक फ़ंक्शन फ़ंक्शन जो ओपनलेयर के लिए विशिष्ट है। जैसा कि आप घड़ी की बहुभुज की स्थिति देख सकते हैं क्षेत्र इसकी पुष्टि करें।

function IsClockwise(feature) 
{ 
if(feature.geometry==null)return -1; 
var vertices=feature.geometry.getVertices(); 
var area=0; 
for (var i = 0; i < (vertices.length); i++) 
    { 
    j = (i + 1) % vertices.length; 
    area += vertices[i].x * vertices[j].y; 
    area -= vertices[j].x * vertices[i].y; 
    // console.log(area); 
    } 
return (area < 0); 
} 

Answer 5

मामले में किसी को ShapeUtils Three.js उपयोग कर रहा है इनबिल्ट isClockWise विधि है जो आंतरिक रूप से area विधि का उपयोग करता गणना क्षेत्र के हस्ताक्षर निर्धारित करने के लिए के साथ आता है।

isClockWise: function (pts) { 

    return ShapeUtils.area(pts) < 0; 

} 

ShapeUtils.isClockWise विधि here पाया जा सकता है।

area: function (contour) { 

    var n = contour.length; 
    var a = 0.0; 

    for (var p = n - 1, q = 0; q < n; p = q ++) { 

     a += contour[ p ].x * contour[ q ].y - contour[ q ].x * contour[ p ].y; 

    } 

    return a * 0.5; 

}, 

ShapeUtils.area विधि here पाया जा सकता है।