查找非自相交闭合多边形的质心

2022-09-20  乐帮网

数学

这一节是查找非自交多边形的质心,给定多边形的 N 个顶点,任务是找到多边形的质心
例子:

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}


方法:
由 n 个顶点 (x0, y0), (x1, y1), ..., (xn-1, yn-1) 定义的非自相交闭合多边形的质心是点 (Cx, Cy),其中:

img

下面是上述方法的实现:

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>

输出:

3.33333333333 -3

时间复杂度:O(n)

空间复杂度:O(1)

https://www.geeksforgeeks.org/find-the-centroid-of-a-non-self-intersecting-closed-polygon/

公众号二维码

关注我的微信公众号
在公众号里留言交流
投稿邮箱:1052839972@qq.com

庭院深深深几许?杨柳堆烟,帘幕无重数。
玉勒雕鞍游冶处,楼高不见章台路。
雨横风狂三月暮。门掩黄昏,无计留春住。
泪眼问花花不语,乱红飞过秋千去。

欧阳修

付款二维码

如果感觉对您有帮助
欢迎向作者提供捐赠
这将是创作的最大动力