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 :
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)