Encuentre el centroide de un polígono cerrado que no se corta a sí mismo

Dados N vértices del polígono, la tarea es encontrar el centroide del polígono
Ejemplos: 
 

Input: ar = {{0, 0}, {0, 8}, {8, 8}, {8, 0}}
Output: {Cx, Cy} = {4, 4}

Input: ar = {{1, 2}, {3, -4}, {6, -7}}
Output: {Cx, Cy} = {3.33, -3}

Enfoque: 
El centroide de un polígono cerrado que no se corta a sí mismo definido por n vértices (x0, y0), (x1, y1), …, (xn-1, yn-1) es el punto (Cx, Cy), donde :
 

C_{x}= \frac{1}{6A} \sum_{i=0}^{n-1}(x_{i}+x_{i+1})(x_{i}* y_{i+1}-x_{i+1}*y_{i})
C_{y}= \frac{1}{6A} \sum_{i=0}^{n-1}(y_{i}+y_{i+1})(x_{i}* y_{i+1}-x_{i+1}*y_{i})
A = \frac{1}{2} \sum_{i=0}^{n-1}(x_{i}*y_{i+1}-x_{i+1}*y_{i})

A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ program to implement the
// above approach
 
#include <bits/stdc++.h>
using namespace std;
 
pair<double, double> find_Centroid(vector<pair<double, double> >& v)
{
    pair<double, double> ans = { 0, 0 };
     
    int n = v.size();
    double signedArea = 0;
     
    // For all vertices
    for (int i = 0; i < v.size(); i++) {
         
        double x0 = v[i].first, y0 = v[i].second;
        double x1 = v[(i + 1) % n].first, y1 =
                            v[(i + 1) % n].second;
                             
        // Calculate value of A
        // using shoelace formula
        double A = (x0 * y1) - (x1 * y0);
        signedArea += A;
         
        // Calculating coordinates of
        // centroid of polygon
        ans.first += (x0 + x1) * A;
        ans.second += (y0 + y1) * A;
    }
 
    signedArea *= 0.5;
    ans.first = (ans.first) / (6 * signedArea);
    ans.second = (ans.second) / (6 * signedArea);
 
    return ans;
}
 
// Driver code
int main()
{
    // Coordinate of the vertices
    vector<pair<double, double> > vp = { { 1, 2 },
                                         { 3, -4 },
                                         { 6, -7 } };
                                          
    pair<double, double> ans = find_Centroid(vp);
     
    cout << setprecision(12) << ans.first << " "
        << ans.second << '\n';
 
    return 0;
}

Java

// Java implementation of the approach
class GFG
{
     
    static double[] find_Centroid(double v[][])
    {
        double []ans = new double[2];
         
        int n = v.length;
        double signedArea = 0;
         
        // For all vertices
        for (int i = 0; i < n; i++)
        {
             
            double x0 = v[i][0], y0 = v[i][1];
            double x1 = v[(i + 1) % n][0], y1 = v[(i + 1) % n][1];
                                 
            // Calculate value of A
            // using shoelace formula
            double A = (x0 * y1) - (x1 * y0);
            signedArea += A;
             
            // Calculating coordinates of
            // centroid of polygon
            ans[0] += (x0 + x1) * A;
            ans[1] += (y0 + y1) * A;
        }
     
        signedArea *= 0.5;
        ans[0] = (ans[0]) / (6 * signedArea);
        ans[1]= (ans[1]) / (6 * signedArea);
     
        return ans;
    }
     
    // Driver code
    public static void main (String[] args)
    {
        // Coordinate of the vertices
        double vp[][] = { { 1, 2 },
                            { 3, -4 },
                            { 6, -7 } };
                                             
        double []ans = find_Centroid(vp);
         
        System.out.println(ans[0] + " " + ans[1]);
    }
}
 
// This code is contributed by AnkitRai01

Python3

# Python3 program to implement the
# above approach
def find_Centroid(v):
    ans = [0, 0]
 
    n = len(v)
    signedArea = 0
 
    # For all vertices
    for i in range(len(v)):
 
        x0 = v[i][0]
        y0 = v[i][1]
        x1 = v[(i + 1) % n][0]
        y1 =v[(i + 1) % n][1]
 
        # Calculate value of A
        # using shoelace formula
        A = (x0 * y1) - (x1 * y0)
        signedArea += A
 
        # Calculating coordinates of
        # centroid of polygon
        ans[0] += (x0 + x1) * A
        ans[1] += (y0 + y1) * A
 
    signedArea *= 0.5
    ans[0] = (ans[0]) / (6 * signedArea)
    ans[1] = (ans[1]) / (6 * signedArea)
 
    return ans
 
# Driver code
 
# Coordinate of the vertices
vp = [ [ 1, 2 ],
       [ 3, -4 ],
       [ 6, -7 ] ]
 
ans = find_Centroid(vp)
 
print(round(ans[0], 12), ans[1])
 
# This code is contributed by Mohit Kumar

C#

// C# implementation of the approach
using System;
 
class GFG
{
    static double[] find_Centroid(double [,]v)
    {
        double []ans = new double[2];
         
        int n = v.GetLength(0);
        double signedArea = 0;
         
        // For all vertices
        for (int i = 0; i < n; i++)
        {
            double x0 = v[i, 0], y0 = v[i, 1];
            double x1 = v[(i + 1) % n, 0],
                    y1 = v[(i + 1) % n, 1];
                                 
            // Calculate value of A
            // using shoelace formula
            double A = (x0 * y1) - (x1 * y0);
            signedArea += A;
             
            // Calculating coordinates of
            // centroid of polygon
            ans[0] += (x0 + x1) * A;
            ans[1] += (y0 + y1) * A;
        }
        signedArea *= 0.5;
        ans[0] = (ans[0]) / (6 * signedArea);
        ans[1]= (ans[1]) / (6 * signedArea);
     
        return ans;
    }
     
    // Driver code
    public static void Main (String[] args)
    {
        // Coordinate of the vertices
        double [,]vp = { { 1, 2 },
                         { 3, -4 },
                         { 6, -7 } };
                                             
        double []ans = find_Centroid(vp);
         
        Console.WriteLine(ans[0] + " " + ans[1]);
    }
}
 
// This code is contributed by PrinciRaj1992

Javascript

<script>
    // Javascript implementation of the approach
     
    function find_Centroid(v)
    {
        let ans = new Array(2);
        ans.fill(0);
           
        let n = v.length;
        let signedArea = 0;
           
        // For all vertices
        for (let i = 0; i < n; i++)
        {
               
            let x0 = v[i][0], y0 = v[i][1];
            let x1 = v[(i + 1) % n][0], y1 = v[(i + 1) % n][1];
                                   
            // Calculate value of A
            // using shoelace formula
            let A = (x0 * y1) - (x1 * y0);
            signedArea += A;
               
            // Calculating coordinates of
            // centroid of polygon
            ans[0] += (x0 + x1) * A;
            ans[1] += (y0 + y1) * A;
        }
       
        signedArea *= 0.5;
        ans[0] = (ans[0]) / (6 * signedArea);
        ans[1]= (ans[1]) / (6 * signedArea);
       
        return ans;
    }
     
    // Coordinate of the vertices
    let vp = [ [ 1, 2 ],
                [ 3, -4 ],
                [ 6, -7 ] ];
 
    let ans = find_Centroid(vp);
 
    document.write(ans[0].toFixed(11) + " " + ans[1]);
  
 // This code is contributed by divyeshrabadiya07.
</script>
Producción: 

3.33333333333 -3

 

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por kunal_76 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *