math - बहुभुज सूत्र




यह निर्धारित करने के लिए कि बहुभुज बिंदुओं की एक सूची दक्षिणावर्त क्रम में है या नहीं? (13)

अन्य उत्तरों में स्पष्टीकरण का उपयोग करके यह मेरा समाधान है:

def segments(poly):
    """A sequence of (x,y) numeric coordinates pairs """
    return zip(poly, poly[1:] + [poly[0]])

def check_clockwise(poly):
    clockwise = False
    if (sum(x0*y1 - x1*y0 for ((x0, y0), (x1, y1)) in segments(poly))) < 0:
        clockwise = not clockwise
    return clockwise

poly = [(2,2),(6,2),(6,6),(2,6)]
check_clockwise(poly)
False

poly = [(2, 6), (6, 6), (6, 2), (2, 2)]
check_clockwise(poly)
True

अंक की एक सूची होने के कारण, अगर मैं घड़ी के क्रम में हैं तो मुझे कैसे पता चलेगा?

उदाहरण के लिए:

point[0] = (5,0)
point[1] = (6,4)
point[2] = (4,5)
point[3] = (1,5)
point[4] = (1,0)

कहेंगे कि यह घड़ी के विपरीत है (या कुछ लोगों के लिए विपरीत दिशा में)।


इन बिंदुओं के द्रव्यमान का केंद्र खोजें।

मान लीजिए कि इस बिंदु से आपके बिंदुओं की रेखाएं हैं।

line0 line1 के लिए दो पंक्तियों के बीच कोण खोजें

लाइन 1 और लाइन 2 के लिए ऐसा करने से पहले

...

...

यदि यह कोण मोटे तौर पर बढ़ रहा है उससे विपरीत है,

अन्यथा यदि यह एकान्त रूप से घट रहा है तो यह घड़ी की दिशा में है

अन्यथा (यह एकान्त नहीं है)

आप तय नहीं कर सकते, इसलिए यह बुद्धिमान नहीं है


इसके लिए एक और समाधान;

const isClockwise = (vertices=[]) => {
    const len = vertices.length;
    const sum = vertices.map(({x, y}, index) => {
        let nextIndex = index + 1;
        if (nextIndex === len) nextIndex = 0;

        return {
            x1: x,
            x2: vertices[nextIndex].x,
            y1: x,
            y2: vertices[nextIndex].x
        }
    }).map(({ x1, x2, y1, y2}) => ((x2 - x1) * (y1 + y2))).reduce((a, b) => a + b);

    if (sum > -1) return true;
    if (sum < 0) return false;
}

इस तरह के सरणी के रूप में सभी शोर ले लो;

const vertices = [{x: 5, y: 0}, {x: 6, y: 4}, {x: 4, y: 5}, {x: 1, y: 5}, {x: 1, y: 0}];
isClockwise(vertices);

ऊपर दिए गए उत्तरों के आधार पर यहां स्विफ्ट 3.0 समाधान है:

    for (i, point) in allPoints.enumerated() {
        let nextPoint = i == allPoints.count - 1 ? allPoints[0] : allPoints[i+1]
        signedArea += (point.x * nextPoint.y - nextPoint.x * point.y)
    }

    let clockwise  = signedArea < 0

कई अविश्वसनीय कार्यान्वयनों का परीक्षण करने के बाद, बॉक्स के बाहर सीडब्ल्यू / सीसीडब्ल्यू अभिविन्यास के संबंध में संतोषजनक परिणाम प्रदान करने वाले एल्गोरिदम एक थे, ओपी द्वारा this धागे ( shoelace_formula_3 ) में पोस्ट किया गया था।

हमेशा की तरह, एक सकारात्मक संख्या एक सीडब्ल्यू अभिविन्यास का प्रतिनिधित्व करती है, जबकि ऋणात्मक संख्या सीसीडब्ल्यू।


कुछ सुझाए गए तरीकों में एक गैर-उत्तल बहुभुज, जैसे कि अर्धशतक के मामले में असफल हो जाएगा। यहां एक सरल है जो गैर-उत्तल बहुभुज के साथ काम करेगा (यह एक आकृति-आठ की तरह स्वयं-अंतरण बहुभुज के साथ भी काम करेगा, यह बताएगा कि यह अधिकतर घड़ी की दिशा में है)।

किनारों पर योग, (एक्स 2 - एक्स 1 ) (वाई 2 + वाई 1 )। यदि परिणाम सकारात्मक है तो वक्र घड़ी की दिशा में है, अगर यह नकारात्मक है तो वक्र विपरीत दिशा में है। (परिणाम एक +/- सम्मेलन के साथ संलग्न क्षेत्र से दोगुना है।)

point[0] = (5,0)   edge[0]: (6-5)(4+0) =   4
point[1] = (6,4)   edge[1]: (4-6)(5+4) = -18
point[2] = (4,5)   edge[2]: (1-4)(5+5) = -30
point[3] = (1,5)   edge[3]: (1-1)(0+5) =   0
point[4] = (1,0)   edge[4]: (5-1)(0+0) =   0
                                         ---
                                         -44  counter-clockwise

जैसा कि इस विकिपीडिया लेख वक्र अभिविन्यास में समझाया गया है, विमान पर 3 अंक p , q और r दिया गया है (यानी एक्स और वाई निर्देशांक के साथ), आप निम्न निर्धारक के संकेत की गणना कर सकते हैं

यदि निर्धारक ऋणात्मक है (यानी Orient(p, q, r) < 0 ), तो बहुभुज दिशात्मक दिशा (सीडब्ल्यू) है। यदि निर्धारक सकारात्मक है (यानी Orient(p, q, r) > 0 ), बहुभुज उन्मुख घुमावदार (सीसीडब्ल्यू) है। निर्धारक शून्य है (यानी Orient(p, q, r) == 0 ) यदि अंक p , q और r collinear

उपर्युक्त सूत्र में, हम p , q और r के निर्देशांक के सामने लोगों को प्रीपेड करते हैं क्योंकि हम समरूप समन्वय का उपयोग कर रहे हैं।


बहुसंख्यक रूप से सरल विधि, यदि आप पहले से ही बहुभुज के अंदर एक बिंदु जानते हैं :

  1. मूल बहुभुज, अंक और उस क्रम में उनके निर्देशांक से कोई भी लाइन सेगमेंट चुनें।

  2. एक ज्ञात "अंदर" बिंदु जोड़ें, और एक त्रिकोण बनाओ।

  3. उन तीन बिंदुओं के साथ यहां सुझाए गए अनुसार सीडब्ल्यू या सीसीडब्ल्यू की गणना करें ।


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

हस्ताक्षरित क्षेत्र की गणना करें: ए = 1/2 * (एक्स 1 * वाई 2 - एक्स 2 * वाई 1 + एक्स 2 * वाई 3 - एक्स 3 * वाई 2 + ... + एक्स एन * वाई 1 - एक्स 1 * वाई एन )

या छद्म कोड में:

signedArea = 0
for each point in points:
    x1 = point[0]
    y1 = point[1]
    if point is last point
        x2 = firstPoint[0]
        y2 = firstPoint[1]
    else
        x2 = nextPoint[0]
        y2 = nextPoint[1]
    end if

    signedArea += (x1 * y2 - x2 * y1)
end for
return signedArea / 2

ध्यान दें कि यदि आप केवल ऑर्डरिंग की जांच कर रहे हैं, तो आपको 2 से विभाजित करने की आवश्यकता नहीं है।

स्रोत: http://mathworld.wolfram.com/PolygonArea.html


मेरा सी # / LINQ समाधान @charlesbretana की क्रॉस उत्पाद सलाह पर आधारित है। आप घुमाव के लिए सामान्य संदर्भ निर्दिष्ट कर सकते हैं। यह तब तक काम करना चाहिए जब वक्र अधिकतर वेक्टर द्वारा परिभाषित विमान में होता है।

using System.Collections.Generic;
using System.Linq;
using System.Numerics;

namespace SolidworksAddinFramework.Geometry
{
    public static class PlanePolygon
    {
        /// <summary>
        /// Assumes that polygon is closed, ie first and last points are the same
        /// </summary>
       public static bool Orientation
           (this IEnumerable<Vector3> polygon, Vector3 up)
        {
            var sum = polygon
                .Buffer(2, 1) // from Interactive Extensions Nuget Pkg
                .Where(b => b.Count == 2)
                .Aggregate
                  ( Vector3.Zero
                  , (p, b) => p + Vector3.Cross(b[0], b[1])
                                  /b[0].Length()/b[1].Length());

            return Vector3.Dot(up, sum) > 0;

        } 

    }
}

एक इकाई परीक्षण के साथ

namespace SolidworksAddinFramework.Spec.Geometry
{
    public class PlanePolygonSpec
    {
        [Fact]
        public void OrientationShouldWork()
        {

            var points = Sequences.LinSpace(0, Math.PI*2, 100)
                .Select(t => new Vector3((float) Math.Cos(t), (float) Math.Sin(t), 0))
                .ToList();

            points.Orientation(Vector3.UnitZ).Should().BeTrue();
            points.Reverse();
            points.Orientation(Vector3.UnitZ).Should().BeFalse();



        } 
    }
}

यह ओपनलेयर 2 के लिए कार्यान्वित कार्य है। घड़ी के बहुभुज होने की स्थिति area < 0 , यह en.wikipedia.org/wiki/Shoelace_formula पुष्टि की गई है।

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);
}

सबसे छोटे वाई के साथ कशेरुका खोजें (और संबंधों के साथ सबसे बड़ा एक्स)। कशेरुक को A होने दें और सूची में अगला शिखर B और C होना चाहिए। अब AB और AC के क्रॉस उत्पाद के संकेत की गणना करें

संदर्भ:


इस उत्तर के आधार पर एल्गोरिदम का एक सरल सी # कार्यान्वयन यहां दिया गया है ।

आइए मान लें कि हमारे पास Vector प्रकार है जिसमें X और Y गुण double

public bool IsClockwise(IList<Vector> vertices)
{
    double sum = 0.0;
    for (int i = 0; i < vertices.Count; i++) {
        Vector v1 = vertices[i];
        Vector v2 = vertices[(i + 1) % vertices.Count]; // % is the modulo operator
        sum += (v2.X - v1.X) * (v2.Y + v1.Y);
    }
    return sum > 0.0;
}




computational-geometry