共计 1721 个字符,预计需要花费 5 分钟才能阅读完成。
给定蕴含多个点的汇合,从其中取三个点组成三角形,返回能组成的最大三角形的面积。
示例:
输出: points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
输入: 2
解释:
这五个点如下图所示。组成的橙色三角形是最大的,面积为 2。留神:
3 <= points.length <= 50.
不存在反复的点。-50 <= points[i][j] <= 50.
后果误差值在 10^-6 以内都认为是正确答案。
思路:
-
- 鞋带公式,用于计算任意多边形的面积,可用于计算三角形的面积;
-
- 海伦公式,从三个顶点失去三边长,并应用海伦公司计算出面积;
- 3. 三角形面积公式
S = 1/2 * a * b * sin(C)
,首先失去两边的长度,通过叉积算出夹角的正弦值,并应用公式计算出面积。
次要记录前两种实现形式。
1. 鞋带公式:
比方已知 ΔABC 三个顶点的坐标 A:(x1,y1)、B:(x2,y2)、C:(x3,y3),对应的矩阵是这样:
计算面积先计算两头的矩阵:
$ a=(x1×y2)+(x2×y3)+(x3×y1) $
再从最右侧矩阵计算:
$ b=(y1×x2)+(y2×x3)+(y3×x1) $
则三角形面积为:
$ SΔABC=12|a−b|=12|((x1×y2)+(x2×y3)+(x3×y1))−((y1×x2)+(y2×x3)+(y3×x1))| $
抽离进去即有:
公式中约定:当下标大于 n 时,xn+1=x1, yn+1=y1。在此就不证实了。
鞋带公式 - 实现代码
var largestTriangleArea1 = function (points) {
var maxs = 0;
for (var i = 0; i < points.length; i++) {for (var j = i+1; j < points.length; j++) {for (var s = j+1; s < points.length; s++) {
maxs = Math.max(maxs,0.5*Math.abs(points[i][0]*points[j][1]+
points[j][0]*points[s][1]+
points[s][0]*points[i][1]-
points[i][1]*points[j][0]-
points[j][1]*points[s][0]-
points[s][1]*points[i][0]))
}
}
}
return maxs;
};
2. 海伦公式
不同的面积公式对应不同的宰割办法。$ S = 1/2hb $
对应的是割补矩形法,而海伦公式对应如下
var largestTriangleArea = function (points) {
var maxs = 0;
for (var i = 0; i < points.length; i++) {for (var j = i+1; j < points.length; j++) {for (var s = j+1; s < points.length; s++) {console.log(points[j][0],points[i][0])
var a = Math.sqrt(Math.pow( Math.abs(points[j][0] - points[i][0]),2)+Math.pow(Math.abs(points[j][1] - points[i][1]),2));
var b = Math.sqrt(Math.pow( Math.abs(points[s][0] - points[j][0]),2)+Math.pow(Math.abs(points[s][1] - points[j][1]),2));
var c = Math.sqrt(Math.pow( Math.abs(points[i][0] - points[s][0]),2)+Math.pow(Math.abs(points[i][1] - points[s][1]),2));
var l = (a+b+c)*0.5;
maxs = Math.max(maxs,Math.sqrt(l*(l-a)*(l-b)*(l-c)))
}
}
}
return maxs;
};
tips: 该形式还存在精度问题。
参考文档:
1. 海伦公式的几何意义是什么?
2.【Green 公式】Hunter’s Apprentice(判断多边形为顺时针或逆时针)– 鞋带公式
3. 求简略多边形面积时十分有用的“鞋带公式”
正文完